trie 树 的代码
程序员文章站
2022-06-03 18:09:57
...
想起搜狐老大的一句话
看代码先看h文件,擦,当初感觉他这句话很2,现在想想,诶。
代码摘自
shellinabox
看代码先看h文件,擦,当初感觉他这句话很2,现在想想,诶。
代码摘自
shellinabox
// trie.h -- Basic implementation of a trie abstract data type #ifndef TRIE_H__ #define TRIE_H__ #include "libhttp/http.h" struct Trie { void (*destructor)(void *, char *); void *arg; char *key; char *value; int idx; char ch; struct Trie *children; int numChildren; }; struct Trie *newTrie(void (*destructor)(void *, char *), void *arg); void initTrie(struct Trie *trie, void (*destructor)(void *, char *), void *arg); void destroyTrie(struct Trie *trie); void deleteTrie(struct Trie *trie); void addToTrie(struct Trie *trie, const char *key, char *value); char *getFromTrie(const struct Trie *trie, const char *key, char **diff); #endif /* TRIE_H__ */
// trie.c -- Basic implementation of a trie abstract data type #include "config.h" #include <stdlib.h> #include <string.h> #include "libhttp/trie.h" #include "logging/logging.h" struct Trie *newTrie(void (*destructor)(void *, char *), void *arg) { struct Trie *trie; check(trie = malloc(sizeof(struct Trie))); initTrie(trie, destructor, arg); return trie; } void initTrie(struct Trie *trie, void (*destructor)(void *, char *), void *arg) { trie->destructor = destructor; trie->arg = arg; trie->key = NULL; trie->value = NULL; trie->idx = -1; trie->ch = '\000'; trie->children = NULL; trie->numChildren = 0; } void destroyTrie(struct Trie *trie) { if (trie) { free(trie->key); for (int i = 0; i < trie->numChildren; i++) { if (trie->destructor && !trie->children[i].ch) { trie->destructor(trie->arg, trie->children[i].value); } else { check(!trie->children[i].value); } destroyTrie(&trie->children[i]); } free(trie->children); } } void deleteTrie(struct Trie *trie) { destroyTrie(trie); free(trie); } static void addLeafToTrie(struct Trie *trie, char ch, const char *key, int len, void *value) { check (len >= 0); if (len) { check(trie->key = malloc(len)); memcpy(trie->key, key, len); } else { trie->key = NULL; } trie->value = NULL; trie->idx = len; trie->ch = ch; check(trie->children = malloc(sizeof(struct Trie))); trie->numChildren = 1; initTrie(trie->children, trie->destructor, trie->arg); trie->children->value = value; } void addToTrie(struct Trie *trie, const char *key, char *value) { if (trie->numChildren == 0) { addLeafToTrie(trie, '\000', key, strlen(key), value); } else { nextNode:; int len = strlen(key); for (int i = 0; i < trie->idx; i++) { if (key[i] != trie->key[i]) { struct Trie *child; check(child = malloc(2*sizeof(struct Trie))); child->destructor = trie->destructor; child->arg = trie->arg; check(child->key = malloc(trie->idx - i - 1)); memcpy(child->key, trie->key + i + 1, trie->idx - i - 1); child->value = trie->value; child->idx = trie->idx - i - 1; child->ch = trie->key[i]; child->children = trie->children; child->numChildren = trie->numChildren; trie->value = NULL; trie->idx = i; trie->children = child; trie->numChildren = 2; child++; child->destructor = trie->destructor; child->arg = trie->arg; if (key[i]) { addLeafToTrie(child, key[i], key + i + 1, len - i - 1, value); } else { initTrie(child, trie->destructor, trie->arg); child->value = value; } return; } } for (int i = 0; i < trie->numChildren; i++) { if (key[trie->idx] == trie->children[i].ch) { if (trie->children[i].ch) { key += trie->idx + 1; trie = &trie->children[i]; goto nextNode; } else { if (trie->destructor) { trie->destructor(trie->arg, trie->children[i].value); } trie->children[i].value = value; return; } } } key += trie->idx; len -= trie->idx; check(trie->children = realloc( trie->children, ++trie->numChildren*sizeof(struct Trie))); struct Trie *newNode = &trie->children[trie->numChildren-1]; if (*key) { newNode->destructor = trie->destructor; newNode->arg = trie->arg; addLeafToTrie(newNode, *key, key + 1, len - 1, value); } else { initTrie(newNode, trie->destructor, trie->arg); newNode->value = value; } } } char *getFromTrie(const struct Trie *trie, const char *key, char **diff) { if (diff) { *diff = NULL; } struct Trie *partial = NULL; char *partialKey = NULL; for (;;) { if (trie->idx > 0) { if (memcmp(trie->key, key, trie->idx)) { if (diff && partial != NULL) { *diff = partialKey; return partial->value; } return NULL; } key += trie->idx; } for (int i = 0; ; i++) { if (i >= trie->numChildren) { if (diff && partial != NULL) { // If the caller provided a "diff" pointer, then we allow partial // matches for the longest possible prefix that is a key in the // trie. Upon return, the "diff" pointer points to the first // character in the key does not match. *diff = partialKey; return partial->value; } return NULL; } else if (*key == trie->children[i].ch) { if (!*key) { if (diff) { *diff = (char *)key; } return trie->children[i].value; } for (int j = i + 1; j < trie->numChildren; j++) { if (!trie->children[j].ch) { partial = trie->children + j; partialKey = (char *)key; break; } } trie = &trie->children[i]; key++; break; } else if (!trie->children[i].ch) { partial = trie->children + i; partialKey = (char *)key; } } } }
上一篇: 萝卜腿
下一篇: 出轨的事归铁路局长管