tools/tesh2/src/list.c

   1
   2 #include <list.h>
   3 #include <errno.h>
   4 #include <stdlib.h>
   5
   6 #define __DEFAULT_BLOCK_CAPACITY 128
   7
   8 static allocator_t
   9 allocator = NULL;
  10
  11 static int
  12 ref = 0;
  13
  14 static link_t
  15 link_new(void* item)
  16 {
  17         link_t link;
  18
  19         if(!item)
  20         {
  21                 errno = EINVAL;
  22                 return NULL;
  23         }
  24
  25         if(!(link = (link_t)allocator_alloc(allocator)))
  26                 return NULL;
  27
  28         link->next = link->prev = NULL;
  29         link->item = item;
  30
  31         return link;
  32 }
  33
  34 static int
  35 link_free(link_t* ref)
  36 {
  37         if(!(*ref))
  38                 return  EINVAL;
  39
  40         allocator_dealloc(allocator, *ref);
  41         *ref = NULL;
  42
  43         return 0;
  44 }
  45
  46 static link_t
  47 search(list_t list, void* item)
  48 {
  49         register link_t cur = list->next;
  50
  51         while(cur != ((link_t)&(list->item)))
  52         {
  53                 if(cur->item == item)
  54                         return cur;
  55
  56                 cur = cur->next;
  57         }
  58
  59         errno = ESRCH;
  60         return NULL;
  61 }
  62
  63
  64
  65 list_t
  66 list_new(fn_finalize_t fn_finalize)
  67 {
  68         list_t list = (list_t)calloc(1,sizeof(s_list_t));
  69
  70         if(!list)
  71                 return NULL;
  72
  73         if(!allocator)
  74         {
  75                 if(!(allocator = allocator_new(__DEFAULT_BLOCK_CAPACITY, sizeof(s_link_t), NULL)))
  76                 {
  77                         free(list);
  78                         return NULL;
  79                 }
  80         }
  81
  82         list->next = list->prev = list->cur = (link_t)(&(list->item));
  83         list->fn_finalize = fn_finalize;
  84         list->pos = -1;
  85         list->size = 0;
  86
  87         ref++;
  88
  89         return list;
  90 }
  91
  92 int
  93 list_rewind(list_t list)
  94 {
  95         if(!list)
  96         {
  97                 errno = EINVAL;
  98                 return 0;
  99         }
 100
 101         if(!list->size)
 102         {
 103                 errno = EAGAIN;
 104                 return 0;
 105         }
 106
 107         list->cur = list->next;
 108         list->pos = 0;
 109
 110         return 1;
 111 }
 112
 113 int
 114 list_unwind(list_t list)
 115 {
 116         if(!list)
 117         {
 118                 errno = EINVAL;
 119                 return 0;
 120         }
 121
 122         if(!list->size)
 123         {
 124                 errno = EAGAIN;
 125                 return 0;
 126         }
 127
 128         list->cur = list->prev;
 129         list->pos = list->size - 1;
 130
 131         return 1;
 132 }
 133
 134 int
 135 list_clear(list_t list)
 136 {
 137         int rv;
 138
 139         if(!list)
 140                 return EINVAL;
 141
 142         if(!list->size)
 143                 return EAGAIN;
 144
 145         if(list->fn_finalize)
 146         {
 147                 void* item;
 148
 149                 while((item = list_pop_back(list)))
 150                         if(0 != (rv = (*(list->fn_finalize))(&item)))
 151                                 return rv;
 152         }
 153         else
 154                 while(list_pop_back(list));
 155
 156         return 0;
 157 }
 158
 159 int
 160 list_free(list_t* list_ptr)
 161 {
 162         if(!(*list_ptr))
 163                 return EINVAL;
 164
 165         if((*list_ptr)->size)
 166                 list_clear(*list_ptr);
 167
 168         if(--ref)
 169                 allocator_free(&allocator);
 170
 171         free(*list_ptr);
 172         *list_ptr = NULL;
 173
 174         return 0;
 175 }
 176
 177 int
 178 list_push_front(list_t list, void* item)
 179 {
 180         link_t what, where, next;
 181
 182     if(!list || !item)
 183         return EINVAL;
 184
 185     if(!(what = (link_t)link_new(item)))
 186         return errno;
 187
 188     where = (link_t)(&(list->item));
 189     next = where->next;
 190
 191     what->prev = where;
 192     what->next = next;
 193     next->prev = what;
 194     where->next = what;
 195
 196     list->size++;
 197
 198     /* the iteration functions are now not permited */
 199     list->pos = -1;
 200     list->cur = (link_t)(&(list->item));
 201
 202     return 0;
 203 }
 204
 205 int
 206 list_push_back(list_t list, void* item)
 207 {
 208         link_t what, where, prev;
 209
 210         if(!list || !item)
 211         return EINVAL;
 212
 213     if(!(what = (link_t)link_new(item)))
 214         return errno;
 215
 216     where = (link_t)(&(list->item));
 217     prev = where->prev;
 218         what->next = where;
 219         what->prev = prev;
 220     prev->next = what;
 221     where->prev = what;
 222
 223     list->size++;
 224
 225     /* the iteration functions are now not permited */
 226     list->pos = -1;
 227     list->cur = (link_t)(&(list->item));
 228
 229     return 0;
 230 }
 231
 232 int
 233 list_insert_after(list_t list, void* what, void* where)
 234 {
 235     link_t __what, __where, __next;
 236
 237     if(!list || !what || !where)
 238         return EINVAL;
 239
 240     if(!(__what = link_new(what)))
 241         return errno;
 242
 243     if((__where = search(list, where)))
 244         return errno;
 245
 246     __next = __where->next;
 247
 248     __what->prev = __where;
 249     __what->next = __next;
 250     __next->prev = __what;
 251     __where->next = __what;
 252
 253     list->size++;
 254
 255     return 0;
 256 }
 257
 258 int
 259 list_insert_before(list_t list, void* what, void* where)
 260 {
 261     link_t __what, __where, __prev;
 262
 263      if(!list || !what || !where)
 264         return EINVAL;
 265
 266     if(!(__what = link_new(what)))
 267         return errno;
 268
 269     if((__where = search(list, where)))
 270         return errno;
 271
 272     __prev = __where->prev;
 273
 274         __what->next = __where;
 275     __what->prev = __prev;
 276     __prev->next = __what;
 277     __where->prev = __what;
 278
 279     list->size++;
 280
 281     return 0;
 282 }
 283
 284
 285 void*
 286 list_pop_back(list_t list)
 287 {
 288         link_t link, next, prev;
 289         void* item;
 290
 291         if(!list)
 292         {
 293                 errno = EINVAL;
 294                 return NULL;
 295         }
 296
 297         if(!list->size)
 298         {
 299                 errno = EAGAIN;
 300                 return NULL;
 301         }
 302
 303         link = list->prev;
 304
 305         next = link->next;
 306     prev = link->prev;
 307     prev->next = next;
 308     next->prev = prev;
 309
 310     list->size--;
 311
 312     item = link->item;
 313
 314     link_free((link_t*)&link);
 315
 316     /* the iteration functions are now not permited */
 317     list->pos = -1;
 318     list->cur = (link_t)(&(list->item));
 319
 320     return item;
 321 }
 322
 323 void*
 324 list_pop_front(list_t list)
 325 {
 326
 327         link_t link, next, prev;
 328         void* item;
 329
 330         if(!list)
 331         {
 332                 errno = EINVAL;
 333                 return NULL;
 334         }
 335
 336         if(!list->size)
 337         {
 338                 errno = EAGAIN;
 339                 return NULL;
 340         }
 341
 342         link = list->next;
 343
 344         next = link->next;
 345     prev = link->prev;
 346     prev->next = next;
 347     next->prev = prev;
 348
 349     list->size--;
 350
 351     item = link->item;
 352     link_free((link_t*)&link);
 353
 354     /* the iteration functions are now not permited */
 355     list->pos = -1;
 356     list->cur = (link_t)(&(list->item));
 357
 358     return item;
 359 }
 360
 361 int
 362 list_remove(list_t list, void* item)
 363 {
 364         link_t link, next, prev;
 365
 366         if(!list || !item)
 367                 return EINVAL;
 368
 369         if(!list->size)
 370                 return EAGAIN;
 371
 372         if(!(link = search(list, item)))
 373                 return errno;
 374
 375         next = link->next;
 376     prev = link->prev;
 377     prev->next = next;
 378     next->prev = prev;
 379
 380     list->size--;
 381
 382     /* the iteration functions are now not permited */
 383     list->pos = -1;
 384     list->cur = (link_t)(&(list->item));
 385
 386     return link_free((link_t*)&link);
 387 }
 388
 389 int
 390 list_get_size(list_t list)
 391 {
 392         if(!list)
 393         {
 394                 errno = EINVAL;
 395                 return -1;
 396         }
 397
 398         return list->size;
 399 }
 400
 401 int
 402 list_contains(list_t list, void* item)
 403 {
 404         register link_t cur;
 405
 406         if(!list || !item)
 407         {
 408                 errno = EINVAL;
 409                 return 0;
 410         }
 411
 412         if(!list->size)
 413         {
 414                 errno = EAGAIN;
 415                 return 0;
 416         }
 417
 418         cur = list->next;
 419
 420         while(cur != ((link_t)&(list->item)))
 421         {
 422                 if(cur->item == item)
 423                         return 1;
 424
 425                 cur = cur->next;
 426         }
 427
 428         return 0;
 429 }
 430
 431 int
 432 list_is_empty(list_t list)
 433 {
 434         if(!list)
 435         {
 436                 errno = EINVAL;
 437                 return 0;
 438         }
 439
 440         return !list->size;
 441 }
 442
 443 int
 444 list_is_autodelete(list_t list)
 445 {
 446         if(!list)
 447         {
 448                 errno = EINVAL;
 449                 return 0;
 450         }
 451
 452         return NULL != list->fn_finalize;
 453 }
 454
 455 int
 456 list_move_next(list_t list)
 457 {
 458         if(!list)
 459         {
 460                 errno = EINVAL;
 461                 return 0;
 462         }
 463
 464         if(!list->size || (-1 == list->pos))
 465         {
 466                 errno = EAGAIN;
 467                 return 0;
 468         }
 469
 470         if(list->cur != (link_t)(&(list->item)))
 471         {
 472                 list->cur = list->cur->next;
 473                 list->pos++;
 474                 return 1;
 475         }
 476
 477         list->pos = -1;
 478         errno = ERANGE;
 479         return 0;
 480 }
 481
 482 void*
 483 list_get(list_t list)
 484 {
 485         if(!list)
 486         {
 487                 errno = EINVAL;
 488                 return NULL;
 489         }
 490
 491         if(!list->size || (-1 == list->pos))
 492         {
 493                 errno = EAGAIN;
 494                 return NULL;
 495         }
 496
 497         return list->cur->item;
 498 }
 499
 500 void*
 501 list_set(list_t list, void* item)
 502 {
 503         void* prev_item;
 504
 505         if(!list || !item)
 506         {
 507                 errno = EINVAL;
 508                 return NULL;
 509         }
 510
 511         if(!list->size  || (-1 == list->pos))
 512         {
 513                 errno = EAGAIN;
 514                 return NULL;
 515         }
 516
 517         prev_item = list->cur->item;
 518         list->cur->item = item;
 519
 520         return prev_item;
 521 }
 522
 523 void*
 524 list_get_at(list_t list, int pos)
 525 {
 526         register link_t cur;
 527
 528         if(!list)
 529         {
 530                 errno = EINVAL;
 531                 return NULL;
 532         }
 533
 534         if(pos < 0 || pos >= list->size)
 535         {
 536                 errno = ERANGE;
 537                 return NULL;
 538         }
 539
 540         if(!list->size)
 541         {
 542                 errno = EAGAIN;
 543                 return NULL;
 544         }
 545
 546         cur = list->next;
 547
 548         while(pos--)
 549                 cur = cur->next;
 550
 551
 552         return cur->item;
 553 }
 554
 555 void*
 556 list_set_at(list_t list, int pos, void* item)
 557 {
 558         register link_t cur;
 559         void* prev_item;
 560
 561         if(!list || !item)
 562         {
 563                 errno = EINVAL;
 564                 return NULL;
 565         }
 566
 567         if(pos < 0 || pos >= list->size)
 568         {
 569                 errno = ERANGE;
 570                 return NULL;
 571         }
 572
 573         if(!list->size)
 574         {
 575                 errno = EAGAIN;
 576                 return NULL;
 577         }
 578
 579         cur = list->next;
 580
 581         while(pos--)
 582                 cur = cur->next;
 583
 584         prev_item = cur->item;
 585         cur->item = item;
 586
 587         return prev_item;
 588
 589 }
 590
 591 int
 592 list_move_prev(list_t list)
 593 {
 594         if(!list)
 595         {
 596                 errno = EINVAL;
 597                 return 0;
 598         }
 599
 600         if(!list->size  || (-1 == list->pos))
 601         {
 602                 errno = EAGAIN;
 603                 return 0;
 604         }
 605
 606         if(list->cur != (link_t)(&(list->item)))
 607         {
 608                 list->cur = list->cur->prev;
 609                 list->pos--;
 610                 return 1;
 611         }
 612
 613         list->pos = -1;
 614         errno = ERANGE;
 615         return 0;
 616 }
 617
 618 static int
 619 seek_set(list_t list, int offset)
 620 {
 621         if(offset > list->size)
 622                 return EINVAL;
 623
 624         list_rewind(list);
 625
 626         while(offset--)
 627                 list_move_next(list);
 628
 629         return 0;
 630 }
 631
 632 static int
 633 seek_end(list_t list, int offset)
 634 {
 635         if(offset > list->size)
 636                 return EINVAL;
 637
 638         list_unwind(list);
 639
 640         while(offset--)
 641                 list_move_prev(list);
 642
 643         return 0;
 644 }
 645
 646
 647 static int
 648 seek_cur(list_t list, int offset)
 649 {
 650         if(list->cur == list->next)
 651         {
 652                 /* we are at the begin of the list */
 653                 seek_set(list, offset);
 654         }
 655         else if(list->cur == list->prev)
 656         {
 657                 /* we are at the end of the list */
 658                 seek_end(list, offset);
 659         }
 660         else
 661         {
 662                 if(offset > (list->size - list->pos + 1))
 663                         return EINVAL;
 664
 665                 while(offset--)
 666                         list_move_next(list);
 667
 668         }
 669
 670         return 0;
 671 }
 672
 673 int
 674 list_seek(list_t list, int offset, int whence)
 675 {
 676         if(!list)
 677                 return EINVAL;
 678
 679         if(!list->size)
 680                 return EAGAIN;
 681
 682         switch(whence)
 683         {
 684                 case SEEK_SET :
 685                 return seek_set(list, offset);
 686
 687                 case SEEK_CUR :
 688                 return seek_cur(list, offset);
 689
 690                 case SEEK_END :
 691                 return seek_end(list, offset);
 692
 693         }
 694
 695         return EINVAL;
 696 }
 697
 698 int
 699 list_tell(list_t list)
 700 {
 701         if(!list)
 702         {
 703                 errno = EINVAL;
 704                 return -1;
 705         }
 706
 707         if(!list->size || (-1 == list->pos))
 708         {
 709                 errno = EAGAIN;
 710                 return -1;
 711         }
 712
 713         return list->pos;
 714 }
 715
 716 int
 717 list_getpos(list_t list, int* pos)
 718 {
 719
 720         if(!list || !pos)
 721         {
 722                 errno = EINVAL;
 723                 return 0;
 724         }
 725
 726         if(!list->size || (-1 == list->pos))
 727         {
 728                 errno = EAGAIN;
 729                 return 0;
 730         }
 731
 732         *pos = list->pos;
 733         return 1;
 734 }
 735
 736 int
 737 list_setpos(list_t list, int pos)
 738 {
 739         if(!list)
 740         {
 741                 errno = EINVAL;
 742                 return 0;
 743         }
 744
 745         if(pos < 0 || pos >= list->size)
 746         {
 747                 errno = ERANGE;
 748                 return 0;
 749         }
 750
 751         if(!list->size)
 752         {
 753                 errno = EAGAIN;
 754                 return 0;
 755         }
 756
 757         list->cur = list->next;
 758         list->pos = pos;
 759
 760         while(pos--)
 761                 list->cur = list->cur->next;
 762
 763         return 1;
 764 }
 765
 766
 767 void*
 768 list_get_front(list_t list)
 769 {
 770         if(!list)
 771         {
 772                 errno = EINVAL;
 773                 return NULL;
 774         }
 775
 776         if(!list->size)
 777         {
 778                 errno = EAGAIN;
 779                 return NULL;
 780         }
 781
 782         return list->next->item;
 783 }
 784
 785
 786 void*
 787 list_get_back(list_t list)
 788 {
 789         if(!list)
 790         {
 791                 errno = EINVAL;
 792                 return NULL;
 793         }
 794
 795         if(!list->size)
 796         {
 797                 errno = EAGAIN;
 798                 return NULL;
 799         }
 800
 801         return list->prev->item;
 802 }