Free the useless node 'h' that was left after a deletion, and keep moving * upward while the parent would also become a non-key single-child node. * The returned node is the first one that remains in the tree and may * require recompression. */
| 1224 | * The returned node is the first one that remains in the tree and may |
| 1225 | * require recompression. */ |
| 1226 | static inline raxNode *raxRemoveCleanup(rax *rax, raxNode *h, raxStack *ts, |
| 1227 | int *trycompress) |
| 1228 | { |
| 1229 | raxNode *child = NULL; |
| 1230 | |
| 1231 | while(h != rax->head) { |
| 1232 | child = h; |
| 1233 | debugf("Freeing child %p [%.*s] key:%d\n", (void*)child, |
| 1234 | (int)child->size, (char*)child->data, child->iskey); |
| 1235 | rax_free(child); |
| 1236 | rax->numnodes--; |
| 1237 | h = raxStackPop(ts); |
| 1238 | /* If this node has more then one child, or actually holds |
| 1239 | * a key, stop here. */ |
| 1240 | if (h->iskey || (!h->iscompr && h->size != 1)) break; |
| 1241 | } |
| 1242 | if (child) { |
| 1243 | debugf("Unlinking child %p from parent %p\n", |
| 1244 | (void*)child, (void*)h); |
| 1245 | raxNode *new = raxRemoveChild(h,child); |
| 1246 | if (new != h) { |
| 1247 | raxNode *parent = raxStackPeek(ts); |
| 1248 | raxNode **parentlink; |
| 1249 | if (parent == NULL) { |
| 1250 | parentlink = &rax->head; |
| 1251 | } else { |
| 1252 | parentlink = raxFindParentLink(parent,h); |
| 1253 | } |
| 1254 | memcpy(parentlink,&new,sizeof(new)); |
| 1255 | } |
| 1256 | |
| 1257 | /* If after the removal the node has just a single child |
| 1258 | * and is not a key, we need to try to compress it. */ |
| 1259 | if (new->size == 1 && new->iskey == 0) { |
| 1260 | *trycompress = 1; |
| 1261 | h = new; |
| 1262 | } |
| 1263 | } |
| 1264 | return h; |
| 1265 | } |
| 1266 | |
| 1267 | /* Remove the specified item. Returns 1 if the item was found and |
| 1268 | * deleted, 0 otherwise. */ |
no test coverage detected