binaries/src/ViennaRNA/lib/list.c

   1 /*
   2   $Log: list.c,v $
   3   Revision 1.5  2003/07/14 13:36:58  ivo
   4   use space() instead of malloc
   5
   6   Revision 1.4  2000/10/10 08:53:52  ivo
   7   include dmalloc.h header if DMALLOC defined
   8
   9   Revision 1.4  2000/10/10 08:04:34  ivo
  10   include dmalloc header id DMALLOC defined
  11
  12   Revision 1.3  1998/03/30 14:24:51  ivo
  13   use RNA package utils.h
  14
  15   Revision 1.2  1997/10/09  19:01:50  steve
  16   *** empty log message ***
  17
  18   Revision 1.1  1997/08/04 21:05:32  walter
  19   Initial revision
  20
  21 */
  22 /*
  23    (C) 1991 Kendall Bennett.
  24 */
  25
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include "utils.h"
  29 #include "list.h"
  30
  31 /*@unused@*/
  32 static char rcsid[] = "$Id: list.c,v 1.5 2003/07/14 13:36:58 ivo Exp $";
  33
  34 #define PUBLIC
  35 PUBLIC void *
  36 lst_newnode (int size)
  37 /****************************************************************************
  38 *
  39 * Function:     lst_newnode
  40 * Parameters:   size - Amount of memory to allocate for node
  41 * Returns:      Pointer to the allocated node's user space.
  42 *
  43 * Description:  Allocates the memory required for a node, adding a small
  44 *               header at the start of the node. We return a reference to
  45 *               the user space of the node, as if it had been allocated via
  46 *               malloc().
  47 *
  48 ****************************************************************************/
  49 {
  50   LST_BUCKET *node;
  51
  52   node = (LST_BUCKET *) space (size + sizeof (LST_BUCKET));
  53
  54   return LST_USERSPACE (node);  /* Return pointer to user space */
  55 }
  56
  57 PUBLIC void
  58 lst_freenode (void *node)
  59 /****************************************************************************
  60 *
  61 * Function:     lst_freenode
  62 * Parameters:   node - Node to free.
  63 *
  64 * Description:  Frees a node previously allocated with lst_newnode().
  65 *
  66 ****************************************************************************/
  67 {
  68   free (LST_HEADER (node));
  69 }
  70
  71 PUBLIC LIST *
  72 lst_init (void)
  73 /****************************************************************************
  74 *
  75 * Function:     lst_init
  76 * Returns:      Pointer to a newly created list.
  77 *
  78 * Description:  Initialises a list and returns a pointer to it.
  79 *
  80 ****************************************************************************/
  81 {
  82   LIST *l;
  83
  84   if ((l = (LIST *) space (sizeof (LIST))) != NULL)
  85     {
  86       l->count = 0;
  87       l->head = &(l->hz[0]);
  88       l->z = &(l->hz[1]);
  89       l->head->next = l->z->next = l->z;
  90     }
  91
  92   return l;
  93 }
  94
  95 PUBLIC void
  96 lst_kill (LIST * l, void (*freeNode) (void *node))
  97 /****************************************************************************
  98 *
  99 * Function:     lst_kill
 100 * Parameters:   l - List to kill
 101 *               freeNode - Pointer to user routine to free a node
 102 *
 103 * Description:  Kills the list l, by deleting all of the elements contained
 104 *               within the list one by one and then deleting the list
 105 *               itself. Note that we call the user supplied routine
 106 *               (*freeNode)() to free each list node. This allows the user
 107 *               program to perform any extra processing needed to kill each
 108 *               node (if each node contains pointers to other items on the
 109 *               heap for example). If no extra processing is required, just
 110 *               pass the address of lst_freenode(), ie:
 111 *
 112 *               lst_kill(myList,lst_freenode);
 113 *
 114 ****************************************************************************/
 115 {
 116   LST_BUCKET *n, *p;
 117
 118   n = l->head->next;
 119   while (n != l->z)
 120     {                           /* Free all nodes in list  */
 121       p = n;
 122       n = n->next;
 123       (*freeNode) (LST_USERSPACE (p));
 124     }
 125   free (l);                     /* Free the list itself    */
 126 }
 127
 128 PUBLIC void
 129 lst_insertafter (LIST * l, void *node, void *after)
 130 /****************************************************************************
 131 *
 132 * Function:     lst_insertafter
 133 * Parameters:   l - List to insert node into
 134 *               node - Pointer to user space of node to insert
 135 *               after - Pointer to user space of node to insert node after
 136 *
 137 * Description:  Inserts a new node into the list after the node 'after'. To
 138 *               insert a new node at the beginning of the list, user the
 139 *               macro LST_HEAD in place of 'after'. ie:
 140 *
 141 *               lst_insertafter(mylist,node,LST_HEAD(mylist));
 142 *
 143 ****************************************************************************/
 144 {
 145   LST_BUCKET *n = LST_HEADER (node), *a = LST_HEADER (after);
 146
 147   n->next = a->next;
 148   a->next = n;
 149   l->count++;
 150 }
 151
 152 PUBLIC void *
 153 lst_deletenext (LIST * l, void *node)
 154 /****************************************************************************
 155 *
 156 * Function:     lst_deletenext
 157 * Parameters:   l - List to delete node from.
 158 *               node - Node to delete the next node from
 159 * Returns:      Pointer to the deleted node's userspace.
 160 *
 161 * Description:  Removes the node AFTER 'node' from the list l.
 162 *
 163 ****************************************************************************/
 164 {
 165   LST_BUCKET *n = LST_HEADER (node);
 166
 167   node = LST_USERSPACE (n->next);
 168   n->next = n->next->next;
 169   l->count--;
 170   return node;
 171 }
 172
 173 PUBLIC void *
 174 lst_first (LIST * l)
 175 /****************************************************************************
 176 *
 177 * Function:     lst_first
 178 * Parameters:   l - List to obtain first node from
 179 * Returns:      Pointer to first node in list, NULL if list is empty.
 180 *
 181 * Description:  Returns a pointer to the user space of the first node in
 182 *               the list. If the list is empty, we return NULL.
 183 *
 184 ****************************************************************************/
 185 {
 186   LST_BUCKET *n;
 187
 188   n = l->head->next;
 189   return (n == l->z ? NULL : LST_USERSPACE (n));
 190 }
 191
 192 PUBLIC void *
 193 lst_next (void *prev)
 194 /****************************************************************************
 195 *
 196 * Function:     lst_next
 197 * Parameters:   prev - Previous node in list to obtain next node from
 198 * Returns:      Pointer to the next node in the list, NULL at end of list.
 199 *
 200 * Description:  Returns a pointer to the user space of the next node in the
 201 *               list given a pointer to the user space of the previous node.
 202 *               If we have reached the end of the list, we return NULL. The
 203 *               end of the list is detected when the next pointer of a node
 204 *               points back to itself, as does the dummy last node's next
 205 *               pointer. This enables us to detect the end of the list
 206 *               without needed access to the list data structure itself.
 207 *
 208 *               NOTE:   We do no checking to ensure that 'prev' is NOT a
 209 *                       NULL pointer.
 210 *
 211 ****************************************************************************/
 212 {
 213   LST_BUCKET *n = LST_HEADER (prev);
 214
 215   n = n->next;
 216   return (n == n->next ? NULL : LST_USERSPACE (n));
 217 }
 218
 219 /* Static globals required by merge()   */
 220
 221 static LST_BUCKET *z;
 222 static int (*cmp) (void *, void *);
 223
 224 static LST_BUCKET *
 225 merge (LST_BUCKET * a, LST_BUCKET * b, LST_BUCKET ** end)
 226 /****************************************************************************
 227 *
 228 * Function:     merge
 229 * Parameters:   a,b - Sublist's to merge
 230 * Returns:      Pointer to the merged sublists.
 231 *
 232 * Description:  Merges two sorted lists of nodes together into a single
 233 *               sorted list.
 234 *
 235 ****************************************************************************/
 236 {
 237   LST_BUCKET *c;
 238
 239   /* Go through the lists, merging them together in sorted order  */
 240
 241   c = z;
 242   while (a != z && b != z)
 243     {
 244       if ((*cmp) (LST_USERSPACE (a), LST_USERSPACE (b)) <= 0)
 245         {
 246           c->next = a;
 247           c = a;
 248           a = a->next;
 249         }
 250       else
 251         {
 252           c->next = b;
 253           c = b;
 254           b = b->next;
 255         }
 256     };
 257
 258   /* If one of the lists is not exhausted, then re-attach it to the end
 259    * of the newly merged list
 260    */
 261
 262   if (a != z)
 263     c->next = a;
 264   if (b != z)
 265     c->next = b;
 266
 267   /* Set *end to point to the end of the newly merged list        */
 268
 269   while (c->next != z)
 270     c = c->next;
 271   *end = c;
 272
 273   /* Determine the start of the merged lists, and reset z to point to
 274    * itself
 275    */
 276
 277   c = z->next;
 278   z->next = z;
 279   return c;
 280 }
 281
 282 PUBLIC void
 283 lst_mergesort (LIST * l, int (*cmp_func) (void *, void *))
 284 /****************************************************************************
 285 *
 286 * Function:     lst_mergesort
 287 * Parameters:   l - List to merge sort
 288 *               cmp_func - Function to compare two user spaces
 289 *
 290 * Description:  Mergesort's all the nodes in the list. 'cmp' must point to
 291 *               a comparison function that can compare the user spaces of
 292 *               two different nodes. 'cmp' should work the same as
 293 *               strcmp(), in terms of the values it returns.
 294 *
 295 ****************************************************************************/
 296 {
 297   int i, N;
 298   LST_BUCKET *a, *b;            /* Pointers to sublists to merge                */
 299   LST_BUCKET *c;                /* Pointer to end of sorted sublists            */
 300   LST_BUCKET *head;             /* Pointer to dummy head node for list          */
 301   LST_BUCKET *todo;             /* Pointer to sublists yet to be sorted         */
 302   LST_BUCKET *t;                /* Temporary                                                            */
 303
 304   /* Set up globals required by merge() and pointer to head       */
 305
 306   z = l->z;
 307   cmp = cmp_func;
 308   head = l->head;
 309
 310   for (N = 1, a = z; a != head->next; N = N + N)
 311     {
 312       todo = head->next;
 313       c = head;
 314       while (todo != z)
 315         {
 316
 317           /* Build first sublist to be merged, and splice from main list
 318            */
 319
 320           a = t = todo;
 321           for (i = 1; i < N; i++)
 322             t = t->next;
 323           b = t->next;
 324           t->next = z;
 325           t = b;
 326
 327           /* Build second sublist to be merged and splice from main list
 328            */
 329
 330           for (i = 1; i < N; i++)
 331             t = t->next;
 332           todo = t->next;
 333           t->next = z;
 334
 335           /* Merge the two sublists created, and set 'c' to point to the
 336            * end of the newly merged sublists.
 337            */
 338
 339           c->next = merge (a, b, &t);
 340           c = t;
 341         }
 342     }
 343 }
 344
 345 #ifdef LIST_TEST
 346
 347 /*---------------------------------------------------------------*/
 348 /*---------------------------------------------------------------*/
 349
 350 /* Simple program to test the list routines */
 351
 352 typedef struct
 353 {
 354   char name[40];
 355   int age;
 356 }
 357 REC;
 358
 359 /*---------------------------------------------------------------*/
 360
 361 int
 362 my_cmp (REC * r1, REC * r2)
 363 {
 364   return strcmp (r1->name, r2->name);
 365 }
 366
 367 /*---------------------------------------------------------------*/
 368
 369 void
 370 main (void)
 371 {
 372   LIST *list;
 373   int done = 0;
 374   REC *rec;
 375   char line[80];
 376
 377   list = lst_init ();
 378
 379   printf ("Type a list of names and ages. Empty line quits\n\n");
 380
 381   while (!done)
 382     {
 383       rec = lst_newnode (sizeof (REC));
 384       gets (line);
 385       if ((done = (line[0] == '\0')) != 1)
 386         {
 387           strcpy (rec->name, line);
 388           gets (line);
 389           rec->age = atoi (line);
 390           lst_insertafter (list, rec, LST_HEAD (list));
 391         }
 392     };
 393
 394   printf ("\nThe list you typed in was:\n\n");
 395
 396   for (rec = lst_first (list); rec; rec = lst_next (rec))
 397     printf ("Name: %s, Age: %d\n", rec->name, rec->age);
 398
 399   printf ("\nSorting the list...\n\n");
 400
 401   lst_mergesort (list, my_cmp);
 402
 403   for (rec = lst_first (list); rec; rec = lst_next (rec))
 404     printf ("Name: %s, Age: %d\n", rec->name, rec->age);
 405
 406   lst_kill (list, lst_freenode);
 407 }
 408
 409 /*---------------------------------------------------------------*/
 410
 411 #endif