1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /*
3 * Copyright 2014 Couchbase, Inc.
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * 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,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 #include "sllist.h"
19 #include <libcouchbase/assert.h>
20 #include <stdlib.h>
21 #include <stdio.h>
22 #ifndef INLINE
23 #ifdef _MSC_VER
24 #define INLINE __inline
25 #elif __GNUC__
26 #define INLINE __inline__
27 #else
28 #define INLINE inline
29 #endif /* MSC_VER */
30 #endif /* !INLINE */
31
32
33 static INLINE int
sllist_contains(sllist_root * list,sllist_node * item)34 sllist_contains(sllist_root *list, sllist_node *item)
35 {
36 sllist_node *ll;
37 SLLIST_FOREACH(list, ll) {
38 if (item == ll) {
39 return 1;
40 }
41 }
42 return 0;
43 }
44
45 static INLINE unsigned
sllist_get_size(sllist_root * list)46 sllist_get_size(sllist_root *list)
47 {
48 unsigned ret = 0;
49 sllist_node *ll;
50 SLLIST_FOREACH(list, ll) {
51 ret++;
52 }
53 return ret;
54 }
55
56 /* #define SLLIST_DEBUG */
57
58 #ifdef SLLIST_DEBUG
59 #define slist_sanity_insert(l, n) lcb_assert(!slist_contains(l, n))
60 #else
61 #define slist_sanity_insert(l, n)
62 #endif
63
64 static INLINE void
slist_iter_init_at(sllist_node * node,sllist_iterator * iter)65 slist_iter_init_at(sllist_node *node, sllist_iterator *iter)
66 {
67 iter->cur = node->next;
68 iter->prev = node;
69 iter->removed = 0;
70
71 if (iter->cur) {
72 iter->next = iter->cur->next;
73 } else {
74 iter->next = NULL;
75 }
76 }
77
78 static INLINE void
slist_iter_init(sllist_root * list,sllist_iterator * iter)79 slist_iter_init(sllist_root *list, sllist_iterator *iter)
80 {
81 slist_iter_init_at(&list->first_prev, iter);
82 }
83
84 static INLINE void
slist_iter_incr(sllist_root * list,sllist_iterator * iter)85 slist_iter_incr(sllist_root *list, sllist_iterator *iter)
86 {
87 if (!iter->removed) {
88 iter->prev = iter->prev->next;
89 } else {
90 iter->removed = 0;
91 }
92
93 if ((iter->cur = iter->next)) {
94 iter->next = iter->cur->next;
95 } else {
96 iter->next = NULL;
97 }
98
99 lcb_assert(iter->cur != iter->prev);
100
101 (void)list;
102 }
103
104 static INLINE void
sllist_iter_remove(sllist_root * list,sllist_iterator * iter)105 sllist_iter_remove(sllist_root *list, sllist_iterator *iter)
106 {
107 iter->prev->next = iter->next;
108
109 /** GCC strict aliasing. Yay. */
110 if (iter->prev->next == NULL && iter->prev == &list->first_prev) {
111 list->last = NULL;
112 } else if (iter->cur == list->last && iter->next == NULL) {
113 /* removing the last item */
114 list->last = iter->prev;
115 }
116 iter->removed = 1;
117 }
118
119 static INLINE void
sllist_remove_head(sllist_root * list)120 sllist_remove_head(sllist_root *list)
121 {
122 if (!SLLIST_FIRST(list)) {
123 return;
124 }
125
126 SLLIST_FIRST(list) = SLLIST_FIRST(list)->next;
127
128 if (!SLLIST_FIRST(list)) {
129 list->last = NULL;
130 }
131 }
132
133 static INLINE void
sllist_remove(sllist_root * list,sllist_node * item)134 sllist_remove(sllist_root *list, sllist_node *item)
135 {
136 sllist_iterator iter;
137 SLLIST_ITERFOR(list, &iter) {
138 if (iter.cur == item) {
139 sllist_iter_remove(list, &iter);
140 return;
141 }
142 }
143 fprintf(stderr, "SLLIST: Requested to remove item %p which is not in %p\n", (void*)list, (void*)item);
144 lcb_assert(0);
145 }
146
147 static INLINE void
sllist_append(sllist_root * list,sllist_node * item)148 sllist_append(sllist_root *list, sllist_node *item)
149 {
150 if (SLLIST_IS_EMPTY(list)) {
151 SLLIST_FIRST(list) = list->last = item;
152 item->next = NULL;
153 } else {
154 slist_sanity_insert(list, item);
155 list->last->next = item;
156 list->last = item;
157 }
158 item->next = NULL;
159 }
160
161 static INLINE void
sllist_prepend(sllist_root * list,sllist_node * item)162 sllist_prepend(sllist_root *list, sllist_node *item)
163 {
164 if (SLLIST_IS_EMPTY(list)) {
165 SLLIST_FIRST(list) = list->last = item;
166 } else {
167 slist_sanity_insert(list, item);
168 item->next = SLLIST_FIRST(list);
169 SLLIST_FIRST(list) = item;
170 }
171 }
172
173 static void
sllist_insert(sllist_root * list,sllist_node * prev,sllist_node * item)174 sllist_insert(sllist_root *list, sllist_node *prev, sllist_node *item)
175 {
176 item->next = prev->next;
177 prev->next = item;
178 if (item->next == NULL) {
179 list->last = item;
180 }
181 }
182
183 static INLINE void
sllist_insert_sorted(sllist_root * list,sllist_node * item,int (* compar)(sllist_node *,sllist_node *))184 sllist_insert_sorted(sllist_root *list, sllist_node *item,
185 int (*compar)(sllist_node*, sllist_node*))
186 {
187 sllist_iterator iter;
188 SLLIST_ITERFOR(list, &iter) {
189 int rv = compar(item, iter.cur);
190 /** if the item we have is before the current, prepend it here */
191 if (rv <= 0) {
192 sllist_insert(list, iter.prev, item);
193 return;
194 }
195 }
196 sllist_append(list, item);
197 }
198