Low level child removal from node. The new node pointer (after the child * removal) is returned. Note that this function does not fix the pointer * of the parent node in its parent, so this task is up to the caller. * The function never fails for out of memory. */
| 947 | * of the parent node in its parent, so this task is up to the caller. |
| 948 | * The function never fails for out of memory. */ |
| 949 | raxNode *raxRemoveChild(raxNode *parent, raxNode *child) { |
| 950 | debugnode("raxRemoveChild before", parent); |
| 951 | /* If parent is a compressed node (having a single child, as for definition |
| 952 | * of the data structure), the removal of the child consists into turning |
| 953 | * it into a normal node without children. */ |
| 954 | if (parent->iscompr) { |
| 955 | void *data = NULL; |
| 956 | if (parent->iskey) data = raxGetData(parent); |
| 957 | parent->isnull = 0; |
| 958 | parent->iscompr = 0; |
| 959 | parent->size = 0; |
| 960 | if (parent->iskey) raxSetData(parent,data); |
| 961 | debugnode("raxRemoveChild after", parent); |
| 962 | return parent; |
| 963 | } |
| 964 | |
| 965 | /* Otherwise we need to scan for the child pointer and memmove() |
| 966 | * accordingly. |
| 967 | * |
| 968 | * 1. To start we seek the first element in both the children |
| 969 | * pointers and edge bytes in the node. */ |
| 970 | raxNode **cp = raxNodeFirstChildPtr(parent); |
| 971 | raxNode **c = cp; |
| 972 | unsigned char *e = parent->data; |
| 973 | |
| 974 | /* 2. Search the child pointer to remove inside the array of children |
| 975 | * pointers. */ |
| 976 | while(1) { |
| 977 | raxNode *aux; |
| 978 | memcpy(&aux,c,sizeof(aux)); |
| 979 | if (aux == child) break; |
| 980 | c++; |
| 981 | e++; |
| 982 | } |
| 983 | |
| 984 | /* 3. Remove the edge and the pointer by memmoving the remaining children |
| 985 | * pointer and edge bytes one position before. */ |
| 986 | int taillen = parent->size - (e - parent->data) - 1; |
| 987 | debugf("raxRemoveChild tail len: %d\n", taillen); |
| 988 | memmove(e,e+1,taillen); |
| 989 | |
| 990 | /* Compute the shift, that is the amount of bytes we should move our |
| 991 | * child pointers to the left, since the removal of one edge character |
| 992 | * and the corresponding padding change, may change the layout. |
| 993 | * We just check if in the old version of the node there was at the |
| 994 | * end just a single byte and all padding: in that case removing one char |
| 995 | * will remove a whole sizeof(void*) word. */ |
| 996 | size_t shift = ((parent->size+4) % sizeof(void*)) == 1 ? sizeof(void*) : 0; |
| 997 | |
| 998 | /* Move the children pointers before the deletion point. */ |
| 999 | if (shift) |
| 1000 | memmove(((char*)cp)-shift,cp,(parent->size-taillen-1)*sizeof(raxNode**)); |
| 1001 | |
| 1002 | /* Move the remaining "tail" pointers at the right position as well. */ |
| 1003 | size_t valuelen = (parent->iskey && !parent->isnull) ? sizeof(void*) : 0; |
| 1004 | memmove(((char*)c)-shift,c+1,taillen*sizeof(raxNode**)+valuelen); |
| 1005 | |
| 1006 | /* 4. Update size. */ |
no test coverage detected