Skip to content

Instantly share code, notes, and snippets.

@cls cls/intern.c
Last active Aug 29, 2015

Embed
What would you like to do?
Interning strings with a prefix tree
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const char *
intern(const char *s)
{
union tree {
const char *str;
union tree *sub;
};
static union tree root;
union tree *node = &root;
const char *p = s;
do {
if(!node->sub) {
node->sub = calloc(1 << CHAR_BIT, sizeof *node->sub);
if(!node->sub)
return NULL;
}
node = &node->sub[(unsigned char)*p];
} while(*p++);
if(!node->str)
node->str = strdup(s);
return node->str;
}
int
main(int argc, char **argv)
{
int i;
const char *s;
for(i = 1; i < argc; i++) {
s = intern(argv[i]);
if(!s) {
perror(argv[0]);
return 1;
}
printf("%p: %s\n", (void *)s, s);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.