Turn the node 'n', that must be a node without any children, into a * compressed node representing a set of nodes linked one after the other * and having exactly one child each. The node can be a key or not: this * property and the associated value if any will be preserved. * * The function also returns a child node, since the last node of the * compressed chain cannot be part of the chain:
| 395 | * compressed chain cannot be part of the chain: it has zero children while |
| 396 | * we can only compress inner nodes with exactly one child each. */ |
| 397 | raxNode *raxCompressNode(raxNode *n, unsigned char *s, size_t len, raxNode **child) { |
| 398 | assert(n->size == 0 && n->iscompr == 0); |
| 399 | void *data = NULL; /* Initialized only to avoid warnings. */ |
| 400 | size_t newsize; |
| 401 | |
| 402 | debugf("Compress node: %.*s\n", (int)len,s); |
| 403 | |
| 404 | /* Allocate the child to link to this node. */ |
| 405 | *child = raxNewNode(0,0); |
| 406 | if (*child == NULL) return NULL; |
| 407 | |
| 408 | /* Make space in the parent node. */ |
| 409 | newsize = sizeof(raxNode)+len+raxPadding(len)+sizeof(raxNode*); |
| 410 | if (n->iskey) { |
| 411 | data = raxGetData(n); /* To restore it later. */ |
| 412 | if (!n->isnull) newsize += sizeof(void*); |
| 413 | } |
| 414 | raxNode *newn = rax_realloc(n,newsize); |
| 415 | if (newn == NULL) { |
| 416 | rax_free(*child); |
| 417 | return NULL; |
| 418 | } |
| 419 | n = newn; |
| 420 | |
| 421 | n->iscompr = 1; |
| 422 | n->size = len; |
| 423 | memcpy(n->data,s,len); |
| 424 | if (n->iskey) raxSetData(n,data); |
| 425 | raxNode **childfield = raxNodeLastChildPtr(n); |
| 426 | memcpy(childfield,child,sizeof(*child)); |
| 427 | return n; |
| 428 | } |
| 429 | |
| 430 | /* Low level function that walks the tree looking for the string |
| 431 | * 's' of 'len' bytes. The function returns the number of characters |
no test coverage detected