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