* dcache.c (dcache_block): Replace member newer with next,prev.

	(dcache_struct): Delete member newest.
	(block_func): New typedef.
	(append_block, remove_block, for_each_block): New functions.
	(invalidate_block, free_block): New functions.
	(dcache_invalidate): Update
	(dcache_invalidate_line, dcache_alloc): Update to use new list
	accessors.
	(dcache_free): Ditto.  Fix memory leak.

2 files changed, 120 insertions, 36 deletions

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index 7bfd1a8..59cc5c5 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,3 +1,15 @@
+2009-11-13  Doug Evans  <dje@google.com>
+
+	* dcache.c (dcache_block): Replace member newer with next,prev.
+	(dcache_struct): Delete member newest.
+	(block_func): New typedef.
+	(append_block, remove_block, for_each_block): New functions.
+	(invalidate_block, free_block): New functions.
+	(dcache_invalidate): Update
+	(dcache_invalidate_line, dcache_alloc): Update to use new list
+	accessors.
+	(dcache_free): Ditto.  Fix memory leak.
+
 2009-11-13  Paul Pluzhnikov  <ppluzhnikov@google.com>
 
 	* python/py-prettyprint.c (print_string_repr): Suppress
diff --git a/gdb/dcache.c b/gdb/dcache.c
index e8728e9..d926e9d 100644
--- a/gdb/dcache.c
+++ b/gdb/dcache.c
@@ -88,7 +88,10 @@
 
 struct dcache_block
 {
-  struct dcache_block *newer;	/* for LRU and free list */
+  /* for least-recently-allocated and free lists */
+  struct dcache_block *prev;
+  struct dcache_block *next;
+
   CORE_ADDR addr;		/* address of data */
   gdb_byte data[LINE_SIZE];	/* bytes at given address */
   int refs;			/* # hits */
@@ -97,9 +100,10 @@ struct dcache_block
 struct dcache_struct
 {
   splay_tree tree;
-  struct dcache_block *oldest;
-  struct dcache_block *newest;
+  struct dcache_block *oldest; /* least-recently-allocated list */
 
+  /* The free list is maintained identically to OLDEST to simplify
+     the code: we only need one set of accessors.  */
   struct dcache_block *freelist;
 
   /* The number of in-use lines in the cache.  */
@@ -109,6 +113,8 @@ struct dcache_struct
   ptid_t ptid;
 };
 
+typedef void (block_func) (struct dcache_block *block, void *param);
+
 static struct dcache_block *dcache_hit (DCACHE *dcache, CORE_ADDR addr);
 
 static int dcache_write_line (DCACHE *dcache, struct dcache_block *db);
@@ -132,28 +138,98 @@ show_dcache_enabled_p (struct ui_file *file, int from_tty,
 
 static DCACHE *last_cache; /* Used by info dcache */
 
-/* Free all the data cache blocks, thus discarding all cached data.  */
+/* Add BLOCK to circular block list BLIST, behind the block at *BLIST.
+   *BLIST is not updated (unless it was previously NULL of course).
+   This is for the least-recently-allocated list's sake:
+   BLIST points to the oldest block.
+   ??? This makes for poor cache usage of the free list,
+   but is it measurable?  */
 
-void
-dcache_invalidate (DCACHE *dcache)
+static void
+append_block (struct dcache_block **blist, struct dcache_block *block)
 {
-  struct dcache_block *block, *next;
+  if (*blist)
+    {
+      block->next = *blist;
+      block->prev = (*blist)->prev;
+      block->prev->next = block;
+      (*blist)->prev = block;
+      /* We don't update *BLIST here to maintain the invariant that for the
+	 least-recently-allocated list *BLIST points to the oldest block.  */
+    }
+  else
+    {
+      block->next = block;
+      block->prev = block;
+      *blist = block;
+    }
+}
 
-  block = dcache->oldest;
+/* Remove BLOCK from circular block list BLIST.  */
 
-  while (block)
+static void
+remove_block (struct dcache_block **blist, struct dcache_block *block)
+{
+  if (block->next == block)
+    {
+      *blist = NULL;
+    }
+  else
     {
-      splay_tree_remove (dcache->tree, (splay_tree_key) block->addr);
-      next = block->newer;
+      block->next->prev = block->prev;
+      block->prev->next = block->next;
+      /* If we removed the block *BLIST points to, shift it to the next block
+	 to maintain the invariant that for the least-recently-allocated list
+	 *BLIST points to the oldest block.  */
+      if (*blist == block)
+	*blist = block->next;
+    }
+}
 
-      block->newer = dcache->freelist;
-      dcache->freelist = block;
+/* Iterate over all elements in BLIST, calling FUNC.
+   PARAM is passed to FUNC.
+   FUNC may remove the block it's passed, but only that block.  */
 
-      block = next;
+static void
+for_each_block (struct dcache_block **blist, block_func *func, void *param)
+{
+  struct dcache_block *db;
+
+  if (*blist == NULL)
+    return;
+
+  db = *blist;
+  do
+    {
+      struct dcache_block *next = db->next;
+
+      func (db, param);
+      db = next;
     }
+  while (*blist && db != *blist);
+}
+
+/* BLOCK_FUNC function for dcache_invalidate.
+   This doesn't remove the block from the oldest list on purpose.
+   dcache_invalidate will do it later.  */
+
+static void
+invalidate_block (struct dcache_block *block, void *param)
+{
+  DCACHE *dcache = (DCACHE *) param;
+
+  splay_tree_remove (dcache->tree, (splay_tree_key) block->addr);
+  append_block (&dcache->freelist, block);
+}
+
+/* Free all the data cache blocks, thus discarding all cached data.  */
+
+void
+dcache_invalidate (DCACHE *dcache)
+{
+  for_each_block (&dcache->oldest, invalidate_block, dcache);
 
   dcache->oldest = NULL;
-  dcache->newest = NULL;
   dcache->size = 0;
   dcache->ptid = null_ptid;
 }
@@ -168,8 +244,8 @@ dcache_invalidate_line (DCACHE *dcache, CORE_ADDR addr)
   if (db)
     {
       splay_tree_remove (dcache->tree, (splay_tree_key) db->addr);
-      db->newer = dcache->freelist;
-      dcache->freelist = db;
+      remove_block (&dcache->oldest, db);
+      append_block (&dcache->freelist, db);
       --dcache->size;
     }
 }
@@ -251,9 +327,9 @@ dcache_alloc (DCACHE *dcache, CORE_ADDR addr)
 
   if (dcache->size >= DCACHE_SIZE)
     {
-      /* Evict the least recently used line.  */
+      /* Evict the least recently allocated line.  */
       db = dcache->oldest;
-      dcache->oldest = db->newer;
+      remove_block (&dcache->oldest, db);
 
       splay_tree_remove (dcache->tree, (splay_tree_key) db->addr);
     }
@@ -261,7 +337,7 @@ dcache_alloc (DCACHE *dcache, CORE_ADDR addr)
     {
       db = dcache->freelist;
       if (db)
-        dcache->freelist = db->newer;
+	remove_block (&dcache->freelist, db);
       else
 	db = xmalloc (sizeof (struct dcache_block));
 
@@ -269,16 +345,10 @@ dcache_alloc (DCACHE *dcache, CORE_ADDR addr)
     }
 
   db->addr = MASK (addr);
-  db->newer = NULL;
   db->refs = 0;
 
-  if (dcache->newest)
-    dcache->newest->newer = db;
-
-  dcache->newest = db;
-
-  if (!dcache->oldest)
-    dcache->oldest = db;
+  /* Put DB at the end of the list, it's the newest.  */
+  append_block (&dcache->oldest, db);
 
   splay_tree_insert (dcache->tree, (splay_tree_key) db->addr,
 		     (splay_tree_value) db);
@@ -356,7 +426,6 @@ dcache_init (void)
 				 NULL);
 
   dcache->oldest = NULL;
-  dcache->newest = NULL;
   dcache->freelist = NULL;
   dcache->size = 0;
   dcache->ptid = null_ptid;
@@ -365,22 +434,25 @@ dcache_init (void)
   return dcache;
 }
 
+/* BLOCK_FUNC routine for dcache_free.  */
+
+static void
+free_block (struct dcache_block *block, void *param)
+{
+  free (block);
+}
+
 /* Free a data cache.  */
 
 void
 dcache_free (DCACHE *dcache)
 {
-  struct dcache_block *db, *next;
-
   if (last_cache == dcache)
     last_cache = NULL;
 
   splay_tree_delete (dcache->tree);
-  for (db = dcache->freelist; db != NULL; db = next)
-    {
-      next = db->newer;
-      xfree (db);
-    }
+  for_each_block (&dcache->oldest, free_block, NULL);
+  for_each_block (&dcache->freelist, free_block, NULL);
   xfree (dcache);
 }