ベンチとかはやってない。
404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン?
そのデータ構造は、君の魂を差し出すに足るものかい? 連想配列( Associative array )がコレクション( Collection )、すなわち数多のデータ構造をまとめるデータ構造としての覇...
http://blog.livedoor.jp/dankogai/archives/51765855.html
#include <stdio.h>
#include <stdlib.h>
typedef struct _trie {
char c;
unsigned int n;
struct _trie** next;
void* value;
} trie;
trie*
trie_new() {
trie* p = (trie*) malloc(sizeof(trie));
p->c = 0;
p->n = 0;
p->next = NULL;
return p;
}
void
trie_free(trie* p) {
unsigned int i;
for (i = 0; i < p->n; i++)
trie_free(p->next[i]);
if (p->n)
free(p->next);
free(p);
}
trie*
trie_put(trie* p, const char* key, const void* value) {
if (*key == 0) {
p->value = (void*) value;
return p;
}
trie* next = NULL;
int i;
for (i = 0; i < p->n; i++)
if (p->next[i]->c == *key) {
next = p;
break;
}
if (!next) {
if (!(next = trie_new())) return NULL;
trie** children = (trie**) realloc(p->next, p->n * sizeof(trie*));
if (!children) return NULL;
p->next = children;
next->c = *key;
p->next[p->n] = next;
p->n++;
}
return trie_put(next, key+1, value);
}
trie*
trie_get(trie* p, const char* key) {
if (p->c) {
if (p->c != *key)
return NULL;
if (p->c == *key && *(key+1) == 0)
return p;
key++;
}
int i;
trie* value = NULL;
for (i = 0; i < p->n; i++) {
if ((value = trie_get(p->next[i], key)))
return value;
}
return NULL;
}
void
safe_puts(const char* key, const trie* p) {
if (!p)
printf("%s not found\n", key);
else if (!p->value)
printf("%s: null\n", key);
else
printf("%s: %s\n", key, (char*) p->value);
}
int
main(int argc, char* argv[]) {
trie* p = trie_new();
trie* v;
trie_put(p, "foo", "bar");
trie_put(p, "bar", "baz");
v = trie_get(p, "baz");
safe_puts("baz", v);
v = trie_get(p, "foo");
safe_puts("foo", v);
v = trie_get(p, "bar");
safe_puts("bar", v);
trie_put(p, "うんこ", "うんこっこー");
v = trie_get(p, "うんこ");
safe_puts("うんこ", v);
v = trie_get(p, "404 blog");
safe_puts("404 blog", v);
trie_free(p);
return 0;
}
baz not found
foo: bar
bar: baz
うんこ: うんこっこー
404 blog not found
