| 91 | } |
| 92 | |
| 93 | bool strset_add(struct strset *set, const char *member) |
| 94 | { |
| 95 | size_t len = strlen(member); |
| 96 | const u8 *bytes = (const u8 *)member; |
| 97 | struct strset *np; |
| 98 | const char *str; |
| 99 | struct node *newn; |
| 100 | size_t byte_num; |
| 101 | u8 bit_num, new_dir; |
| 102 | |
| 103 | /* Empty set? */ |
| 104 | if (!set->u.n) { |
| 105 | return set_string(set, set, member); |
| 106 | } |
| 107 | |
| 108 | /* Find closest existing member. */ |
| 109 | str = closest(*set, member); |
| 110 | |
| 111 | /* Find where they differ. */ |
| 112 | for (byte_num = 0; str[byte_num] == member[byte_num]; byte_num++) { |
| 113 | if (member[byte_num] == '\0') { |
| 114 | /* All identical! */ |
| 115 | errno = EEXIST; |
| 116 | return false; |
| 117 | } |
| 118 | } |
| 119 | |
| 120 | /* Find which bit differs (if we had ilog8, we'd use it) */ |
| 121 | bit_num = ilog32_nz((u8)str[byte_num] ^ bytes[byte_num]) - 1; |
| 122 | assert(bit_num < CHAR_BIT); |
| 123 | |
| 124 | /* Which direction do we go at this bit? */ |
| 125 | new_dir = ((bytes[byte_num]) >> bit_num) & 1; |
| 126 | |
| 127 | /* Allocate new node. */ |
| 128 | newn = malloc(sizeof(*newn)); |
| 129 | if (!newn) { |
| 130 | errno = ENOMEM; |
| 131 | return false; |
| 132 | } |
| 133 | newn->nul_byte = '\0'; |
| 134 | newn->byte_num = byte_num; |
| 135 | newn->bit_num = bit_num; |
| 136 | if (unlikely(!set_string(set, &newn->child[new_dir], member))) { |
| 137 | free(newn); |
| 138 | return false; |
| 139 | } |
| 140 | |
| 141 | /* Find where to insert: not closest, but first which differs! */ |
| 142 | np = set; |
| 143 | while (!np->u.s[0]) { |
| 144 | u8 direction = 0; |
| 145 | |
| 146 | /* Special node which represents the empty string will |
| 147 | * break here too! */ |
| 148 | if (np->u.n->byte_num > byte_num) |
| 149 | break; |
| 150 | /* Subtle: bit numbers are "backwards" for comparison */ |