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 /* internal use only
 211  * Insert dl_node  at marker.
 212  * If direction true it inserts after.
 213  * If direction false it inserts before.
 214  * move marker to inserted node
 215  * return pointer to inserted node
 216  */
 217 void *_dlist_insert_dlnode(struct dlist *list,struct dl_node *new_node,int direction)
 218 {
 219   if(list==NULL || new_node==NULL)
 220     return(NULL);
 221   if(list->marker==NULL) //in case the marker ends up unset
 222     list->marker=list->head;
 223   list->count++;
 224   if(list->head->next==NULL)
 225     {
 226       list->head->next=list->head->prev=new_node;
 227       new_node->prev=list->head;
 228       new_node->next=list->head;
 229     }
 230   else if(direction)
 231     {
 232       new_node->next=list->marker->next;
 233       new_node->prev=list->marker;
 234       list->marker->next->prev=new_node;
 235       list->marker->next=new_node;
 236     }
 237   else
 238     {
 239       new_node->prev=list->marker->prev;
 240       new_node->next=list->marker;
 241       list->marker->prev->next=new_node;
 242       list->marker->prev=new_node;
 243     }
 244   list->marker=new_node;
 245   return(list->marker);
 246 }
 247
 248
 249
 250 /*
 251  * Remove DL_node from list without deallocating data.
 252  * if marker == killme .
 253  *  when direction true it moves marker after
 254  *  when direction false it moves marker before.
 255  * to previous if there is no next.
 256  */
 257 void *_dlist_remove(Dlist *list,DL_node *killme,int direction)
 258 {
 259   if(killme!=NULL)
 260     {
 261       void *killer_data=killme->data;
 262       // take care of head and marker pointers.
 263       if(list->marker==killme)
 264         _dlist_mark_move(list,direction);
 265       if(killme ==list->head->next)
 266         list->head->next=killme->next;
 267       if(killme==list->head->prev)
 268         list->head->prev=killme->prev;
 269       // remove from list
 270       if(killme->prev !=NULL)
 271         killme->prev->next=killme->next;
 272       if(killme->next !=NULL)
 273         killme->next->prev=killme->prev;
 274       list->count--;
 275       free(killme);
 276       return(killer_data);
 277     }
 278   else
 279     return (NULL);
 280 }
 281
 282 /*
 283  * move dl_node from source to dest
 284  * if marker == target .
 285  *  when direction true it moves marker after
 286  *  when direction false it moves marker before.
 287  * to previous if there is no next.
 288  */
 289 void dlist_move(struct dlist *source, struct dlist *dest, struct dl_node *target,int direction)
 290 {
 291
 292   if(target!=NULL)
 293     {
 294       if(target==source->head)
 295         {
 296           //not even going to try
 297         }
 298       else
 299         {
 300           // take care of head and marker pointers.
 301           if(source->marker==target)
 302             _dlist_mark_move(source,direction);
 303           if(target ==source->head->next)
 304             source->head->next=target->next;
 305           if(target==source->head->prev)
 306             source->head->prev=target->prev;
 307           // remove from list
 308           if(source->count==1)
 309             {
 310               target->prev=NULL;
 311               target->next=NULL;
 312               source->head->next=NULL;
 313               source->head->prev=NULL;
 314             }
 315           else
 316             {
 317               if(target->prev !=NULL)
 318                 target->prev->next=target->next;
 319               if(target->next !=NULL)
 320                 target->next->prev=target->prev;
 321               target->prev=NULL;
 322               target->next=NULL;
 323             }
 324           source->count--;
 325           _dlist_insert_dlnode(dest,target,direction);
 326         }
 327     }
 328 }
 329
 330
 331 /*
 332  * Insert node containing data after end.
 333  */
 334 void dlist_push(Dlist *list,void *data)
 335 {
 336   list->marker=list->head->prev;
 337   dlist_insert(list,data,1);
 338 }
 339
 340 /*
 341  * Insert node containing data at start.
 342  */
 343
 344 void dlist_unshift(Dlist *list,void *data)
 345
 346 {
 347   list->marker=list->head->next;
 348   dlist_insert(list,data,0);
 349 }
 350
 351 void dlist_unshift_sorted(Dlist *list, void *data,
 352                         int (*sorter)(void *new_elem, void *old_elem))
 353 {
 354         if (list->count == 0)
 355                 dlist_unshift(list, data);
 356         else {
 357                 list->marker=list->head->next;
 358                 dlist_insert_sorted(list, data, sorter);
 359         }
 360 }
 361
 362 /*
 363  * Remove end node from list.
 364  * Return pointer to data in removed node.
 365  * Null if no nodes.
 366  */
 367
 368 void *dlist_pop(Dlist *list)
 369 {
 370   return(_dlist_remove(list,list->head->prev,0));
 371 }
 372
 373 /*
 374  * Remove start node from list.
 375  * Return pointer to data in removed node.
 376  * Null if no nodes.
 377  */
 378
 379 void *dlist_shift(Dlist *list)
 380 {
 381   return(_dlist_remove(list,list->head->next,1));
 382 }
 383
 384
 385 /*
 386  * destroy the list freeing all memory
 387  */
 388
 389
 390 void dlist_destroy(Dlist *list)
 391 {
 392   if(list !=NULL)
 393     {
 394       dlist_start(list);
 395       dlist_next(list);
 396       while (dlist_mark(list)) {
 397               dlist_delete(list,1);
 398       }
 399       free(list);
 400     }
 401 }
 402
 403 /**
 404  *  Return void pointer to list_data element matching comp function criteria
 405  *  else null
 406  *  Does not move the marker.
 407  */
 408
 409 void *dlist_find_custom(struct dlist *list, void *target, int (*comp)(void *, void *))
 410 {
 411         /* test the comp function on each node */
 412         struct dl_node *nodepointer;
 413         dlist_for_each_nomark(list,nodepointer)
 414                 if(comp(target,nodepointer->data))
 415                         return(nodepointer->data);
 416         return(NULL);
 417 }
 418
 419 /**
 420  * Apply the node_operation function to each data node in the list
 421  */
 422 void dlist_transform(struct dlist *list, void (*node_operation)(void *))
 423 {
 424         struct dl_node *nodepointer;
 425         dlist_for_each_nomark(list,nodepointer)
 426                 node_operation(nodepointer->data);
 427 }
 428
 429 /**
 430  * insert new into list in sorted order
 431  * sorter function in form int sorter(new,ith)
 432  *       must return 1 for when new should go before ith
 433  *       else 0
 434  * return pointer to inserted node
 435  * NOTE: assumes list is already sorted
 436  */
 437 void *dlist_insert_sorted(struct dlist *list, void *new, int (*sorter)(void *, void *))
 438 {
 439         for(dlist_start(list),dlist_next(list); \
 440                 list->marker!=list->head && !sorter(new,list->marker->data);dlist_next(list));
 441         return(dlist_insert_before(list,new));
 442 }
 443
 444 /*
 445  * NOTE: internal use only
 446  */
 447 int _dlist_merge(struct dlist *listsource, struct dlist *listdest, unsigned int passcount, int (*compare)(void *, void *))
 448 {
 449
 450   struct dl_node *l1head;
 451   struct dl_node *l2head;
 452   struct dl_node *target;
 453   unsigned int l1count=0;
 454   unsigned int l2count=0;
 455   unsigned int mergecount=0;
 456   while(listsource->count>0)
 457     {
 458       l1head=listsource->head->next;
 459       l2head=l1head;
 460       while((l1count<passcount)&&(l2head!=listsource->head))
 461         {
 462           l2head=l2head->next;
 463           l1count++;
 464         }
 465       // so now we have two lists to merge
 466
 467       if(l2head==listsource->head)
 468         {// l2count
 469           l2count=0;
 470         }
 471       else
 472         {
 473           l2count=passcount;
 474         }
 475       while(l1count>0 || l2count>0)
 476         {
 477           mergecount++;
 478           if((l2count>0)&&(l1count>0))
 479             {
 480               // we have things to merge
 481               int result=compare(l1head->data,l2head->data);
 482               if(result>0)
 483                 {
 484                   // move from l2
 485                   target=l2head;
 486                   l2head=l2head->next;
 487                   dlist_move(listsource,listdest,target,1);
 488                   l2count--;
 489                   if(l2head==listsource->head)
 490                     l2count=0;
 491                 }
 492               else
 493                 {
 494                   // move from l1
 495                   target=l1head;
 496                   l1head=l1head->next;
 497                   dlist_move(listsource,listdest,target,1);
 498                   l1count--;
 499                 }
 500             }
 501           else if(l1count>0)
 502             {
 503               // only have l1 to work with
 504               while(l1count>0)
 505                 {
 506                   target=l1head;
 507                   l1head=l1head->next;
 508                   dlist_move(listsource,listdest,target,1);
 509                   l1count--;
 510                 }
 511             }
 512           else if(l2count>0)
 513             {
 514               // only have l2 to work with
 515               while(l2count>0)
 516                 {
 517                   if(l2head==listsource->head)
 518                     {
 519                       l2count=0;
 520                     }
 521                   else
 522                     {
 523                       target=l2head;
 524                       l2head=l2head->next;
 525                       dlist_move(listsource,listdest,target,1);
 526                       l2count--;
 527                     }
 528                 }
 529             }
 530           else
 531             { //nothing left and this should be unreachable
 532             }
 533         }
 534     }
 535   return(mergecount);
 536 }
 537
 538 /**
 539  * mergesort the list based on compare
 540  * compare function in form int sorter(void * a,void * b)
 541  *       must return >0 for a after b
 542  *       must return <0 for a before b
 543  *       else 0
 544
 545  * NOTE: mergesort changes the mark pointer
 546  */
 547 void dlist_sort_custom(struct dlist *list, int (*compare)(void *, void *))
 548 {
 549
 550   struct dlist *listsource, *listdest, *swap;
 551   struct dlist *templist;
 552   unsigned int passcount = 1;
 553   unsigned int mergecount = 1;
 554
 555   dlist_start(list);
 556   templist = dlist_new(list->data_size);
 557
 558   // do nothing if there isn't anything to sort
 559   listsource = list;
 560   listdest = templist;
 561   if(listsource->count<2)
 562     { //nothing to do
 563       return;
 564     }
 565   else
 566     {
 567       while(mergecount>0)
 568         {
 569           mergecount=_dlist_merge(listsource, listdest, passcount, compare);
 570           if(mergecount>1)
 571             {
 572               passcount=passcount*2;
 573               //start new pass
 574               swap=listsource;
 575               listsource=listdest;
 576               listdest=swap;
 577             }
 578         }
 579     }
 580   // now put the input list pointers right
 581   // list pointers = newlist pointers
 582   // including the forward and next nodes prev and back pointers
 583   if(list->count==0)
 584     {//copy
 585       list->marker = listdest->marker;
 586       list->count = listdest->count;
 587       list->data_size = listdest->data_size;
 588       list->del_func = listdest->del_func;
 589       list->head->prev = listdest->head->prev;
 590       list->head->next = listdest->head->next;
 591       list->head->data = listdest->head->data;
 592       list->head->next->prev=list->head;
 593       list->head->prev->next=list->head;
 594       templist->head->next=NULL;
 595       templist->head->prev=NULL;
 596       templist->count=0;
 597     }
 598   else
 599     {// no need to copy
 600
 601     }
 602
 603   dlist_destroy(templist);
 604 }
 605
 606
 607
 608 /* internal use function
 609    swaps elements a and b
 610    No sense in juggling node pointers when we can just swap the data pointers
 611 */
 612
 613 void _dlist_swap(struct dlist *list, struct dl_node *a, struct dl_node *b)
 614 {
 615
 616   void *swap=a->data;
 617   a->data=b->data;
 618   b->data=swap;
 619
 620 }
 621