Insert the element 's' of size 'len', setting as auxiliary data * the pointer 'data'. If the element is already present, the associated * data is updated (only if 'overwrite' is set to 1), and 0 is returned, * otherwise the element is inserted and 1 is returned. On out of memory the * function returns 0 as well but sets errno to ENOMEM, otherwise errno will * be set to 0. */
| 507 | * be set to 0. |
| 508 | */ |
| 509 | int raxGenericInsert(rax *rax, unsigned char *s, size_t len, void *data, void **old, int overwrite) { |
| 510 | size_t i; |
| 511 | int j = 0; /* Split position. If raxLowWalk() stops in a compressed |
| 512 | node, the index 'j' represents the char we stopped within the |
| 513 | compressed node, that is, the position where to split the |
| 514 | node for insertion. */ |
| 515 | raxNode *h, **parentlink; |
| 516 | |
| 517 | debugf("### Insert %.*s with value %p\n", (int)len, s, data); |
| 518 | i = raxLowWalk(rax,s,len,&h,&parentlink,&j,NULL); |
| 519 | |
| 520 | /* If i == len we walked following the whole string. If we are not |
| 521 | * in the middle of a compressed node, the string is either already |
| 522 | * inserted or this middle node is currently not a key, but can represent |
| 523 | * our key. We have just to reallocate the node and make space for the |
| 524 | * data pointer. */ |
| 525 | if (i == len && (!h->iscompr || j == 0 /* not in the middle if j is 0 */)) { |
| 526 | debugf("### Insert: node representing key exists\n"); |
| 527 | /* Make space for the value pointer if needed. */ |
| 528 | if (!h->iskey || (h->isnull && overwrite)) { |
| 529 | h = raxReallocForData(h,data); |
| 530 | if (h) memcpy(parentlink,&h,sizeof(h)); |
| 531 | } |
| 532 | if (h == NULL) { |
| 533 | errno = ENOMEM; |
| 534 | return 0; |
| 535 | } |
| 536 | |
| 537 | /* Update the existing key if there is already one. */ |
| 538 | if (h->iskey) { |
| 539 | if (old) *old = raxGetData(h); |
| 540 | if (overwrite) raxSetData(h,data); |
| 541 | errno = 0; |
| 542 | return 0; /* Element already exists. */ |
| 543 | } |
| 544 | |
| 545 | /* Otherwise set the node as a key. Note that raxSetData() |
| 546 | * will set h->iskey. */ |
| 547 | raxSetData(h,data); |
| 548 | rax->numele++; |
| 549 | return 1; /* Element inserted. */ |
| 550 | } |
| 551 | |
| 552 | /* If the node we stopped at is a compressed node, we need to |
| 553 | * split it before to continue. |
| 554 | * |
| 555 | * Splitting a compressed node have a few possible cases. |
| 556 | * Imagine that the node 'h' we are currently at is a compressed |
| 557 | * node containing the string "ANNIBALE" (it means that it represents |
| 558 | * nodes A -> N -> N -> I -> B -> A -> L -> E with the only child |
| 559 | * pointer of this node pointing at the 'E' node, because remember that |
| 560 | * we have characters at the edges of the graph, not inside the nodes |
| 561 | * themselves. |
| 562 | * |
| 563 | * In order to show a real case imagine our node to also point to |
| 564 | * another compressed node, that finally points at the node without |
| 565 | * children, representing 'O': |
| 566 | * |
no test coverage detected