git.ozlabs.org Git - ccan/blob - ccan/ccan_tokenizer/dict.c

   1 #include "dict.h"
   2 #include <string.h>
   3 #include <stdlib.h>
   4 #include <assert.h>
   5
   6 //compare dict_entries by first letter ascending, then by length descending
   7 static int compar_dict_entry(const void *ap, const void *bp) {
   8         const struct dict_entry *a=ap, *b=bp;
   9         unsigned int first_a = (unsigned int)a->str[0];
  10         unsigned int first_b = (unsigned int)b->str[0];
  11         if (first_a < first_b)
  12                 return -1;
  13         else if (first_a > first_b)
  14                 return 1;
  15         else {
  16                 size_t len_a = strlen(a->str);
  17                 size_t len_b = strlen(b->str);
  18                 if (len_a > len_b)
  19                         return -1;
  20                 else if (len_a < len_b)
  21                         return 1;
  22                 else
  23                         return 0;
  24         }
  25 }
  26
  27 struct dict *dict_build(void *ctx, const struct dict_entry *entries, size_t count) {
  28         struct dict *dict = talloc_zero(ctx, struct dict);
  29         struct dict_entry *ent;
  30         int i;
  31
  32         if (!count)
  33                 return dict;
  34
  35         ent = talloc_array(dict, struct dict_entry, count);
  36         memcpy(ent, entries, count*sizeof(struct dict_entry));
  37         qsort(ent, count, sizeof(*ent), compar_dict_entry);
  38
  39         if (ent->str[0]==0) {
  40                 dict->zero = ent;
  41                 ent++, count--;
  42
  43                 if (count && ent->str[0]==0) {
  44                         fprintf(stderr, "dict_entry array contains multiple empty strings\n");
  45                         exit(EXIT_FAILURE);
  46                 }
  47         }
  48
  49         for (i=1; i<256; i++) {
  50                 if (!count)
  51                         break;
  52                 if (ent->str[0] == (char)i)
  53                         dict->by_first_letter[i-1] = ent;
  54                 while (count && ent->str[0] == (char)i)
  55                         ent++, count--;
  56         }
  57
  58         return dict;
  59 }
  60
  61 struct dict_entry *dict_lookup(struct dict *dict, const char **sp, const char *e) {
  62         struct dict_entry *de;
  63         unsigned int first;
  64         if (*sp >= e)
  65                 return NULL;
  66         first = (unsigned int)**sp & 0xFF;
  67
  68         if (!first) {
  69                 if (dict->zero)
  70                         (*sp)++;
  71                 return dict->zero;
  72         }
  73
  74         de = dict->by_first_letter[first-1];
  75         if (!de)
  76                 return NULL;
  77
  78         for (;de->str[0]==(char)first; de++) {
  79                 const char *s = *sp;
  80                 const char *ds = de->str;
  81                 for (;;s++,ds++) {
  82                         if (!*ds) {
  83                                 *sp = s;
  84                                 return de;
  85                         }
  86                         if (s>=e || *s!=*ds)
  87                                 break;
  88                 }
  89         }
  90
  91         return NULL;
  92 }