oscam-llist.c

   1
   2 /* singularly linked-list */
   3
   4 #include "globals.h"
   5 #include "oscam-garbage.h"
   6 #include "oscam-lock.h"
   7 #include "oscam-string.h"
   8
   9 extern char *LOG_LIST;
  10
  11 /*
  12   Locking rules:
  13
  14   mutex lock is needed when...
  15   1. l->initial + l->last is modified/accessed
  16   2. LL_NODE nxt modified/accessed
  17
  18
  19 */
  20
  21 #ifdef WITH_DEBUG
  22 static int8_t chk_debuglog(LLIST *l)
  23 {
  24         return (l && l->lock.name != LOG_LIST);
  25 }
  26 #endif
  27
  28 static void _destroy(LLIST *l)
  29 {
  30         if(!l) { return; }
  31         if(!l->flag++)
  32         {
  33                 cs_writelock(__func__, &l->lock); //just getting sure noone is using it
  34                 cs_writeunlock(__func__, &l->lock);
  35
  36                 cs_lock_destroy(__func__, &l->lock);
  37                 add_garbage(l);
  38         }
  39 }
  40
  41 LLIST *ll_create(const char *name)
  42 {
  43         LLIST *l;
  44         if(!cs_malloc(&l, sizeof(LLIST)))
  45                 { return NULL; }
  46         cs_lock_create(__func__, &l->lock, name, 5000);
  47         return l;
  48 }
  49
  50 void ll_destroy(LLIST **pl)
  51 {
  52         LLIST *l = *pl;
  53         if(!l || l->flag) { return; }
  54         *pl = NULL;
  55         ll_clear(l);
  56
  57         _destroy(l);
  58 }
  59
  60 void ll_destroy_data(LLIST **pl)
  61 {
  62         LLIST *l = *pl;
  63         if(!l) { return; }
  64         *pl = NULL;
  65         ll_clear_data(l);
  66
  67         _destroy(l);
  68 }
  69
  70
  71 void ll_destroy_free_data(LLIST **pl)
  72 {
  73         LLIST *l = *pl;
  74         if(!l||l->flag) { return; }
  75         *pl = NULL;
  76
  77         //*********************************
  78         cs_writelock(__func__, &l->lock);
  79
  80         LL_NODE *n=l->initial, *nxt;
  81         while(n)
  82         {
  83                 nxt = n->nxt;
  84                 NULLFREE(n->obj);
  85                 NULLFREE(n);
  86                 n = nxt;
  87         }
  88         l->version++;
  89         l->count = 0;
  90         l->initial = 0;
  91         l->last = 0;
  92         cs_writeunlock(__func__, &l->lock);
  93         //**********************************
  94
  95         if(!l->flag++)
  96         {
  97                 cs_writelock(__func__, &l->lock); //just getting sure noone is using it
  98                 cs_writeunlock(__func__, &l->lock);
  99
 100                 cs_lock_destroy(__func__, &l->lock);
 101                 NULLFREE(l);
 102         }
 103 }
 104
 105
 106 /* Internal iteration function. Make sure that you don't have a lock and that it and it->l are set. */
 107 static void *ll_iter_next_nolock(LL_ITER *it)
 108 {
 109         if(it->l->version != it->ll_version)
 110         {
 111 #ifdef WITH_DEBUG
 112                 if(chk_debuglog(it->l))
 113                         { cs_log_dbg(D_TRACE, "list changed, searching new position"); }
 114 #endif
 115
 116                 LL_NODE *ptr;
 117                 //cs_readlock(__func__, &it->l->lock);
 118                 if(!it->cur && !it->prv)
 119                 {
 120                         it->cur = it->l->initial;
 121                 }
 122                 else
 123                 {
 124                         for(ptr = it->l->initial; ptr; ptr = ptr->nxt)
 125                         {
 126                                 if(ptr == it->cur)
 127                                 {
 128                                         it->prv = ptr;
 129                                         it->cur = ptr->nxt;
 130                                         break;
 131                                 }
 132                         }
 133                         if(!ptr)
 134                         {
 135                                 ll_iter_reset(it); // restart iteration
 136                                 it->cur = it->l->initial;
 137                         }
 138                 }
 139                 it->ll_version = it->l->version;
 140                 //cs_readunlock(__func__, &it->l->lock);
 141
 142                 if(it->cur)
 143                         { return it->cur->obj; }
 144
 145         }
 146         else
 147         {
 148                 if(it->cur)
 149                 {
 150                         it->prv = it->cur;
 151                         it->cur = it->cur->nxt;
 152                 }
 153                 else if(it->l->initial && !it->prv)
 154                         { it->cur = it->l->initial; }
 155
 156                 if(it->cur)
 157                         { return it->cur->obj; }
 158         }
 159         return NULL;
 160 }
 161
 162 static void ll_clear_int(LLIST *l, int32_t clear_data)
 163 {
 164         if(!l || l->flag) { return; }
 165
 166         cs_writelock(__func__, &l->lock);
 167
 168         LL_NODE *n = l->initial, *nxt;
 169         while(n)
 170         {
 171                 nxt = n->nxt;
 172                 if(clear_data)
 173                         { add_garbage(n->obj); }
 174                 add_garbage(n);
 175                 n = nxt;
 176         }
 177         l->version++;
 178         l->count = 0;
 179         l->initial = 0;
 180         l->last = 0;
 181         cs_writeunlock(__func__, &l->lock);
 182 }
 183
 184 void ll_clear(LLIST *l)
 185 {
 186         ll_clear_int(l, 0);
 187 }
 188
 189
 190 void ll_clear_data(LLIST *l)
 191 {
 192         ll_clear_int(l, 1);
 193 }
 194
 195 /* Appends to the list. Do not call this from outside without having a lock! */
 196 static LL_NODE *ll_append_nolock(LLIST *l, void *obj)
 197 {
 198         if(l && obj && !l->flag)
 199         {
 200                 LL_NODE *new;
 201                 if(!cs_malloc(&new, sizeof(LL_NODE)))
 202                         { return NULL; }
 203                 new->obj = obj;
 204
 205                 if(l->last)
 206                         { l->last->nxt = new; }
 207                 else
 208                         { l->initial = new; }
 209                 l->last = new;
 210
 211                 l->count++;
 212                 return new;
 213         }
 214
 215         return NULL;
 216 }
 217
 218 LL_NODE *ll_append(LLIST *l, void *obj)
 219 {
 220         if(l && obj && !l->flag)
 221         {
 222                 cs_writelock(__func__, &l->lock);
 223
 224                 LL_NODE *n = ll_append_nolock(l, obj);
 225                 cs_writeunlock(__func__, &l->lock);
 226                 return n;
 227         }
 228         return NULL;
 229 }
 230
 231 LL_NODE *ll_prepend(LLIST *l, void *obj)
 232 {
 233         if(l && obj && !l->flag)
 234         {
 235                 LL_NODE *new;
 236                 if(!cs_malloc(&new, sizeof(LL_NODE)))
 237                         { return NULL; }
 238                 new->obj = obj;
 239
 240                 cs_writelock(__func__, &l->lock);
 241
 242                 new->nxt = l->initial;
 243
 244                 l->initial = new;
 245                 if(!l->last)
 246                         { l->last = l->initial; }
 247                 l->count++;
 248                 cs_writeunlock(__func__, &l->lock);
 249
 250                 return new;
 251         }
 252
 253         return NULL;
 254 }
 255
 256 LL_ITER ll_iter_create(LLIST *l)
 257 {
 258         LL_ITER it;
 259         memset(&it, 0, sizeof(it));
 260         it.l = l;
 261         if(it.l)
 262                 { it.ll_version = it.l->version; }
 263         return it;
 264 }
 265
 266
 267 void *ll_iter_next(LL_ITER *it)
 268 {
 269         if(it && it->l && !it->l->flag)
 270         {
 271                 cs_readlock(__func__, &it->l->lock);
 272                 void *res = ll_iter_next_nolock(it);
 273                 cs_readunlock(__func__, &it->l->lock);
 274                 return res;
 275         }
 276         return NULL;
 277 }
 278
 279 void *ll_iter_remove_nolock(LL_ITER *it)
 280 {
 281         void *obj = NULL;
 282         if(it)
 283         {
 284                 LL_NODE *del = it->cur;
 285                 if(del)
 286                 {
 287                         obj = del->obj;
 288                         LL_NODE *prv = it->prv;
 289                         if(it->ll_version != it->l->version || !prv)    // List has been modified so it->prv might be wrong!
 290                         {
 291                                 LL_NODE *n = it->l->initial;
 292                                 prv = NULL;
 293                                 while(n && n != del)
 294                                 {
 295                                         prv = n;
 296                                         n = n->nxt;
 297                                 }
 298                                 if(n != del)
 299                                         { return NULL; }
 300                         }
 301
 302                         if(prv)
 303                                 { prv->nxt = del->nxt; }
 304                         else
 305                                 { it->l->initial = del->nxt; }
 306                         if(!it->l->initial)
 307                                 { it->l->last = NULL; }
 308                         else if(del == it->l->last)
 309                                 { it->l->last = prv; }
 310
 311                         it->cur = it->l->initial;
 312                         it->prv = NULL;
 313                         if(prv != NULL)
 314                         {
 315                                 while(it->cur && it->cur != prv)
 316                                 {
 317                                         it->prv = it->cur;
 318                                         it->cur = it->cur->nxt;
 319                                 }
 320                         }
 321                         else
 322                                 { it->cur = NULL; }
 323                         it->l->count--;
 324                         it->ll_version = ++it->l->version;
 325
 326                         add_garbage(del);
 327                 }
 328         }
 329         return obj;
 330 }
 331
 332 void *ll_iter_next_remove(LL_ITER *it)
 333 {
 334         if(it && it->l && !it->l->flag)
 335         {
 336                 cs_writelock(__func__, &it->l->lock);
 337                 void *res = ll_iter_next_nolock(it);
 338                 ll_iter_remove_nolock(it);
 339                 cs_writeunlock(__func__, &it->l->lock);
 340                 return res;
 341         }
 342         return NULL;
 343 }
 344
 345 void *ll_iter_move(LL_ITER *it, int32_t offset)
 346 {
 347         if(it && it->l && !it->l->flag)
 348         {
 349                 int32_t i;
 350                 void *res = NULL;
 351                 for(i = 0; i < offset; i++)
 352                 {
 353                         res = ll_iter_next_nolock(it);
 354                         if(!res) { break; }
 355                 }
 356
 357                 return res;
 358         }
 359         return NULL;
 360 }
 361
 362 void *ll_iter_peek(const LL_ITER *it, int32_t offset)
 363 {
 364         if(it && it->l && !it->l->flag)
 365         {
 366                 cs_readlock(__func__, &((LL_ITER *)it)->l->lock);
 367
 368                 LL_NODE *n = it->cur;
 369                 int32_t i;
 370
 371                 for(i = 0; i < offset; i++)
 372                 {
 373                         if(n)
 374                                 { n = n->nxt; }
 375                         else
 376                                 { break; }
 377                 }
 378                 cs_readunlock(__func__, &((LL_ITER *)it)->l->lock);
 379
 380                 if(!n)
 381                         { return NULL; }
 382                 return n->obj;
 383         }
 384         return NULL;
 385 }
 386
 387 void ll_iter_reset(LL_ITER *it)
 388 {
 389         if(it)
 390         {
 391                 it->prv = NULL;
 392                 it->cur = NULL;
 393         }
 394 }
 395
 396 void ll_iter_insert(LL_ITER *it, void *obj)
 397 {
 398         if(it && obj && !it->l->flag)
 399         {
 400                 cs_writelock(__func__, &it->l->lock);
 401
 402                 if(!it->cur || !it->cur->nxt)
 403                         { ll_append_nolock(it->l, obj); }
 404                 else
 405                 {
 406                         LL_NODE *n;
 407                         if(!cs_malloc(&n, sizeof(LL_NODE)))
 408                         {
 409                                 cs_writeunlock(__func__, &it->l->lock);
 410                                 return;
 411                         }
 412
 413                         n->obj = obj;
 414                         n->nxt = it->cur->nxt;
 415                         it->cur->nxt = n;
 416
 417                         it->l->count++;
 418                         it->ll_version = ++it->l->version;
 419                 }
 420                 cs_writeunlock(__func__, &it->l->lock);
 421         }
 422 }
 423
 424 /* Removes the element to which the iterator currently points. */
 425 void *ll_iter_remove(LL_ITER *it)
 426 {
 427         void *obj = NULL;
 428         if(it && it->l && !it->l->flag)
 429         {
 430                 LL_NODE *del = it->cur;
 431                 if(del)
 432                 {
 433                         cs_writelock(__func__, &it->l->lock);
 434                         obj = ll_iter_remove_nolock(it);
 435                         cs_writeunlock(__func__, &it->l->lock);
 436                 }
 437         }
 438
 439         return obj;
 440 }
 441
 442 /* Moves the element which is currently pointed to by the iterator to the head of the list.*/
 443 int32_t ll_iter_move_first(LL_ITER *it)
 444 {
 445         int32_t moved = 0;
 446         if(it && it->l && !it->l->flag)
 447         {
 448                 LL_NODE *move = it->cur;
 449                 if(move)
 450                 {
 451                         if(move == it->l->initial)  //Can't move self to first
 452                                 { return 1; }
 453
 454                         LL_NODE *prv = it->prv;
 455                         cs_writelock(__func__, &it->l->lock);
 456                         if(it->ll_version != it->l->version || !prv)        // List has been modified so it->prv might be wrong!
 457                         {
 458                                 LL_NODE *n = it->l->initial;
 459                                 prv = NULL;
 460                                 while(n && n != move)
 461                                 {
 462                                         prv = n;
 463                                         n = n->nxt;
 464                                 }
 465                                 if(n != move)
 466                                 {
 467                                         cs_writeunlock(__func__, &it->l->lock);
 468                                         return moved;
 469                                 }
 470                         }
 471
 472                         if(prv)
 473                                 { prv->nxt = move->nxt; }
 474                         else
 475                                 { it->l->initial = move->nxt; }
 476
 477                         if(prv && it->l->last == move)
 478                                 { it->l->last = prv; }
 479                         move->nxt = it->l->initial;
 480                         it->l->initial = move;
 481
 482                         it->ll_version = ++it->l->version;
 483                         it->prv = NULL;
 484                         cs_writeunlock(__func__, &it->l->lock);
 485                         moved = 1;
 486                 }
 487         }
 488         return moved;
 489 }
 490
 491 void ll_iter_remove_data(LL_ITER *it)
 492 {
 493         void *obj = ll_iter_remove(it);
 494         add_garbage(obj);
 495 }
 496
 497 void *ll_has_elements(const LLIST *l)
 498 {
 499         if(!l || !l->initial || l->flag)
 500                 { return NULL; }
 501         return l->initial->obj;
 502 }
 503
 504 void *ll_last_element(const LLIST *l)
 505 {
 506         if(!l || !l->last || l->flag)
 507                 { return NULL; }
 508         return l->last->obj;
 509 }
 510
 511 int32_t ll_contains(const LLIST *l, const void *obj)
 512 {
 513         if(!l || !obj || l->flag)
 514                 { return 0; }
 515         LL_ITER it = ll_iter_create((LLIST *) l);
 516         const void *data;
 517         while((data = ll_iter_next(&it)))
 518         {
 519                 if(data == obj)
 520                         { break; }
 521         }
 522         return (data == obj);
 523 }
 524
 525 const void *ll_contains_data(const LLIST *l, const void *obj, uint32_t size)
 526 {
 527         if(!l || !obj || l->flag)
 528                 { return NULL; }
 529         LL_ITER it = ll_iter_create((LLIST *) l);
 530         const void *data;
 531         while((data = ll_iter_next(&it)))
 532         {
 533                 if(!memcmp(data, obj, size))
 534                         { break; }
 535         }
 536         return data;
 537 }
 538
 539 int32_t ll_remove(LLIST *l, const void *obj)
 540 {
 541         int32_t n = 0;
 542         LL_ITER it = ll_iter_create(l);
 543         void *data;
 544         while((data = ll_iter_next(&it)))
 545         {
 546                 if(data == obj)
 547                 {
 548                         ll_iter_remove(&it);
 549                         n++;
 550                 }
 551         }
 552         return n;
 553 }
 554
 555 void ll_remove_data(LLIST *l, void *obj)
 556 {
 557         LL_ITER it = ll_iter_create(l);
 558         void *data;
 559         while((data = ll_iter_next(&it)))
 560         {
 561                 if(data == obj)
 562                         { ll_iter_remove_data(&it); }
 563         }
 564 }
 565
 566 // removes all elements from l where elements are in elements_to_remove
 567 int32_t ll_remove_all(LLIST *l, const LLIST *elements_to_remove)
 568 {
 569         int32_t count = 0;
 570         LL_ITER it1 = ll_iter_create(l);
 571         LL_ITER it2 = ll_iter_create((LLIST *) elements_to_remove);
 572
 573         const void *data1, *data2;
 574         while((data1 = ll_iter_next(&it1)))
 575         {
 576                 ll_iter_reset(&it2);
 577                 while((data2 = ll_iter_next(&it2)))
 578                 {
 579                         if(data1 == data2)
 580                         {
 581                                 ll_iter_remove(&it1);
 582                                 count++;
 583                                 break;
 584                         }
 585                 }
 586         }
 587
 588         return count;
 589 }
 590
 591 /* Returns an array with all elements sorted, the amount of elements is stored in size. We do not sort the original linked list
 592    as this might harm running iterations. Furthermore, we need the array anyway for qsort() to work. Remember to free() the result. */
 593 void **ll_sort(const LLIST *l, void *compare, int32_t *size)
 594 {
 595         if(!l || !l->initial || !compare)
 596         {
 597                 *size = 0;
 598                 return NULL;
 599         }
 600         int32_t i = 0;
 601         LL_NODE *n;
 602
 603         cs_readlock(__func__, &((LLIST *)l)->lock);
 604         *size = l->count;
 605         void **p;
 606         if(!cs_malloc(&p, l->count * sizeof(p[0])))
 607         {
 608                 cs_readunlock(__func__, &((LLIST *)l)->lock);
 609                 return NULL;
 610         }
 611         for(n = l->initial; n; n = n->nxt)
 612         {
 613                 p[i++] = n->obj;
 614         }
 615         cs_readunlock(__func__, &((LLIST *)l)->lock);
 616 #ifdef WITH_DEBUG
 617         //  if (chk_debugLog(it->l))
 618         //cs_log_dbg(D_TRACE, "sort: count %d size %d", l->count, sizeof(p[0]));
 619 #endif
 620         qsort(p, l->count, sizeof(p[0]), compare);
 621
 622         return p;
 623 }
 624
 625 void ll_putall(LLIST *dest, LLIST *src)
 626 {
 627         LL_ITER it = ll_iter_create(src);
 628         void *data;
 629         while((data = ll_iter_next(&it)))
 630         {
 631                 ll_append(dest, data);
 632         }
 633 }
 634
 635 //New Iterator:
 636 LL_LOCKITER *ll_li_create(LLIST *l, int32_t writelock)
 637 {
 638         if(!l || l->flag) { return NULL; }
 639
 640         LL_LOCKITER *li;
 641         if(!cs_malloc(&li, sizeof(LL_LOCKITER)))
 642                 { return NULL; }
 643
 644         li->l = l;
 645         li->writelock = writelock;
 646         if(writelock)
 647                 { cs_writelock(__func__, &l->lock); }
 648         else
 649                 { cs_readlock(__func__, &l->lock); }
 650         li->it = ll_iter_create(l);
 651         return li;
 652 }
 653
 654 void ll_li_destroy(LL_LOCKITER *li)
 655 {
 656         if(li && li->l)
 657         {
 658                 if(li->writelock)
 659                         { cs_writeunlock(__func__, &li->l->lock); }
 660                 else
 661                         { cs_readunlock(__func__, &li->l->lock); }
 662                 li->l = NULL;
 663                 add_garbage(li);
 664         }
 665 }
 666
 667 void *ll_li_next(LL_LOCKITER *li)
 668 {
 669         if(li && li->l)
 670         {
 671                 return ll_iter_next_nolock(&li->it);
 672         }
 673         return NULL;
 674 }
 675
 676 LLIST *ll_clone(LLIST *l, uint32_t copysize)
 677 {
 678         if(!l || l->flag) { return NULL; }
 679
 680         LLIST *cloned = ll_create(l->lock.name);
 681         LL_LOCKITER *li = ll_li_create(l, 0);
 682         void *data;
 683         while((data = ll_li_next(li)))
 684         {
 685                 void *new_data;
 686                 if(!cs_malloc(&new_data, copysize))
 687                         { break; }
 688                 memcpy(new_data, data, copysize);
 689                 ll_append_nolock(cloned, new_data);
 690         }
 691         ll_li_destroy(li);
 692         return cloned;
 693 }
 694
 695 void *ll_remove_first(LLIST *l)
 696 {
 697         if(l && !l->flag)
 698         {
 699                 LL_ITER it = ll_iter_create(l);
 700                 void *data = ll_iter_next(&it);
 701                 if(data) { ll_iter_remove(&it); }
 702                 return data;
 703         }
 704         return NULL;
 705 }
 706
 707 void ll_remove_first_data(LLIST *l)
 708 {
 709         void *data = ll_remove_first(l);
 710         if(data) { NULLFREE(data); }
 711 }