Re: Linked lists

[Ben Pfaff]

John Darrington <address@hidden> writes:

> Despite the very comprehensive test programs, I'm still unsure how to
> use the linked lists.

The test programs are terrible as examples, but that's not really
their purpose.

> How would I replace the prev/next pointers in casefile.c with a list,
> and push casefile pointers onto it?

I actually have a large number of patches to existing code to
convert them from by-hand linked lists to 'struct ll' linked
lists.  They're all out-of-date (they date from before the source
tree reorganization), but they're probably still good as
examples.

Here's the one for casefile.c.  It also changes some "int"s to
"bool"s, I see:

Index: casefile.c
===================================================================
RCS file: /cvsroot/pspp/pspp/src/Attic/casefile.c,v
retrieving revision 1.21
diff -u -p -u -r1.21 casefile.c
--- casefile.c  29 Jan 2006 05:03:02 -0000      1.21
+++ casefile.c  3 Jul 2006 17:05:55 -0000
@@ -31,6 +31,7 @@
 #include "error.h"
 #include "full-read.h"
 #include "full-write.h"
+#include "ll.h"
 #include "misc.h"
 #include "mkfile.h"
 #include "settings.h"
@@ -120,14 +121,14 @@
 struct casefile 
   {
     /* Basic data. */
-    struct casefile *next, *prev;       /* Next, prev in global list. */
+    struct ll ll;                       /* Global list element. */
     size_t value_cnt;                   /* Case size in `union value's. */
     size_t case_acct_size;              /* Case size for accounting. */
     unsigned long case_cnt;             /* Number of cases stored. */
     enum { MEMORY, DISK } storage;      /* Where cases are stored. */
     enum { WRITE, READ } mode;          /* Is writing or reading allowed? */
-    struct casereader *readers;         /* List of our readers. */
-    int being_destroyed;                /* Does a destructive reader exist? */
+    struct ll_list readers;             /* List of our readers. */
+    bool being_destroyed;               /* Does a destructive reader exist? */
 
     /* Memory storage. */
     struct ccase **cases;               /* Pointer to array of cases. */
@@ -140,13 +141,19 @@ struct casefile 
     size_t buffer_size;                 /* Buffer size in values. */
   };
 
+static struct casefile *
+ll_to_casefile (const struct ll *ll) 
+{
+  return ll_data (ll, struct casefile, ll);
+}
+
 /* For reading out the cases in a casefile. */
 struct casereader 
   {
-    struct casereader *next, *prev;     /* Next, prev in casefile's list. */
+    struct ll ll;                       /* Casefile's list element. */
     struct casefile *cf;                /* Our casefile. */
     unsigned long case_idx;             /* Case number of current case. */
-    int destructive;                    /* Is this a destructive reader? */
+    bool destructive;                   /* Is this a destructive reader? */
 
     /* Disk storage. */
     int fd;                             /* File descriptor. */
@@ -155,15 +162,14 @@ struct casereader 
     struct ccase c;                     /* Current case. */
   };
 
-/* Return the case number of the current case */
-unsigned long
-casereader_cnum(const struct casereader *r)
+static struct casereader *
+ll_to_casereader (const struct ll *ll) 
 {
-  return r->case_idx;
+  return ll_data (ll, struct casereader, ll);
 }
 
-/* Doubly linked list of all casefiles. */
-static struct casefile *casefiles;
+/* All casefiles. */
+static struct ll_list casefiles = LL_INITIALIZER (casefiles);
 
 /* Number of bytes of case allocated in in-memory casefiles. */
 static size_t case_bytes;
@@ -185,18 +191,14 @@ struct casefile *
 casefile_create (size_t value_cnt) 
 {
   struct casefile *cf = xmalloc (sizeof *cf);
-  cf->next = casefiles;
-  cf->prev = NULL;
-  if (cf->next != NULL)
-    cf->next->prev = cf;
-  casefiles = cf;
+  ll_push_head (&casefiles, &cf->ll);
   cf->value_cnt = value_cnt;
   cf->case_acct_size = (cf->value_cnt + 4) * sizeof *cf->buffer;
   cf->case_cnt = 0;
   cf->storage = MEMORY;
   cf->mode = WRITE;
-  cf->readers = NULL;
-  cf->being_destroyed = 0;
+  ll_init (&cf->readers);
+  cf->being_destroyed = false;
   cf->cases = NULL;
   cf->fd = -1;
   cf->filename = NULL;
@@ -215,15 +217,10 @@ casefile_destroy (struct casefile *cf) 
 {
   if (cf != NULL) 
     {
-      if (cf->next != NULL)
-        cf->next->prev = cf->prev;
-      if (cf->prev != NULL)
-        cf->prev->next = cf->next;
-      if (casefiles == cf)
-        casefiles = cf->next;
+      ll_remove (&cf->ll);
 
-      while (cf->readers != NULL) 
-        casereader_destroy (cf->readers);
+      while (!ll_is_empty (&cf->readers)) 
+        casereader_destroy (ll_to_casereader (ll_head (&cf->readers)));
 
       if (cf->cases != NULL) 
         {
@@ -409,13 +406,13 @@ void
 casefile_to_disk (const struct casefile *cf_) 
 {
   struct casefile *cf = (struct casefile *) cf_;
-  struct casereader *reader;
   
   assert (cf != NULL);
 
   if (cf->storage == MEMORY)
     {
       size_t idx, block_cnt;
+      struct casereader *reader;
       
       assert (cf->filename == NULL);
       assert (cf->fd == -1);
@@ -447,7 +444,7 @@ casefile_to_disk (const struct casefile 
       if (cf->mode == READ)
         flush_buffer (cf);
 
-      for (reader = cf->readers; reader != NULL; reader = reader->next)
+      ll_for_each (reader, struct casereader, ll, &cf->readers) 
         reader_open_file (reader);
     }
 }
@@ -479,14 +476,10 @@ casefile_get_reader (const struct casefi
   cf->mode = READ;
 
   reader = xmalloc (sizeof *reader);
-  reader->next = cf->readers;
-  if (cf->readers != NULL)
-    reader->next->prev = reader;
-  cf->readers = reader;
-  reader->prev = NULL;
+  ll_push_head (&cf->readers, &reader->ll);
   reader->cf = cf;
   reader->case_idx = 0;
-  reader->destructive = 0;
+  reader->destructive = false;
   reader->fd = -1;
   reader->buffer = NULL;
   reader->buffer_pos = 0;
@@ -509,10 +502,10 @@ casefile_get_destructive_reader (struct 
 {
   struct casereader *reader;
   
-  assert (cf->readers == NULL);
+  assert (ll_is_empty (&cf->readers));
   reader = casefile_get_reader (cf);
-  reader->destructive = 1;
-  cf->being_destroyed = 1;
+  reader->destructive = true;
+  cf->being_destroyed = true;
   return reader;
 }
 
@@ -642,7 +635,7 @@ casereader_read_xfer (struct casereader 
 {
   assert (reader != NULL);
 
-  if (reader->destructive == 0
+  if (!reader->destructive
       || reader->case_idx >= reader->cf->case_cnt
       || reader->cf->storage == DISK) 
     return casereader_read (reader, c);
@@ -674,12 +667,7 @@ casereader_destroy (struct casereader *r
 {
   assert (reader != NULL);
 
-  if (reader->next != NULL)
-    reader->next->prev = reader->prev;
-  if (reader->prev != NULL)
-    reader->prev->next = reader->next;
-  if (reader->cf->readers == reader)
-    reader->cf->readers = reader->next;
+  ll_remove (&reader->ll);
 
   if (reader->cf->buffer == NULL)
     reader->cf->buffer = reader->buffer;
@@ -699,6 +687,13 @@ casereader_destroy (struct casereader *r
   free (reader);
 }
 
+/* Return the case number of the current case. */
+unsigned long
+casereader_cnum (const struct casereader *r)
+{
+  return r->case_idx;
+}
+
 /* Calls open(), passing FILENAME and FLAGS, repeating as necessary
    to deal with interrupted calls. */
 static int
@@ -743,13 +738,11 @@ register_atexit (void) 
     }
 }
 
-
-
 /* atexit() handler that closes and deletes our temporary
    files. */
 static void
 exit_handler (void) 
 {
-  while (casefiles != NULL)
-    casefile_destroy (casefiles);
+  while (!ll_is_empty (&casefiles))
+    casefile_destroy (ll_to_casefile (ll_head (&casefiles)));
 }

-- 
"I don't want to learn the constitution and the declaration of
 independence (marvelous poetry though it be) by heart, and worship the
 flag and believe that there is a god and the dollar is its prophet."
--Maarten Wiltink in the Monastery