ntfs/libntfs/index.c

194 static VCN *ntfs_ie_get_vcn_addr(INDEX_ENTRY *ie)
196 	return (VCN *)((u8 *)ie + le16_to_cpu(ie->length) - sizeof(VCN));
202 VCN ntfs_ie_get_vcn(INDEX_ENTRY *ie)
204 	return sle64_to_cpup(ntfs_ie_get_vcn_addr(ie));
212 static INDEX_ENTRY *ntfs_ie_get_next(INDEX_ENTRY *ie)
214 	return (INDEX_ENTRY *)((char *)ie + le16_to_cpu(ie->length));
223 static int ntfs_ie_end(INDEX_ENTRY *ie)
225 	return ie->ie_flags & INDEX_ENTRY_END || !ie->length;
231 static INDEX_ENTRY *ntfs_ie_get_last(INDEX_ENTRY *ie, char *ies_end)
235 	while ((char *)ie < ies_end && !ntfs_ie_end(ie))
236 		ie = ntfs_ie_get_next(ie);
238 	return ie;
243 	INDEX_ENTRY *ie;
247 	ie = ntfs_ie_get_first(ih);
250 		ie = ntfs_ie_get_next(ie);
252 	return ie;
255 static INDEX_ENTRY *ntfs_ie_prev(INDEX_HEADER *ih, INDEX_ENTRY *ie)
264 	while (tmp != ie) {
272 char *ntfs_ie_filename_get(INDEX_ENTRY *ie)
276 	fn = (FILE_NAME_ATTR *)&ie->key;
280 void ntfs_ie_filename_dump(INDEX_ENTRY *ie)
284 	s = ntfs_ie_filename_get(ie);
291 	INDEX_ENTRY *ie;
295 	ie = ntfs_ie_get_first(ih);
296 	while (!ntfs_ie_end(ie)) {
297 		ntfs_ie_filename_dump(ie);
298 		ie = ntfs_ie_get_next(ie);
305 	INDEX_ENTRY *ie;
311 	ie = ntfs_ie_get_first(ih);
312 	for (n = 0; !ntfs_ie_end(ie) && (u8 *)ie < end; n++)
313 		ie = ntfs_ie_get_next(ie);
327 static void ntfs_ie_delete(INDEX_HEADER *ih, INDEX_ENTRY *ie)
333 	new_size = le32_to_cpu(ih->index_length) - le16_to_cpu(ie->length);
335 	memmove(ie, (u8 *)ie + le16_to_cpu(ie->length),
336 		new_size - ((u8 *)ie - (u8 *)ih));
339 static void ntfs_ie_set_vcn(INDEX_ENTRY *ie, VCN vcn)
341 	*ntfs_ie_get_vcn_addr(ie) = cpu_to_le64(vcn);
345  *  Insert @ie index entry at @pos entry. Used @ih values should be ok already.
347 static void ntfs_ie_insert(INDEX_HEADER *ih, INDEX_ENTRY *ie, INDEX_ENTRY *pos)
349 	int ie_size = le16_to_cpu(ie->length);
356 	memcpy(pos, ie, ie_size);
359 static INDEX_ENTRY *ntfs_ie_dup(INDEX_ENTRY *ie)
365 	dup = ntfs_malloc(le16_to_cpu(ie->length));
367 		memcpy(dup, ie, le16_to_cpu(ie->length));
372 static INDEX_ENTRY *ntfs_ie_dup_novcn(INDEX_ENTRY *ie)
375 	int size = le16_to_cpu(ie->length);
379 	if (ie->ie_flags & INDEX_ENTRY_NODE)
384 		memcpy(dup, ie, size);
488 	INDEX_ENTRY *ie;
500 	for (ie = ntfs_ie_get_first(ih); ; ie = ntfs_ie_get_next(ie)) {
502 		if ((u8 *)ie + sizeof(INDEX_ENTRY_HEADER) > index_end ||
503 		    (u8 *)ie + le16_to_cpu(ie->length) > index_end) {
514 		if (ntfs_ie_end(ie))
526 					&ie->key, le16_to_cpu(ie->key_length));
542 			*ie_out = ie;
555 	if (!(ie->ie_flags & INDEX_ENTRY_NODE)) {
557 		*ie_out = ie;
563 	*vcn = ntfs_ie_get_vcn(ie);
674 	INDEX_ENTRY *ie;
719 	ret = ntfs_ie_lookup(key, key_len, icx, &ir->index, &vcn, &ie);
761 	ret = ntfs_ie_lookup(key, key_len, icx, &ib->index, &vcn, &ie);
789 	icx->entry = ie;
790 	icx->data = (u8 *)ie + offsetof(INDEX_ENTRY, key);
791 	icx->data_len = le16_to_cpu(ie->key_length);
837 	INDEX_ENTRY *ie, *ie_start;
843 	ie = ie_start = ntfs_ie_get_first(ih);
846 	while ((u8 *)ie < ie_end && !ntfs_ie_end(ie)) {
847 		ie = ntfs_ie_get_next(ie);
857 	for (i = 0, ie = ie_start; i <= median; i++)
858 		ie = ntfs_ie_get_next(ie);
860 	return ie;
1069 			    INDEX_ENTRY *ie)
1081 		ntfs_ie_set_vcn(ie_last, ntfs_ie_get_vcn(ie));
1083 	memcpy(ie, ie_last, le16_to_cpu(ie_last->length));
1085 	ib->index.index_length = cpu_to_le32(((char *)ie - ies_start) +
1086 		le16_to_cpu(ie->length) + le32_to_cpu(ib->index.entries_offset));
1121 	INDEX_ENTRY *ie;
1161 	ie = ntfs_ie_get_first(&ir->index);
1162 	ie->ie_flags |= INDEX_ENTRY_NODE;
1163 	ie->length = cpu_to_le16(sizeof(INDEX_ENTRY_HEADER) + sizeof(VCN));
1167 					     + le16_to_cpu(ie->length));
1199 	ntfs_ie_set_vcn(ie, new_ib_vcn);
1275  * NOTE: 'ie' must be a copy of a real index entry.
1277 static int ntfs_ie_add_vcn(INDEX_ENTRY **ie)
1279 	INDEX_ENTRY *p, *old = *ie;
1287 	*ie = p;
1295 	INDEX_ENTRY *ie_node, *ie;
1301 	ie = ntfs_ie_dup(orig_ie);
1302 	if (!ie)
1305 	if (!(ie->ie_flags & INDEX_ENTRY_NODE))
1306 		if (ntfs_ie_add_vcn(&ie))
1313 	ntfs_ie_insert(ih, ie, ie_node);
1317 	free(ie);
1368 static int ntfs_ib_insert(ntfs_index_context *icx, INDEX_ENTRY *ie, VCN new_vcn)
1388 	/* FIXME: sizeof(VCN) should be included only if ie has no VCN */
1389 	if (idx_size + le16_to_cpu(ie->length) + sizeof(VCN) > allocated_size) {
1396 	if (ntfs_ih_insert(&ib->index, ie, new_vcn, ntfs_icx_parent_pos(icx)))
1451 int ntfs_ie_add(ntfs_index_context *icx, INDEX_ENTRY *ie)
1460 	fn = ntfs_ie_filename_get(ie);
1468 		if (!ntfs_index_lookup(&ie->key, le16_to_cpu(ie->key_length), icx)) {
1484 		new_size = le32_to_cpu(ih->index_length) + le16_to_cpu(ie->length);
1504 	ntfs_ie_insert(ih, ie, icx->entry);
1523 	INDEX_ENTRY *ie;
1539 	ie = ntfs_calloc(ie_size);
1540 	if (!ie)
1543 	ie->indexed_file = cpu_to_le64(mref);
1544 	ie->length 	 = cpu_to_le16(ie_size);
1545 	ie->key_length 	 = cpu_to_le16(fn_size);
1546 	memcpy(&ie->key, fn, fn_size);
1552 	ret = ntfs_ie_add(icx, ie);
1557 	free(ie);
1562 			   INDEX_ENTRY *ie, INDEX_BLOCK *ib)
1569 	ie_roam = ntfs_ie_dup_novcn(ie);
1573 	ntfs_ie_delete(ih, ie);
1595 	INDEX_ENTRY *ie;
1599 	ie = ntfs_ie_get_first(ih);
1600 	ie->ie_flags &= ~INDEX_ENTRY_NODE;
1601 	ie->length = cpu_to_le16(le16_to_cpu(ie->length) - sizeof(VCN));
1617 	INDEX_ENTRY *ie, *ie_prev;
1621 	ie = ntfs_ie_get_by_pos(ih, ntfs_icx_parent_pos(icx));
1622 	ie_prev = ntfs_ie_prev(ih, ie);
1624 	ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(ie_prev));
1633 	INDEX_ENTRY *ie;
1657 	ie = ntfs_ie_get_by_pos(parent_ih, ntfs_icx_parent_pos(icx));
1658 	if (!ntfs_ie_end(ie)) {
1659 		ret = ntfs_ih_takeout(icx, parent_ih, ie, ib);
1688 	INDEX_ENTRY *ie_succ, *ie, *entry = icx->entry;
1730 	ie = ntfs_ie_dup(ie_succ);
1731 	if (!ie)
1734 	if (ntfs_ie_add_vcn(&ie))
1737 	ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(icx->entry));
1744 	delta = le16_to_cpu(ie->length) - le16_to_cpu(icx->entry->length);
1765 	ntfs_ie_insert(ih, ie, entry);
1785 	free(ie);
1928 static INDEX_ENTRY *ntfs_index_walk_down(INDEX_ENTRY *ie,
1934 	entry = ie;
1968 static INDEX_ENTRY *ntfs_index_walk_up(INDEX_ENTRY *ie,
1974 	entry = ie;
2042 INDEX_ENTRY *ntfs_index_next(INDEX_ENTRY *ie, ntfs_index_context *ictx)
2053 	if (ie->ie_flags & INDEX_ENTRY_END)
2054 		next = ntfs_index_walk_up(ie, ictx);
2061 		next = (INDEX_ENTRY*)((char*)ie + le16_to_cpu(ie->length));