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// Includes.
20//
21
22#include <citrusleaf/cf_vector.h>
23#include <citrusleaf/alloc.h>
24#include <string.h>
25
26//==========================================================
27// Constants & typedefs.
28//
29
30// Private flags.
31#define VECTOR_FLAG_FREE_SELF 0x10
32#define VECTOR_FLAG_FREE_VECTOR 0x20
33
34
35//==========================================================
36// Forward declarations.
37//
38
39static bool vector_resize(cf_vector *v, uint32_t new_capacity);
40
41
42//==========================================================
43// Macros.
44//
45
46#define VECTOR_LOCK(_v) \
47if ((_v->flags & VECTOR_FLAG_BIGLOCK) != 0) { \
48 pthread_mutex_lock(&((cf_vector *)_v)->LOCK); \
49}
50
51#define VECTOR_UNLOCK(_v) \
52if ((_v->flags & VECTOR_FLAG_BIGLOCK) != 0) { \
53 pthread_mutex_unlock(&((cf_vector *)_v)->LOCK); \
54}
55
56
57//==========================================================
58// Public API.
59//
60
61cf_vector *
62cf_vector_create(uint32_t ele_sz, uint32_t capacity, uint32_t flags)
63{
64 cf_vector *v = cf_malloc(sizeof(cf_vector));
65
66 if (! v) {
67 return NULL;
68 }
69
70 if (cf_vector_init(v, ele_sz, capacity,
71 flags | VECTOR_FLAG_FREE_SELF) != 0) {
72 cf_free(v);
73 return NULL;
74 }
75
76 return v;
77}
78
79int
80cf_vector_init(cf_vector *v, uint32_t ele_sz, uint32_t capacity, uint32_t flags)
81{
82 uint8_t *buf;
83
84 if (capacity != 0) {
85 if (! (buf = cf_malloc(capacity * ele_sz))) {
86 return -1;
87 }
88 }
89 else {
90 buf = NULL;
91 }
92
93 cf_vector_init_with_buf(v, ele_sz, capacity, buf,
94 flags | VECTOR_FLAG_FREE_VECTOR);
95
96 return 0;
97}
98
99void
100cf_vector_init_with_buf(cf_vector *v, uint32_t ele_sz, uint32_t capacity,
101 uint8_t *buf, uint32_t flags)
102{
103 v->ele_sz = ele_sz;
104 v->flags = flags;
105 v->capacity = capacity;
106 v->count = 0;
107 v->vector = buf;
108
109 if ((flags & VECTOR_FLAG_INITZERO) != 0 && v->vector) {
110 memset(v->vector, 0, capacity * ele_sz);
111 }
112
113 if ((flags & VECTOR_FLAG_BIGLOCK) != 0) {
114 pthread_mutex_init(&v->LOCK, NULL);
115 }
116}
117
118// Deprecated - use cf_vector_init_with_buf().
119void
120cf_vector_init_smalloc(cf_vector *v, uint32_t ele_sz, uint8_t *sbuf,
121 uint32_t sbuf_sz, uint32_t flags)
122{
123 cf_vector_init_with_buf(v, ele_sz, sbuf_sz / ele_sz, sbuf, flags);
124}
125
126void
127cf_vector_destroy(cf_vector *v)
128{
129 if ((v->flags & VECTOR_FLAG_BIGLOCK) != 0) {
130 pthread_mutex_destroy(&v->LOCK);
131 }
132
133 if (v->vector && (v->flags & VECTOR_FLAG_FREE_VECTOR) != 0) {
134 cf_free(v->vector);
135 }
136
137 if ((v->flags & VECTOR_FLAG_FREE_SELF) != 0) {
138 cf_free(v);
139 }
140}
141
142int
143cf_vector_set(cf_vector *v, uint32_t idx, const void *val)
144{
145 VECTOR_LOCK(v);
146
147 if (idx >= v->capacity) {
148 VECTOR_UNLOCK(v);
149 return -1;
150 }
151
152 memcpy(v->vector + (idx * v->ele_sz), val, v->ele_sz);
153
154 if (idx >= v->count) {
155 v->count = idx + 1;
156 }
157
158 VECTOR_UNLOCK(v);
159
160 return 0;
161}
162
163int
164cf_vector_append_lockfree(cf_vector *v, const void *val)
165{
166 if (v->count >= v->capacity && ! vector_resize(v, v->count * 2)) {
167 return -1;
168 }
169
170 memcpy(v->vector + (v->count * v->ele_sz), val, v->ele_sz);
171 v->count++;
172
173 return 0;
174}
175
176int
177cf_vector_append(cf_vector *v, const void *val)
178{
179 VECTOR_LOCK(v);
180
181 int ret = cf_vector_append_lockfree(v, val);
182
183 VECTOR_UNLOCK(v);
184
185 return ret;
186}
187
188int
189cf_vector_append_unique(cf_vector *v, const void *val)
190{
191 VECTOR_LOCK(v);
192
193 uint8_t *p = v->vector;
194 uint32_t ele_sz = v->ele_sz;
195
196 for (uint32_t i = 0; i < v->count; i++) {
197 if (memcmp(val, p, ele_sz) == 0) {
198 VECTOR_UNLOCK(v);
199 return 0;
200 }
201
202 p += ele_sz;
203 }
204
205 int rv = cf_vector_append_lockfree(v, val);
206
207 VECTOR_UNLOCK(v);
208
209 return rv;
210}
211
212int
213cf_vector_pop(cf_vector *v, void *val)
214{
215 VECTOR_LOCK(v);
216
217 if (v->count == 0) {
218 VECTOR_UNLOCK(v);
219 return -1;
220 }
221
222 v->count--;
223 memcpy(val, v->vector + (v->count * v->ele_sz), v->ele_sz);
224
225 VECTOR_UNLOCK(v);
226
227 return 0;
228}
229
230int
231cf_vector_get(const cf_vector *v, uint32_t idx, void *val)
232{
233 VECTOR_LOCK(v);
234
235 if (idx >= v->capacity) {
236 VECTOR_UNLOCK(v);
237 return -1;
238 }
239
240 memcpy(val, v->vector + (idx * v->ele_sz), v->ele_sz);
241
242 VECTOR_UNLOCK(v);
243
244 return 0;
245}
246
247bool
248cf_vector_get_sized(const cf_vector *v, uint32_t idx, void *val, uint32_t sz)
249{
250 if (v->ele_sz <= sz) {
251 return cf_vector_get(v, idx, val) == 0;
252 }
253
254 uint8_t* buf = alloca(v->ele_sz);
255
256 if (cf_vector_get(v, idx, &buf) != 0) {
257 return false;
258 }
259
260 return true;
261}
262
263void *
264cf_vector_getp(cf_vector *v, uint32_t idx)
265{
266 VECTOR_LOCK(v);
267
268 if (idx >= v->capacity) {
269 VECTOR_UNLOCK(v);
270 return NULL;
271 }
272
273 void *ele = v->vector + (idx * v->ele_sz);
274
275 VECTOR_UNLOCK(v);
276
277 return ele;
278}
279
280void *
281cf_vector_getp_vlock(cf_vector *v, uint32_t idx, pthread_mutex_t **vlock)
282{
283 if ((v->flags & VECTOR_FLAG_BIGLOCK) == 0) {
284 return NULL;
285 }
286
287 VECTOR_LOCK(v);
288
289 if (idx >= v->capacity) {
290 VECTOR_UNLOCK(v);
291 return NULL;
292 }
293
294 *vlock = &((cf_vector *)v)->LOCK;
295
296 return v->vector + (idx * v->ele_sz);
297}
298
299int
300cf_vector_delete(cf_vector *v, uint32_t idx)
301{
302 VECTOR_LOCK(v);
303
304 if (idx >= v->count) {
305 VECTOR_UNLOCK(v);
306 return -1;
307 }
308
309 if (idx != v->count - 1) {
310 memmove(v->vector + (idx * v->ele_sz),
311 v->vector + ((idx + 1) * v->ele_sz),
312 (v->count - (idx + 1)) * v->ele_sz );
313 }
314
315 v->count--;
316
317 VECTOR_UNLOCK(v);
318
319 return 0;
320}
321
322int
323cf_vector_delete_range(cf_vector *v, uint32_t start, uint32_t end)
324{
325 if (start >= end) {
326 return -1;
327 }
328
329 VECTOR_LOCK(v);
330
331 if (start >= v->count || end > v->count) {
332 VECTOR_UNLOCK(v);
333 return -1;
334 }
335
336 // Copy down if not at end.
337 if (end != v->count) {
338 memmove( v->vector + (start * v->ele_sz),
339 v->vector + ((end) * v->ele_sz),
340 (v->count - end) * v->ele_sz );
341
342 }
343
344 v->count -= end - start;
345
346 VECTOR_UNLOCK(v);
347
348 return 0;
349}
350
351void
352cf_vector_clear(cf_vector *v)
353{
354 VECTOR_LOCK(v);
355
356 v->count = 0;
357
358 if ((v->flags & VECTOR_FLAG_INITZERO) != 0) {
359 memset(v->vector, 0, v->capacity * v->ele_sz);
360 }
361
362 VECTOR_UNLOCK(v);
363}
364
365void
366cf_vector_compact(cf_vector *v)
367{
368 VECTOR_LOCK(v);
369
370 if (v->capacity != 0 && (v->count != v->capacity)) {
371 v->vector = cf_realloc(v->vector, v->count * v->capacity);
372 v->capacity = v->count;
373 }
374
375 VECTOR_UNLOCK(v);
376}
377
378
379//==========================================================
380// Local helpers - variable key size public API.
381//
382
383static bool
384vector_resize(cf_vector *v, uint32_t new_capacity)
385{
386 if (new_capacity == 0) {
387 new_capacity = 2;
388 }
389
390 uint8_t *p;
391
392 if (! v->vector || (v->flags & VECTOR_FLAG_FREE_VECTOR) == 0) {
393 if (! (p = cf_malloc(new_capacity * v->ele_sz))) {
394 return false;
395 }
396
397 if (v->vector) {
398 memcpy(p, v->vector, v->capacity * v->ele_sz);
399 v->flags |= VECTOR_FLAG_FREE_VECTOR;
400 }
401 }
402 else if (! (p = cf_realloc(v->vector, new_capacity * v->ele_sz))) {
403 return false;
404 }
405
406 v->vector = p;
407
408 if ((v->flags & VECTOR_FLAG_INITZERO) != 0) {
409 memset(v->vector + (v->capacity * v->ele_sz), 0,
410 (new_capacity - v->capacity) * v->ele_sz);
411 }
412
413 v->capacity = new_capacity;
414
415 return true;
416}
417