Branch data Line data Source code
1 : : /***
2 : : This file is part of PulseAudio.
3 : :
4 : : Copyright 2006-2008 Lennart Poettering
5 : : Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
6 : : Copyright (C) 2012 Canonical Ltd.
7 : :
8 : : Contact: Jyri Sarha <Jyri.Sarha@nokia.com>
9 : :
10 : : PulseAudio is free software; you can redistribute it and/or modify
11 : : it under the terms of the GNU Lesser General Public License as
12 : : published by the Free Software Foundation; either version 2.1 of the
13 : : License, or (at your option) any later version.
14 : :
15 : : PulseAudio is distributed in the hope that it will be useful, but
16 : : WITHOUT ANY WARRANTY; without even the implied warranty of
17 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 : : Lesser General Public License for more details.
19 : :
20 : : You should have received a copy of the GNU Lesser General Public
21 : : License along with PulseAudio; if not, write to the Free Software
22 : : Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
23 : : USA.
24 : : ***/
25 : :
26 : : #ifdef HAVE_CONFIG_H
27 : : #include <config.h>
28 : : #endif
29 : :
30 : : #include <pulse/xmalloc.h>
31 : :
32 : : #include <pulsecore/atomic.h>
33 : : #include <pulsecore/log.h>
34 : : #include <pulsecore/macro.h>
35 : : #include <pulsecore/core-util.h>
36 : : #include <pulsecore/macro.h>
37 : :
38 : : #include "flist.h"
39 : :
40 : : #define FLIST_SIZE 128
41 : :
42 : : /* Atomic table indices contain
43 : : sign bit = if set, indicates empty/NULL value
44 : : tag bits (to avoid the ABA problem)
45 : : actual index bits
46 : : */
47 : :
48 : : /* Lock free single linked list element. */
49 : : struct pa_flist_elem {
50 : : pa_atomic_t next;
51 : : pa_atomic_ptr_t ptr;
52 : : };
53 : :
54 : : typedef struct pa_flist_elem pa_flist_elem;
55 : :
56 : : struct pa_flist {
57 : : char *name;
58 : : unsigned size;
59 : :
60 : : pa_atomic_t current_tag;
61 : : int index_mask;
62 : : int tag_shift;
63 : : int tag_mask;
64 : :
65 : : /* Stack that contains pointers stored into free list */
66 : : pa_atomic_t stored;
67 : : /* Stack that contains empty list elements */
68 : : pa_atomic_t empty;
69 : : pa_flist_elem table[];
70 : : };
71 : :
72 : : /* Lock free pop from linked list stack */
73 : 1770 : static pa_flist_elem *stack_pop(pa_flist *flist, pa_atomic_t *list) {
74 : : pa_flist_elem *popped;
75 : : int idx;
76 [ - + ]: 1770 : pa_assert(list);
77 : :
78 : : do {
79 : 1770 : idx = pa_atomic_load(list);
80 [ + + ]: 1770 : if (idx < 0)
81 : : return NULL;
82 : 1711 : popped = &flist->table[idx & flist->index_mask];
83 [ - + ]: 1770 : } while (!pa_atomic_cmpxchg(list, idx, pa_atomic_load(&popped->next)));
84 : :
85 : : return popped;
86 : : }
87 : :
88 : : /* Lock free push to linked list stack */
89 : 13230 : static void stack_push(pa_flist *flist, pa_atomic_t *list, pa_flist_elem *new_elem) {
90 : : int tag, newindex, next;
91 [ - + ]: 13230 : pa_assert(list);
92 : :
93 : 26460 : tag = pa_atomic_inc(&flist->current_tag);
94 : 13230 : newindex = new_elem - flist->table;
95 [ + - ][ + ]: 13230 : pa_assert(newindex >= 0 && newindex < (int) flist->size);
96 : 13231 : newindex |= (tag << flist->tag_shift) & flist->tag_mask;
97 : :
98 : : do {
99 : 13231 : next = pa_atomic_load(list);
100 : 13231 : pa_atomic_store(&new_elem->next, next);
101 [ - + ]: 13231 : } while (!pa_atomic_cmpxchg(list, next, newindex));
102 : 13231 : }
103 : :
104 : 20 : pa_flist *pa_flist_new_with_name(unsigned size, const char *name) {
105 : : pa_flist *l;
106 : : unsigned i;
107 [ - + ]: 20 : pa_assert(name);
108 : :
109 [ + + ]: 20 : if (!size)
110 : 10 : size = FLIST_SIZE;
111 : :
112 : 20 : l = pa_xmalloc0(sizeof(pa_flist) + sizeof(pa_flist_elem) * size);
113 : :
114 : 20 : l->name = pa_xstrdup(name);
115 : 20 : l->size = size;
116 : :
117 [ + + ]: 190 : while (1 << l->tag_shift < (int) size)
118 : 170 : l->tag_shift++;
119 : 20 : l->index_mask = (1 << l->tag_shift) - 1;
120 : 20 : l->tag_mask = INT_MAX - l->index_mask;
121 : :
122 : 20 : pa_atomic_store(&l->stored, -1);
123 : 20 : pa_atomic_store(&l->empty, -1);
124 [ + + ]: 11540 : for (i=0; i < size; i++) {
125 : 11520 : stack_push(l, &l->empty, &l->table[i]);
126 : : }
127 : 20 : return l;
128 : : }
129 : :
130 : 10 : pa_flist *pa_flist_new(unsigned size) {
131 : 10 : return pa_flist_new_with_name(size, "unknown");
132 : : }
133 : :
134 : 9 : void pa_flist_free(pa_flist *l, pa_free_cb_t free_cb) {
135 [ - + ]: 9 : pa_assert(l);
136 [ - + ]: 9 : pa_assert(l->name);
137 : :
138 [ - + ]: 9 : if (free_cb) {
139 : : pa_flist_elem *elem;
140 [ # # ]: 0 : while((elem = stack_pop(l, &l->stored)))
141 : 0 : free_cb(pa_atomic_ptr_load(&elem->ptr));
142 : : }
143 : :
144 : 9 : pa_xfree(l->name);
145 : 9 : pa_xfree(l);
146 : 9 : }
147 : :
148 : 882 : int pa_flist_push(pa_flist *l, void *p) {
149 : : pa_flist_elem *elem;
150 [ - + ]: 882 : pa_assert(l);
151 [ - + ]: 882 : pa_assert(p);
152 : :
153 : 882 : elem = stack_pop(l, &l->empty);
154 [ - + ]: 882 : if (elem == NULL) {
155 [ # # ]: 0 : if (pa_log_ratelimit(PA_LOG_DEBUG))
156 : 0 : pa_log_debug("%s flist is full (don't worry)", l->name);
157 : : return -1;
158 : : }
159 : 882 : pa_atomic_ptr_store(&elem->ptr, p);
160 : 882 : stack_push(l, &l->stored, elem);
161 : :
162 : 882 : return 0;
163 : : }
164 : :
165 : 888 : void* pa_flist_pop(pa_flist *l) {
166 : : pa_flist_elem *elem;
167 : : void *ptr;
168 [ - + ]: 888 : pa_assert(l);
169 : :
170 : 888 : elem = stack_pop(l, &l->stored);
171 [ + + ]: 888 : if (elem == NULL)
172 : : return NULL;
173 : :
174 : 1658 : ptr = pa_atomic_ptr_load(&elem->ptr);
175 : :
176 : 829 : stack_push(l, &l->empty, elem);
177 : :
178 : 888 : return ptr;
179 : : }
|
