libsysfs/sysfs/dlist.h

   1 /*
   2  * dlist.h
   3  *
   4  * Copyright (C) 2003 Eric J Bohm
   5  *
   6  *  This library is free software; you can redistribute it and/or
   7  *  modify it under the terms of the GNU Lesser General Public
   8  *  License as published by the Free Software Foundation; either
   9  *  version 2.1 of the License, or (at your option) any later version.
  10  *
  11  *  This library is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14  *  Lesser General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU Lesser General Public
  17  *  License along with this library; if not, write to the Free Software
  18  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  19  *
  20  */
  21 #ifndef _DLIST_H_
  22 #define _DLIST_H_
  23
  24 /* Double linked list header.
  25
  26 * navigate your list with DLIST_PREV and DLIST_NEXT.  These are macros
  27 * so function call overhead is minimized.
  28
  29 * Supports perl style push, pop, shift, unshift list semantics.
  30
  31 * You allocate the data and give dlist the pointer.  If your data is
  32 * complex set the dlist->del_func to a an appropriate delete using
  33 * dlist_new_with_delete.  Your delete function must match
  34 (void * )(del(void *)
  35 *Otherwise dlist will just use free.
  36
  37 * NOTE: The small amount of pain involved in doing that allows us to
  38 * avoid copy in copy out semantics.
  39
  40 * Dlist uses an internal mark pointer to keep track of where you are
  41 * in the list.
  42
  43 * insert and delete take a directional parameter. Where direction
  44 * corresponds to the direction in which you want the list to go.
  45 * true direction corresponded to progressing forward in the last
  46 * false to regressing in the list.
  47 * so a dlist_insert(yourlist,item,1) will insert it after the mark
  48 * so a dlist_insert(yourlist,item,0) will insert it before the mark
  49 * any insert will move the mark to the new node regardless of the direction.
  50
  51 * Just use the dlist_(insert|delete)_(before|after) macros if you do not want
  52 * to think about it.
  53
  54 */
  55
  56 #include <stddef.h>
  57
  58 typedef struct dl_node {
  59   struct dl_node *prev;
  60   struct dl_node *next;
  61   void *data;
  62 } DL_node;
  63
  64 typedef struct dlist {
  65   DL_node *marker;
  66   unsigned long count;
  67   size_t data_size;
  68   void (*del_func)(void *);
  69   DL_node headnode;
  70   DL_node *head;
  71 } Dlist;
  72
  73 Dlist *dlist_new(size_t datasize);
  74 Dlist *dlist_new_with_delete(size_t datasize,void (*del_func)(void*));
  75 void *_dlist_mark_move(Dlist *list,int direction);
  76 void *dlist_mark(Dlist *);
  77 void dlist_start(Dlist *);
  78 void dlist_end(Dlist *);
  79 void dlist_move(struct dlist *source, struct dlist *dest, struct dl_node *target,int direction);
  80 void *dlist_insert(Dlist *,void *,int) ;
  81
  82 void *dlist_insert_sorted(struct dlist *list, void *new_elem, int (*sorter)(void *, void *));
  83
  84 void dlist_delete(Dlist *,int);
  85
  86 void dlist_push(Dlist *,void *);
  87
  88 void dlist_unshift(Dlist *,void *);
  89 void dlist_unshift_sorted(Dlist *,void *,int (*sorter)(void *, void *));
  90
  91 void *dlist_pop(Dlist *);
  92
  93 void *dlist_shift(Dlist *);
  94
  95 void dlist_destroy(Dlist *);
  96
  97 int _dlist_merge(struct dlist *listsource, struct dlist *listdest, unsigned int passcount, int (*compare)(void *, void *));
  98
  99 void *dlist_find_custom(struct dlist *list, void *target, int (*comp)(void *, void *));
 100
 101 void dlist_sort_custom(struct dlist *list, int (*compare)(void *, void *));
 102
 103
 104 void _dlist_swap(struct dlist *list, struct dl_node *a, struct dl_node *b);
 105
 106 void dlist_transform(struct dlist *list, void (*node_operation)(void *));
 107
 108
 109 /*
 110  * _dlist_remove is for internal use only
 111  * _dlist_mark_move is for internal use only
 112  */
 113 void *_dlist_remove(struct dlist *,struct dl_node *,int );
 114 void *_dlist_insert_dlnode(struct dlist *list,struct dl_node *new_node,int direction);
 115
 116 #define dlist_prev(A) _dlist_mark_move((A),0)
 117 #define dlist_next(A) _dlist_mark_move((A),1)
 118
 119 #define dlist_insert_before(A,B) dlist_insert((A),(B),0)
 120 #define dlist_insert_after(A,B) dlist_insert((A),(B),1)
 121
 122 #define dlist_delete_before(A) dlist_delete((A),0)
 123 #define dlist_delete_after(A) dlist_delete((A),1)
 124
 125 /**
 126  * provide for loop header which iterates the mark from start to end
 127  * list: the dlist pointer, use dlist_mark(list) to get iterator
 128  */
 129 #define dlist_for_each(list) \
 130         for(dlist_start(list),dlist_next(list); \
 131                 (list)->marker!=(list)->head;dlist_next(list))
 132
 133 /**
 134  * provide for loop header which iterates the mark from end to start
 135  * list: the dlist pointer, use dlist_mark(list) to get iterator
 136  */
 137 #define dlist_for_each_rev(list) \
 138         for(dlist_end(list),dlist_prev(list); \
 139                 (list)->marker!=(list)->head;dlist_prev(list))
 140
 141 /**
 142  * provide for loop header which iterates through the list without moving mark
 143  * list: the dlist_pointer
 144  * iterator: dl_node pointer to iterate
 145  */
 146 #define dlist_for_each_nomark(list,iterator) \
 147         for((iterator)=(list)->head->next; (iterator)!=(list)->head; \
 148                 (iterator)=(iterator)->next)
 149
 150 /**
 151  * provide for loop header which iterates through the list without moving mark
 152  * in reverse
 153  * list: the dlist_pointer
 154  * iterator: dl_node pointer to iterate
 155  */
 156 #define dlist_for_each_nomark_rev(list,iterator) \
 157         for((iterator)=(list)->head->prev; (iterator)!=(list)->head; \
 158                 (iterator)=(iterator)->prev)
 159 /**
 160  * provide for loop header which iterates through the list providing a
 161  * data iterator
 162  * list: the dlist pointer
 163  * data_iterator: the pointer of type datatype to iterate
 164  * datatype:  actual type of the contents in the dl_node->data
 165  */
 166
 167 #define dlist_for_each_data(list,data_iterator,datatype) \
 168         for(dlist_start(list), (data_iterator)=(datatype *) dlist_next(list); \
 169         (list)->marker!=(list)->head;(data_iterator)=(datatype *) dlist_next(list))
 170
 171 /**
 172  * provide for loop header which iterates through the list providing a
 173  * data iterator in reverse
 174  * list: the dlist pointer
 175  * data_iterator: the pointer of type datatype to iterate
 176  * datatype:  actual type of the contents in the dl_node->data
 177  */
 178 #define dlist_for_each_data_rev(list,data_iterator,datatype) \
 179         for(dlist_end(list), (data_iterator)=(datatype *) dlist_prev(list); \
 180         (list)->marker!=(list)->head;(data_iterator)=(datatype *) dlist_prev(list))
 181
 182 /**
 183  * provide for loop header which iterates through the list providing a
 184  * data iterator without moving the mark
 185  * list: the dlist pointer
 186  * iterator: the dl_node pointer to iterate
 187  * data_iterator: the pointer of type datatype to iterate
 188  * datatype:  actual type of the contents in the dl_node->data
 189  */
 190
 191 #define dlist_for_each_data_nomark(list,iterator,data_iterator,datatype) \
 192         for((iterator)=(list)->head->next, (data_iterator)=(datatype *) (iterator)->data; \
 193         (iterator)!=(list)->head;(iterator)=(iterator)->next,(data_iterator)=(datatype *) (iterator))
 194
 195 /**
 196  * provide for loop header which iterates through the list providing a
 197  * data iterator in reverse without moving the mark
 198  * list: the dlist pointer
 199  * iterator: the dl_node pointer to iterate
 200  * data_iterator: the pointer of type datatype to iterate
 201  * datatype:  actual type of the contents in the dl_node->data
 202  */
 203 #define dlist_for_each_data_nomark_rev(list,iterator, data_iterator,datatype) \
 204         for((iterator)=(list)->head->prev, (data_iterator)=(datatype *) (iterator)->data; \
 205         (iterator)!=(list)->head;(iterator)=(iterator)->prev,(data_iterator)=(datatype *) (iterator))
 206
 207 #endif /* _DLIST_H_ */