1 /*
2 * Copyright 2013-2015 Samy Al Bahra
3 * Copyright 2013-2014 AppNexus, Inc.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25 * SUCH DAMAGE.
26 */
27
28 #include <ck_array.h>
29 #include <ck_cc.h>
30 #include <ck_pr.h>
31 #include <ck_stdbool.h>
32 #include <ck_string.h>
33
34 static struct _ck_array *
ck_array_create(struct ck_malloc * allocator,unsigned int length)35 ck_array_create(struct ck_malloc *allocator, unsigned int length)
36 {
37 struct _ck_array *active;
38
39 active = allocator->malloc(sizeof(struct _ck_array) + sizeof(void *) * length);
40 if (active == NULL)
41 return NULL;
42
43 active->n_committed = 0;
44 active->length = length;
45
46 return active;
47 }
48
49 bool
ck_array_init(struct ck_array * array,unsigned int mode,struct ck_malloc * allocator,unsigned int length)50 ck_array_init(struct ck_array *array, unsigned int mode, struct ck_malloc *allocator, unsigned int length)
51 {
52 struct _ck_array *active;
53
54 (void)mode;
55
56 if (allocator->realloc == NULL ||
57 allocator->malloc == NULL ||
58 allocator->free == NULL ||
59 length == 0)
60 return false;
61
62 active = ck_array_create(allocator, length);
63 if (active == NULL)
64 return false;
65
66 array->n_entries = 0;
67 array->allocator = allocator;
68 array->active = active;
69 array->transaction = NULL;
70 return true;
71 }
72
73 bool
ck_array_put(struct ck_array * array,void * value)74 ck_array_put(struct ck_array *array, void *value)
75 {
76 struct _ck_array *target;
77 unsigned int size;
78
79 /*
80 * If no transaction copy has been necessary, attempt to do in-place
81 * modification of the array.
82 */
83 if (array->transaction == NULL) {
84 target = array->active;
85
86 if (array->n_entries == target->length) {
87 size = target->length << 1;
88
89 target = array->allocator->realloc(target,
90 sizeof(struct _ck_array) + sizeof(void *) * array->n_entries,
91 sizeof(struct _ck_array) + sizeof(void *) * size,
92 true);
93
94 if (target == NULL)
95 return false;
96
97 ck_pr_store_uint(&target->length, size);
98
99 /* Serialize with respect to contents. */
100 ck_pr_fence_store();
101 ck_pr_store_ptr(&array->active, target);
102 }
103
104 target->values[array->n_entries++] = value;
105 return true;
106 }
107
108 target = array->transaction;
109 if (array->n_entries == target->length) {
110 size = target->length << 1;
111
112 target = array->allocator->realloc(target,
113 sizeof(struct _ck_array) + sizeof(void *) * array->n_entries,
114 sizeof(struct _ck_array) + sizeof(void *) * size,
115 true);
116
117 if (target == NULL)
118 return false;
119
120 target->length = size;
121 array->transaction = target;
122 }
123
124 target->values[array->n_entries++] = value;
125 return false;
126 }
127
128 int
ck_array_put_unique(struct ck_array * array,void * value)129 ck_array_put_unique(struct ck_array *array, void *value)
130 {
131 unsigned int i, limit;
132 void **v;
133
134 limit = array->n_entries;
135 if (array->transaction != NULL) {
136 v = array->transaction->values;
137 } else {
138 v = array->active->values;
139 }
140
141 for (i = 0; i < limit; i++) {
142 if (v[i] == value)
143 return 1;
144 }
145
146 return -!ck_array_put(array, value);
147 }
148
149 bool
ck_array_remove(struct ck_array * array,void * value)150 ck_array_remove(struct ck_array *array, void *value)
151 {
152 struct _ck_array *target;
153 unsigned int i;
154
155 if (array->transaction != NULL) {
156 target = array->transaction;
157
158 for (i = 0; i < array->n_entries; i++) {
159 if (target->values[i] == value) {
160 target->values[i] = target->values[--array->n_entries];
161 return true;
162 }
163 }
164
165 return false;
166 }
167
168 target = array->active;
169
170 for (i = 0; i < array->n_entries; i++) {
171 if (target->values[i] == value)
172 break;
173 }
174
175 if (i == array->n_entries)
176 return false;
177
178 /* If there are pending additions, immediately eliminate the operation. */
179 if (target->n_committed != array->n_entries) {
180 ck_pr_store_ptr(&target->values[i], target->values[--array->n_entries]);
181 return true;
182 }
183
184 /*
185 * The assumption is that these allocations are small to begin with.
186 * If there is no immediate opportunity for transaction, allocate a
187 * transactional array which will be applied upon commit time.
188 */
189 target = ck_array_create(array->allocator, array->n_entries);
190 if (target == NULL)
191 return false;
192
193 memcpy(target->values, array->active->values, sizeof(void *) * array->n_entries);
194 target->length = array->n_entries;
195 target->n_committed = array->n_entries;
196 target->values[i] = target->values[--array->n_entries];
197
198 array->transaction = target;
199 return true;
200 }
201
202 bool
ck_array_commit(ck_array_t * array)203 ck_array_commit(ck_array_t *array)
204 {
205 struct _ck_array *m = array->transaction;
206
207 if (m != NULL) {
208 struct _ck_array *p;
209
210 m->n_committed = array->n_entries;
211 ck_pr_fence_store();
212 p = array->active;
213 ck_pr_store_ptr(&array->active, m);
214 array->allocator->free(p, sizeof(struct _ck_array) +
215 p->length * sizeof(void *), true);
216 array->transaction = NULL;
217
218 return true;
219 }
220
221 ck_pr_fence_store();
222 ck_pr_store_uint(&array->active->n_committed, array->n_entries);
223 return true;
224 }
225
226 void
ck_array_deinit(struct ck_array * array,bool defer)227 ck_array_deinit(struct ck_array *array, bool defer)
228 {
229
230 array->allocator->free(array->active,
231 sizeof(struct _ck_array) + sizeof(void *) * array->active->length, defer);
232
233 if (array->transaction != NULL) {
234 array->allocator->free(array->transaction,
235 sizeof(struct _ck_array) + sizeof(void *) * array->transaction->length, defer);
236 }
237
238 array->transaction = array->active = NULL;
239 return;
240 }
241