ntfs/libntfs/index.c

52  * ntfs_index_entry_mark_dirty - mark an index entry dirty
53  * @ictx:	ntfs index context describing the index entry
55  * Mark the index entry described by the index entry context @ictx dirty.
57  * If the index entry is in the index root attribute, simply mark the inode
61  * If the index entry is in an index block belonging to the index allocation
146 	if (!icx->bad_index && !icx->entry)
200  *  Get the subnode vcn to which the index entry refers.
229  *  Find the last entry in the index block
345  *  Insert @ie index entry at @pos entry. Used @ih values should be ok already.
491 		ntfs_log_error("Invalid index entry offset in inode %lld\n",
513  *		Check the consistency of an index entry
515  *	Make sure data and key do not overflow from entry.
516  *	As a side effect, an entry with zero length is rejected.
517  *	This entry must be a full one (no INDEX_ENTRY_END flag), and its
534 		ntfs_log_error("Overflow from index entry in inode %lld\n",
545 					" entry in inode %lld\n",
555 					" entry in inode %lld\n",
568  *             entry exists and @ie_out points to this entry.
570  *                    entry doesn't exist and @ie_out is the insertion point.
589 	 * reach the last entry.
596 			ntfs_log_error("Index entry out of bounds in inode "
602 		 * The last entry cannot contain a key.  It can however contain
616 			/* Make sure key and data do not overflow from entry */
631 		 * If @key collates before the key of the current entry, there
653 		ntfs_log_debug("Index entry wasn't found.\n");
668 	ntfs_log_trace("Parent entry number %d\n", item);
738  * ntfs_index_lookup - find a key in an index and return its index entry
741  * @icx:	[IN/OUT] context describing the index and the returned entry
750  * describe the index entry containing the matching @key.  @icx->entry is the
751  * index entry and @icx->data and @icx->data_len are the index entry data and
755  * @icx is setup to describe the index entry whose key collates immediately
757  * an index entry with a key of @key would need to be inserted.
762  * When finished with the entry and its data, call ntfs_index_ctx_put() to free
765  * If the index entry was modified, call ntfs_index_entry_mark_dirty() before
872 		ntfs_log_error("Index entry with child node found in a leaf "
892 	icx->entry = ie;
954 	 * NOTE: this could be also the entry at the half of the index block.
1109 	 * Copy all entries, including the termination entry
1134 	 * Move the index root termination entry forward
1146 	INDEX_ENTRY *ie_head;		/* first entry after the median */
1377  * NOTE: 'ie' must be a copy of a real index entry.
1572 			ntfs_log_perror("Index already have such entry");
1576 			ntfs_log_perror("Failed to find place for new entry");
1606 	ntfs_ie_insert(ih, ie, icx->entry);
1683 		 * while deleting an entry from root index
1705  *  Used if an empty index block to be deleted has END entry as the parent
1726  *  Used if an empty index block to be deleted has END entry as the parent
1803 	INDEX_ENTRY *ie_succ, *ie, *entry = icx->entry;
1820 	ie_succ = ntfs_ie_get_next(icx->entry);
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);
1868 			entry = ntfs_ie_get_by_pos(ih, entry_pos);
1879 	ntfs_ie_delete(ih, entry);
1880 	ntfs_ie_insert(ih, ie, entry);
1907  * ntfs_index_rm - remove entry from the index
1908  * @icx:	index context describing entry to delete
1910  * Delete entry described by @icx from the index. Index context is always
1924 	if (!icx || (!icx->ib && !icx->ir) || ntfs_ie_end(icx->entry)) {
1934 	if (icx->entry->ie_flags & INDEX_ENTRY_NODE) {
1940 		ntfs_ie_delete(ih, icx->entry);
2033  *	until there are no subnode in the first index entry
2034  *	returns the entry at the bottom left in subnode
2040 	INDEX_ENTRY *entry;
2043 	entry = ie;
2045 		vcn = ntfs_ie_get_vcn(entry);
2063 			ictx->entry = ntfs_ie_get_first(&ictx->ib->index);
2064 			entry = ictx->entry;
2066 			entry = (INDEX_ENTRY*)NULL;
2067 	} while (entry && (entry->ie_flags & INDEX_ENTRY_NODE));
2068 	return (entry);
2073  *	until there is a valid data entry in parent
2074  *	returns the parent entry or NULL if no more parent
2080 	INDEX_ENTRY *entry;
2083 	entry = ie;
2101 					entry = ntfs_ie_get_by_pos(
2105 					entry = (INDEX_ENTRY*)NULL;
2110 					entry = ntfs_ie_get_by_pos(
2114 					entry = (INDEX_ENTRY*)NULL;
2116 		ictx->entry = entry;
2117 		} while (entry && (ictx->pindex > 0)
2118 			 && (entry->ie_flags & INDEX_ENTRY_END));
2120 		entry = (INDEX_ENTRY*)NULL;
2121 	return (entry);
2125  *		Get next entry in an index according to collating sequence.
2128  *	Returns next entry or NULL if none
2134  *                 +---+---+---+---+---+---+---+---+    no key in last entry
2166 			 * get next entry in same node
2167                          * there is always one after any entry with data