dict.c

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