| 58 | } |
| 59 | |
| 60 | bool strmap_add_(struct strmap *map, const char *member, const void *value) |
| 61 | { |
| 62 | size_t len = strlen(member); |
| 63 | const u8 *bytes = (const u8 *)member; |
| 64 | struct strmap *n; |
| 65 | struct node *newn; |
| 66 | size_t byte_num; |
| 67 | u8 bit_num, new_dir; |
| 68 | |
| 69 | assert(value); |
| 70 | |
| 71 | /* Empty map? */ |
| 72 | if (!map->u.n) { |
| 73 | map->u.s = member; |
| 74 | map->v = (void *)value; |
| 75 | return true; |
| 76 | } |
| 77 | |
| 78 | /* Find closest existing member. */ |
| 79 | n = closest(map, member, len); |
| 80 | |
| 81 | /* Find where they differ. */ |
| 82 | for (byte_num = 0; n->u.s[byte_num] == member[byte_num]; byte_num++) { |
| 83 | if (member[byte_num] == '\0') { |
| 84 | /* All identical! */ |
| 85 | errno = EEXIST; |
| 86 | return false; |
| 87 | } |
| 88 | } |
| 89 | |
| 90 | /* Find which bit differs (if we had ilog8, we'd use it) */ |
| 91 | bit_num = ilog32_nz((u8)n->u.s[byte_num] ^ bytes[byte_num]) - 1; |
| 92 | assert(bit_num < CHAR_BIT); |
| 93 | |
| 94 | /* Which direction do we go at this bit? */ |
| 95 | new_dir = ((bytes[byte_num]) >> bit_num) & 1; |
| 96 | |
| 97 | /* Allocate new node. */ |
| 98 | newn = malloc(sizeof(*newn)); |
| 99 | if (!newn) { |
| 100 | errno = ENOMEM; |
| 101 | return false; |
| 102 | } |
| 103 | newn->byte_num = byte_num; |
| 104 | newn->bit_num = bit_num; |
| 105 | newn->child[new_dir].v = (void *)value; |
| 106 | newn->child[new_dir].u.s = member; |
| 107 | |
| 108 | /* Find where to insert: not closest, but first which differs! */ |
| 109 | n = map; |
| 110 | while (!n->v) { |
| 111 | u8 direction = 0; |
| 112 | |
| 113 | if (n->u.n->byte_num > byte_num) |
| 114 | break; |
| 115 | /* Subtle: bit numbers are "backwards" for comparison */ |
| 116 | if (n->u.n->byte_num == byte_num && n->u.n->bit_num < bit_num) |
| 117 | break; |