-static int add_new_string(struct udev_rules *rules, const char *str, size_t bytes)
-{
- int off;
-
- /* grow buffer if needed */
- if (rules->buf_cur + bytes+1 >= rules->buf_max) {
- char *buf;
- unsigned int add;
-
- /* double the buffer size */
- add = rules->buf_max;
- if (add < bytes * 8)
- add = bytes * 8;
-
- buf = realloc(rules->buf, rules->buf_max + add);
- if (buf == NULL)
- return -1;
- rules->buf = buf;
- rules->buf_max += add;
- }
- off = rules->buf_cur;
- memcpy(&rules->buf[rules->buf_cur], str, bytes);
- rules->buf_cur += bytes;
- rules->buf_count++;
- return off;
-}
-
-static int add_string(struct udev_rules *rules, const char *str)
-{
- unsigned int node_idx;
- struct trie_node *new_node;
- unsigned int new_node_idx;
- unsigned char key;
- unsigned short len;
- unsigned int depth;
- unsigned int off;
- struct trie_node *parent;
-
- /* walk trie, start from last character of str to find matching tails */
- len = strlen(str);
- key = str[len-1];
- node_idx = 0;
- for (depth = 0; depth <= len; depth++) {
- struct trie_node *node;
- unsigned int child_idx;
-
- node = &rules->trie_nodes[node_idx];
- off = node->value_off + node->value_len - len;
-
- /* match against current node */
- if (depth == len || (node->value_len >= len && memcmp(&rules->buf[off], str, len) == 0))
- return off;
-
- /* lookup child node */
- key = str[len - 1 - depth];
- child_idx = node->child_idx;
- while (child_idx > 0) {
- struct trie_node *child;
-
- child = &rules->trie_nodes[child_idx];
- if (child->key == key)
- break;
- child_idx = child->next_child_idx;
- }
- if (child_idx == 0)
- break;
- node_idx = child_idx;
- }
-
- /* string not found, add it */
- off = add_new_string(rules, str, len + 1);
-
- /* grow trie nodes if needed */
- if (rules->trie_nodes_cur >= rules->trie_nodes_max) {
- struct trie_node *nodes;
- unsigned int add;
-
- /* double the buffer size */
- add = rules->trie_nodes_max;
- if (add < 8)
- add = 8;
-
- nodes = realloc(rules->trie_nodes, (rules->trie_nodes_max + add) * sizeof(struct trie_node));
- if (nodes == NULL)
- return -1;
- rules->trie_nodes = nodes;
- rules->trie_nodes_max += add;
- }
-
- /* get a new node */
- new_node_idx = rules->trie_nodes_cur;
- rules->trie_nodes_cur++;
- new_node = &rules->trie_nodes[new_node_idx];
- memset(new_node, 0x00, sizeof(struct trie_node));
- new_node->value_off = off;
- new_node->value_len = len;
- new_node->key = key;
-
- /* join the parent's child list */
- parent = &rules->trie_nodes[node_idx];
- if (parent->child_idx == 0) {
- parent->child_idx = new_node_idx;
- } else {
- struct trie_node *last_child;
-
- last_child = &rules->trie_nodes[parent->last_child_idx];
- last_child->next_child_idx = new_node_idx;
- }
- parent->last_child_idx = new_node_idx;
- return off;
-}
-