Lines Matching refs:key
55 static int fallible_read_node(struct ubifs_info *c, const union ubifs_key *key,
326 ubifs_assert(is_hash_key(c, &zbr->key));
388 * @zbr: key and position of the node
401 ubifs_assert(is_hash_key(c, &zbr->key));
411 err = fallible_read_node(c, &zbr->key, zbr, node);
496 * @key: key of node to read
503 static int fallible_read_node(struct ubifs_info *c, const union ubifs_key *key,
508 dbg_tnck(key, "LEB %d:%d, key ", zbr->lnum, zbr->offs);
510 ret = try_read_node(c, node, key_type(c, key), zbr->len, zbr->lnum,
516 /* All nodes have key in the same place */
517 key_read(c, &dent->key, &node_key);
518 if (keys_cmp(c, key, &node_key) != 0)
522 dbg_mntk(key, "dangling branch LEB %d:%d len %d, key ",
694 * @key: key of a directory or extended attribute entry
699 * This function is called for "hashed" keys to make sure that the found key
704 * This means that @n may be set to %-1 if the leftmost key in @zn is the
707 static int resolve_collision(struct ubifs_info *c, const union ubifs_key *key,
730 if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) {
758 * 'tnc_insert()' would correct the parent key.
794 if (keys_cmp(c, &znode->zbranch[nn].key, key))
838 err = fallible_read_node(c, &zbr->key, zbr, dent);
876 * @key: key
880 * @adding: indicates caller is adding a key to the TNC
896 const union ubifs_key *key,
931 if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) {
976 if (keys_cmp(c, &znode->zbranch[nn].key, key))
998 dbg_mntk(key, "dangling match LEB %d:%d len %d key ",
1025 * @key: key of directory entry
1040 const union ubifs_key *key,
1059 if (keys_cmp(c, &znode->zbranch[nn].key, key))
1077 if (keys_cmp(c, &znode->zbranch[nn].key, key))
1091 * If we do not have a unique key that resides in a znode, then we cannot
1156 * @key: key to lookup
1161 * refers key @key. The found zero-level znode is returned in @zn. There are 3
1163 * o exact match, i.e. the found zero-level znode contains key @key, then %1
1166 * @key, then %0 is returned and slot number of the closest branch is stored
1168 * o @key is so small that it is even less than the lowest key of the
1175 int ubifs_lookup_level0(struct ubifs_info *c, const union ubifs_key *key,
1182 dbg_tnck(key, "search key ");
1183 ubifs_assert(key_type(c, key) < UBIFS_INVALID_KEY);
1197 exact = ubifs_search_zbranch(c, znode, key, n);
1219 if (exact || !is_hash_key(c, key) || *n != -1) {
1225 * Here is a tricky place. We have not found the key and this is a
1226 * "hashed" key, which may collide. The rest of the code deals with
1241 * In the examples, if we are looking for key "5", we may reach nodes
1243 * left and see if there is "5" key there. If there is, we have to
1247 * elements which are equivalent to the next key in the parent in the
1255 * And this becomes what is at the first "picture" after key "5" marked
1258 * removing the leftmost key, we would have to correct the key of the
1260 * if we changed the leftmost key of the parent znode, the garbage
1275 if (keys_cmp(c, key, &znode->zbranch[*n].key)) {
1289 * @key: key to lookup
1294 * refers key @key. The found zero-level znode is returned in @zn. There are 3
1296 * o exact match, i.e. the found zero-level znode contains key @key, then %1
1298 * o not exact match, which means that zero-level znode does not contain @key
1301 * o @key is so small that it is even less than the lowest key of the
1311 static int lookup_level0_dirty(struct ubifs_info *c, const union ubifs_key *key,
1318 dbg_tnck(key, "search and dirty key ");
1336 exact = ubifs_search_zbranch(c, znode, key, n);
1363 if (exact || !is_hash_key(c, key) || *n != -1) {
1380 if (keys_cmp(c, key, &znode->zbranch[*n].key)) {
1440 * @key: node key to lookup
1445 * This function looks up and reads node with key @key. The caller has to make
1450 int ubifs_tnc_locate(struct ubifs_info *c, const union ubifs_key *key,
1459 found = ubifs_lookup_level0(c, key, &znode, &n);
1472 if (is_hash_key(c, key)) {
1495 err = fallible_read_node(c, key, &zbr, node);
1528 unsigned int block = key_block(c, &bu->key);
1536 /* Find first key */
1537 err = ubifs_lookup_level0(c, &bu->key, &znode, &n);
1548 /* Add this key */
1556 union ubifs_key *key;
1559 /* Find next key */
1564 key = &zbr->key;
1565 /* See if there is another data key for this file */
1566 if (key_inum(c, key) != key_inum(c, &bu->key) ||
1567 key_type(c, key) != UBIFS_DATA_KEY) {
1572 /* First key found */
1594 next_block = key_block(c, key);
1599 /* Add this key */
1636 block = key_block(c, &bu->key) + bu->blk_cnt;
1639 if (key_block(c, &bu->zbranch[bu->cnt - 1].key) < block)
1724 /* Make sure the key of the read node is correct */
1726 if (!keys_eq(c, &zbr->key, &key1)) {
1727 ubifs_err(c, "bad key in node at LEB %d:%d",
1729 dbg_tnck(&zbr->key, "looked for key ");
1730 dbg_tnck(&key1, "found node's key ");
1783 dbg_tnck(&bu->key, "key ");
1802 * @key: node key to lookup
1806 * This function look up and reads a node which contains name hash in the key.
1808 * key, so we have to sequentially look to all of them until the needed one is
1812 static int do_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,
1818 dbg_tnck(key, "name '%.*s' key ", nm->len, nm->name);
1820 found = ubifs_lookup_level0(c, key, &znode, &n);
1831 err = resolve_collision(c, key, &znode, &n, nm);
1850 * @key: node key to lookup
1854 * This function look up and reads a node which contains name hash in the key.
1856 * key, so we have to sequentially look to all of them until the needed one is
1860 int ubifs_tnc_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,
1870 err = ubifs_tnc_lookup(c, key, node);
1882 return do_lookup_nm(c, key, node, nm);
1890 * This is a helper function for 'tnc_insert()'. When the key of the leftmost
1897 union ubifs_key *key, *key1;
1902 key = &znode->zbranch[0].key;
1903 key1 = &znode->parent->zbranch[0].key;
1905 while (keys_cmp(c, key, key1) < 0) {
1906 key_copy(c, key, key1);
1911 key1 = &znode->parent->zbranch[0].key;
1949 * After inserting at slot zero, the lower bound of the key range of
1951 * then the upper bound of the key range may change, and furthermore
1954 * TNC using the key from the index node on flash. That is bad because
1983 union ubifs_key *key = &zbr->key, *key1;
1992 dbg_tnck(key, "inserted at %d level %d, key ", n, znode->level);
1996 /* Ensure parent's key is correct */
2007 dbg_tnck(key, "splitting level %d, key ", znode->level);
2011 * We can no longer be sure of finding this znode by key, so we
2023 if (znode->level == 0 && key_type(c, key) == UBIFS_DATA_KEY) {
2026 key1 = &znode->zbranch[n - 1].key;
2027 if (key_inum(c, key1) == key_inum(c, key) &&
2037 key1 = &znode->zbranch[0].key;
2038 if (key_inum(c, key1) == key_inum(c, key) &&
2040 key1 = &znode->zbranch[n].key;
2041 if (key_inum(c, key1) != key_inum(c, key) ||
2100 /* Insert new key and branch */
2101 dbg_tnck(key, "inserting at %d level %d, key ", n, zn->level);
2114 zbr->key = zn->zbranch[0].key;
2137 zi->zbranch[0].key = znode->zbranch[0].key;
2142 zi->zbranch[1].key = zn->zbranch[0].key;
2161 * @key: key to add
2166 * This function adds a node with key @key to TNC. The node may be new or it may
2170 int ubifs_tnc_add(struct ubifs_info *c, const union ubifs_key *key, int lnum,
2177 dbg_tnck(key, "%d:%d, len %d, key ", lnum, offs, len);
2178 found = lookup_level0_dirty(c, key, &znode, &n);
2186 key_copy(c, key, &zbr.key);
2208 * @key: key to add
2215 * This function replaces a node with key @key in the TNC only if the old node
2219 int ubifs_tnc_replace(struct ubifs_info *c, const union ubifs_key *key,
2226 dbg_tnck(key, "old LEB %d:%d, new LEB %d:%d, len %d, key ", old_lnum,
2228 found = lookup_level0_dirty(c, key, &znode, &n);
2247 } else if (is_hash_key(c, key)) {
2248 found = resolve_collision_directly(c, key, &znode, &n,
2293 * @key: key to add
2302 int ubifs_tnc_add_nm(struct ubifs_info *c, const union ubifs_key *key,
2309 dbg_tnck(key, "LEB %d:%d, name '%.*s', key ",
2311 found = lookup_level0_dirty(c, key, &znode, &n);
2319 found = fallible_resolve_collision(c, key, &znode, &n,
2322 found = resolve_collision(c, key, &znode, &n, nm);
2357 key_copy(c, key, &zbr.key);
2365 * by passing 'ubifs_tnc_remove_nm()' the same key but
2374 return ubifs_tnc_remove_nm(c, key, &noname);
2403 dbg_tnck(&znode->zbranch[n].key, "deleting key ");
2503 * @key: key of node
2507 int ubifs_tnc_remove(struct ubifs_info *c, const union ubifs_key *key)
2513 dbg_tnck(key, "key ");
2514 found = lookup_level0_dirty(c, key, &znode, &n);
2532 * @key: key of node
2537 int ubifs_tnc_remove_nm(struct ubifs_info *c, const union ubifs_key *key,
2544 dbg_tnck(key, "%.*s, key ", nm->len, nm->name);
2545 err = lookup_level0_dirty(c, key, &znode, &n);
2551 err = fallible_resolve_collision(c, key, &znode, &n,
2554 err = resolve_collision(c, key, &znode, &n, nm);
2579 * key_in_range - determine if a key falls within a range of keys.
2581 * @key: key to check
2582 * @from_key: lowest key in range
2583 * @to_key: highest key in range
2585 * This function returns %1 if the key is in range and %0 otherwise.
2587 static int key_in_range(struct ubifs_info *c, union ubifs_key *key,
2590 if (keys_cmp(c, key, from_key) < 0)
2592 if (keys_cmp(c, key, to_key) > 0)
2600 * @from_key: lowest key to remove
2601 * @to_key: highest key to remove
2612 union ubifs_key *key;
2622 key = from_key;
2631 key = &znode->zbranch[n].key;
2632 if (!key_in_range(c, key, from_key, to_key)) {
2649 key = &znode->zbranch[i].key;
2650 if (!key_in_range(c, key, from_key, to_key))
2659 dbg_tnck(key, "removing key ");
2736 key_read(c, &xent->key, &key1);
2749 * @key: key of last entry
2753 * after the given key (@key) if there is one. @nm is used to resolve
2756 * If the name of the current entry is not known and only the key is known,
2758 * little bit different and it returns the entry corresponding to this key, not
2759 * the next one. If the key was not found, the closest "right" entry is
2762 * If the fist entry has to be found, @key has to contain the lowest possible
2763 * key value for this inode and @name has to be %NULL.
2770 union ubifs_key *key,
2773 int n, err, type = key_type(c, key);
2779 dbg_tnck(key, "%s ", nm->name ? (char *)nm->name : "(lowest)");
2780 ubifs_assert(is_hash_key(c, key));
2783 err = ubifs_lookup_level0(c, key, &znode, &n);
2791 err = fallible_resolve_collision(c, key, &znode, &n,
2794 err = resolve_collision(c, key, &znode, &n, nm);
2813 * However, the given key does not exist in the TNC
2834 dkey = &zbr->key;
2835 if (key_inum(c, dkey) != key_inum(c, key) ||
2974 * @key: index node key to lookup
2979 * This function searches an indexing node by its first key @key and its
2984 * looked for does not have to have exactly the same leftmost key @key, because
2985 * the leftmost key may have been changed, in which case TNC will contain a
2997 union ubifs_key *key, int level,
3003 ubifs_assert(key_type(c, key) < UBIFS_INVALID_KEY);
3026 ubifs_search_zbranch(c, znode, key, &n);
3029 * We reached a znode where the leftmost key is greater
3030 * than the key we are searching for. This is the same
3041 ubifs_search_zbranch(c, znode, key, &n);
3053 /* If the key is unique, there is nowhere else to look */
3054 if (!is_hash_key(c, key))
3057 * The key is not unique and so may be also in the znodes to either
3079 /* Stop if the key is less than the one we are looking for */
3080 if (keys_cmp(c, &znode->zbranch[n].key, key) < 0)
3101 /* Stop if the key is greater than the one we are looking for */
3102 if (keys_cmp(c, &znode->zbranch[n].key, key) > 0)
3111 * @key: key of index node
3121 * Note, the @key argument has to be the key of the first child. Also note,
3125 int is_idx_node_in_tnc(struct ubifs_info *c, union ubifs_key *key, int level,
3130 znode = lookup_znode(c, key, level, lnum, offs);
3142 * @key: node key
3152 static int is_leaf_node_in_tnc(struct ubifs_info *c, union ubifs_key *key,
3158 const int unique = !is_hash_key(c, key);
3160 found = ubifs_lookup_level0(c, key, &znode, &n);
3171 * Because the key is not unique, we have to look left
3183 if (keys_cmp(c, key, &znode->zbranch[n].key))
3199 if (keys_cmp(c, key, &znode->zbranch[n].key))
3211 * @key: node key
3218 * negative error code in case of failure. For index nodes, @key has to be the
3219 * key of the first child. An index node is considered to be in the TNC only if
3222 int ubifs_tnc_has_node(struct ubifs_info *c, union ubifs_key *key, int level,
3229 err = is_idx_node_in_tnc(c, key, level, lnum, offs);
3241 err = is_leaf_node_in_tnc(c, key, lnum, offs);
3251 * @key: index node key
3257 * collected. The @key argument has to be the key of the first child. This
3262 int ubifs_dirty_idx_node(struct ubifs_info *c, union ubifs_key *key, int level,
3269 znode = lookup_znode(c, key, level, lnum, offs);
3302 union ubifs_key from_key, to_key, *key;
3321 key = &from_key;
3334 key = &znode->zbranch[n].key;
3335 if (!key_in_range(c, key, &from_key, &to_key))
3339 block = key_block(c, key);