2 files changed, 63 insertions, 53 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);
 }
 
diff --git a/src/references.h b/src/references.h
index 5038c49..cc59509 100644
--- a/src/references.h
+++ b/src/references.h
@@ -7,21 +7,21 @@
 extern "C" {
 #endif
 
-#define REFMAP_SIZE 16
-
 struct cmark_reference {
   struct cmark_reference *next;
   unsigned char *label;
   unsigned char *url;
   unsigned char *title;
-  unsigned int hash;
+  unsigned int age;
 };
 
 typedef struct cmark_reference cmark_reference;
 
 struct cmark_reference_map {
   cmark_mem *mem;
-  cmark_reference *table[REFMAP_SIZE];
+  cmark_reference *refs;
+  cmark_reference **sorted;
+  unsigned int size;
 };
 
 typedef struct cmark_reference_map cmark_reference_map;