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