oscam-llist.c

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