1/*
2 * Copyright 2008-2018 Aerospike, Inc.
3 *
4 * Portions may be licensed to Aerospike, Inc. under one or more contributor
5 * license agreements.
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
8 * use this file except in compliance with the License. You may obtain a copy of
9 * the License at http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
13 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
14 * License for the specific language governing permissions and limitations under
15 * the License.
16 */
17
18/**
19 * double linked list functionality
20 */
21#include <citrusleaf/cf_ll.h>
22#include <citrusleaf/alloc.h>
23
24/**
25 * SYNOPSIS
26 * LinkedList
27 * Sometimes the answer is a doubly linked list. It's not that frequent, but
28 * all the corner cases in a double linked list can be annoying.
29 */
30
31/******************************************************************************
32 * MACROS
33 ******************************************************************************/
34
35#define LL_UNLOCK(_ll) if ( _ll->uselock ) { pthread_mutex_unlock(&(_ll->LOCK)); }
36#define LL_LOCK(_ll) if ( _ll->uselock ) { pthread_mutex_lock(&(_ll->LOCK)); }
37
38/******************************************************************************
39 * FUNCTIONS
40 ******************************************************************************/
41
42void cf_ll_prepend_lockfree(cf_ll * ll, cf_ll_element * e) {
43 // empty list
44 if (ll->head == 0) {
45 ll->head = e;
46 ll->tail = e;
47 e->next = 0;
48 e->prev = 0;
49 }
50
51 // at least one element - add to head
52 else {
53 e->next = ll->head;
54 e->prev = 0;
55
56 ll->head->prev = e;
57 ll->head = e;
58 }
59
60 ll->sz++;
61}
62
63void cf_ll_prepend(cf_ll *ll, cf_ll_element *e ) {
64 LL_LOCK(ll);
65 cf_ll_prepend_lockfree(ll, e);
66 LL_UNLOCK(ll)
67}
68
69void cf_ll_append_lockfree(cf_ll *ll, cf_ll_element *e ) {
70 if (ll->head == 0) {
71 ll->head = e;
72 ll->tail = e;
73 e->next = 0;
74 e->prev = 0;
75 }
76 // at least one element - add to tail
77 else {
78 e->next = 0;
79 e->prev = ll->tail;
80
81 ll->tail->next = e;
82 ll->tail = e;
83 }
84
85 ll->sz++;
86}
87
88
89void cf_ll_append(cf_ll *ll, cf_ll_element *e ) {
90 LL_LOCK(ll);
91
92 cf_ll_append_lockfree(ll, e);
93
94 LL_UNLOCK(ll);
95}
96
97void cf_ll_insert_after_lockfree(cf_ll *ll, cf_ll_element *cur, cf_ll_element *ins) {
98 ins->next = cur->next;
99 ins->prev = cur;
100
101 if (cur->next == 0)
102 ll->tail = ins;
103 else
104 cur->next->prev = ins;
105
106 cur->next = ins;
107
108 ll->sz++;
109}
110
111
112void cf_ll_insert_after(cf_ll *ll, cf_ll_element *cur, cf_ll_element *ins) {
113 LL_LOCK(ll);
114 cf_ll_insert_after_lockfree(ll, cur, ins);
115 LL_UNLOCK(ll);
116}
117
118void cf_ll_insert_before_lockfree(cf_ll *ll, cf_ll_element *cur, cf_ll_element *ins) {
119
120 ins->next = cur;
121 ins->prev = cur->prev;
122
123 if (cur->prev == 0)
124 ll->head = ins;
125 else
126 cur->prev->next = ins;
127 cur->prev = ins;
128
129 ll->sz++;
130}
131
132void cf_ll_insert_before(cf_ll *ll, cf_ll_element *cur, cf_ll_element *ins) {
133 LL_LOCK(ll);
134 cf_ll_insert_before_lockfree( ll, cur, ins);
135 LL_UNLOCK(ll);
136}
137
138
139void cf_ll_delete_lockfree(cf_ll *ll, cf_ll_element *e ) {
140 // make empty
141 if (ll->sz == 1) {
142 ll->head = 0;
143 ll->tail = 0;
144 }
145
146 // head delete
147 else if (e == ll->head) {
148 ll->head = e->next;
149 e->next->prev = 0;
150 }
151 // tail delete
152 else if (e == ll->tail) {
153 ll->tail = e->prev;
154 e->prev->next = 0;
155 }
156 // we're in the middle somewhere
157 else {
158 e->prev->next = e->next;
159 e->next->prev = e->prev;
160 }
161
162 ll->sz --;
163
164 if (ll->destroy_fn)
165 (ll->destroy_fn) (e);
166}
167
168void cf_ll_delete(cf_ll *ll, cf_ll_element *e ) {
169 // extra check for fun
170 if (ll->sz == 0) return;
171
172 LL_LOCK(ll);
173
174 cf_ll_delete_lockfree(ll, e);
175
176 LL_UNLOCK(ll);
177
178}
179
180
181int cf_ll_reduce( cf_ll *ll, bool forward, cf_ll_reduce_fn fn, void *udata) {
182 int rv = 0;
183
184 LL_LOCK(ll);
185
186 cf_ll_element *cur = forward ? ll->head : ll->tail;
187
188 while (cur) {
189
190 if ( (rv = (*fn) (cur, udata) ) ) {
191
192 if (rv == CF_LL_REDUCE_DELETE) {
193
194 cf_ll_element *next = forward ? cur->next : cur->prev;
195 // Calls the destructor on cur, can't touch it after that
196 cf_ll_delete_lockfree(ll, cur);
197 cur = next;
198
199 }
200 else
201 goto Exit;
202 }
203 else {
204 cur = forward ? cur->next : cur->prev;
205 }
206 }
207
208Exit:
209 LL_UNLOCK(ll);
210 return(rv);
211}
212
213int cf_ll_insert_reduce(cf_ll *ll, cf_ll_element *e, bool forward, cf_ll_reduce_fn fn, void *udata) {
214 int rv = 0;
215 LL_LOCK(ll);
216
217 cf_ll_element *cur = forward ? ll->head : ll->tail;
218
219 while (cur) {
220
221 if ( (rv = (*fn) (cur, udata) ) ) {
222
223 if (rv == CF_LL_REDUCE_INSERT) {
224
225 if (forward)
226 cf_ll_insert_before_lockfree(ll, cur, e);
227 else
228 cf_ll_insert_after_lockfree(ll, cur, e);
229 rv = 0;
230
231 }
232
233 goto Exit;
234
235 }
236 else {
237 cur = forward ? cur->next : cur->prev;
238 }
239 }
240
241 // give chance to insert at "end"
242 if ( (rv = (*fn) (cur, udata) ) ) {
243 if (rv == CF_LL_REDUCE_INSERT) {
244 if (forward)
245 cf_ll_append_lockfree(ll, e);
246 else
247 cf_ll_prepend_lockfree(ll, e);
248 rv = 0;
249 }
250 }
251
252Exit:
253 LL_UNLOCK(ll);
254 return(rv);
255}
256
257uint32_t cf_ll_size(cf_ll *ll) {
258 LL_LOCK(ll);
259 uint32_t sz = ll->sz;
260 LL_UNLOCK(ll);
261 return(sz);
262}
263
264cf_ll_element * cf_ll_search_lockfree(cf_ll *ll, cf_ll_element *e, bool forward, cf_ll_reduce_fn fn) {
265 if (ll->head == NULL) {
266 return NULL;
267 }
268 int rv = 0;
269 cf_ll_element *cur = forward ? ll->head : ll->tail;
270
271 while (cur) {
272 rv = (*fn) (cur, (void*)e);
273
274 if (rv == CF_LL_REDUCE_MATCHED) {
275 return cur;
276 }
277 else if (rv == CF_LL_REDUCE_NOT_MATCHED) {
278 cur = forward ? cur->next : cur->prev;
279 rv = 0;
280 }
281 else {
282 return NULL;
283 }
284 }
285 return NULL;
286}
287
288cf_ll_element * cf_ll_search(cf_ll *ll, cf_ll_element *e, bool forward, cf_ll_reduce_fn fn)
289{
290 LL_LOCK(ll);
291
292 cf_ll_element * ele = NULL;
293 ele = cf_ll_search_lockfree(ll, e, forward, fn);
294
295 LL_UNLOCK(ll);
296
297 return ele;
298}
299
300cf_ll_iterator * cf_ll_getIterator(cf_ll * ll, bool forward)
301{
302 cf_ll_iterator *iter = NULL;
303 iter = (cf_ll_iterator *)cf_malloc(sizeof(cf_ll_iterator));
304 if (iter == NULL) {
305 return NULL;
306 }
307 iter->forward = forward;
308 iter->next = iter->forward ? ll->head : ll->tail;
309 return iter;
310}
311
312void cf_ll_releaseIterator(cf_ll_iterator *iter)
313{
314 if (iter) cf_free(iter);
315}
316
317cf_ll_element * cf_ll_getNext(cf_ll_iterator *iter)
318{
319 if (!iter) return NULL;
320 cf_ll_element * ele = iter->next;
321 if (ele != NULL) {
322 iter->next = iter->forward ? ele->next : ele->prev;
323 }
324 return ele;
325}
326
327/* Return the element at the specified zero-based index
328 * where 0 is the head, 1 is the element next to head
329 * and so on. Negative integers are used in order to count
330 * from the tail, -1 is the last element, -2 the penultimante
331 * and so on. If the index is out of range NULL is returned. */
332cf_ll_element *cf_ll_index(cf_ll *ll, int index)
333{
334 cf_ll_element *ele = NULL;
335 if (index < 0) {
336 index = (-index) - 1;
337 ele = ll->tail;
338 while (index-- && ele) {
339 ele = ele->prev;
340 }
341 }
342 else {
343 ele = ll->head;
344 while (index-- && ele) {
345 ele = ele->next;
346 }
347 }
348 return ele;
349}
350
351int cf_ll_init(cf_ll *ll, cf_ll_destructor destroy_fn, bool uselock) {
352 ll->head = 0;
353 ll->tail = 0;
354 ll->destroy_fn = destroy_fn;
355 ll->sz = 0;
356 ll->uselock = uselock;
357 if (uselock) {
358 pthread_mutex_init(&ll->LOCK, 0);
359 }
360 return(0);
361}
362