[3593] | 1 |
|
---|
| 2 | /* singularly linked-list */
|
---|
| 3 |
|
---|
| 4 | #include <stdlib.h>
|
---|
| 5 |
|
---|
| 6 | #include "globals.h"
|
---|
[3609] | 7 | #include "module-datastruct-llist.h"
|
---|
[3593] | 8 |
|
---|
[4908] | 9 | /*
|
---|
| 10 | Locking rules:
|
---|
| 11 |
|
---|
| 12 | mutex lock is needed when...
|
---|
[5234] | 13 | 1. l->initial + l->last is modified/accessed
|
---|
[4908] | 14 | 2. LL_NODE nxt modified/accessed
|
---|
| 15 |
|
---|
| 16 |
|
---|
| 17 | */
|
---|
[3593] | 18 | static void _destroy(LLIST *l)
|
---|
| 19 | {
|
---|
[5307] | 20 | if (!l) return;
|
---|
[5333] | 21 | int32_t oldtype, res, i = 0;
|
---|
[5307] | 22 | pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &oldtype);
|
---|
[5333] | 23 | if (!l->flag++) {
|
---|
| 24 | /* FIXME: Because of unknown reasons we sometimes get a deadlock here if we use pthread_mutex_lock. So only wait up to about 500ms... */
|
---|
| 25 | while(i < 25 && (res = pthread_mutex_trylock(&l->lock)) == EBUSY){
|
---|
| 26 | cs_sleepms(20);
|
---|
| 27 | ++i;
|
---|
| 28 | }
|
---|
| 29 | if(res == 0)
|
---|
| 30 | pthread_mutex_unlock(&l->lock);
|
---|
| 31 | if(res != EINVAL && res != EFAULT)
|
---|
| 32 | pthread_mutex_destroy(&l->lock);
|
---|
[5307] | 33 | add_garbage(l);
|
---|
[5085] | 34 | }
|
---|
[5307] | 35 | pthread_setcancelstate(oldtype, NULL);
|
---|
| 36 | pthread_testcancel();
|
---|
[3593] | 37 | }
|
---|
| 38 |
|
---|
| 39 | LLIST *ll_create()
|
---|
| 40 | {
|
---|
[5186] | 41 | LLIST *l = cs_malloc(&l, sizeof(LLIST), 0);
|
---|
[4839] | 42 | pthread_mutex_init(&l->lock, NULL);
|
---|
[3593] | 43 | return l;
|
---|
| 44 | }
|
---|
| 45 |
|
---|
[5233] | 46 | int32_t ll_lock(LLIST *l)
|
---|
[5085] | 47 | {
|
---|
[5233] | 48 | int32_t res = 1;
|
---|
[5304] | 49 | while (l && !l->flag && (res=cs_trylock(&l->lock))) {
|
---|
[5100] | 50 | cs_debug_mask(D_TRACE, "trylock ll_lock wait");
|
---|
| 51 | cs_sleepms(50);
|
---|
| 52 | }
|
---|
[5187] | 53 | return !res;
|
---|
[5085] | 54 | }
|
---|
| 55 |
|
---|
| 56 | void ll_unlock(LLIST *l)
|
---|
| 57 | {
|
---|
[5304] | 58 | if (l)
|
---|
[5307] | 59 | cs_unlock(&l->lock);
|
---|
[5085] | 60 | }
|
---|
| 61 |
|
---|
[3593] | 62 | void ll_destroy(LLIST *l)
|
---|
| 63 | {
|
---|
[3634] | 64 | if (!l) return;
|
---|
[3593] | 65 | ll_clear(l);
|
---|
| 66 |
|
---|
| 67 | _destroy(l);
|
---|
| 68 | }
|
---|
| 69 |
|
---|
| 70 | void ll_destroy_data(LLIST *l)
|
---|
| 71 | {
|
---|
[3634] | 72 | if (!l) return;
|
---|
[3593] | 73 | ll_clear_data(l);
|
---|
| 74 |
|
---|
| 75 | _destroy(l);
|
---|
| 76 | }
|
---|
| 77 |
|
---|
[5063] | 78 | void *ll_iter_next_nolock(LL_ITER *it)
|
---|
| 79 | {
|
---|
| 80 | if (it && it->l) {
|
---|
| 81 | if (it->cur) {
|
---|
| 82 | it->prv = it->cur;
|
---|
| 83 | it->cur = it->cur->nxt;
|
---|
| 84 | } else if (it->l->initial && !it->prv)
|
---|
| 85 | it->cur = it->l->initial;
|
---|
| 86 |
|
---|
| 87 | if (it->cur)
|
---|
| 88 | return it->cur->obj;
|
---|
| 89 | }
|
---|
| 90 |
|
---|
| 91 | return NULL;
|
---|
| 92 | }
|
---|
| 93 |
|
---|
[5233] | 94 | static void ll_clear_int(LLIST *l, int32_t clear_data)
|
---|
[3593] | 95 | {
|
---|
[4421] | 96 | if (!l) return;
|
---|
[3593] | 97 |
|
---|
[5187] | 98 | if (!ll_lock(l)) return;
|
---|
| 99 |
|
---|
[5232] | 100 | LL_NODE *n=l->initial, *nxt;
|
---|
| 101 | while (n) {
|
---|
| 102 | nxt = n->nxt;
|
---|
| 103 | if (n && !n->flag++) {
|
---|
[5062] | 104 | if (clear_data)
|
---|
[5232] | 105 | add_garbage(n->obj);
|
---|
| 106 | add_garbage(n);
|
---|
[5062] | 107 | }
|
---|
[5232] | 108 | n = nxt;
|
---|
[5062] | 109 | }
|
---|
[4421] | 110 | l->count = 0;
|
---|
[5064] | 111 | l->initial = 0;
|
---|
[5234] | 112 | l->last = 0;
|
---|
[5085] | 113 | ll_unlock(l);
|
---|
[3593] | 114 | }
|
---|
| 115 |
|
---|
[5062] | 116 | void ll_clear(LLIST *l)
|
---|
| 117 | {
|
---|
| 118 | ll_clear_int(l, 0);
|
---|
| 119 | }
|
---|
| 120 |
|
---|
| 121 |
|
---|
[3593] | 122 | void ll_clear_data(LLIST *l)
|
---|
| 123 | {
|
---|
[5062] | 124 | ll_clear_int(l, 1);
|
---|
[3593] | 125 | }
|
---|
| 126 |
|
---|
[4908] | 127 | LL_NODE* ll_append_nolock(LLIST *l, void *obj)
|
---|
[3593] | 128 | {
|
---|
[4421] | 129 | if (l && obj) {
|
---|
[5299] | 130 | LL_NODE *new;
|
---|
| 131 | if(!cs_malloc(&new,sizeof(LL_NODE), -1)) return NULL;
|
---|
[3593] | 132 | new->obj = obj;
|
---|
| 133 |
|
---|
[5234] | 134 | if (l->last)
|
---|
| 135 | l->last->nxt = new;
|
---|
| 136 | else
|
---|
[3593] | 137 | l->initial = new;
|
---|
[5234] | 138 | l->last = new;
|
---|
| 139 |
|
---|
[4421] | 140 | l->count++;
|
---|
[4505] | 141 | return new;
|
---|
[3593] | 142 | }
|
---|
[4528] | 143 |
|
---|
[4505] | 144 | return NULL;
|
---|
[3593] | 145 | }
|
---|
| 146 |
|
---|
[4908] | 147 | LL_NODE* ll_append(LLIST *l, void *obj)
|
---|
| 148 | {
|
---|
| 149 | if (l && obj) {
|
---|
[5187] | 150 | if (!ll_lock(l)) return NULL;
|
---|
| 151 |
|
---|
[4908] | 152 | LL_NODE *n = ll_append_nolock(l, obj);
|
---|
[5085] | 153 | ll_unlock(l);
|
---|
[4908] | 154 | return n;
|
---|
| 155 | }
|
---|
| 156 | return NULL;
|
---|
| 157 | }
|
---|
| 158 |
|
---|
[4528] | 159 | LL_NODE *ll_prepend(LLIST *l, void *obj)
|
---|
[4421] | 160 | {
|
---|
| 161 | if (l && obj) {
|
---|
[5187] | 162 | if (!ll_lock(l)) return NULL;
|
---|
| 163 |
|
---|
[5299] | 164 | LL_NODE *new;
|
---|
| 165 | if(!cs_malloc(&new,sizeof(LL_NODE), -1)) return NULL;
|
---|
[4528] | 166 |
|
---|
| 167 | new->obj = obj;
|
---|
| 168 | new->nxt = l->initial;
|
---|
| 169 |
|
---|
| 170 | l->initial = new;
|
---|
[5234] | 171 | if (!l->last)
|
---|
| 172 | l->last = l->initial;
|
---|
[4531] | 173 | l->count++;
|
---|
[5085] | 174 | ll_unlock(l);
|
---|
[4528] | 175 |
|
---|
| 176 | return new;
|
---|
[4421] | 177 | }
|
---|
[4528] | 178 |
|
---|
| 179 | return NULL;
|
---|
[4421] | 180 | }
|
---|
| 181 |
|
---|
[5226] | 182 | LL_ITER ll_iter_create(LLIST *l)
|
---|
[3593] | 183 | {
|
---|
[5226] | 184 | LL_ITER it;
|
---|
| 185 | memset(&it, 0, sizeof(it));
|
---|
| 186 | it.l = l;
|
---|
[3593] | 187 | return it;
|
---|
| 188 | }
|
---|
| 189 |
|
---|
[4536] | 190 |
|
---|
[4908] | 191 | void *ll_iter_next(LL_ITER *it)
|
---|
| 192 | {
|
---|
| 193 | if (it && it->l) {
|
---|
[5187] | 194 | if (!ll_lock(it->l)) return NULL;
|
---|
[4908] | 195 | void *res = ll_iter_next_nolock(it);
|
---|
[5085] | 196 | ll_unlock(it->l);
|
---|
[4908] | 197 | return res;
|
---|
| 198 | }
|
---|
| 199 | return NULL;
|
---|
| 200 | }
|
---|
| 201 |
|
---|
[4994] | 202 | void *ll_iter_move(LL_ITER *it, int32_t offset)
|
---|
[4988] | 203 | {
|
---|
| 204 | if (it && it->l) {
|
---|
[5187] | 205 | if (!ll_lock(it->l)) return NULL;
|
---|
[4994] | 206 | int32_t i;
|
---|
[4993] | 207 | void *res = NULL;
|
---|
[4988] | 208 | for (i=0; i<offset; i++) {
|
---|
| 209 | res = ll_iter_next_nolock(it);
|
---|
| 210 | if (!res) break;
|
---|
| 211 | }
|
---|
[5085] | 212 | ll_unlock(it->l);
|
---|
[4988] | 213 | return res;
|
---|
| 214 | }
|
---|
| 215 | return NULL;
|
---|
| 216 | }
|
---|
| 217 |
|
---|
[4994] | 218 | void *ll_iter_peek(LL_ITER *it, int32_t offset)
|
---|
[3611] | 219 | {
|
---|
[4908] | 220 | if (it && it->l) {
|
---|
[5187] | 221 | if (!ll_lock(it->l)) return NULL;
|
---|
| 222 |
|
---|
[4908] | 223 | LL_NODE *n = it->cur;
|
---|
[4994] | 224 | int32_t i;
|
---|
[3611] | 225 |
|
---|
[4908] | 226 | for (i = 0; i < offset; i++) {
|
---|
| 227 | if (n)
|
---|
| 228 | n = n->nxt;
|
---|
| 229 | else
|
---|
| 230 | break;
|
---|
| 231 | }
|
---|
[5085] | 232 | ll_unlock(it->l);
|
---|
[4908] | 233 |
|
---|
| 234 | if (!n)
|
---|
| 235 | return NULL;
|
---|
| 236 | return n->obj;
|
---|
| 237 | }
|
---|
| 238 | return NULL;
|
---|
[3611] | 239 | }
|
---|
| 240 |
|
---|
[3593] | 241 | void ll_iter_reset(LL_ITER *it)
|
---|
| 242 | {
|
---|
[4528] | 243 | if (it) {
|
---|
| 244 | it->prv = NULL;
|
---|
| 245 | it->cur = NULL;
|
---|
| 246 | }
|
---|
[3593] | 247 | }
|
---|
| 248 |
|
---|
| 249 | void ll_iter_insert(LL_ITER *it, void *obj)
|
---|
| 250 | {
|
---|
[4528] | 251 | if (it && obj) {
|
---|
[5187] | 252 | if (!ll_lock(it->l)) return;
|
---|
| 253 |
|
---|
[4528] | 254 | if (!it->cur || !it->cur->nxt)
|
---|
[4908] | 255 | ll_append_nolock(it->l, obj);
|
---|
[4404] | 256 | else {
|
---|
[5299] | 257 | LL_NODE *n;
|
---|
| 258 | if(!cs_malloc(&n,sizeof(LL_NODE), -1)) return;
|
---|
[3593] | 259 |
|
---|
[4528] | 260 | n->obj = obj;
|
---|
| 261 | n->nxt = it->cur->nxt;
|
---|
| 262 | it->cur->nxt = n;
|
---|
| 263 |
|
---|
| 264 | it->l->count++;
|
---|
[4404] | 265 | }
|
---|
[5085] | 266 | ll_unlock(it->l);
|
---|
[3593] | 267 | }
|
---|
| 268 | }
|
---|
| 269 |
|
---|
| 270 | void *ll_iter_remove(LL_ITER *it)
|
---|
| 271 | {
|
---|
[4839] | 272 | void *obj = NULL;
|
---|
[4528] | 273 | if (it) {
|
---|
[5187] | 274 | if (!ll_lock(it->l)) return NULL;
|
---|
[4528] | 275 | LL_NODE *del = it->cur;
|
---|
[4831] | 276 | if (del && !del->flag++) { //preventing duplicate free because of multiple threads
|
---|
[4839] | 277 | obj = del->obj;
|
---|
[4531] | 278 | LL_NODE *prv = it->prv;
|
---|
| 279 |
|
---|
| 280 | if (prv)
|
---|
| 281 | prv->nxt = del->nxt;
|
---|
[4528] | 282 | else
|
---|
| 283 | it->l->initial = del->nxt;
|
---|
[5234] | 284 | if (!it->l->initial)
|
---|
| 285 | it->l->last = NULL;
|
---|
| 286 | else if (del == it->l->last)
|
---|
| 287 | it->l->last = prv;
|
---|
| 288 |
|
---|
[4421] | 289 | it->l->count--;
|
---|
[4528] | 290 | ll_iter_reset(it);
|
---|
[4908] | 291 | while (prv && ll_iter_next_nolock(it))
|
---|
[4528] | 292 | if (it->cur == prv)
|
---|
| 293 | break;
|
---|
| 294 |
|
---|
| 295 | add_garbage(del);
|
---|
[3593] | 296 | }
|
---|
[5085] | 297 | ll_unlock(it->l);
|
---|
[3593] | 298 | }
|
---|
| 299 |
|
---|
[4839] | 300 | return obj;
|
---|
[3593] | 301 | }
|
---|
| 302 |
|
---|
[5233] | 303 | int32_t ll_iter_move_first(LL_ITER *it)
|
---|
[5056] | 304 | {
|
---|
[5233] | 305 | int32_t moved = 0;
|
---|
[5056] | 306 | if (it) {
|
---|
[5187] | 307 | if (!ll_lock(it->l)) return moved;
|
---|
| 308 |
|
---|
[5056] | 309 | LL_NODE *move = it->cur;
|
---|
| 310 | if (move && !move->flag++) { //preventing duplicate free because of multiple threads
|
---|
| 311 | LL_NODE *prv = it->prv;
|
---|
| 312 |
|
---|
| 313 | if (prv)
|
---|
| 314 | prv->nxt = move->nxt;
|
---|
| 315 | else
|
---|
| 316 | it->l->initial = move->nxt;
|
---|
| 317 |
|
---|
[5234] | 318 | if (prv && it->l->last == move)
|
---|
| 319 | it->l->last = prv;
|
---|
[5056] | 320 | move->nxt = it->l->initial;
|
---|
| 321 | it->l->initial = move;
|
---|
| 322 | moved = 1;
|
---|
| 323 |
|
---|
| 324 | ll_iter_reset(it);
|
---|
| 325 | }
|
---|
[5085] | 326 | ll_unlock(it->l);
|
---|
[5056] | 327 | }
|
---|
| 328 | return moved;
|
---|
| 329 | }
|
---|
| 330 |
|
---|
[3593] | 331 | void ll_iter_remove_data(LL_ITER *it)
|
---|
| 332 | {
|
---|
| 333 | void *obj = ll_iter_remove(it);
|
---|
[4442] | 334 | add_garbage(obj);
|
---|
[3593] | 335 | }
|
---|
| 336 |
|
---|
[4994] | 337 | int32_t ll_count(LLIST *l)
|
---|
[3593] | 338 | {
|
---|
[4404] | 339 | if (!l)
|
---|
| 340 | return 0;
|
---|
| 341 |
|
---|
[4421] | 342 | return l->count;
|
---|
[3593] | 343 | }
|
---|
| 344 |
|
---|
[4066] | 345 | void *ll_has_elements(LLIST *l) {
|
---|
| 346 | if (!l || !l->initial)
|
---|
| 347 | return NULL;
|
---|
| 348 | return l->initial->obj;
|
---|
| 349 | }
|
---|
| 350 |
|
---|
[4994] | 351 | int32_t ll_contains(LLIST *l, void *obj)
|
---|
[4513] | 352 | {
|
---|
[4639] | 353 | if (!l || !obj)
|
---|
| 354 | return 0;
|
---|
[5226] | 355 | LL_ITER it = ll_iter_create(l);
|
---|
[4513] | 356 | void *data;
|
---|
[5226] | 357 | while ((data=ll_iter_next(&it))) {
|
---|
[4513] | 358 | if (data==obj)
|
---|
| 359 | break;
|
---|
| 360 | }
|
---|
| 361 | return (data==obj);
|
---|
| 362 | }
|
---|
| 363 |
|
---|
[5255] | 364 | void *ll_contains_data(LLIST *l, void *obj, uint32_t size)
|
---|
[5242] | 365 | {
|
---|
| 366 | if (!l || !obj)
|
---|
[5255] | 367 | return NULL;
|
---|
[5242] | 368 | LL_ITER it = ll_iter_create(l);
|
---|
| 369 | void *data;
|
---|
| 370 | while ((data=ll_iter_next(&it))) {
|
---|
| 371 | if (!memcmp(data,obj,size))
|
---|
| 372 | break;
|
---|
| 373 | }
|
---|
[5255] | 374 | return data;
|
---|
[5242] | 375 | }
|
---|
| 376 |
|
---|
[5042] | 377 | int32_t ll_remove(LLIST *l, void *obj)
|
---|
[4513] | 378 | {
|
---|
[5233] | 379 | int32_t n = 0;
|
---|
[5226] | 380 | LL_ITER it = ll_iter_create(l);
|
---|
[4513] | 381 | void *data;
|
---|
[5226] | 382 | while ((data=ll_iter_next(&it))) {
|
---|
[5042] | 383 | if (data==obj) {
|
---|
[5226] | 384 | ll_iter_remove(&it);
|
---|
[5042] | 385 | n++;
|
---|
| 386 | }
|
---|
[4513] | 387 | }
|
---|
[5042] | 388 | return n;
|
---|
[4513] | 389 | }
|
---|
| 390 |
|
---|
| 391 | void ll_remove_data(LLIST *l, void *obj)
|
---|
| 392 | {
|
---|
[5226] | 393 | LL_ITER it = ll_iter_create(l);
|
---|
[4513] | 394 | void *data;
|
---|
[5226] | 395 | while ((data=ll_iter_next(&it))) {
|
---|
[4513] | 396 | if (data==obj)
|
---|
[5226] | 397 | ll_iter_remove_data(&it);
|
---|
[4513] | 398 | }
|
---|
| 399 | }
|
---|
[4747] | 400 |
|
---|
| 401 | // removes all elements from l where elements are in elements_to_remove
|
---|
[4994] | 402 | int32_t ll_remove_all(LLIST *l, LLIST *elements_to_remove)
|
---|
[4747] | 403 | {
|
---|
[4994] | 404 | int32_t count = 0;
|
---|
[5226] | 405 | LL_ITER it1 = ll_iter_create(l);
|
---|
| 406 | LL_ITER it2 = ll_iter_create(elements_to_remove);
|
---|
[4747] | 407 |
|
---|
| 408 | void *data1, *data2;
|
---|
[5226] | 409 | while ((data1=ll_iter_next(&it1))) {
|
---|
| 410 | ll_iter_reset(&it2);
|
---|
| 411 | while ((data2=ll_iter_next(&it2))) {
|
---|
[4747] | 412 | if (data1 == data2) {
|
---|
[5234] | 413 | ll_iter_remove(&it1);
|
---|
[4747] | 414 | count++;
|
---|
| 415 | break;
|
---|
| 416 | }
|
---|
| 417 | }
|
---|
| 418 | }
|
---|
| 419 |
|
---|
| 420 | return count;
|
---|
| 421 | }
|
---|
[5234] | 422 |
|
---|
| 423 | void ll_sort(LLIST *l, void *compare)
|
---|
| 424 | {
|
---|
| 425 | if (!l || !l->initial || !compare) return;
|
---|
| 426 |
|
---|
| 427 | if (!ll_lock(l)) return;
|
---|
| 428 |
|
---|
| 429 | //Because this list has no prv pointer, we can not do qsort, so
|
---|
| 430 | //copy to a flat array, sort them, and then copy back
|
---|
| 431 | void **p = cs_malloc(&p, l->count*sizeof(p[0]), 0);
|
---|
| 432 | LL_NODE *n = l->initial;
|
---|
| 433 | int32_t i=0;
|
---|
| 434 | while (n) {
|
---|
| 435 | p[i++] = n->obj;
|
---|
| 436 | n=n->nxt;
|
---|
| 437 | }
|
---|
| 438 |
|
---|
[5279] | 439 | cs_debug_mask(D_TRACE, "sort: count %d size %d", l->count, sizeof(p[0]));
|
---|
[5234] | 440 |
|
---|
| 441 | qsort(p, l->count, sizeof(p[0]), compare);
|
---|
| 442 |
|
---|
| 443 | n = l->initial;
|
---|
| 444 | i = 0;
|
---|
| 445 | while (n) {
|
---|
| 446 | n->obj = p[i++];
|
---|
| 447 | n=n->nxt;
|
---|
| 448 | }
|
---|
| 449 |
|
---|
| 450 | free(p);
|
---|
| 451 |
|
---|
| 452 | ll_unlock(l);
|
---|
| 453 | }
|
---|