Remove the specified item. Returns 1 if the item was found and * deleted, 0 otherwise. */
| 1267 | /* Remove the specified item. Returns 1 if the item was found and |
| 1268 | * deleted, 0 otherwise. */ |
| 1269 | int raxRemove(rax *rax, unsigned char *s, size_t len, void **old) { |
| 1270 | raxNode *h; |
| 1271 | raxNode **parentlink; |
| 1272 | raxStack ts; |
| 1273 | |
| 1274 | debugf("### Delete: %.*s\n", (int)len, s); |
| 1275 | raxStackInit(&ts); |
| 1276 | int splitpos = 0; |
| 1277 | int inline_leaf = 0; |
| 1278 | size_t i = raxLowWalk(rax,s,len,&h,&parentlink,&splitpos,&ts,&inline_leaf); |
| 1279 | int trycompress = 0; /* Will be set to 1 if we should try to optimize the |
| 1280 | tree resulting from the deletion. */ |
| 1281 | |
| 1282 | /* Inline leaves can be deleted directly, without materializing a |
| 1283 | * temporary node. */ |
| 1284 | if (i == len && inline_leaf) { |
| 1285 | void *val; |
| 1286 | memcpy(&val,parentlink,sizeof(val)); |
| 1287 | if (old) *old = val; |
| 1288 | rax->numele--; |
| 1289 | h = raxRemoveChildAtPtr(h,parentlink); |
| 1290 | if (h->size == 0 && h->iskey == 0) { |
| 1291 | debugf("Key deleted as inline leaf. Cleanup needed.\n"); |
| 1292 | h = raxRemoveCleanup(rax,h,&ts,&trycompress); |
| 1293 | } else if (h->size == 1 && h->iskey == 0) { |
| 1294 | trycompress = 1; |
| 1295 | } |
| 1296 | goto postdelete; |
| 1297 | } |
| 1298 | |
| 1299 | if (i != len || (h->iscompr && splitpos != 0) || !h->iskey) { |
| 1300 | raxStackFree(&ts); |
| 1301 | return 0; |
| 1302 | } |
| 1303 | if (old) *old = raxGetData(h); |
| 1304 | h->iskey = 0; |
| 1305 | rax->numele--; |
| 1306 | |
| 1307 | /* If this node has no children, the deletion needs to reclaim the |
| 1308 | * no longer used nodes. This is an iterative process that needs to |
| 1309 | * walk the three upward, deleting all the nodes with just one child |
| 1310 | * that are not keys, until the head of the rax is reached or the first |
| 1311 | * node with more than one child is found. */ |
| 1312 | |
| 1313 | if (h->size == 0) { |
| 1314 | debugf("Key deleted in node without children. Cleanup needed.\n"); |
| 1315 | h = raxRemoveCleanup(rax,h,&ts,&trycompress); |
| 1316 | } else if (h->size == 1) { |
| 1317 | /* If the node had just one child, after the removal of the key |
| 1318 | * further compression with adjacent nodes is potentially possible. */ |
| 1319 | trycompress = 1; |
| 1320 | } |
| 1321 | |
| 1322 | postdelete: |
| 1323 | /* Don't try node compression if our nodes pointers stack is not |
| 1324 | * complete because of OOM while executing raxLowWalk() */ |
| 1325 | if (trycompress && ts.oom) trycompress = 0; |
| 1326 |
no test coverage detected