Lines Matching refs:index
2 * index.c - NTFS index handling. Originated from the Linux-NTFS project.
42 #include "index.h"
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
58 * containing the index root attribute dirty. This ensures the mftrecord, and
59 * hence the index root attribute, will be written out to disk later.
61 * If the index entry is in an index block belonging to the index allocation
62 * attribute, set ib_dirty to TRUE, thus index block will be updated during
92 ntfs_log_perror("Failed to write index block %lld, inode %llu",
111 * ntfs_index_ctx_get - allocate and initialize a new index context
114 * @name_len: length of the index name
116 * Allocate a new index context, initialize it with @ni and return it.
164 * ntfs_index_ctx_put - release an index context
165 * @icx: index context to free
167 * Release the index context @icx, releasing all associated resources.
176 * ntfs_index_ctx_reinit - reinitialize an index context
177 * @icx: index context to reinitialize
179 * Reinitialize the index context @icx so it can be used for ntfs_index_lookup.
200 * Get the subnode vcn to which the index entry refers.
219 /* FIXME: check if it isn't overflowing the index block size */
229 * Find the last entry in the index block
345 * Insert @ie index entry at @pos entry. Used @ih values should be ok already.
437 * Check the consistency of an index block
439 * Make sure the index block does not overflow from the index record.
441 * defined in the index root.
446 * |<--->| offsetof(INDEX_BLOCK, index)
449 * | | | seq index entries unused
463 u32 ib_size = (unsigned)le32_to_cpu(ib->index.allocated_size)
464 + offsetof(INDEX_BLOCK, index);
467 ntfs_log_error("Corrupt index block signature: vcn %lld inode "
474 ntfs_log_error("Corrupt index block: VCN (%lld) is different "
483 ntfs_log_error("Corrupt index block : VCN (%lld) of inode %llu "
484 "has a size (%u) differing from the index "
490 if (le32_to_cpu(ib->index.entries_offset) < sizeof(INDEX_HEADER)) {
491 ntfs_log_error("Invalid index entry offset in inode %lld\n",
495 if (le32_to_cpu(ib->index.index_length)
496 <= le32_to_cpu(ib->index.entries_offset)) {
497 ntfs_log_error("No space for index entries in inode %lld\n",
501 if (le32_to_cpu(ib->index.allocated_size)
502 < le32_to_cpu(ib->index.index_length)) {
513 * Check the consistency of an index entry
519 * index record.
534 ntfs_log_error("Overflow from index entry in inode %lld\n",
544 ntfs_log_error("File name overflow from index"
554 ntfs_log_error("Data overflow from index"
564 * Find a key in the index block.
572 * @vcn will contain the node index block.
632 * is definitely no such key in this index but we might need to
648 * We have finished with this index block without success. Check for the
650 * otherwise we will keep searching in another index block.
680 ntfs_log_perror("Failed to open index allocation of inode "
699 ntfs_log_perror("Failed to read index block");
701 ntfs_log_error("Failed to read full index block at "
731 ntfs_log_perror("Corrupt index pointer (%d)", icx->pindex);
738 * ntfs_index_lookup - find a key in an index and return its index entry
739 * @key: [IN] key for which to search in the index
741 * @icx: [IN/OUT] context describing the index and the returned entry
746 * Look for the @key in the index specified by the index lookup context @icx.
747 * ntfs_index_lookup() walks the contents of the index looking for the @key.
749 * If the @key is found in the index, 0 is returned and @icx is setup to
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
754 * If the @key is not found in the index, -1 is returned, errno = ENOENT and
755 * @icx is setup to describe the index entry whose key collates immediately
756 * after the search @key, i.e. this is the position in the index at which
757 * an index entry with a key of @key would need to be inserted.
765 * If the index entry was modified, call ntfs_index_entry_mark_dirty() before
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);
871 if ((ib->index.ih_flags & NODE_MASK) == LEAF_NODE) {
925 ib->index.entries_offset = cpu_to_le32((ih_size +
927 ib->index.index_length = const_cpu_to_le32(0);
928 ib->index.allocated_size = cpu_to_le32(ib_size -
930 ib->index.ih_flags = node_type;
954 * NOTE: this could be also the entry at the half of the index block.
1105 ies_start = (char *)ntfs_ie_get_first(&ir->index);
1106 ies_end = (char *)ntfs_ie_get_end(&ir->index);
1113 memcpy(ntfs_ie_get_first(&ib->index), ies_start, i);
1115 ib->index.ih_flags = ir->index.ih_flags;
1116 ib->index.index_length = cpu_to_le32(i +
1117 le32_to_cpu(ib->index.entries_offset));
1130 ies_start = (char *)ntfs_ie_get_first(&ir->index);
1131 ies_end = (char *)ntfs_ie_get_end(&ir->index);
1134 * Move the index root termination entry forward
1153 src->index.ih_flags & NODE_MASK);
1159 ies_end = (u8 *)ntfs_ie_get_end(&src->index);
1161 memcpy(ntfs_ie_get_first(&dst->index), ie_head, tail_size);
1163 dst->index.index_length = cpu_to_le32(tail_size +
1164 le32_to_cpu(dst->index.entries_offset));
1179 ies_start = (char *)ntfs_ie_get_first(&ib->index);
1180 ies_end = (char *)ntfs_ie_get_end(&ib->index);
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));
1236 if ((ir->index.ih_flags & NODE_MASK) == SMALL_INDEX)
1250 ntfs_log_perror("Failed to move index root to index block");
1264 ie = ntfs_ie_get_first(&ir->index);
1268 ir->index.ih_flags = LARGE_INDEX;
1269 ir->index.index_length = cpu_to_le32(le32_to_cpu(ir->index.entries_offset)
1271 ir->index.allocated_size = ir->index.index_length;
1273 + le32_to_cpu(ir->index.allocated_size);
1278 * index, we may have to move the root to an extent
1294 /* FIXME: revert index root */
1315 * ntfs_ir_truncate - Truncate index root attribute
1335 ret = ntfs_attr_truncate(na, data_size + offsetof(INDEX_ROOT, index));
1342 icx->ir->index.allocated_size = cpu_to_le32(data_size);
1352 * ntfs_ir_make_space - Make more space for the index root attribute
1377 * NOTE: 'ie' must be a copy of a real index entry.
1447 new_size = le32_to_cpu(icx->ir->index.index_length) +
1460 return ntfs_ih_insert(&icx->ir->index, median, new_vcn,
1488 idx_size = le32_to_cpu(ib->index.index_length);
1489 allocated_size = le32_to_cpu(ib->index.allocated_size);
1498 if (ntfs_ih_insert(&ib->index, ie, new_vcn, ntfs_icx_parent_pos(icx)))
1511 * ntfs_ib_split - Split an index block
1527 median = ntfs_ie_get_median(&ib->index);
1581 ih = &icx->ir->index;
1583 ih = &icx->ib->index;
1591 ntfs_log_trace("index block sizes: allocated: %d needed: %d\n",
1616 * ntfs_index_add_filename - add filename to directory index
1617 * @ni: ntfs inode describing directory to which index add filename
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
1760 parent_ih = &icx->ir->index;
1769 parent_ih = &ib->index;
1828 ie_succ = ntfs_ie_get_first(&ib->index);
1836 if ((ib->index.ih_flags & NODE_MASK) == INDEX_NODE)
1839 if (ntfs_ih_zero_entry(&ib->index)) {
1841 ntfs_log_perror("Empty index block");
1855 ih = &icx->ir->index;
1857 ih = &icx->ib->index;
1867 ih = &icx->ir->index;
1889 ntfs_ie_delete(&ib->index, ie_succ);
1891 if (ntfs_ih_zero_entry(&ib->index)) {
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
1911 * reinitialized after use of this function, so it can be used for index
1930 ih = &icx->ir->index;
1932 ih = &icx->ib->index;
1997 * ntfs_index_root_get - read the index root of an attribute
1999 * @attr: attribute for which we want its index root
2001 * This function will read the related index root an ntfs attribute.
2003 * On success a buffer is allocated with the content of the index root
2032 * Walk down the index tree (leaf bound)
2033 * until there are no subnode in the first index entry
2063 ictx->entry = ntfs_ie_get_first(&ictx->ib->index);
2072 * Walk up the index tree (root bound)
2102 &ictx->ir->index,
2111 &ictx->ib->index,
2125 * Get next entry in an index according to collating sequence.