1 #include "map.h"
2 #include "utf8.h"
3 #include "parser.h"
4
5 // normalize map label: collapse internal whitespace to single space,
6 // remove leading/trailing whitespace, case fold
7 // Return NULL if the label is actually empty (i.e. composed solely from
8 // whitespace)
normalize_map_label(cmark_mem * mem,cmark_chunk * ref)9 unsigned char *normalize_map_label(cmark_mem *mem, cmark_chunk *ref) {
10 cmark_strbuf normalized = CMARK_BUF_INIT(mem);
11 unsigned char *result;
12
13 if (ref == NULL)
14 return NULL;
15
16 if (ref->len == 0)
17 return NULL;
18
19 cmark_utf8proc_case_fold(&normalized, ref->data, ref->len);
20 cmark_strbuf_trim(&normalized);
21 cmark_strbuf_normalize_whitespace(&normalized);
22
23 result = cmark_strbuf_detach(&normalized);
24 assert(result);
25
26 if (result[0] == '\0') {
27 mem->free(result);
28 return NULL;
29 }
30
31 return result;
32 }
33
34 static int
labelcmp(const unsigned char * a,const unsigned char * b)35 labelcmp(const unsigned char *a, const unsigned char *b) {
36 return strcmp((const char *)a, (const char *)b);
37 }
38
39 static int
refcmp(const void * p1,const void * p2)40 refcmp(const void *p1, const void *p2) {
41 cmark_map_entry *r1 = *(cmark_map_entry **)p1;
42 cmark_map_entry *r2 = *(cmark_map_entry **)p2;
43 int res = labelcmp(r1->label, r2->label);
44 return res ? res : ((int)r1->age - (int)r2->age);
45 }
46
47 static int
refsearch(const void * label,const void * p2)48 refsearch(const void *label, const void *p2) {
49 cmark_map_entry *ref = *(cmark_map_entry **)p2;
50 return labelcmp((const unsigned char *)label, ref->label);
51 }
52
sort_map(cmark_map * map)53 static void sort_map(cmark_map *map) {
54 unsigned int i = 0, last = 0, size = map->size;
55 cmark_map_entry *r = map->refs, **sorted = NULL;
56
57 sorted = (cmark_map_entry **)map->mem->calloc(size, sizeof(cmark_map_entry *));
58 while (r) {
59 sorted[i++] = r;
60 r = r->next;
61 }
62
63 qsort(sorted, size, sizeof(cmark_map_entry *), refcmp);
64
65 for (i = 1; i < size; i++) {
66 if (labelcmp(sorted[i]->label, sorted[last]->label) != 0)
67 sorted[++last] = sorted[i];
68 }
69
70 map->sorted = sorted;
71 map->size = last + 1;
72 }
73
cmark_map_lookup(cmark_map * map,cmark_chunk * label)74 cmark_map_entry *cmark_map_lookup(cmark_map *map, cmark_chunk *label) {
75 cmark_map_entry **ref = NULL;
76 unsigned char *norm;
77
78 if (label->len < 1 || label->len > MAX_LINK_LABEL_LENGTH)
79 return NULL;
80
81 if (map == NULL || !map->size)
82 return NULL;
83
84 norm = normalize_map_label(map->mem, label);
85 if (norm == NULL)
86 return NULL;
87
88 if (!map->sorted)
89 sort_map(map);
90
91 ref = (cmark_map_entry **)bsearch(norm, map->sorted, map->size, sizeof(cmark_map_entry *), refsearch);
92 map->mem->free(norm);
93
94 if (!ref)
95 return NULL;
96
97 return ref[0];
98 }
99
cmark_map_free(cmark_map * map)100 void cmark_map_free(cmark_map *map) {
101 cmark_map_entry *ref;
102
103 if (map == NULL)
104 return;
105
106 ref = map->refs;
107 while (ref) {
108 cmark_map_entry *next = ref->next;
109 map->free(map, ref);
110 ref = next;
111 }
112
113 map->mem->free(map->sorted);
114 map->mem->free(map);
115 }
116
cmark_map_new(cmark_mem * mem,cmark_map_free_f free)117 cmark_map *cmark_map_new(cmark_mem *mem, cmark_map_free_f free) {
118 cmark_map *map = (cmark_map *)mem->calloc(1, sizeof(cmark_map));
119 map->mem = mem;
120 map->free = free;
121 return map;
122 }
123