Reimplemented the Dicache using dlib ADTs

For a long time it had a custom ADT with a list of nodes and each
node a linked list (with pointers). The last memory bug motivated me to
try to normalize it to use dlib. Now, it got simpler, shorter, and
possibly faster (although conversion wasn't a simple task).

PD: It also uses less memory now.

3 files changed, 85 insertions, 139 deletions

diff --git a/src/cache.c b/src/cache.c
index 6a7d2748..c4bc1f9b 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -110,7 +110,7 @@ static int Cache_entry_by_url_cmp(const void *v1, const void *v2)
 }
 
 /*
- * Initialize dicache data
+ * Initialize cache data
  */
 void a_Cache_init(void)
 {
diff --git a/src/dicache.c b/src/dicache.c
index 33730f05..a2904c32 100644
--- a/src/dicache.c
+++ b/src/dicache.c
@@ -28,15 +28,10 @@ enum {
    DIC_Jpeg
 };
 
-typedef struct {
-   int valid;            /* flag */
-   DilloUrl *url;        /* primary "Key" for this dicache entry */
-   DICacheEntry *first;  /* pointer to the first dicache entry in this list */
-} DICacheNode;
 
 /*
- * List of DICacheNode. One node per URL. Each node may have several
- * versions of the same image in a linked list.
+ * List of DICacheEntry. May hold several versions of the same image,
+ * although most of the time it holds just one.
  */
 static Dlist *CachedIMGs = NULL;
 
@@ -45,24 +40,20 @@ static uint_t dicache_size_total; /* invariant: dicache_size_total is
                                    * of all the images in the dicache. */
 
 /*
- * Compare two dicache nodes
+ * Compare function for image entries
  */
-static int Dicache_node_cmp(const void *v1, const void *v2)
+static int Dicache_entry_cmp(const void *v1, const void *v2)
 {
-   const DICacheNode *n1 = v1, *n2 = v2;
-
-   return a_Url_cmp(n1->url, n2->url);
-}
-
-/*
- * Compare function for searching a node by Url
- */
-static int Dicache_node_by_url_cmp(const void *v1, const void *v2)
-{
-   const DICacheNode *node = v1;
-   const DilloUrl *url = v2;
-
-   return a_Url_cmp(node->url, url);
+   const DICacheEntry *e1 = v1, *e2 = v2;
+
+   int st = a_Url_cmp(e1->url, e2->url);
+   if (st == 0) {
+      if (e2->version == DIC_Last)
+         st = (e1->Flags & DIF_Last ? 0 : -1);
+      else
+         st = (e1->version - e2->version);
+   }
+   return st;
 }
 
 /*
@@ -83,6 +74,7 @@ static DICacheEntry *Dicache_entry_new(void)
 
    entry->width = 0;
    entry->height = 0;
+   entry->Flags = DIF_Valid;
    entry->SurvCleanup = 0;
    entry->type = DILLO_IMG_TYPE_NOTSET;
    entry->cmap = NULL;
@@ -98,41 +90,29 @@ static DICacheEntry *Dicache_entry_new(void)
    entry->DecoderData = NULL;
    entry->DecodedSize = 0;
 
-   entry->next = NULL;
-
    return entry;
 }
 
 /*
  * Add a new entry in the dicache
- * (a single node (URL) may have several entries)
+ * (a single URL may have several entries)
  */
 static DICacheEntry *Dicache_add_entry(const DilloUrl *Url)
 {
-   DICacheEntry *entry;
-   DICacheNode *node;
+   DICacheEntry e, *entry, *last;
 
    entry = Dicache_entry_new();
-
-   if ((node = dList_find_sorted(CachedIMGs, Url, Dicache_node_by_url_cmp))) {
-      /* this URL is already in CachedIMGs, add entry at the END of the list */
-      DICacheEntry *ptr = node->first;
-
-      node->valid = 1;
-      for (  ; ptr->next; ptr = ptr->next);
-      ptr->next = entry;
-      entry->version = ptr->version+1;
-      entry->url = node->url;
-
-   } else { /* no node yet, so create one */
-      DICacheNode *node = dNew(DICacheNode, 1);
-
-      node->url = a_Url_dup(Url);
-      entry->url = node->url;
-      node->first = entry;
-      node->valid = 1;
-      dList_insert_sorted(CachedIMGs, node, Dicache_node_cmp);
+   e.url = (DilloUrl*)Url;
+   e.version = DIC_Last;
+   last = dList_find_sorted(CachedIMGs, &e, Dicache_entry_cmp);
+   if (last) {
+      /* URL is already in CachedIMGs, make a new version */
+      last->Flags &= ~DIF_Last;
+      entry->version = last->version + 1;
    }
+   entry->url = a_Url_dup(Url);
+   entry->Flags |= DIF_Last;
+   dList_insert_sorted(CachedIMGs, entry, Dicache_entry_cmp);
 
    return entry;
 }
@@ -146,23 +126,15 @@ static DICacheEntry *Dicache_add_entry(const DilloUrl *Url)
  */
 DICacheEntry *a_Dicache_get_entry(const DilloUrl *Url, int version)
 {
-   DICacheNode *node;
+   DICacheEntry e;
    DICacheEntry *entry = NULL;
 
    dReturn_val_if_fail(version != 0, NULL);
-
-   node = dList_find_sorted(CachedIMGs, Url, Dicache_node_by_url_cmp);
-   if (node) {
-      if (version == DIC_Last) {
-         if (node->valid) {
-            entry = node->first;
-            for ( ;  (entry && entry->next); entry = entry->next);
-         }
-      } else {
-         entry = node->first;
-         for ( ; entry && entry->version != version; entry = entry->next) ;
-      }
-   }
+   e.url = (DilloUrl*)Url;
+   e.version = version;
+   entry = dList_find_sorted(CachedIMGs, &e, Dicache_entry_cmp);
+   if (entry && !(entry->Flags & DIF_Valid) && version == DIC_Last)
+      entry = NULL;
    return entry;
 }
 
@@ -171,42 +143,29 @@ DICacheEntry *a_Dicache_get_entry(const DilloUrl *Url, int version)
  */
 static void Dicache_remove(const DilloUrl *Url, int version)
 {
-   DICacheNode *node;
-   DICacheEntry *entry, *prev;
-   _MSG("Dicache_remove url=%s\n", URL_STR(Url));
-   node = dList_find_sorted(CachedIMGs, Url, Dicache_node_by_url_cmp);
-   prev = entry = (node) ? node->first : NULL;
-
-   while (entry && (entry->version != version) ) {
-      prev = entry;
-      entry = entry->next;
-   }
+   DICacheEntry e, *entry;
 
-   if (entry) {
-      _MSG("Dicache_remove Imgbuf=%p Decoder=%p DecoderData=%p\n",
-          entry->v_imgbuf, entry->Decoder, entry->DecoderData);
-      /* Eliminate this dicache entry */
-      dFree(entry->cmap);
-      a_Bitvec_free(entry->BitVec);
-      a_Imgbuf_unref(entry->v_imgbuf);
-      if (entry->Decoder) {
-         entry->Decoder(CA_Abort, entry->DecoderData);
-      }
-      dicache_size_total -= entry->TotalSize;
-
-      if (node->first == entry) {
-         if (!entry->next) {
-            /* last entry with this URL. Remove the node as well */
-            dList_remove(CachedIMGs, node);
-            a_Url_free(node->url);
-            dFree(node);
-         } else
-            node->first = entry->next;
-      } else {
-         prev->next = entry->next;
-      }
-      dFree(entry);
+   _MSG("Dicache_remove url=%s\n", URL_STR(Url));
+   e.url = (DilloUrl*)Url;
+   e.version = version;
+   entry = dList_find_sorted(CachedIMGs, &e, Dicache_entry_cmp);
+   dReturn_if (entry == NULL);
+
+   _MSG("Dicache_remove Imgbuf=%p Decoder=%p DecoderData=%p\n",
+       entry->v_imgbuf, entry->Decoder, entry->DecoderData);
+   /* Eliminate this dicache entry */
+   dList_remove(CachedIMGs, entry);
+   dicache_size_total -= entry->TotalSize;
+
+   /* entry cleanup */
+   a_Url_free(entry->url);
+   dFree(entry->cmap);
+   a_Bitvec_free(entry->BitVec);
+   a_Imgbuf_unref(entry->v_imgbuf);
+   if (entry->Decoder) {
+      entry->Decoder(CA_Abort, entry->DecoderData);
    }
+   dFree(entry);
 }
 
 /*
@@ -249,11 +208,9 @@ DICacheEntry* a_Dicache_ref(const DilloUrl *Url, int version)
  */
 void a_Dicache_invalidate_entry(const DilloUrl *Url)
 {
-   DICacheNode *node;
-
-   node = dList_find_sorted(CachedIMGs, Url, Dicache_node_by_url_cmp);
-   if (node)
-      node->valid = 0;
+   DICacheEntry *entry = a_Dicache_get_entry(Url, DIC_Last);
+   if (entry)
+      entry->Flags &= ~DIF_Valid;
 }
 
 
@@ -550,29 +507,21 @@ void a_Dicache_callback(int Op, CacheClient_t *Client)
 void a_Dicache_cleanup(void)
 {
    int i;
-   DICacheNode *node;
-   DICacheEntry *entry, *next;
-
-   MSG("a_Dicache_cleanup\n");
-   for (i = 0; i < dList_length(CachedIMGs); ++i) {
-      node = dList_nth_data(CachedIMGs, i);
-      /* iterate each entry of this node */
-      for (entry = node->first; entry; entry = next) {
-         next = entry->next;
-         MSG(" SurvCleanup = %d\n", entry->SurvCleanup);
-         if (entry->RefCount == 0 &&
-             (!entry->v_imgbuf || a_Imgbuf_last_reference(entry->v_imgbuf))) {
-            if (--entry->SurvCleanup >= 0)
-               continue;  /* keep the entry one more pass */
-
-            /* free this unused entry */
-            _MSG("a_Dicache_cleanup: removing entry...\n");
-            Dicache_remove(node->url, entry->version);
-            if (!next && node != dList_nth_data(CachedIMGs, i))
-               --i; /* removed node, adjust counter */
-         }
+   DICacheEntry *entry;
+
+   for (i = 0; (entry = dList_nth_data(CachedIMGs, i)); ++i) {
+      _MSG(" SurvCleanup = %d\n", entry->SurvCleanup);
+      if (entry->RefCount == 0 &&
+          (!entry->v_imgbuf || a_Imgbuf_last_reference(entry->v_imgbuf))) {
+         if (--entry->SurvCleanup >= 0)
+            continue;  /* keep the entry one more pass */
+
+         /* free this unused entry */
+         Dicache_remove(entry->url, entry->version);
+         --i; /* adjust counter */
       }
    }
+   MSG("a_Dicache_cleanup: length = %d\n", dList_length(CachedIMGs));
 }
 
 /* ------------------------------------------------------------------------- */
@@ -583,22 +532,17 @@ void a_Dicache_cleanup(void)
  */
 void a_Dicache_freeall(void)
 {
-   DICacheNode *node;
    DICacheEntry *entry;
 
-   /* Remove every dicache node and its entries */
-   while ((node = dList_nth_data(CachedIMGs, 0))) {
-      while ((entry = node->first)) {
-         node->first = entry->next;
-         dFree(entry->cmap);
-         a_Bitvec_free(entry->BitVec);
-         a_Imgbuf_unref(entry->v_imgbuf);
-         dicache_size_total -= entry->TotalSize;
-         dFree(entry);
-      }
-      dList_remove_fast(CachedIMGs, node);
-      a_Url_free(node->url);
-      dFree(node);
+   /* Remove all the dicache entries */
+   while ((entry = dList_nth_data(CachedIMGs, dList_length(CachedIMGs)-1))) {
+      dList_remove_fast(CachedIMGs, entry);
+      a_Url_free(entry->url);
+      dFree(entry->cmap);
+      a_Bitvec_free(entry->BitVec);
+      a_Imgbuf_unref(entry->v_imgbuf);
+      dicache_size_total -= entry->TotalSize;
+      dFree(entry);
    }
    dList_free(CachedIMGs);
 }
diff --git a/src/dicache.h b/src/dicache.h
index 0390d214..7d5ef6ee 100644
--- a/src/dicache.h
+++ b/src/dicache.h
@@ -12,6 +12,9 @@ extern "C" {
 
 /* Symbolic name to request the last version of an image */
 #define DIC_Last  -1
+/* Flags: Last version, Valid entry */
+#define DIF_Last  1
+#define DIF_Valid 2
 
 
 /* These will reflect the entry's "state" */
@@ -28,7 +31,8 @@ typedef struct DICacheEntry {
    DilloUrl *url;          /* Image URL for this entry */
    DilloImgType type;      /* Image type */
    uint_t width, height;   /* As taken from image data */
-   int SurvCleanup;        /* Cleanup-pass survival for unused images */
+   short Flags;            /* See Flags */
+   short SurvCleanup;      /* Cleanup-pass survival for unused images */
    uchar_t *cmap;          /* Color map */
    void *v_imgbuf;         /* Void pointer to an Imgbuf object */
    uint_t TotalSize;       /* Amount of memory the image takes up */
@@ -42,8 +46,6 @@ typedef struct DICacheEntry {
    uint_t DecodedSize;     /* Size of already decoded data */
    CA_Callback_t Decoder;  /* Client function */
    void *DecoderData;      /* Client function data */
-
-   struct DICacheEntry *next; /* Link to the next "newer" version */
 } DICacheEntry;