libsysfs/dlist.c

   1 /*
   2  * dlist.c
   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 021110307 USA
  19  *
  20  */
  21
  22
  23 /* Double linked list implementation.
  24
  25  * You allocate the data and give dlist the pointer.
  26  * If your data is complex set the dlist->del_func to a an appropriate
  27  * delete function.  Otherwise dlist will just use free.
  28
  29 */
  30 #include "dlist.h"
  31
  32 /*
  33  * Return pointer to node at marker.
  34  * else null if no nodes.
  35  */
  36
  37 inline void *dlist_mark(Dlist *list)
  38 {
  39   if(list->marker!=NULL)
  40     return(list->marker->data);
  41   else
  42     return(NULL);
  43 }
  44
  45 /*
  46  * Set marker to start.
  47  */
  48
  49 inline void dlist_start(Dlist *list)
  50 {
  51   list->marker=list->head;
  52 }
  53
  54 /*
  55  * Set marker to end.
  56  */
  57
  58 inline void dlist_end(Dlist *list)
  59 {
  60   list->marker=list->head;
  61 }
  62
  63 /* internal use function
  64  * quickie inline to consolidate the marker movement logic
  65  * in one place
  66  *
  67  * when direction true it moves marker after
  68  * when direction false it moves marker before.
  69  * return pointer to data at new marker
  70  * if nowhere to move the marker in desired direction return null
  71  */
  72 inline void *_dlist_mark_move(Dlist *list,int direction)
  73 {
  74   if(direction)
  75     {
  76       if( list->marker->next!=NULL)
  77         list->marker=list->marker->next;
  78       else
  79         return(NULL);
  80     }
  81   else
  82     {
  83       if( list->marker->prev!=NULL)
  84         list->marker=list->marker->prev;
  85       else
  86         return(NULL);
  87     }
  88   if(list->marker!=list->head)
  89     return(list->marker->data);
  90   else
  91     return(NULL);
  92 }
  93
  94 /*
  95  * Create new linked list to store nodes of datasize.
  96  * return null if list cannot be created.
  97  */
  98 Dlist *dlist_new(size_t datasize)
  99 {
 100   Dlist *list=NULL;
 101   if((list=malloc(sizeof(Dlist))))
 102     {
 103       list->marker=NULL;
 104       list->count=0L;
 105       list->data_size=datasize;
 106       list->del_func=free;
 107       list->head=&(list->headnode);
 108       list->head->prev=NULL;
 109       list->head->next=NULL;
 110       list->head->data=NULL;
 111     }
 112   return(list);
 113 }
 114
 115 /*
 116  * Create new linked list to store nodes of datasize set list
 117  * data node delete function to the passed in del_func
 118  * return null if list cannot be created.
 119  */
 120 Dlist *dlist_new_with_delete(size_t datasize,void (*del_func)(void*))
 121 {
 122   Dlist *list=NULL;
 123   list=dlist_new(datasize);
 124   if(list!=NULL)
 125     list->del_func=del_func;
 126   return(list);
 127 }
 128
 129
 130 /*
 131  * remove marker node from list
 132  * call data_delete function on data if registered.
 133  * otherwise call free.
 134  * when direction true it moves marker after
 135  * when direction false it moves marker before.
 136  * free marker node
 137  * return nothing.
 138  */
 139 void dlist_delete(Dlist *list,int direction)
 140 {
 141   if((list->marker != list->head)&&(list->marker!=NULL))
 142     {
 143       DL_node *corpse;
 144       corpse=list->marker;
 145       _dlist_mark_move(list,direction);
 146       if(list->head->next==corpse)
 147         list->head->next=corpse->next;
 148       if(list->head->prev==corpse)
 149         list->head->prev=corpse->prev;
 150       if(corpse->prev!=NULL) //should be impossible
 151         corpse->prev->next=corpse->next;
 152       if(corpse->next!=NULL) //should be impossible
 153         corpse->next->prev=corpse->prev;
 154       list->del_func(corpse->data);
 155       list->count--;
 156       free(corpse);
 157     }
 158 }
 159
 160 /*
 161  * Insert node containing data at marker.
 162  * If direction true it inserts after.
 163  * If direction false it inserts before.
 164  * move marker to inserted node
 165  * return pointer to inserted node
 166  */
 167 void *dlist_insert(Dlist *list,void *data,int direction)
 168 {
 169   DL_node *new_node=NULL;
 170   if(list==NULL || data==NULL)
 171     return(NULL);
 172   if(list->marker==NULL) //in case the marker ends up unset
 173     list->marker=list->head;
 174   if((new_node=malloc(sizeof(DL_node))))
 175     {
 176       new_node->data=data;
 177       new_node->prev=NULL;
 178       new_node->next=NULL;
 179       list->count++;
 180       if(list->head->next==NULL) //no l
 181         {
 182           list->head->next=list->head->prev=new_node;
 183           new_node->prev=list->head;
 184           new_node->next=list->head;
 185         }
 186       else if(direction)
 187         {
 188           new_node->next=list->marker->next;
 189           new_node->prev=list->marker;
 190           list->marker->next->prev=new_node;
 191           list->marker->next=new_node;
 192         }
 193       else
 194         {
 195           new_node->prev=list->marker->prev;
 196           new_node->next=list->marker;
 197           list->marker->prev->next=new_node;
 198           list->marker->prev=new_node;
 199         }
 200         list->marker=new_node;
 201     }
 202   else
 203     {
 204       return(NULL);
 205     }
 206   return(list->marker->data);
 207 }
 208
 209 /*
 210  * Remove DL_node from list without deallocating data.
 211  * if marker == killme .
 212  *  when direction true it moves marker after
 213  *  when direction false it moves marker before.
 214  * to previous if there is no next.
 215  */
 216 void *_dlist_remove(Dlist *list,DL_node *killme,int direction)
 217 {
 218   if(killme!=NULL)
 219     {
 220       void *killer_data=killme->data;
 221       // take care of head and marker pointers.
 222       if(list->marker==killme)
 223         _dlist_mark_move(list,direction);
 224       if(killme ==list->head->next)
 225         list->head->next=killme->next;
 226       if(killme==list->head->prev)
 227         list->head->prev=killme->prev;
 228       // remove from list
 229       if(killme->prev !=NULL)
 230         killme->prev->next=killme->next;
 231       if(killme->next !=NULL)
 232         killme->next->prev=killme->prev;
 233       list->count--;
 234       free(killme);
 235       return(killer_data);
 236     }
 237   else
 238     return (NULL);
 239 }
 240
 241
 242 /*
 243  * Insert node containing data after end.
 244  */
 245 void dlist_push(Dlist *list,void *data)
 246 {
 247   list->marker=list->head->prev;
 248   dlist_insert(list,data,1);
 249 }
 250
 251 /*
 252  * Insert node containing data at start.
 253  */
 254
 255 void dlist_unshift(Dlist *list,void *data)
 256
 257 {
 258   list->marker=list->head->next;
 259   dlist_insert(list,data,0);
 260 }
 261
 262
 263 /*
 264  * Remove end node from list.
 265  * Return pointer to data in removed node.
 266  * Null if no nodes.
 267  */
 268
 269 void *dlist_pop(Dlist *list)
 270 {
 271   return(_dlist_remove(list,list->head->prev,0));
 272 }
 273
 274 /*
 275  * Remove start node from list.
 276  * Return pointer to data in removed node.
 277  * Null if no nodes.
 278  */
 279
 280 void *dlist_shift(Dlist *list)
 281 {
 282   return(_dlist_remove(list,list->head->next,1));
 283 }
 284
 285
 286 /*
 287  * destroy the list freeing all memory
 288  */
 289
 290
 291 void dlist_destroy(Dlist *list)
 292 {
 293   if(list !=NULL)
 294     {
 295       dlist_start(list);
 296       dlist_next(list);
 297       while (dlist_mark(list)) {
 298               dlist_delete(list,1);
 299       }
 300       free(list);
 301     }
 302 }
 303
 304 /**
 305  *  Return void pointer to list_data element matching comp function criteria
 306  *  else null
 307  *  Does not move the marker.
 308  */
 309
 310 void *dlist_find_custom(struct dlist *list, void *target, int (*comp)(void *, void *))
 311 {
 312         /* test the comp function on each node */
 313         struct dl_node *nodepointer;
 314         dlist_for_each_nomark(list,nodepointer)
 315                 if(comp(target,nodepointer->data))
 316                         return(nodepointer->data);
 317         return(NULL);
 318 }
 319
 320 /**
 321  * Apply the node_operation function to each data node in the list
 322  */
 323 void dlist_transform(struct dlist *list, void (*node_operation)(void *))
 324 {
 325         struct dl_node *nodepointer;
 326         dlist_for_each_nomark(list,nodepointer)
 327                 node_operation(nodepointer->data);
 328 }
 329
 330 /**
 331  * insert new into list in sorted order
 332  * sorter function in form int sorter(new,ith)
 333  *       must return 1 for when new should go before ith
 334  *       else 0
 335  * return pointer to inserted node
 336  * NOTE: assumes list is already sorted
 337  */
 338 void *dlist_insert_sorted(struct dlist *list, void *new, int (*sorter)(void *, void *))
 339 {
 340         for(dlist_start(list),dlist_next(list); \
 341                 list->marker!=list->head && !sorter(new,list->marker->data);dlist_next(list));
 342         return(dlist_insert_before(list,new));
 343 }