pdf: add splines
[neatpost.git] / dict.c
blob49d2134d6ae7d8b8a8deb2dbe134ff80acd77d57
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include "post.h"
6 #define CNTMIN (1 << 10)
8 struct dict {
9 struct iset *map;
10 char **key;
11 int *val;
12 int size;
13 int n;
14 int notfound; /* the value returned for missing keys */
15 int hashlen; /* the number of characters used for hashing */
16 int dupkeys; /* duplicate keys if set */
19 static void dict_extend(struct dict *d, int size)
21 d->key = mextend(d->key, d->size, size, sizeof(d->key[0]));
22 d->val = mextend(d->val, d->size, size, sizeof(d->val[0]));
23 d->size = size;
27 * initialise a dictionary
29 * notfound: the value returned for missing keys.
30 * dupkeys: if nonzero, store a copy of keys inserted via dict_put().
31 * hashlen: the number of characters used for hashing
33 struct dict *dict_make(int notfound, int dupkeys, int hashlen)
35 struct dict *d = malloc(sizeof(*d));
36 memset(d, 0, sizeof(*d));
37 d->n = 1;
38 d->hashlen = hashlen ? hashlen : 32;
39 d->dupkeys = dupkeys;
40 d->notfound = notfound;
41 d->map = iset_make();
42 dict_extend(d, CNTMIN);
43 return d;
46 void dict_free(struct dict *d)
48 int i;
49 if (d->dupkeys)
50 for (i = 0; i < d->size; i++)
51 free(d->key[i]);
52 free(d->val);
53 free(d->key);
54 iset_free(d->map);
55 free(d);
58 static int dict_hash(struct dict *d, char *key)
60 unsigned long hash = (unsigned char) *key++;
61 int i = d->hashlen;
62 while (--i > 0 && *key)
63 hash = (hash << 5) + hash + (unsigned char) *key++;
64 return hash & 0x3ff;
67 void dict_put(struct dict *d, char *key, int val)
69 int idx;
70 if (d->n >= d->size)
71 dict_extend(d, d->n + CNTMIN);
72 if (d->dupkeys) {
73 int len = strlen(key) + 1;
74 char *dup = malloc(len);
75 memcpy(dup, key, len);
76 key = dup;
78 idx = d->n++;
79 d->key[idx] = key;
80 d->val[idx] = val;
81 iset_put(d->map, dict_hash(d, key), idx);
84 /* return the index of key in d */
85 int dict_idx(struct dict *d, char *key)
87 int h = dict_hash(d, key);
88 int *b = iset_get(d->map, h);
89 int *r = b + iset_len(d->map, h);
90 while (b && --r >= b)
91 if (!strcmp(d->key[*r], key))
92 return *r;
93 return -1;
96 char *dict_key(struct dict *d, int idx)
98 return d->key[idx];
101 int dict_val(struct dict *d, int idx)
103 return d->val[idx];
106 int dict_get(struct dict *d, char *key)
108 int idx = dict_idx(d, key);
109 return idx >= 0 ? d->val[idx] : d->notfound;
112 /* match a prefix of key; in the first call, *idx should be -1 */
113 int dict_prefix(struct dict *d, char *key, int *pos)
115 int *r = iset_get(d->map, dict_hash(d, key));
116 while (r && r[++*pos] >= 0) {
117 int idx = r[*pos];
118 int plen = strlen(d->key[idx]);
119 if (!strncmp(d->key[idx], key, plen))
120 return d->val[idx];
122 return d->notfound;