liamoc.net
the hito embeddable programming language
1#include "intern.h"
2#include "util.h"
3#include <stdlib.h>
4#include <string.h>
5#include <stdint.h>
6
7
8#define INITIAL_CAPACITY 1024
9
10typedef struct intern_entry intern_entry_t;
11struct intern_entry {
12 const char *str;
13 intern_entry_t *next;
14};
15
16struct intern_table {
17 size_t capacity;
18 intern_entry_t **buckets;
19};
20
21intern_table_t *intern_table_alloc(void) {
22 intern_table_t *table = malloc(sizeof(struct intern_table));
23 if (table == NULL)
24 die("Out of memory: cannot allocate intern table.");
25
26 table->capacity = INITIAL_CAPACITY;
27 table->buckets = calloc(table->capacity, sizeof(intern_entry_t *));
28 if (table->buckets == NULL)
29 die("Out of memory: cannot allocate intern table buckets.");
30
31 return table;
32}
33
34void intern_table_free(intern_table_t *table) {
35 for (size_t i = 0; i < table->capacity; i++) {
36 intern_entry_t *entry = table->buckets[i];
37 while (entry != NULL) {
38 intern_entry_t *next = entry->next;
39 free((char *)entry->str);
40 free(entry);
41 entry = next;
42 }
43 }
44 free(table->buckets);
45 free(table);
46}
47
48
49intern_t intern(intern_table_t *table, const char *str) {
50 return intern_prefix(table, str, strlen(str));
51}
52
53intern_t intern_prefix(intern_table_t *table, const char *str, size_t len) {
54 uint32_t h = hash_buffer(str, len);
55 size_t index = h % table->capacity;
56 for (intern_entry_t *entry = table->buckets[index]; entry != NULL; entry = entry->next)
57 if (strncmp(entry->str, str, len) == 0)
58 return entry->str;
59
60 char *copy = malloc(len + 1);
61 if (copy == NULL)
62 die("Out of memory: cannot allocate interned string");
63
64 strncpy(copy, str, len);
65 copy[len] = '\0';
66 intern_entry_t *new_entry = malloc(sizeof(intern_entry_t));
67 if (new_entry == NULL)
68 die("Out of memory: cannot allocate intern table entry");
69
70 new_entry->str = copy;
71 new_entry->next = table->buckets[index];
72 table->buckets[index] = new_entry;
73 return copy;
74}
75
76const char * intern_exists(intern_table_t *table, const char *str) {
77 uint32_t h = hash_string(str);
78 size_t index = h % table->capacity;
79 for (intern_entry_t *entry = table->buckets[index];
80 entry != NULL;
81 entry = entry->next) if (strcmp(entry->str, str) == 0)
82 return entry->str;
83 return NULL;
84}