Genralizing Pointer Routines

[Gisle Aas]

In article <14714 at smoke.brl.mil> gwyn at smoke.brl.mil (Doug Gwyn) writes:
   In article <cbN7yBm00UhW45Cnh2 at andrew.cmu.edu> rg2c+ at andrew.cmu.edu (Robert Nelson Gasch) writes:
   >In PASCAL, if you have 3 linked lists of different pointer types,
   >you have to write 3 different Insert, search & delete routines; one
   >for each pointer type. I was wondering if these routines can be 
   >generalized for any pointer type in C?

   Yes, the simplest scheme is to have a special "linkage" substructure
   as the first member of each type of node structure.  By appropriate
   use of casts etc., common link-manipulation routines can be used for
   all the node types, in a portable ("strictly conforming") manner.

Or you could use the preprocessor. These macros operate on double
linked lists. The idea should be simple to extend.

#ifdef lint
   int _ZERO_;
#else
   #define _ZERO_ 0
#endif
#define STATEMENT(s)    do {s} while (_ZERO_)

/* don't use this macro directly */
#define _dl_insert(z,d,first,prev,next)         \
   if (first) {                                 \
      z->prev = d->prev;                        \
      z->next = d;                              \
      d->prev->next = z;                        \
      d->prev = z;                              \
   } else {                                     \
      first = z;                                \
      z->next = z;                              \
      z->prev = z;                              \
   }

/* insert the element z just before the element d which is a member of
 * the list starting with element first.
 */
#define dl_insert(z,d,first,prev,next)          \
STATEMENT(                                      \
   _dl_insert(z,d,first,prev,next);             \
   if (d == first)                              \
      first = z;                                \
)

#define dl_insert_first(z,first,prev,next)      \
STATEMENT(                                      \
   _dl_insert(z,first,first,prev,next);         \
   first = z;                                   \
)

#define dl_insert_last(z,first,prev,next)       \
STATEMENT(                                      \
   _dl_insert(z,first,first,prev,next);         \
)

#define dl_remove(z,first,prev,next)            \
STATEMENT(                                      \
   z->next->prev = z->prev;                     \
   z->prev->next = z->next;                     \
   if (z == first) first = z->next;             \
   if (z == first) first = NULL;                \
)


/*---- Example of use, not tested ----*/

struct node *list1 = NULL, *list2 = NULL;   /* list heads */
struct node {
   sometype foo;
   ...

   struct node *next1, *prev1;
   struct node *next2, *prev2;
}


x = malloc(sizeof(node));
dl_insert_first(x,list1,prev1,next2);
dl_insert_last(x,list2,prev2,next2);
dl_remove(x,list2,prev2,next2);

--
Gisle Aas               |  snail: Boks 114 Blindern, N-0314 Oslo, Norway
Norsk Regnesentral      |  X.400: G=Gisle;S=Aas;O=nr;P=uninett;C=no
voice: +47-2-453561     |  inet:  Gisle.Aas at nr.no