trie 树 的代码
想起搜狐老大的一句话看代码先看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.ch) { trie->destructor(trie->arg, trie->children.value); } else { check(!trie->children.value); } destroyTrie(&trie->children); } 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 != trie->key) { 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; 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) { addLeafToTrie(child, key, 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->children.ch) { if (trie->children.ch) { key += trie->idx + 1; trie = &trie->children; goto nextNode; } else { if (trie->destructor) { trie->destructor(trie->arg, trie->children.value); } trie->children.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; 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.ch) { if (!*key) { if (diff) { *diff = (char *)key; } return trie->children.value; } for (int j = i + 1; j < trie->numChildren; j++) { if (!trie->children.ch) { partial = trie->children + j; partialKey = (char *)key; break; } } trie = &trie->children; key++; break; } else if (!trie->children.ch) { partial = trie->children + i; partialKey = (char *)key; } }}}
页:
[1]