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