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 ? (((unsigned char) (s)[1]) << 8) | (unsigned char) (s)[0] : (unsigned char) s[0])
   7
   8 /*
   9  * initialise a dictionary
  10  *
  11  * notfound: the value returned for missing keys.
  12  * dupkeys: if nonzero, store a copy of keys inserted via dict_put().
  13  * level2: use two characters for hasing
  14  */
  15 void dict_init(struct dict *d, int size, long notfound, int dupkeys, int level2)
  16 {
  17         int headsize = (level2 ? 256 * 256 : 256) * sizeof(d->head[0]);
  18         memset(d, 0, sizeof(*d));
  19         d->size = size;
  20         d->n = 1;
  21         d->level2 = level2;
  22         d->notfound = notfound;
  23         d->key = xmalloc(size * sizeof(d->key[0]));
  24         d->val = xmalloc(size * sizeof(d->val[0]));
  25         d->next = xmalloc(size * sizeof(d->next[0]));
  26         d->head = xmalloc(headsize);
  27         memset(d->head, 0, headsize);
  28         if (dupkeys)
  29                 d->buf = xmalloc(size * NMLEN);
  30 }
  31
  32 void dict_done(struct dict *d)
  33 {
  34         free(d->val);
  35         free(d->key);
  36         free(d->next);
  37         free(d->buf);
  38         free(d->head);
  39 }
  40
  41 void dict_put(struct dict *d, char *key, long val)
  42 {
  43         int idx;
  44         if (d->n >= d->size)
  45                 return;
  46         if (d->buf) {
  47                 int len = strlen(key) + 1;
  48                 if (d->buflen + len >= d->size * NMLEN)
  49                         return;
  50                 memcpy(d->buf + d->buflen, key, len);
  51                 key = d->buf + d->buflen;
  52                 d->buflen += len;
  53         }
  54         idx = d->n++;
  55         d->key[idx] = key;
  56         d->val[idx] = val;
  57         d->next[idx] = d->head[DHASH(d, key)];
  58         d->head[DHASH(d, key)] = idx;
  59 }
  60
  61 /* return the index of key in d */
  62 int dict_idx(struct dict *d, char *key)
  63 {
  64         int idx = d->head[DHASH(d, key)];
  65         while (idx > 0) {
  66                 if (!strcmp(d->key[idx], key))
  67                         return idx;
  68                 idx = d->next[idx];
  69         }
  70         return -1;
  71 }
  72
  73 char *dict_key(struct dict *d, int idx)
  74 {
  75         return d->key[idx];
  76 }
  77
  78 long dict_val(struct dict *d, int idx)
  79 {
  80         return d->val[idx];
  81 }
  82
  83 long dict_get(struct dict *d, char *key)
  84 {
  85         int idx = dict_idx(d, key);
  86         return idx >= 0 ? d->val[idx] : d->notfound;
  87 }
  88
  89 /* match a prefix of key; in the first call, *idx should be -1 */
  90 long dict_prefix(struct dict *d, char *key, int *idx)
  91 {
  92         int plen;
  93         if (!*idx)
  94                 return d->notfound;
  95         if (*idx < 0)
  96                 *idx = d->head[DHASH(d, key)];
  97         else
  98                 *idx = d->next[*idx];
  99         while (*idx > 0) {
 100                 plen = strlen(d->key[*idx]);
 101                 if (!strncmp(d->key[*idx], key, plen))
 102                         return d->val[*idx];
 103                 *idx = d->next[*idx];
 104         }
 105         return d->notfound;
 106 }