Dogcows Code - chaz/rasterize/blob - list.h

   1
   2 /*
   3  * CS5600 University of Utah
   4  * Charles McGarvey
   5  * mcgarvey@eng.utah.edu
   6  */
   7
   8 #ifndef _LIST_H_
   9 #define _LIST_H_
  10
  11 #include "common.h"
  12
  13
  14 /*
  15  * A linked-list with a stack-like interface.
  16  * The value of each node can be any pointer.
  17  */
  18 struct list
  19 {
  20     void*           val;
  21     struct list*    link;
  22     void            (*dtor)(void*);
  23 };
  24 typedef struct list list_t;
  25
  26
  27 /*
  28  * Add a value to the list.  It will become the first item.
  29  * This is a O(1) operation.
  30  */
  31 INLINE_MAYBE
  32 void list_push2(list_t** l, void* value, void (*destructor)(void*))
  33 {
  34     list_t* n = (list_t*)mem_alloc(sizeof(list_t));
  35     n->val = value;
  36     n->link = *l;
  37     n->dtor = destructor;
  38     *l = n;
  39 }
  40
  41 /*
  42  * Add a value to the list with no destructor set.
  43  */
  44 INLINE_MAYBE
  45 void list_push(list_t** l, void* value)
  46 {
  47     list_push2(l, value, NULL);
  48 }
  49
  50
  51 /*
  52  * Create a new list with a single value.
  53  */
  54 INLINE_MAYBE
  55 list_t* list_new2(void* value, void (*destructor)(void*))
  56 {
  57     list_t* l = NULL;
  58     list_push2(&l, value, destructor);
  59     return l;
  60 }
  61
  62 /*
  63  * Create a new list with a single value without a destructor set.
  64  */
  65 INLINE_MAYBE
  66 list_t* list_new(void* value)
  67 {
  68     list_t* l = NULL;
  69     list_push2(&l, value, 0);
  70     return l;
  71 }
  72
  73
  74 /*
  75  * Remove a value from the front of the list.  If the node has dtor set, it
  76  * will be used to destroy the value.
  77  * This is a O(1) operation.
  78  */
  79 INLINE_MAYBE
  80 void list_pop(list_t** l)
  81 {
  82     list_t* n = (*l)->link;
  83
  84     if ((*l)->dtor) {
  85         (*l)->dtor((*l)->val);
  86     }
  87     mem_free(*l);
  88
  89     *l = n;
  90 }
  91
  92 /*
  93  * Destroy the list, freeing up all of its memory.
  94  * This is a O(n) operation.
  95  */
  96 INLINE_MAYBE
  97 void list_destroy(list_t** l)
  98 {
  99     while (*l) {
 100         list_pop(l);
 101     }
 102 }
 103
 104
 105 /*
 106  * Reverse the order of the items in the list.
 107  * This is a O(n) operation.
 108  */
 109 void list_reverse(list_t** l);
 110
 111
 112 #endif // _LIST_H_
 113