diff options
Diffstat (limited to 'src/references.c')
-rw-r--r-- | src/references.c | 108 |
1 files changed, 59 insertions, 49 deletions
diff --git a/src/references.c b/src/references.c index f0d871f..4830689 100644 --- a/src/references.c +++ b/src/references.c @@ -5,15 +5,6 @@ #include "inlines.h" #include "chunk.h" -static unsigned int refhash(const unsigned char *link_ref) { - unsigned int hash = 0; - - while (*link_ref) - hash = (*link_ref++) + (hash << 6) + (hash << 16) - hash; - - return hash; -} - static void reference_free(cmark_reference_map *map, cmark_reference *ref) { cmark_mem *mem = map->mem; if (ref != NULL) { @@ -53,21 +44,6 @@ static unsigned char *normalize_reference(cmark_mem *mem, cmark_chunk *ref) { return result; } -static void add_reference(cmark_reference_map *map, cmark_reference *ref) { - cmark_reference *t = ref->next = map->table[ref->hash % REFMAP_SIZE]; - - while (t) { - if (t->hash == ref->hash && !strcmp((char *)t->label, (char *)ref->label)) { - reference_free(map, ref); - return; - } - - t = t->next; - } - - map->table[ref->hash % REFMAP_SIZE] = ref; -} - void cmark_reference_create(cmark_reference_map *map, cmark_chunk *label, cmark_chunk *url, cmark_chunk *title) { cmark_reference *ref; @@ -77,64 +53,98 @@ void cmark_reference_create(cmark_reference_map *map, cmark_chunk *label, if (reflabel == NULL) return; + assert(map->sorted == NULL); + ref = (cmark_reference *)map->mem->calloc(1, sizeof(*ref)); ref->label = reflabel; - ref->hash = refhash(ref->label); ref->url = cmark_clean_url(map->mem, url); ref->title = cmark_clean_title(map->mem, title); - ref->next = NULL; + ref->age = map->size; + ref->next = map->refs; + + map->refs = ref; + map->size++; +} + +static int +labelcmp(const unsigned char *a, const unsigned char *b) { + return strcmp((const char *)a, (const char *)b); +} - add_reference(map, ref); +static int +refcmp(const void *p1, const void *p2) { + cmark_reference *r1 = *(cmark_reference **)p1; + cmark_reference *r2 = *(cmark_reference **)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_reference *ref = *(cmark_reference **)p2; + return labelcmp(label, ref->label); +} + +static void sort_references(cmark_reference_map *map) { + unsigned int i = 0, last = 0, size = map->size; + cmark_reference *r = map->refs, **sorted = NULL; + + sorted = map->mem->calloc(size, sizeof(cmark_reference *)); + while (r) { + sorted[i++] = r; + r = r->next; + } + + qsort(sorted, size, sizeof(cmark_reference *), 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; } // Returns reference if refmap contains a reference with matching // label, otherwise NULL. cmark_reference *cmark_reference_lookup(cmark_reference_map *map, cmark_chunk *label) { - cmark_reference *ref = NULL; + cmark_reference **ref = NULL; unsigned char *norm; - unsigned int hash; if (label->len < 1 || label->len > MAX_LINK_LABEL_LENGTH) return NULL; - if (map == NULL) + if (map == NULL || !map->size) return NULL; norm = normalize_reference(map->mem, label); if (norm == NULL) return NULL; - hash = refhash(norm); - ref = map->table[hash % REFMAP_SIZE]; - - while (ref) { - if (ref->hash == hash && !strcmp((char *)ref->label, (char *)norm)) - break; - ref = ref->next; - } + if (!map->sorted) + sort_references(map); + ref = bsearch(norm, map->sorted, map->size, sizeof(cmark_reference *), + refsearch); map->mem->free(norm); - return ref; + return ref ? ref[0] : NULL; } void cmark_reference_map_free(cmark_reference_map *map) { - unsigned int i; + cmark_reference *ref; if (map == NULL) return; - for (i = 0; i < REFMAP_SIZE; ++i) { - cmark_reference *ref = map->table[i]; - cmark_reference *next; - - while (ref) { - next = ref->next; - reference_free(map, ref); - ref = next; - } + ref = map->refs; + while (ref) { + cmark_reference *next = ref->next; + reference_free(map, ref); + ref = next; } + map->mem->free(map->sorted); map->mem->free(map); } |