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#pragma once
18
19/*
20 * SYNOPSIS
21 * LinkedList
22 * Sometimes the answer is a doubly linked list. It's not that frequent, but
23 * all the corner cases in a double linked list can be annoying.
24 *
25 * the current use pattern is the caller creates a structure that starts with a 'cf_ll_element',
26 * ie, can be cast to a cf_ll_element. The caller allocates and frees the memory.
27 * (There are far cooler ways to do this, so if you want to improve this, go ahead!
28 *
29 */
30
31#include <aerospike/as_std.h>
32#include <pthread.h>
33
34#ifdef __cplusplus
35extern "C" {
36#endif
37
38/******************************************************************************
39 * CONSTANTS
40 ******************************************************************************/
41
42#define CF_LL_REDUCE_DELETE (1)
43#define CF_LL_REDUCE_INSERT (2)
44#define CF_LL_REDUCE_MATCHED (3)
45#define CF_LL_REDUCE_NOT_MATCHED (4)
46/******************************************************************************
47 * TYPES
48 ******************************************************************************/
49
50typedef struct cf_ll_s cf_ll;
51typedef struct cf_ll_element_s cf_ll_element;
52typedef struct cf_ll_iterator_s cf_ll_iterator;
53typedef int (*cf_ll_reduce_fn) (cf_ll_element * e, void *udata);
54typedef void (*cf_ll_destructor) (cf_ll_element * e);
55
56/**
57 * cf_ll_element
58 * The element that must be included in structures
59 * This element should be the FIRST element in the structure where it is being included
60 */
61struct cf_ll_element_s {
62 cf_ll_element * next;
63 cf_ll_element * prev;
64};
65
66/**
67 * cf_ll_iterator
68 * the linked list iterator
69 */
70struct cf_ll_iterator_s {
71 cf_ll_element * next;
72 bool forward;
73};
74/**
75 * cf_ll
76 * the linked list container
77 */
78struct cf_ll_s {
79 cf_ll_element * head;
80 cf_ll_element * tail;
81 cf_ll_destructor destroy_fn;
82 uint32_t sz;
83 bool uselock;
84 pthread_mutex_t LOCK;
85};
86
87/******************************************************************************
88 * INLINE FUNCTIONS
89 ******************************************************************************/
90
91static inline cf_ll_element *cf_ll_get_head(cf_ll *ll) {
92 return(ll->head);
93}
94
95static inline cf_ll_element *cf_ll_get_tail(cf_ll *ll) {
96 return(ll->tail);
97}
98
99static inline cf_ll_element *cf_ll_get_next(cf_ll_element *e) {
100 return(e->next);
101}
102
103static inline cf_ll_element *cf_ll_get_prev(cf_ll_element *e) {
104 return(e->prev);
105}
106
107/******************************************************************************
108 * FUNCTIONS
109 ******************************************************************************/
110
111/**
112 * Insert to head
113 */
114void cf_ll_prepend(cf_ll *ll, cf_ll_element *e );
115
116/**
117 * Insert to tail
118 */
119void cf_ll_append(cf_ll *ll, cf_ll_element *e );
120
121/**
122 * Insert after element !! warning! consider threadsafety before using this call!
123 */
124void cf_ll_insert_after(cf_ll *ll, cf_ll_element *cur, cf_ll_element *ins);
125
126/**
127 * Insert before element !! warning! consider threadsafey before using this call!
128 */
129void cf_ll_insert_before(cf_ll *ll, cf_ll_element *cur, cf_ll_element *ins);
130
131/**
132 * delete element - the real joy of a doubly linked list
133 * If a destructor function has been set, call it as well
134 */
135void cf_ll_delete(cf_ll *ll, cf_ll_element *e );
136
137uint32_t cf_ll_size(cf_ll *ll);
138/*
139 * Create a iterator for linked list. Will move from head to tail
140 * if forward is true else from tail to head
141 */
142cf_ll_iterator * cf_ll_getIterator(cf_ll * ll, bool forward);
143
144/*
145 * Get next element of linked list pointed by iterator
146 */
147cf_ll_element * cf_ll_getNext(cf_ll_iterator *iter);
148
149/*
150 * Release iterator
151 */
152void cf_ll_releaseIterator(cf_ll_iterator *iter);
153
154/*
155 * Search an element in the linked list.
156 */
157cf_ll_element * cf_ll_search(cf_ll *ll, cf_ll_element *e, bool forward, cf_ll_reduce_fn fn);
158
159/*
160 * Get the linked list element through indexing
161 */
162cf_ll_element *cf_ll_index(cf_ll *ll, int index);
163/**
164 * The way these reduces work:
165 * ** If you're reducing and you want to delete this element, return CF_LL_REDUCE_DELETE
166 * and it'll be removed from the list - but iteration will not halt
167 * ** If you return a negative value, the reduction will terminate immediatly and that
168 * return value will be passed to the reducer
169 * ** The 'forward' parameter specifies whether you want to traverse from front to back,
170 * pass in 'false' to go tail-to-head
171 */
172int cf_ll_reduce( cf_ll *ll, bool forward, cf_ll_reduce_fn fn, void *udata);
173
174/**
175 * Insert-before
176 * Sometimes you want to iterate a list, and insert before a certain element.
177 * Common when you're trying to keep a sorted list and you have some knowledge
178 * that either the list is short, or you're doing inserts of a particular pattern
179 * so that a sorted-table is not the right answer.
180 *
181 * Similar to the reduce function: if you want to bail out of the insert, return a negative
182 * If you want to insert "here", return the special code
183 * At the end of the list, you will be passed a null element (thus meaning you'll always
184 * be called at least once)
185 */
186int cf_ll_insert_reduce(cf_ll *ll, cf_ll_element *e, bool forward, cf_ll_reduce_fn fn, void *udata);
187
188/**
189 * Call this function on a head structure to initialize it to empty
190 * Call with whether you want a locked version of a lockfree version
191 * if you're handling your own locks
192 *
193 * If you're using a standard delete methodology, then don't need a destructor function,
194 * and can leave it blank. But if you're using the reduce / delete pattern, then
195 * there's not an easy way for the application-level delete to occur, because you can't
196 * free the structure first then call delete. (you could insert the element on a queue,
197 * but it would have to carefully be a reference counted object, and then you'd still
198 * need the linked-list-reduceor to decrement the linked list....)
199 * In that case, you need to have a destructor
200 * function that gets fired every time a removal from the list occurs. even on explicit
201 * deletes it's called, just to be fancy.
202 *
203 * Note that when the destructor is called, the lock for the linked list is held
204 * (if you've allocated the linked list with a lock)
205 */
206int cf_ll_init(cf_ll *ll, cf_ll_destructor destroy_fn, bool uselock);
207
208/******************************************************************************/
209
210#ifdef __cplusplus
211} // end extern "C"
212#endif
213