Skip to content

Instantly share code, notes, and snippets.

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

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);
return NULL;
node = &node->sub[(unsigned char)*p];
} while(*p++);
node->str = strdup(s);
return node->str;
main(int argc, char **argv)
int i;
const char *s;
for(i = 1; i < argc; i++) {
s = intern(argv[i]);
if(!s) {
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.