dict.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include "post.h"
   5
   6 #define DHASH(d, s)     ((unsigned char) (s)[0])
   7 #define CNTMIN          (1 << 10)
   8
   9 struct dict {
  10         struct iset *map;
  11         char **key;
  12         int *val;
  13         int size;
  14         int n;
  15         int notfound;           /* the value returned for missing keys */
  16         int dupkeys;            /* duplicate keys if set */
  17 };
  18
  19 static void dict_extend(struct dict *d, int size)
  20 {
  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;
  24 }
  25
  26 struct dict *dict_make(int notfound, int dupkeys)
  27 {
  28         struct dict *d = xmalloc(sizeof(*d));
  29         memset(d, 0, sizeof(*d));
  30         d->n = 1;
  31         d->dupkeys = dupkeys;
  32         d->notfound = notfound;
  33         d->map = iset_make();
  34         dict_extend(d, CNTMIN);
  35         return d;
  36 }
  37
  38 void dict_free(struct dict *d)
  39 {
  40         int i;
  41         if (d->dupkeys)
  42                 for (i = 0; i < d->size; i++)
  43                         free(d->key[i]);
  44         free(d->val);
  45         free(d->key);
  46         iset_free(d->map);
  47         free(d);
  48 }
  49
  50 void dict_put(struct dict *d, char *key, int val)
  51 {
  52         int idx;
  53         if (d->n >= d->size)
  54                 dict_extend(d, d->n + CNTMIN);
  55         if (d->dupkeys) {
  56                 int len = strlen(key) + 1;
  57                 char *dup = xmalloc(len);
  58                 memcpy(dup, key, len);
  59                 key = dup;
  60         }
  61         idx = d->n++;
  62         d->key[idx] = key;
  63         d->val[idx] = val;
  64         iset_put(d->map, DHASH(d, key), idx);
  65 }
  66
  67 /* return the index of key in d */
  68 int dict_idx(struct dict *d, char *key)
  69 {
  70         int h = DHASH(d, key);
  71         int *b = iset_get(d->map, h);
  72         int *r = b + iset_len(d->map, h);
  73         while (b && --r >= b)
  74                 if (!strcmp(d->key[*r], key))
  75                         return *r;
  76         return -1;
  77 }
  78
  79 char *dict_key(struct dict *d, int idx)
  80 {
  81         return d->key[idx];
  82 }
  83
  84 int dict_val(struct dict *d, int idx)
  85 {
  86         return d->val[idx];
  87 }
  88
  89 int dict_get(struct dict *d, char *key)
  90 {
  91         int idx = dict_idx(d, key);
  92         return idx >= 0 ? d->val[idx] : d->notfound;
  93 }
  94
  95 /* match a prefix of key; in the first call, *idx should be -1 */
  96 int dict_prefix(struct dict *d, char *key, int *pos)
  97 {
  98         int *r = iset_get(d->map, DHASH(d, key));
  99         while (r && r[++*pos] >= 0) {
 100                 int idx = r[*pos];
 101                 int plen = strlen(d->key[idx]);
 102                 if (!strncmp(d->key[idx], key, plen))
 103                         return d->val[idx];
 104         }
 105         return d->notfound;
 106 }