ntfs/libntfs/index.c

194 static leVCN *ntfs_ie_get_vcn_addr(INDEX_ENTRY *ie)
196 	return (leVCN *)((u8 *)ie + le16_to_cpu(ie->length) - sizeof(leVCN));
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_sle64(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);
525 int ntfs_index_entry_inconsistent(const INDEX_ENTRY *ie,
531 	if (ie->key_length
532 		&& ((le16_to_cpu(ie->key_length) + offsetof(INDEX_ENTRY, key))
533 			    > le16_to_cpu(ie->length))) {
541 				    + ie->key.file_name.file_name_length
543 				> le16_to_cpu(ie->length)) {
550 			if (ie->data_length
551 				&& ((le16_to_cpu(ie->data_offset)
552 				    + le16_to_cpu(ie->data_length))
553 				    > le16_to_cpu(ie->length))) {
579 	INDEX_ENTRY *ie;
591 	for (ie = ntfs_ie_get_first(ih); ; ie = ntfs_ie_get_next(ie)) {
593 		if ((u8 *)ie + sizeof(INDEX_ENTRY_HEADER) > index_end ||
594 		    (u8 *)ie + le16_to_cpu(ie->length) > index_end) {
605 		if (ntfs_ie_end(ie))
617 		if (ntfs_index_entry_inconsistent(ie, icx->ir->collation_rule,
623 					&ie->key, le16_to_cpu(ie->key_length));
639 			*ie_out = ie;
652 	if (!(ie->ie_flags & INDEX_ENTRY_NODE)) {
654 		*ie_out = ie;
660 	*vcn = ntfs_ie_get_vcn(ie);
774 	INDEX_ENTRY *ie;
816 	ret = ntfs_ie_lookup(key, key_len, icx, &ir->index, &vcn, &ie);
858 	ret = ntfs_ie_lookup(key, key_len, icx, &ib->index, &vcn, &ie);
892 	icx->entry = ie;
893 	icx->data = (u8 *)ie + offsetof(INDEX_ENTRY, key);
894 	icx->data_len = le16_to_cpu(ie->key_length);
940 	INDEX_ENTRY *ie, *ie_start;
946 	ie = ie_start = ntfs_ie_get_first(ih);
949 	while ((u8 *)ie < ie_end && !ntfs_ie_end(ie)) {
950 		ie = ntfs_ie_get_next(ie);
960 	for (i = 0, ie = ie_start; i <= median; i++)
961 		ie = ntfs_ie_get_next(ie);
963 	return ie;
1172 			    INDEX_ENTRY *ie)
1184 		ntfs_ie_set_vcn(ie_last, ntfs_ie_get_vcn(ie));
1186 	memcpy(ie, ie_last, le16_to_cpu(ie_last->length));
1188 	ib->index.index_length = cpu_to_le32(((char *)ie - ies_start) +
1189 		le16_to_cpu(ie->length) + le32_to_cpu(ib->index.entries_offset));
1224 	INDEX_ENTRY *ie;
1264 	ie = ntfs_ie_get_first(&ir->index);
1265 	ie->ie_flags |= INDEX_ENTRY_NODE;
1266 	ie->length = const_cpu_to_le16(sizeof(INDEX_ENTRY_HEADER) + sizeof(VCN));
1270 					     + le16_to_cpu(ie->length));
1301 	ntfs_ie_set_vcn(ie, new_ib_vcn);
1377  * NOTE: 'ie' must be a copy of a real index entry.
1379 static int ntfs_ie_add_vcn(INDEX_ENTRY **ie)
1381 	INDEX_ENTRY *p, *old = *ie;
1389 	*ie = p;
1397 	INDEX_ENTRY *ie_node, *ie;
1403 	ie = ntfs_ie_dup(orig_ie);
1404 	if (!ie)
1407 	if (!(ie->ie_flags & INDEX_ENTRY_NODE))
1408 		if (ntfs_ie_add_vcn(&ie))
1415 	ntfs_ie_insert(ih, ie, ie_node);
1419 	free(ie);
1470 static int ntfs_ib_insert(ntfs_index_context *icx, INDEX_ENTRY *ie, VCN new_vcn)
1490 	/* FIXME: sizeof(VCN) should be included only if ie has no VCN */
1491 	if (idx_size + le16_to_cpu(ie->length) + sizeof(VCN) > allocated_size) {
1498 	if (ntfs_ih_insert(&ib->index, ie, new_vcn, ntfs_icx_parent_pos(icx)))
1553 int ntfs_ie_add(ntfs_index_context *icx, INDEX_ENTRY *ie)
1562 	fn = ntfs_ie_filename_get(ie);
1570 		if (!ntfs_index_lookup(&ie->key, le16_to_cpu(ie->key_length), icx)) {
1586 		new_size = le32_to_cpu(ih->index_length) + le16_to_cpu(ie->length);
1606 	ntfs_ie_insert(ih, ie, icx->entry);
1625 	INDEX_ENTRY *ie;
1641 	ie = ntfs_calloc(ie_size);
1642 	if (!ie)
1645 	ie->indexed_file = cpu_to_le64(mref);
1646 	ie->length 	 = cpu_to_le16(ie_size);
1647 	ie->key_length 	 = cpu_to_le16(fn_size);
1648 	memcpy(&ie->key, fn, fn_size);
1654 	ret = ntfs_ie_add(icx, ie);
1659 	free(ie);
1664 			   INDEX_ENTRY *ie, INDEX_BLOCK *ib)
1674 	ie_roam = ntfs_ie_dup_novcn(ie);
1678 	ntfs_ie_delete(ih, ie);
1710 	INDEX_ENTRY *ie;
1714 	ie = ntfs_ie_get_first(ih);
1715 	ie->ie_flags &= ~INDEX_ENTRY_NODE;
1716 	ie->length = cpu_to_le16(le16_to_cpu(ie->length) - sizeof(VCN));
1732 	INDEX_ENTRY *ie, *ie_prev;
1736 	ie = ntfs_ie_get_by_pos(ih, ntfs_icx_parent_pos(icx));
1737 	ie_prev = ntfs_ie_prev(ih, ie);
1739 	ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(ie_prev));
1748 	INDEX_ENTRY *ie;
1772 	ie = ntfs_ie_get_by_pos(parent_ih, ntfs_icx_parent_pos(icx));
1773 	if (!ntfs_ie_end(ie)) {
1774 		ret = ntfs_ih_takeout(icx, parent_ih, ie, ib);
1803 	INDEX_ENTRY *ie_succ, *ie, *entry = icx->entry;
1845 	ie = ntfs_ie_dup(ie_succ);
1846 	if (!ie)
1849 	if (ntfs_ie_add_vcn(&ie))
1852 	ntfs_ie_set_vcn(ie, ntfs_ie_get_vcn(icx->entry));
1859 	delta = le16_to_cpu(ie->length) - le16_to_cpu(icx->entry->length);
1880 	ntfs_ie_insert(ih, ie, entry);
1900 	free(ie);
2037 static INDEX_ENTRY *ntfs_index_walk_down(INDEX_ENTRY *ie,
2043 	entry = ie;
2077 static INDEX_ENTRY *ntfs_index_walk_up(INDEX_ENTRY *ie,
2083 	entry = ie;
2151 INDEX_ENTRY *ntfs_index_next(INDEX_ENTRY *ie, ntfs_index_context *ictx)
2162 	if (ie->ie_flags & INDEX_ENTRY_END)
2163 		next = ntfs_index_walk_up(ie, ictx);
2170 		next = (INDEX_ENTRY*)((char*)ie + le16_to_cpu(ie->length));