include/list.h

   1 /*****************************************************************************
   2  *  $Id: list.h 2899 2002-12-11 19:00:36Z dun $
   3  *****************************************************************************
   4  *  Copyright (C) 2001-2002 The Regents of the University of California.
   5  *  Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER).
   6  *  Written by Chris Dunlap <cdunlap@llnl.gov>.
   7  *
   8  *  This file is from LSD-Tools, the LLNL Software Development Toolbox.
   9  *
  10  *  LSD-Tools is free software; you can redistribute it and/or modify it under
  11  *  the terms of the GNU General Public License as published by the Free
  12  *  Software Foundation; either version 2 of the License, or (at your option)
  13  *  any later version.
  14  *
  15  *  LSD-Tools is distributed in the hope that it will be useful, but WITHOUT
  16  *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17  *  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  18  *  more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License along
  21  *  with LSD-Tools; if not, write to the Free Software Foundation, Inc.,
  22  *  59 Temple Place, Suite 330, Boston, MA  02111-1307  USA.
  23  *****************************************************************************/
  24
  25
  26 #ifndef LSD_LIST_H
  27 #define LSD_LIST_H
  28
  29
  30 /***********
  31  *  Notes  *
  32  ***********/
  33 /*
  34  *  If NDEBUG is not defined, internal debug code will be enabled.  This is
  35  *  intended for development use only and production code should define NDEBUG.
  36  *
  37  *  If WITH_LSD_FATAL_ERROR_FUNC is defined, the linker will expect to
  38  *  find an external lsd_fatal_error(file,line,mesg) function.  By default,
  39  *  lsd_fatal_error(file,line,mesg) is a macro definition that outputs an
  40  *  error message to stderr.  This macro may be redefined to invoke another
  41  *  routine instead.
  42  *
  43  *  If WITH_LSD_NOMEM_ERROR_FUNC is defined, the linker will expect to
  44  *  find an external lsd_nomem_error(file,line,mesg) function.  By default,
  45  *  lsd_nomem_error(file,line,mesg) is a macro definition that returns NULL.
  46  *  This macro may be redefined to invoke another routine instead.
  47  *
  48  *  If WITH_PTHREADS is defined, these routines will be thread-safe.
  49  */
  50
  51
  52 /****************
  53  *  Data Types  *
  54  ****************/
  55
  56 typedef struct list * List;
  57 /*
  58  *  List opaque data type.
  59  */
  60
  61 typedef struct listIterator * ListIterator;
  62 /*
  63  *  List Iterator opaque data type.
  64  */
  65
  66 typedef void (*ListDelF) (void *x);
  67 /*
  68  *  Function prototype to deallocate data stored in a list.
  69  *    This function is responsible for freeing all memory associated
  70  *    with an item, including all subordinate items (if applicable).
  71  */
  72
  73 typedef int (*ListCmpF) (void *x, void *y);
  74 /*
  75  *  Function prototype for comparing two items in a list.
  76  *  Returns less-than-zero if (x<y), zero if (x==y), and
  77  *    greather-than-zero if (x>y).
  78  */
  79
  80 typedef int (*ListFindF) (void *x, void *key);
  81 /*
  82  *  Function prototype for matching items in a list.
  83  *  Returns non-zero if (x==key); o/w returns zero.
  84  */
  85
  86 typedef int (*ListForF) (void *x, void *arg);
  87 /*
  88  *  Function prototype for operating on each item in a list.
  89  *  Returns less-than-zero on error.
  90  */
  91
  92
  93 /*******************************
  94  *  General-Purpose Functions  *
  95  *******************************/
  96
  97 List list_create (ListDelF f);
  98 /*
  99  *  Creates and returns a new empty list, or lsd_nomem_error() on failure.
 100  *  The deletion function [f] is used to deallocate memory used by items
 101  *    in the list; if this is NULL, memory associated with these items
 102  *    will not be freed when the list is destroyed.
 103  *  Note: Abandoning a list without calling list_destroy() will result
 104  *    in a memory leak.
 105  */
 106
 107 void list_destroy (List l);
 108 /*
 109  *  Destroys list [l], freeing memory used for list iterators and the
 110  *    list itself; if a deletion function was specified when the list
 111  *    was created, it will be called for each item in the list.
 112  */
 113
 114 int list_is_empty (List l);
 115 /*
 116  *  Returns non-zero if list [l] is empty; o/w returns zero.
 117  */
 118
 119 int list_count (List l);
 120 /*
 121  *  Returns the number of items in list [l].
 122  */
 123
 124
 125 /***************************
 126  *  List Access Functions  *
 127  ***************************/
 128
 129 void * list_append (List l, void *x);
 130 /*
 131  *  Inserts data [x] at the end of list [l].
 132  *  Returns the data's ptr, or lsd_nomem_error() if insertion failed.
 133  */
 134
 135 void * list_prepend (List l, void *x);
 136 /*
 137  *  Inserts data [x] at the beginning of list [l].
 138  *  Returns the data's ptr, or lsd_nomem_error() if insertion failed.
 139  */
 140
 141 void * list_find_first (List l, ListFindF f, void *key);
 142 /*
 143  *  Traverses list [l] using [f] to match each item with [key].
 144  *  Returns a ptr to the first item for which the function [f]
 145  *    returns non-zero, or NULL if no such item is found.
 146  *  Note: This function differs from list_find() in that it does not require
 147  *    a list iterator; it should only be used when all list items are known
 148  *    to be unique (according to the function [f]).
 149  */
 150
 151 int list_delete_all (List l, ListFindF f, void *key);
 152 /*
 153  *  Traverses list [l] using [f] to match each item with [key].
 154  *  Removes all items from the list for which the function [f] returns
 155  *    non-zero; if a deletion function was specified when the list was
 156  *    created, it will be called to deallocate each item being removed.
 157  *  Returns a count of the number of items removed from the list.
 158  */
 159
 160 int list_for_each (List l, ListForF f, void *arg);
 161 /*
 162  *  For each item in list [l], invokes the function [f] with [arg].
 163  *  Returns a count of the number of items on which [f] was invoked.
 164  *  If [f] returns <0 for a given item, the iteration is aborted and the
 165  *    function returns the negative of that item's position in the list.
 166  */
 167
 168 void list_sort (List l, ListCmpF f);
 169 /*
 170  *  Sorts list [l] into ascending order according to the function [f].
 171  *  Note: Sorting a list resets all iterators associated with the list.
 172  *  Note: The sort algorithm is stable.
 173  */
 174
 175
 176 /****************************
 177  *  Stack Access Functions  *
 178  ****************************/
 179
 180 void * list_push (List l, void *x);
 181 /*
 182  *  Pushes data [x] onto the top of stack [l].
 183  *  Returns the data's ptr, or lsd_nomem_error() if insertion failed.
 184  */
 185
 186 void * list_pop (List l);
 187 /*
 188  *  Pops the data item at the top of the stack [l].
 189  *  Returns the data's ptr, or NULL if the stack is empty.
 190  */
 191
 192 void * list_peek (List l);
 193 /*
 194  *  Peeks at the data item at the top of the stack (or head of the queue) [l].
 195  *  Returns the data's ptr, or NULL if the stack (or queue) is empty.
 196  *  Note: The item is not removed from the list.
 197  */
 198
 199
 200 /****************************
 201  *  Queue Access Functions  *
 202  ****************************/
 203
 204 void * list_enqueue (List l, void *x);
 205 /*
 206  *  Enqueues data [x] at the tail of queue [l].
 207  *  Returns the data's ptr, or lsd_nomem_error() if insertion failed.
 208  */
 209
 210 void * list_dequeue (List l);
 211 /*
 212  *  Dequeues the data item at the head of the queue [l].
 213  *  Returns the data's ptr, or NULL if the queue is empty.
 214  */
 215
 216
 217 /*****************************
 218  *  List Iterator Functions  *
 219  *****************************/
 220
 221 ListIterator list_iterator_create (List l);
 222 /*
 223  *  Creates and returns a list iterator for non-destructively traversing
 224  *    list [l], or lsd_nomem_error() on failure.
 225  */
 226
 227 void list_iterator_reset (ListIterator i);
 228 /*
 229  *  Resets the list iterator [i] to start traversal at the beginning
 230  *    of the list.
 231  */
 232
 233 void list_iterator_destroy (ListIterator i);
 234 /*
 235  *  Destroys the list iterator [i]; list iterators not explicitly destroyed
 236  *    in this manner will be destroyed when the list is deallocated via
 237  *    list_destroy().
 238  */
 239
 240 void * list_next (ListIterator i);
 241 /*
 242  *  Returns a ptr to the next item's data,
 243  *    or NULL once the end of the list is reached.
 244  *  Example: i=list_iterator_create(i); while ((x=list_next(i))) {...}
 245  */
 246
 247 void * list_insert (ListIterator i, void *x);
 248 /*
 249  *  Inserts data [x] immediately before the last item returned via list
 250  *    iterator [i]; once the list iterator reaches the end of the list,
 251  *    insertion is made at the list's end.
 252  *  Returns the data's ptr, or lsd_nomem_error() if insertion failed.
 253  */
 254
 255 void * list_find (ListIterator i, ListFindF f, void *key);
 256 /*
 257  *  Traverses the list from the point of the list iterator [i]
 258  *    using [f] to match each item with [key].
 259  *  Returns a ptr to the next item for which the function [f]
 260  *    returns non-zero, or NULL once the end of the list is reached.
 261  *  Example: i=list_iterator_reset(i); while ((x=list_find(i,f,k))) {...}
 262  */
 263
 264 void * list_remove (ListIterator i);
 265 /*
 266  *  Removes from the list the last item returned via list iterator [i]
 267  *    and returns the data's ptr.
 268  *  Note: The client is responsible for freeing the returned data.
 269  */
 270
 271 int list_delete (ListIterator i);
 272 /*
 273  *  Removes from the list the last item returned via list iterator [i];
 274  *    if a deletion function was specified when the list was created,
 275  *    it will be called to deallocate the item being removed.
 276  *  Returns a count of the number of items removed from the list
 277  *    (ie, '1' if the item was removed, and '0' otherwise).
 278  */
 279
 280
 281 #endif /* !LSD_LIST_H */