Merge.
[ccan] / 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 }