shared/LL.h

   1 #ifndef LL_H
   2 #define LL_H
   3
   4 /***********************************************************************
   5   Linked Lists!  (Doubly-Linked Lists)
   6   *******************************************************************
   7
   8   To create a list, do the following:
   9
  10     LinkedList *list;
  11     list = LL_new();
  12     if(!list) handle_an_error();
  13
  14   The list can hold any type of data.  You will need to typecast your
  15   datatype to a "void *", though.  So, to add something to the list,
  16   the following would be a good way to start:
  17
  18     typedef struct my_data {
  19       char string[16];
  20       int number;
  21     } my_data;
  22
  23     my_data *thingie;
  24
  25     for(something to something else)
  26     {
  27       thingie = malloc(sizeof(my_data));
  28       LL_AddNode(list, (void *)thingie);  // typecast it to a "void *"
  29     }
  30
  31     For errors, the general convention is that "0" means success, and
  32     a negative number means failure.  Check LL.c to be sure, though.
  33
  34   *******************************************************************
  35
  36   To change the data, try this:
  37
  38     thingie = (my_data *)LL_Get(list);  // typecast it back to "my_data"
  39     thingie->number = another_number;
  40
  41   You don't need to "Put" the data back, but it doesn't hurt anything.
  42
  43     LL_Put(list, (void *)thingie);
  44
  45   However, if you want to point the node's data somewhere else, you'll
  46   need to get the current data first, keep track of it, then set the data
  47   to a new location:
  48
  49     my_data * old_thingie, new_thingie;
  50
  51     old_thingie = (my_data *)LL_Get(list);
  52     LL_Put(list, (void *)new_thingie);
  53
  54     // Now, do something with old_thingie.  (maybe, free it?)
  55
  56   Or, you could just delete the node entirely and then add a new one:
  57
  58     my_data * thingie;
  59
  60     thingie = (my_data *)LL_DeleteNode(list);
  61     free(thingie);
  62
  63     thingie->number = 666;
  64
  65     LL_InsertNode(list, (void *)thingie);
  66
  67   *******************************************************************
  68
  69   To operate on each list item, try this:
  70
  71     LL_Rewind(list);
  72     do {
  73       my_data = (my_data *)LL_Get(list);
  74       ... do something to it ...
  75     } while(LL_Next(list) == 0);
  76
  77   *******************************************************************
  78
  79   You can also treat the list like a stack, or a queue.  Just use the
  80   following functions:
  81
  82     LL_Push()      // Regular stack stuff: add, remove, peek, rotate
  83     LL_Pop()
  84     LL_Top()
  85     LL_Roll()
  86
  87     LL_Shift()     // Other end of the stack (like in perl)
  88     LL_Unshift()
  89     LL_Look()
  90     LL_UnRoll()
  91
  92     LL_Enqueue()   // Standard queue operations
  93     LL_Dequeue()
  94
  95   There are also other goodies, like sorting and searching.
  96
  97   *******************************************************************
  98
  99   Array-like operations will come later, to allow numerical indexing:
 100
 101     LL_nGet(list, 3);
 102     LL_nSwap(list, 6, 13);
 103     LL_nPut(list, -4, data);   // Puts item at 4th place from the end..
 104
 105   More ideas for later:
 106
 107     LL_MoveNode(list, amount);  // Slides a node to another spot in the list
 108     -- LL_MoveNode(list, -1); // moves a node back one toward the head
 109
 110     ... um, more?
 111
 112   *******************************************************************
 113   That's about it, for now...  Be sure to free the list when you're done!
 114 ***********************************************************************/
 115
 116 // See LL.c for more detailed descriptions of these functions.
 117
 118 typedef struct LL_node {
 119         struct LL_node *next, *prev;
 120         void *data;
 121 } LL_node;
 122
 123 typedef struct LinkedList {
 124         LL_node head, tail;
 125         LL_node *current;
 126 } LinkedList;
 127
 128 // Creates a new list...
 129 LinkedList *LL_new ();
 130 // Destroying lists...
 131 int LL_Destroy (LinkedList * list);
 132 int LL_node_Destroy (LL_node * node);
 133 int LL_node_Unlink (LL_node * node);
 134 int LL_node_DestroyData (LL_node * node);
 135
 136 // Returns to the beginning of the list...
 137 int LL_Rewind (LinkedList * list);
 138 // Goes to the end of the list...
 139 int LL_End (LinkedList * list);
 140 // Go to the next node
 141 int LL_Next (LinkedList * list);
 142 // Go to the previous node
 143 int LL_Prev (LinkedList * list);
 144
 145 // Data manipulation
 146 void *LL_Get (LinkedList * list);
 147 int LL_Put (LinkedList * list, void *data);
 148 // Don't use these next two unless you really know what you're doing.
 149 LL_node *LL_GetNode (LinkedList * list);
 150 int LL_PutNode (LinkedList * list, LL_node * node);
 151
 152 void *LL_GetFirst (LinkedList * list);  // gets data from first node
 153 void *LL_GetNext (LinkedList * list);     //            ... next node
 154 void *LL_GetPrev (LinkedList * list);     //            ... prev node
 155 void *LL_GetLast (LinkedList * list);     //            ... last node
 156
 157 int LL_AddNode (LinkedList * list, void *add);  // Adds node AFTER current one
 158 int LL_InsertNode (LinkedList * list, void *add);       // Adds node BEFORE current one
 159 // Removes a node from the link; returns the data from the node
 160 void *LL_DeleteNode (LinkedList * list);
 161 // Removes a specific node...
 162 void *LL_Remove (LinkedList * list, void *data);
 163
 164 // Stack operations
 165 int LL_Push (LinkedList * list, void *add);     // Add node to end of list
 166 void *LL_Pop (LinkedList * list);                 // Remove node from end of list
 167 void *LL_Top (LinkedList * list);                 // Peek at end node
 168 void *LL_Shift (LinkedList * list);       // Remove node from start of list
 169 void *LL_Look (LinkedList * list);                // Peek at first node
 170 int LL_Unshift (LinkedList * list, void *add);  // Add node to beginning of list
 171
 172 int LL_Roll (LinkedList * list);                  // Make first node last
 173 int LL_UnRoll (LinkedList * list);                // Roll the other way...
 174
 175 // Queue operations...
 176 //int LL_Enqueue(LinkedList *list, void *add);
 177 //void * LL_Dequeue(LinkedList *list);
 178 //////////////////////////////////////////////////////////////////////
 179 // Queue operations...
 180 #define LL_Enqueue(list,add) LL_Push(list,add)
 181
 182 #define LL_Dequeue(list) LL_Shift(list)
 183
 184 int LL_PriorityEnqueue (LinkedList * list, void *add, int compare (void *, void *));
 185
 186 int LL_SwapNodes (LL_node * one, LL_node * two);        // Switch two nodes positions...
 187 int LL_nSwapNodes (int one, int two);   // Switch two nodes positions...
 188
 189 int LL_Length (LinkedList * list);                // Returns # of nodes in entire list
 190
 191 // Searching...
 192 void *LL_Find (LinkedList * list, int compare (void *, void *), void *value);
 193
 194 // Array operation...
 195 void *LL_GetByIndex (LinkedList * list, int index);  // gets the nth node, 0 being the first
 196
 197 // Sorts the list...
 198 int LL_Sort (LinkedList * list, int compare (void *, void *));
 199
 200 // Debugging...
 201 void LL_dprint (LinkedList * list);
 202
 203 #endif