source: trunk/module-datastruct-llist.c @ 5375

Last change on this file since 5375 was 5333, checked in by Admin, 3 years ago

Only wait up to 500ms in llist destroy as there seem to exist deadlock conditions...

File size: 8.4 KB
Line 
1
2/* singularly linked-list */
3
4#include <stdlib.h>
5
6#include "globals.h"
7#include "module-datastruct-llist.h"
8
9/*
10  Locking rules:
11 
12  mutex lock is needed when...
13  1. l->initial + l->last is modified/accessed
14  2. LL_NODE nxt modified/accessed
15
16
17*/
18static void _destroy(LLIST *l)
19{
20    if (!l) return;
21    int32_t oldtype, res, i = 0;
22    pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, &oldtype);       
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);
33        add_garbage(l);
34    }
35    pthread_setcancelstate(oldtype, NULL);
36    pthread_testcancel();
37}
38
39LLIST *ll_create()
40{
41    LLIST *l = cs_malloc(&l, sizeof(LLIST), 0);
42    pthread_mutex_init(&l->lock, NULL);
43    return l;
44}
45
46int32_t ll_lock(LLIST *l)
47{
48    int32_t res = 1;
49    while (l && !l->flag && (res=cs_trylock(&l->lock))) {
50        cs_debug_mask(D_TRACE, "trylock ll_lock wait");
51        cs_sleepms(50);
52    }
53    return !res;
54}
55
56void ll_unlock(LLIST *l)
57{
58    if (l)
59        cs_unlock(&l->lock);
60}
61
62void ll_destroy(LLIST *l)
63{
64    if (!l) return;
65    ll_clear(l);
66
67    _destroy(l);
68}
69
70void ll_destroy_data(LLIST *l)
71{
72    if (!l) return;
73    ll_clear_data(l);
74
75    _destroy(l);
76}
77
78void *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
94static void ll_clear_int(LLIST *l, int32_t clear_data)
95{
96    if (!l) return;
97
98    if (!ll_lock(l)) return;
99   
100    LL_NODE *n=l->initial, *nxt;
101    while (n) {
102        nxt = n->nxt;
103        if (n && !n->flag++) {
104            if (clear_data)
105                add_garbage(n->obj);
106            add_garbage(n);
107        }
108        n = nxt;
109    }
110    l->count = 0;
111    l->initial = 0;
112    l->last = 0;
113    ll_unlock(l);
114}
115
116void ll_clear(LLIST *l)
117{
118    ll_clear_int(l, 0);
119}
120
121
122void ll_clear_data(LLIST *l)
123{
124    ll_clear_int(l, 1);
125}
126
127LL_NODE* ll_append_nolock(LLIST *l, void *obj)
128{
129    if (l && obj) {
130        LL_NODE *new;
131        if(!cs_malloc(&new,sizeof(LL_NODE), -1)) return NULL;
132        new->obj = obj;
133       
134        if (l->last)
135            l->last->nxt = new;
136        else
137            l->initial = new;
138        l->last = new;   
139       
140        l->count++;
141        return new;
142    }
143
144    return NULL;
145}
146
147LL_NODE* ll_append(LLIST *l, void *obj)
148{
149    if (l && obj) {
150        if (!ll_lock(l)) return NULL;
151       
152        LL_NODE *n = ll_append_nolock(l, obj);
153        ll_unlock(l);
154        return n;
155    }
156    return NULL;
157}
158
159LL_NODE *ll_prepend(LLIST *l, void *obj)
160{
161    if (l && obj) {
162        if (!ll_lock(l)) return NULL;
163       
164        LL_NODE *new;
165        if(!cs_malloc(&new,sizeof(LL_NODE), -1)) return NULL;
166
167        new->obj = obj;
168        new->nxt = l->initial;
169
170        l->initial = new;
171        if (!l->last)
172            l->last = l->initial;
173        l->count++;
174        ll_unlock(l);
175
176        return new;
177    }
178
179    return NULL;
180}
181
182LL_ITER ll_iter_create(LLIST *l)
183{
184    LL_ITER it;
185    memset(&it, 0, sizeof(it));
186    it.l = l;
187    return it;
188}
189
190
191void *ll_iter_next(LL_ITER *it)
192{
193    if (it && it->l) {
194        if (!ll_lock(it->l)) return NULL;
195        void *res = ll_iter_next_nolock(it);
196        ll_unlock(it->l);
197        return res;
198    }
199    return NULL;
200}
201
202void *ll_iter_move(LL_ITER *it, int32_t offset)
203{
204    if (it && it->l) {
205        if (!ll_lock(it->l)) return NULL;
206        int32_t i;
207        void *res = NULL;
208        for (i=0; i<offset; i++) {
209            res = ll_iter_next_nolock(it);
210            if (!res) break;
211        }
212        ll_unlock(it->l);
213        return res;
214    }
215    return NULL;
216}
217
218void *ll_iter_peek(LL_ITER *it, int32_t offset)
219{
220    if (it && it->l) {
221        if (!ll_lock(it->l)) return NULL;
222       
223        LL_NODE *n = it->cur;
224        int32_t i;
225
226        for (i = 0; i < offset; i++) {
227            if (n)
228                n = n->nxt;
229            else
230                break;
231        }
232        ll_unlock(it->l);
233       
234        if (!n)
235            return NULL;
236        return n->obj;
237    }
238    return NULL;
239}
240
241void ll_iter_reset(LL_ITER *it)
242{
243    if (it) {
244        it->prv = NULL;
245        it->cur = NULL;
246    }
247}
248
249void ll_iter_insert(LL_ITER *it, void *obj)
250{
251    if (it && obj) {
252        if (!ll_lock(it->l)) return;
253       
254        if (!it->cur || !it->cur->nxt)
255            ll_append_nolock(it->l, obj);
256        else {
257            LL_NODE *n;
258            if(!cs_malloc(&n,sizeof(LL_NODE), -1)) return;
259
260            n->obj = obj;
261            n->nxt = it->cur->nxt;
262            it->cur->nxt = n;
263
264            it->l->count++;
265        }
266        ll_unlock(it->l);
267    }
268}
269
270void *ll_iter_remove(LL_ITER *it)
271{
272    void *obj = NULL;
273    if (it) {
274        if (!ll_lock(it->l)) return NULL;
275        LL_NODE *del = it->cur;
276        if (del && !del->flag++) { //preventing duplicate free because of multiple threads
277            obj = del->obj;
278            LL_NODE *prv = it->prv;
279           
280            if (prv)
281                prv->nxt = del->nxt;
282            else
283                it->l->initial = del->nxt;
284            if (!it->l->initial)
285                it->l->last = NULL;
286            else if (del == it->l->last)
287                it->l->last = prv;
288               
289            it->l->count--;
290            ll_iter_reset(it);
291            while (prv && ll_iter_next_nolock(it))
292                if (it->cur == prv)
293                    break;
294
295            add_garbage(del);
296        }
297        ll_unlock(it->l);
298    }
299
300    return obj;
301}
302
303int32_t ll_iter_move_first(LL_ITER *it)
304{
305    int32_t moved = 0;
306    if (it) {
307        if (!ll_lock(it->l)) return moved;
308       
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                               
318            if (prv && it->l->last == move)
319                it->l->last = prv;
320            move->nxt = it->l->initial;
321            it->l->initial = move;
322            moved = 1;
323           
324            ll_iter_reset(it);
325        }
326        ll_unlock(it->l);
327    }
328    return moved;
329}
330
331void ll_iter_remove_data(LL_ITER *it)
332{
333    void *obj = ll_iter_remove(it);
334    add_garbage(obj);
335}
336
337int32_t ll_count(LLIST *l)
338{
339    if (!l)
340      return 0;
341     
342    return l->count;
343}
344
345void *ll_has_elements(LLIST *l) {
346  if (!l || !l->initial)
347    return NULL;
348  return l->initial->obj;
349}
350
351int32_t ll_contains(LLIST *l, void *obj)
352{
353    if (!l || !obj)
354      return 0;
355    LL_ITER it = ll_iter_create(l);
356    void *data;
357    while ((data=ll_iter_next(&it))) {
358      if (data==obj)
359        break;
360    }
361    return (data==obj);
362}
363
364void *ll_contains_data(LLIST *l, void *obj, uint32_t size)
365{
366    if (!l || !obj)
367      return NULL;
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    }
374    return data;
375}
376
377int32_t ll_remove(LLIST *l, void *obj)
378{
379    int32_t n = 0;
380    LL_ITER it = ll_iter_create(l);
381    void *data;
382    while ((data=ll_iter_next(&it))) {
383        if (data==obj) {
384            ll_iter_remove(&it);
385            n++;
386        }
387    }
388    return n;
389}
390
391void ll_remove_data(LLIST *l, void *obj)
392{
393    LL_ITER it = ll_iter_create(l);
394    void *data;
395    while ((data=ll_iter_next(&it))) {
396      if (data==obj)
397        ll_iter_remove_data(&it);
398    }
399}
400
401// removes all elements from l where elements are in elements_to_remove
402int32_t ll_remove_all(LLIST *l, LLIST *elements_to_remove)
403{
404        int32_t count = 0;
405        LL_ITER it1 = ll_iter_create(l);
406        LL_ITER it2 = ll_iter_create(elements_to_remove);
407       
408        void *data1, *data2;
409        while ((data1=ll_iter_next(&it1))) {
410                ll_iter_reset(&it2);
411                while ((data2=ll_iter_next(&it2))) {
412                        if (data1 == data2) {
413                                ll_iter_remove(&it1);
414                                count++;
415                                break;
416                        }
417                }
418        }
419
420        return count;
421}
422
423void 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   
439    cs_debug_mask(D_TRACE, "sort: count %d size %d", l->count, sizeof(p[0]));
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}
Note: See TracBrowser for help on using the repository browser.