81
/* OK, normal data node, let's walk down */
82
bit = string_equal_bits(x, node->key, bit);
84
return NULL; /* no more common bits */
81
/* OK, normal data node, let's walk down but don't compare data
82
* if we already reached the end of the key.
84
if (likely(bit >= 0)) {
85
bit = string_equal_bits(x, node->key, bit);
86
if (likely(bit < node_bit)) {
88
return NULL; /* no more common bits */
90
/* bit < 0 : we reached the end of the key. If we
91
* are in a tree with unique keys, we can return
92
* this node. Otherwise we have to walk it down
93
* and stop comparing bits.
95
if (eb_gettag(root->b[EB_RGHT]))
86
100
troot = node->node.branches.b[(((unsigned char*)x)[node_bit >> 3] >>
87
101
(~node_bit & 7)) & 1];
159
173
* The last two cases can easily be partially merged.
161
bit = string_equal_bits(new->key, old->key, bit);
176
bit = string_equal_bits(new->key, old->key, bit);
179
/* key was already there */
181
/* we may refuse to duplicate this key if the tree is
182
* tagged as containing only unique keys.
184
if (eb_gettag(root_right))
187
/* new arbitrarily goes to the right and tops the dup tree */
188
old->node.leaf_p = new_left;
189
new->node.leaf_p = new_rght;
190
new->node.branches.b[EB_LEFT] = old_leaf;
191
new->node.branches.b[EB_RGHT] = new_leaf;
193
root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
162
197
diff = cmp_bits(new->key, old->key, bit);
199
/* new->key < old->key, new takes the left */
165
200
new->node.leaf_p = new_left;
166
201
old->node.leaf_p = new_rght;
167
202
new->node.branches.b[EB_LEFT] = new_leaf;
168
203
new->node.branches.b[EB_RGHT] = old_leaf;
170
/* we may refuse to duplicate this key if the tree is
171
* tagged as containing only unique keys.
173
if (diff == 0 && eb_gettag(root_right))
176
/* new->key >= old->key, new goes the right */
205
/* new->key > old->key, new takes the right */
177
206
old->node.leaf_p = new_left;
178
207
new->node.leaf_p = new_rght;
179
208
new->node.branches.b[EB_LEFT] = old_leaf;
180
209
new->node.branches.b[EB_RGHT] = new_leaf;
184
root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
199
222
* the current node's because as long as they are identical, we
200
223
* know we descend along the correct side.
202
if (old_node_bit < 0) {
203
/* we're above a duplicate tree, we must compare till the end */
204
bit = string_equal_bits(new->key, old->key, bit);
207
else if (bit < old_node_bit) {
208
bit = string_equal_bits(new->key, old->key, bit);
225
if (bit >= 0 && (bit < old_node_bit || old_node_bit < 0))
226
bit = string_equal_bits(new->key, old->key, bit);
211
if (bit < old_node_bit) { /* we don't have all bits in common */
212
/* The tree did not contain the key, so we insert <new> before the node
213
* <old>, and set ->bit to designate the lowest bit position in <new>
214
* which applies to ->branches.b[].
228
if (unlikely(bit < 0)) {
229
/* Perfect match, we must only stop on head of dup tree
230
* or walk down to a leaf.
232
if (old_node_bit < 0) {
233
/* We know here that string_equal_bits matched all
234
* bits and that we're on top of a dup tree, then
235
* we can perform the dup insertion and return.
238
ret = eb_insert_dup(&old->node, &new->node);
239
return container_of(ret, struct ebmb_node, node);
241
/* OK so let's walk down */
243
else if (bit < old_node_bit || old_node_bit < 0) {
244
/* The tree did not contain the key, or we stopped on top of a dup
245
* tree, possibly containing the key. In the former case, we insert
246
* <new> before the node <old>, and set ->bit to designate the lowest
247
* bit position in <new> which applies to ->branches.b[]. In the later
248
* case, we add the key to the existing dup tree. Note that we cannot
249
* enter here if we match an intermediate node's key that is not the
250
* head of a dup tree.
216
252
eb_troot_t *new_left, *new_rght;
217
253
eb_troot_t *new_leaf, *old_node;
219
255
new_left = eb_dotag(&new->node.branches, EB_LEFT);
220
256
new_rght = eb_dotag(&new->node.branches, EB_RGHT);
221
257
new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
230
267
new->node.branches.b[EB_LEFT] = new_leaf;
231
268
new->node.branches.b[EB_RGHT] = old_node;
234
271
old->node.node_p = new_left;
235
272
new->node.leaf_p = new_rght;
236
273
new->node.branches.b[EB_LEFT] = old_node;
237
274
new->node.branches.b[EB_RGHT] = new_leaf;
241
ret = eb_insert_dup(&old->node, &new->node);
242
return container_of(ret, struct ebmb_node, node);
added
removed
ebtree/ebsttree.h
