* Search the tree until the appropriate location for the given key is found: * 1. Start at the root node, with n = 0 * 2. If a[0] at the current level is a matching subtree entry, unpack that * subtree entry and remove it; restart search at the current level. * 3. Use the nth nibble of the key as an index into a: * - If a[n] is an int_node, recurse from #2 into that node and increment n
| 102 | * In any case, set *tree and *n, and return pointer to the tree location. |
| 103 | */ |
| 104 | static void **note_tree_search(struct notes_tree *t, struct int_node **tree, |
| 105 | unsigned char *n, const unsigned char *key_sha1) |
| 106 | { |
| 107 | struct leaf_node *l; |
| 108 | unsigned char i; |
| 109 | void *p = (*tree)->a[0]; |
| 110 | |
| 111 | if (GET_PTR_TYPE(p) == PTR_TYPE_SUBTREE) { |
| 112 | l = (struct leaf_node *) CLR_PTR_TYPE(p); |
| 113 | if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_oid.hash)) { |
| 114 | /* unpack tree and resume search */ |
| 115 | (*tree)->a[0] = NULL; |
| 116 | load_subtree(t, l, *tree, *n); |
| 117 | free(l); |
| 118 | return note_tree_search(t, tree, n, key_sha1); |
| 119 | } |
| 120 | } |
| 121 | |
| 122 | i = GET_NIBBLE(*n, key_sha1); |
| 123 | p = (*tree)->a[i]; |
| 124 | switch (GET_PTR_TYPE(p)) { |
| 125 | case PTR_TYPE_INTERNAL: |
| 126 | *tree = CLR_PTR_TYPE(p); |
| 127 | (*n)++; |
| 128 | return note_tree_search(t, tree, n, key_sha1); |
| 129 | case PTR_TYPE_SUBTREE: |
| 130 | l = (struct leaf_node *) CLR_PTR_TYPE(p); |
| 131 | if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_oid.hash)) { |
| 132 | /* unpack tree and resume search */ |
| 133 | (*tree)->a[i] = NULL; |
| 134 | load_subtree(t, l, *tree, *n); |
| 135 | free(l); |
| 136 | return note_tree_search(t, tree, n, key_sha1); |
| 137 | } |
| 138 | /* fall through */ |
| 139 | default: |
| 140 | return &((*tree)->a[i]); |
| 141 | } |
| 142 | } |
| 143 | |
| 144 | /* |
| 145 | * To find a leaf_node: |
no test coverage detected