dict.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include "post.h"
   5
   6 #define CNTMIN          (1 << 10)
   7
   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 */
  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 /*
  27  * initialise a dictionary
  28  *
  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
  32  */
  33 struct dict *dict_make(int notfound, int dupkeys, int hashlen)
  34 {
  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;
  44 }
  45
  46 void dict_free(struct dict *d)
  47 {
  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);
  56 }
  57
  58 static int dict_hash(struct dict *d, char *key)
  59 {
  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;
  65 }
  66
  67 void dict_put(struct dict *d, char *key, int val)
  68 {
  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;
  77         }
  78         idx = d->n++;
  79         d->key[idx] = key;
  80         d->val[idx] = val;
  81         iset_put(d->map, dict_hash(d, key), idx);
  82 }
  83
  84 /* return the index of key in d */
  85 int dict_idx(struct dict *d, char *key)
  86 {
  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;
  94 }
  95
  96 char *dict_key(struct dict *d, int idx)
  97 {
  98         return d->key[idx];
  99 }
 100
 101 int dict_val(struct dict *d, int idx)
 102 {
 103         return d->val[idx];
 104 }
 105
 106 int dict_get(struct dict *d, char *key)
 107 {
 108         int idx = dict_idx(d, key);
 109         return idx >= 0 ? d->val[idx] : d->notfound;
 110 }
 111
 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)
 114 {
 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];
 121         }
 122         return d->notfound;
 123 }