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