Remove the specified item. Returns 1 if the item was found and * deleted, 0 otherwise. */
| 1020 | /* Remove the specified item. Returns 1 if the item was found and |
| 1021 | * deleted, 0 otherwise. */ |
| 1022 | int raxRemove(rax *rax, unsigned char *s, size_t len, void **old) { |
| 1023 | raxNode *h; |
| 1024 | raxStack ts; |
| 1025 | |
| 1026 | debugf("### Delete: %.*s\n", (int)len, s); |
| 1027 | raxStackInit(&ts); |
| 1028 | int splitpos = 0; |
| 1029 | size_t i = raxLowWalk(rax,s,len,&h,NULL,&splitpos,&ts); |
| 1030 | if (i != len || (h->iscompr && splitpos != 0) || !h->iskey) { |
| 1031 | raxStackFree(&ts); |
| 1032 | return 0; |
| 1033 | } |
| 1034 | if (old) *old = raxGetData(h); |
| 1035 | h->iskey = 0; |
| 1036 | rax->numele--; |
| 1037 | |
| 1038 | /* If this node has no children, the deletion needs to reclaim the |
| 1039 | * no longer used nodes. This is an iterative process that needs to |
| 1040 | * walk the three upward, deleting all the nodes with just one child |
| 1041 | * that are not keys, until the head of the rax is reached or the first |
| 1042 | * node with more than one child is found. */ |
| 1043 | |
| 1044 | int trycompress = 0; /* Will be set to 1 if we should try to optimize the |
| 1045 | tree resulting from the deletion. */ |
| 1046 | |
| 1047 | if (h->size == 0) { |
| 1048 | debugf("Key deleted in node without children. Cleanup needed.\n"); |
| 1049 | raxNode *child = NULL; |
| 1050 | while(h != rax->head) { |
| 1051 | child = h; |
| 1052 | debugf("Freeing child %p [%.*s] key:%d\n", (void*)child, |
| 1053 | (int)child->size, (char*)child->data, child->iskey); |
| 1054 | rax_free(child); |
| 1055 | rax->numnodes--; |
| 1056 | h = raxStackPop(&ts); |
| 1057 | /* If this node has more then one child, or actually holds |
| 1058 | * a key, stop here. */ |
| 1059 | if (h->iskey || (!h->iscompr && h->size != 1)) break; |
| 1060 | } |
| 1061 | if (child) { |
| 1062 | debugf("Unlinking child %p from parent %p\n", |
| 1063 | (void*)child, (void*)h); |
| 1064 | raxNode *new = raxRemoveChild(h,child); |
| 1065 | if (new != h) { |
| 1066 | raxNode *parent = raxStackPeek(&ts); |
| 1067 | raxNode **parentlink; |
| 1068 | if (parent == NULL) { |
| 1069 | parentlink = &rax->head; |
| 1070 | } else { |
| 1071 | parentlink = raxFindParentLink(parent,h); |
| 1072 | } |
| 1073 | memcpy(parentlink,&new,sizeof(new)); |
| 1074 | } |
| 1075 | |
| 1076 | /* If after the removal the node has just a single child |
| 1077 | * and is not a key, we need to try to compress it. */ |
| 1078 | if (new->size == 1 && new->iskey == 0) { |
| 1079 | trycompress = 1; |
no test coverage detected