1 /* WEED is free software; you can redistribute it and/or
2 modify it under the terms of the GNU Lesser General Public
3 License as published by the Free Software Foundation; either
4 version 3 of the License, or (at your option) any later version.
5
6 Weed is distributed in the hope that it will be useful,
7 but WITHOUT ANY WARRANTY; without even the implied warranty of
8 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
9 Lesser General Public License for more details.
10
11 You should have received a copy of the GNU Lesser General Public
12 License along with this source code; if not, write to the Free Software
13 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
14
15 Weed is developed by:
16 Gabriel "Salsaman" Finch - http://lives-video.com
17
18 partly based on LiViDO, which is developed by:
19 Niels Elburg - http://veejay.sf.net
20 Denis "Jaromil" Rojo - http://freej.dyne.org
21 Tom Schouten - http://zwizwa.fartit.com
22 Andraz Tori - http://cvs.cinelerra.org
23
24 reviewed with suggestions and contributions from:
25 Silvano "Kysucix" Galliani - http://freej.dyne.org
26 Kentaro Fukuchi - http://megaui.net/fukuchi
27 Jun Iio - http://www.malib.net
28 Carlo Prelz - http://www2.fluido.as:8080/
29 */
30
31 /* (C) G. Finch, 2005 - 2020 */
32
33 // implementation of libweed with or without glib's slice allocator, with or without thread safety (needs pthread)
34
35 #include <string.h>
36 #include <stdlib.h>
37 #include <stdio.h>
38
39 #ifdef USE_GSLICE
40 #include <glib.h>
41 #endif
42
43 #define __LIBWEED__
44
45 #ifndef NEED_LOCAL_WEED
46 #include <weed/weed.h>
47 #else
48 #include "weed.h"
49 #endif
50
51 //#define WEED_MAGIC_HASH 0x7C9EBD07 // the magic number
52 #define WEED_MAGIC_HASH 0xB82E802F
53 #define WEED_FLAG_OP_DELETE WEED_FLAG_RESERVED_0
54
55 #if defined __GNUC__ && !defined WEED_IGN_GNUC_OPT
56 #define GNU_FLATTEN __attribute__((flatten)) // inline all function calls
57 #define GNU_CONST __attribute__((const))
58 #define GNU_HOT __attribute__((hot))
59 #define GNU_PURE __attribute__((pure))
60 #else
61 #define GNU_FLATTEN
62 #define GNU_CONST
63 #define GNU_HOT
64 #define GNU_PURE
65 #endif
66
67 // Define EXPORTED for any platform
68 #if defined _WIN32 || defined __CYGWIN__ || defined IS_MINGW
69 #ifdef WIN_EXPORT
70 #ifdef __GNUC__
71 #define EXPORTED __attribute__ ((dllexport))
72 #else
73 #define EXPORTED __declspec(dllexport) // Note: actually gcc seems to also support this syntax.
74 #endif
75 #else
76 #ifdef __GNUC__
77 #define EXPORTED __attribute__ ((dllimport))
78 #else
79 #define EXPORTED __declspec(dllimport) // Note: actually gcc seems to also support this syntax.
80 #endif
81 #endif
82 #define NOT_EXPORTED
83 #else
84 #if __GNUC__ >= 4
85 #define EXPORTED __attribute__ ((visibility ("default")))
86 #define NOT_EXPORTED __attribute__ ((visibility ("hidden")))
87 #else
88 #define EXPORTED
89 #define NOT_EXPORTED
90 #endif
91 #endif
92
93 #include <pthread.h>
94
95 typedef struct {
96 pthread_rwlock_t chain_lock;
97 pthread_rwlock_t data_lock;
98 pthread_mutex_t data_mutex;
99 } leaf_priv_data_t;
100
101 typedef struct {
102 leaf_priv_data_t ldata;
103 pthread_rwlock_t reader_count;
104 pthread_mutex_t structure_mutex;
105 } plant_priv_data_t;
106
107 #define is_plant(leaf) (leaf->key_hash == WEED_MAGIC_HASH)
108
109 #define get_data_lock(leaf) (is_plant(leaf) ? \
110 &(((plant_priv_data_t *)((leaf)->private_data))->ldata.data_lock) : \
111 &(((leaf_priv_data_t *)((leaf)->private_data))->data_lock))
112
113 #define get_chain_lock(leaf) (is_plant(leaf) ? \
114 &(((plant_priv_data_t *)((leaf)->private_data))->ldata.chain_lock) : \
115 &(((leaf_priv_data_t *)((leaf)->private_data))->chain_lock))
116
117 #define get_data_mutex(leaf) (is_plant(leaf) ? \
118 &(((plant_priv_data_t *)((leaf)->private_data))->ldata.data_mutex) : \
119 &(((leaf_priv_data_t *)((leaf)->private_data))->data_mutex))
120
121 #define get_structure_mutex(plant) (&(((plant_priv_data_t *)((plant)->private_data))->structure_mutex))
122
123
124 #define get_count_lock(plant) (&(((plant_priv_data_t *)((plant)->private_data))->reader_count))
125
126 #define data_lock_unlock(obj) do { \
127 if ((obj)) pthread_rwlock_unlock(get_data_lock((obj)));} while (0)
128
129 #define data_lock_writelock(obj) do { \
130 if ((obj)) pthread_rwlock_wrlock(get_data_lock((obj)));} while (0)
131
132 #define data_lock_readlock(obj) do { \
133 if ((obj)) pthread_rwlock_rdlock(get_data_lock((obj)));} while (0)
134
135 #define chain_lock_unlock(obj) do { \
136 if ((obj)) pthread_rwlock_unlock(get_chain_lock((obj)));} while (0)
137
138 #define chain_lock_writelock(obj) do { \
139 if ((obj)) pthread_rwlock_wrlock(get_chain_lock((obj)));} while (0)
140
141 #define chain_lock_readlock(obj) do { \
142 if ((obj)) pthread_rwlock_rdlock(get_chain_lock((obj)));} while (0)
143
144 #define chain_lock_try_writelock(obj) (pthread_rwlock_trywrlock(get_chain_lock((obj))))
145
146 #define chain_lock_try_readlock(obj) (pthread_rwlock_tryrdlock(get_chain_lock((obj))))
147
148 #define structure_mutex_trylock(obj) (pthread_mutex_trylock(get_structure_mutex((obj))))
149
150 #define structure_mutex_lock(obj) do { \
151 if ((obj)) pthread_mutex_lock(get_structure_mutex((obj)));} while (0)
152
153 #define structure_mutex_unlock(obj) do { \
154 if ((obj)) pthread_mutex_unlock(get_structure_mutex((obj)));} while (0)
155
156 #define reader_count_add(obj) do { \
157 if ((obj)) pthread_rwlock_rdlock(get_count_lock((obj)));} while (0)
158
159 #define reader_count_sub(obj) do { \
160 if ((obj)) pthread_rwlock_unlock(get_count_lock((obj)));} while (0)
161
162 #define reader_count_wait(obj) do { \
163 if ((obj)) pthread_rwlock_wrlock(get_count_lock((obj))); \
164 pthread_rwlock_unlock(get_count_lock((obj)));} while (0)
165
166 #define return_unlock(obj, val) do { \
167 typeof(val) myval = (val); data_lock_unlock((obj)); return myval;} while (0)
168
data_lock_upgrade(weed_leaf_t * leaf,int block)169 static int data_lock_upgrade(weed_leaf_t *leaf, int block) {
170 if (leaf) {
171 // try to grab the mutex
172 int ret = pthread_mutex_trylock(get_data_mutex(leaf));
173 if (ret) {
174 // if we fail and !block, return with data readlock held
175 if (!block) return ret;
176 else {
177 // otherwise, drop the data readlock in case a writer is blocked
178 // then block until we do get data mutex
179 data_lock_unlock(leaf);
180 pthread_mutex_lock(get_data_mutex(leaf));
181 }
182 }
183 else data_lock_unlock(leaf);
184 // now we can wait for the writelock and then unlock mutex
185 // subsequent writers will drop their readlocks and block on the mutex
186 data_lock_writelock(leaf);
187 pthread_mutex_unlock(get_data_mutex(leaf));
188 }
189 return 0;
190 }
191
chain_lock_upgrade(weed_leaf_t * leaf,int have_rdlock,int is_del)192 static int chain_lock_upgrade(weed_leaf_t *leaf, int have_rdlock, int is_del) {
193 // grab the mutex, release the readlock held, grab a write lock, release the mutex,
194 // release the writelock
195 // if blocking is 0, then we return if we cannot get the mutex
196 // return 0 if we got the write lock, otherwise
197 if (leaf) {
198 if (!have_rdlock) {
199 // lock the leaf (plant)
200 structure_mutex_lock(leaf);
201 }
202 else chain_lock_unlock(leaf);
203 // now we have the mutex lock, we grab the writelock
204 // with the mutex held, other threads will be blocked
205 // and released their readlocks, allowing us to proceed
206
207 chain_lock_writelock(leaf);
208
209 // if it is a SET, then we release the mutex; the next writer
210 // will block on writelock; subsequent writeers will block on the mutex
211 if (is_del) leaf->flags |= WEED_FLAG_OP_DELETE;
212 else if (!have_rdlock) structure_mutex_unlock(leaf);
213
214 }
215 return 0;
216 }
217
218 static int allbugfixes = 0;
219 static int debugmode = 0;
220
221 static int32_t _abi_ = WEED_ABI_VERSION;
222
223 EXPORTED int32_t weed_get_abi_version(void);
224 EXPORTED weed_error_t weed_init(int32_t abi, uint64_t init_flags);
225
226 static weed_plant_t *_weed_plant_new(int32_t plant_type) GNU_FLATTEN;
227 static weed_error_t _weed_plant_free(weed_plant_t *) GNU_FLATTEN;
228 static char **_weed_plant_list_leaves(weed_plant_t *, weed_size_t *nleaves) GNU_FLATTEN;
229 static weed_error_t _weed_leaf_get(weed_plant_t *, const char *key, int32_t idx,
230 weed_voidptr_t value) GNU_HOT;
231 static weed_error_t _weed_leaf_set(weed_plant_t *, const char *key, uint32_t seed_type,
232 weed_size_t num_elems, weed_voidptr_t values) GNU_FLATTEN;
233 static weed_size_t _weed_leaf_num_elements(weed_plant_t *, const char *key) GNU_FLATTEN;
234 static weed_size_t _weed_leaf_element_size(weed_plant_t *, const char *key, int32_t idx) GNU_FLATTEN;
235 static uint32_t _weed_leaf_seed_type(weed_plant_t *, const char *key) GNU_FLATTEN;
236 static uint32_t _weed_leaf_get_flags(weed_plant_t *, const char *key) GNU_FLATTEN;
237 static weed_error_t _weed_leaf_delete(weed_plant_t *, const char *key) GNU_FLATTEN;
238
239 /* host only functions */
240 static weed_error_t _weed_leaf_set_flags(weed_plant_t *, const char *key, uint32_t flags) GNU_FLATTEN;
241
242 static weed_error_t _weed_leaf_set_private_data(weed_plant_t *, const char *key, void *data)
243 GNU_FLATTEN;
244 static weed_error_t _weed_leaf_get_private_data(weed_plant_t *, const char *key, void **data_return)
245 GNU_FLATTEN;
246
247 /* internal functions */
248 static weed_leaf_t *weed_find_leaf(weed_plant_t *, const char *key, uint32_t *hash_ret)
249 GNU_FLATTEN GNU_HOT;
250 static weed_leaf_t *weed_leaf_new(const char *key, uint32_t seed_type, uint32_t hash) GNU_FLATTEN;
251
252 static int weed_strcmp(const char *, const char *) GNU_HOT;
253 static weed_size_t weed_strlen(const char *) GNU_PURE;
254 static uint32_t weed_hash(const char *) GNU_PURE;
255
256 #ifdef USE_GSLICE
257 #define weed_malloc g_slice_alloc
258 #define weed_malloc_sizeof g_slice_new
259 #define weed_unmalloc_sizeof g_slice_free
260 #define weed_unmalloc_and_copy g_slice_free1
261
262 #if GLIB_CHECK_VERSION(2, 14, 0)
263 #define weed_malloc_and_copy(bsize, block) g_slice_copy(bsize, block)
264 #endif
265
266 #else
267 #define weed_malloc malloc
268 #define weed_malloc_sizeof(t) malloc(sizeof(t))
269 #define weed_unmalloc_sizeof(t, ptr) free(ptr)
270 #define weed_unmalloc_and_copy(size, ptr) free(ptr)
271 #endif
272
273 #ifndef weed_malloc_and_copy
274 #define weed_malloc_and_copy(size, src) memcpy(malloc(size), src, size)
275 #endif
276
277 #define weed_strdup(oldstring, size) (!oldstring ? (char *)NULL : \
278 size < _WEED_PADBYTES_ ? memcpy(leaf->padding, key, size + 1) : \
279 (char *)(weed_malloc_and_copy(weed_strlen(oldstring) + 1, \
280 oldstring)))
281
282 #define IS_VALID_SEED_TYPE(seed_type) ((seed_type >=64 || (seed_type >= 1 && seed_type <= 5) ? 1 : 0))
283
weed_get_abi_version(void)284 EXPORTED int32_t weed_get_abi_version(void) {return _abi_;}
285
weed_init(int32_t abi,uint64_t init_flags)286 EXPORTED weed_error_t weed_init(int32_t abi, uint64_t init_flags) {
287 // this is called by the host in order for it to set its version of the functions
288
289 // *the plugin should never call this, instead the plugin functions are passed to the plugin
290 // from the host in the "host_info" plant*
291
292 if (abi < 0 || abi > WEED_ABI_VERSION) return WEED_ERROR_BADVERSION;
293 _abi_ = abi;
294
295 if (init_flags & WEED_INIT_ALLBUGFIXES) allbugfixes = 1;
296 if (init_flags & WEED_INIT_DEBUGMODE) debugmode = 1;
297
298 if (debugmode) {
299 fprintf(stderr, "Weed padding size is %d\n", _WEED_PADBYTES_);
300 }
301
302 weed_leaf_get = _weed_leaf_get;
303 weed_leaf_delete = _weed_leaf_delete;
304 weed_plant_free = _weed_plant_free;
305 weed_plant_new = _weed_plant_new;
306 weed_leaf_set = _weed_leaf_set;
307 weed_plant_list_leaves = _weed_plant_list_leaves;
308 weed_leaf_num_elements = _weed_leaf_num_elements;
309 weed_leaf_element_size = _weed_leaf_element_size;
310 weed_leaf_seed_type = _weed_leaf_seed_type;
311 weed_leaf_get_flags = _weed_leaf_get_flags;
312 weed_leaf_set_flags = _weed_leaf_set_flags;
313 if (_abi_ >= 200) {
314 weed_leaf_get_private_data = _weed_leaf_get_private_data;
315 weed_leaf_set_private_data = _weed_leaf_set_private_data;
316 }
317 return WEED_SUCCESS;
318 }
319
320 #define weed_strlen(s) ((s) ? strlen((s)) : 0)
321 #define weed_strcmp(s1, s2) ((!(s1) || !(s2)) ? (s1 != s2) : strcmp(s1, s2))
322
323 #define get16bits(d) (*((const uint16_t *) (d)))
324
325 #define HASHROOT 5381
326 // fast hash from: http://www.azillionmonkeys.com/qed/hash.html
327 // (c) Paul Hsieh
weed_hash(const char * key)328 static uint32_t weed_hash(const char *key) {
329 if (key && *key) {
330 int len = weed_strlen(key), rem = len & 3;
331 uint32_t hash = len + HASHROOT, tmp;
332 len >>= 2;
333 for (; len > 0; len--) {
334 hash += get16bits (key);
335 tmp = (get16bits (key+2) << 11) ^ hash;
336 hash = (hash << 16) ^ tmp;
337 key += 4;
338 hash += hash >> 11;
339 }
340 switch (rem) {
341 case 3: hash += get16bits (key);
342 hash ^= hash << 16;
343 hash ^= ((int8_t)key[2]) << 18;
344 hash += hash >> 11;
345 break;
346 case 2: hash += get16bits (key);
347 hash ^= hash << 11; hash += hash >> 17;
348 break;
349 case 1: hash += (int8_t)*key;
350 hash ^= hash << 10; hash += hash >> 1;
351 break;
352 default: break;
353 }
354 hash ^= hash << 3; hash += hash >> 5; hash ^= hash << 4;
355 hash += hash >> 17; hash ^= hash << 25; hash += hash >> 6;
356 return hash;
357 }
358 return 0;
359 }
360
361 #define weed_seed_is_ptr(seed_type) (seed_type >= 64 ? 1 : 0)
362
363 #define weed_seed_get_size(seed_type, size) (seed_type == WEED_SEED_FUNCPTR ? WEED_FUNCPTR_SIZE : \
364 weed_seed_is_ptr(seed_type) ? WEED_VOIDPTR_SIZE : \
365 (seed_type == WEED_SEED_BOOLEAN || \
366 seed_type == WEED_SEED_INT) ? 4 : \
367 seed_type == WEED_SEED_DOUBLE ? 8 : \
368 seed_type == WEED_SEED_INT64 ? 8 : \
369 seed_type == WEED_SEED_STRING ? size : 0)
370
weed_data_free(weed_data_t ** data,weed_size_t num_valid_elems,weed_size_t num_elems,uint32_t seed_type)371 static inline void *weed_data_free(weed_data_t **data, weed_size_t num_valid_elems,
372 weed_size_t num_elems, uint32_t seed_type) {
373 int is_nonptr = !weed_seed_is_ptr(seed_type);
374 for (weed_size_t i = 0; i < num_valid_elems; i++) {
375 if (is_nonptr && data[i]->value.voidptr)
376 weed_unmalloc_and_copy(data[i]->size, data[i]->value.voidptr);
377 weed_unmalloc_sizeof(weed_data_t, data[i]);
378 }
379 weed_unmalloc_and_copy(num_elems * sizeof(weed_data_t *), data);
380 return NULL;
381 }
382
weed_data_new(uint32_t seed_type,weed_size_t num_elems,weed_voidptr_t values)383 static inline weed_data_t **weed_data_new(uint32_t seed_type, weed_size_t num_elems,
384 weed_voidptr_t values) {
385 weed_data_t **data;
386 if (!num_elems) return NULL;
387 if (!(data = (weed_data_t **)weed_malloc(num_elems * sizeof(weed_data_t *)))) return NULL;
388 else {
389 char **valuec = (char **)values;
390 weed_voidptr_t *valuep = (weed_voidptr_t *)values;
391 weed_funcptr_t *valuef = (weed_funcptr_t *)values;
392 int is_ptr = (weed_seed_is_ptr(seed_type));
393 for (int i = 0; i < num_elems; i++) {
394 if (!(data[i] = weed_malloc_sizeof(weed_data_t)))
395 return weed_data_free(data, --i, num_elems, seed_type);
396 if (seed_type == WEED_SEED_STRING) {
397 data[i]->value.voidptr = (weed_voidptr_t)(((data[i]->size = weed_strlen(valuec[i])) > 0) ?
398 (weed_voidptr_t)weed_malloc_and_copy(data[i]->size, valuec[i]) : NULL);
399 } else {
400 data[i]->size = weed_seed_get_size(seed_type, 0);
401 if (seed_type == WEED_SEED_FUNCPTR)
402 memcpy(&data[i]->value.funcptr, &valuef[i], WEED_FUNCPTR_SIZE);
403 else {
404 if (is_ptr) memcpy(&data[i]->value.voidptr, &valuep[i], WEED_VOIDPTR_SIZE);
405 else data[i]->value.voidptr =
406 (weed_voidptr_t)(weed_malloc_and_copy(data[i]->size,
407 (char *)values + i * data[i]->size));
408 }}
409 if (!is_ptr && !data[i]->value.voidptr && data[i]->size > 0) //ymemory error
410 return weed_data_free(data, --i, num_elems, seed_type);
411 }}
412 return data;
413 }
414
weed_find_leaf(weed_plant_t * plant,const char * key,uint32_t * hash_ret)415 static inline weed_leaf_t *weed_find_leaf(weed_plant_t *plant, const char *key, uint32_t *hash_ret) {
416 uint32_t hash = WEED_MAGIC_HASH;
417 weed_leaf_t *leaf = plant, *chain_leaf = NULL;
418 int checkmode = 0;
419
420 if (!plant) return NULL;
421
422 if (key && *key) {
423 // if hash_ret is set then this is a setter looking for leaf
424 // in this case it already has a rwt_writelock and does not need to check further
425 if (!hash_ret) {
426 /// grab rwt mutex
427 /// if we get a readlock, then remove it at end
428 /// othewise check flagbits, if op. is !SET, run in checking mode
429 if (chain_lock_try_readlock(plant)) {
430 // another thread has writelock
431 if (plant->flags & WEED_FLAG_OP_DELETE) checkmode = 1;
432 }
433 else chain_lock_unlock(plant);
434 // this counts the number of readers running in non-check mode
435 if (!checkmode) {
436 reader_count_add(plant);
437 }
438 }
439
440 hash = weed_hash(key);
441
442 while (leaf && (hash != leaf->key_hash || weed_strcmp((char *)leaf->key, (char *)key))) {
443 leaf = leaf->next;
444 if (checkmode && leaf) {
445 // lock leaf so it cannot be freed till we have passed over it
446 // also we will block if the next leaf is about to be adjusted
447 chain_lock_readlock(leaf);
448 chain_lock_unlock(chain_leaf); // does nothing if chain_leaf is NULL
449 chain_leaf = leaf;
450 }
451 }
452 if (leaf) data_lock_readlock(leaf);
453 if (!hash_ret) {
454 chain_lock_unlock(chain_leaf);
455 if (!checkmode) reader_count_sub(plant);
456 }
457 }
458 else data_lock_readlock(leaf);
459 if (hash_ret) *hash_ret = hash;
460 return leaf;
461 }
462
weed_leaf_free(weed_leaf_t * leaf)463 static inline void *weed_leaf_free(weed_leaf_t *leaf) {
464 if (leaf->data)
465 weed_data_free((void *)leaf->data, leaf->num_elements, leaf->num_elements, leaf->seed_type);
466 if (leaf->key != leaf->padding) weed_unmalloc_and_copy(weed_strlen(leaf->key) + 1,
467 (void *)leaf->key);
468 data_lock_unlock(leaf);
469 data_lock_readlock(leaf);
470 data_lock_upgrade(leaf, 1);
471 data_lock_unlock(leaf);
472
473 if (is_plant(leaf)) {
474 plant_priv_data_t *pdata = (plant_priv_data_t *)leaf->private_data;
475 weed_unmalloc_sizeof(plant_priv_data_t, pdata);
476 }
477 else {
478 leaf_priv_data_t *ldata = (leaf_priv_data_t *)leaf->private_data;
479 weed_unmalloc_sizeof(leaf_priv_data_t, ldata);
480 }
481 weed_unmalloc_sizeof(weed_leaf_t, leaf);
482 return NULL;
483 }
484
weed_leaf_new(const char * key,uint32_t seed_type,uint32_t hash)485 static inline weed_leaf_t *weed_leaf_new(const char *key, uint32_t seed_type, uint32_t hash) {
486 weed_leaf_t *leaf = weed_malloc_sizeof(weed_leaf_t);
487 if (!leaf) return NULL;
488 leaf->key_hash = hash;
489 leaf->next = NULL;
490 leaf->key = weed_strdup(key, weed_strlen(key));
491 if (!leaf->key) {weed_unmalloc_sizeof(weed_leaf_t, leaf); return NULL;}
492 leaf->num_elements = 0;
493 leaf->seed_type = seed_type;
494 leaf->flags = 0;
495 leaf->data = NULL;
496 if (is_plant(leaf)) {
497 plant_priv_data_t *pdata = weed_malloc_sizeof(plant_priv_data_t);
498 if (!pdata) {
499 if (leaf->key != leaf->padding)
500 weed_unmalloc_and_copy(weed_strlen(leaf->key + 1) + 2,
501 (void *)leaf->key);
502 weed_unmalloc_sizeof(weed_leaf_t, leaf); return NULL;}
503 pthread_rwlock_init(&pdata->ldata.chain_lock, NULL);
504 pthread_rwlock_init(&pdata->ldata.data_lock, NULL);
505 pthread_mutex_init(&pdata->ldata.data_mutex, NULL);
506
507 pthread_rwlock_init(&pdata->reader_count, NULL);
508 pthread_mutex_init(&pdata->structure_mutex, NULL);
509 leaf->private_data = (void *)pdata;
510 }
511 else {
512 leaf_priv_data_t *ldata = weed_malloc_sizeof(leaf_priv_data_t);
513 if (!ldata) {
514 if (leaf->key != leaf->padding)
515 weed_unmalloc_and_copy(weed_strlen(leaf->key + 1) + 2,
516 (void *)leaf->key);
517 weed_unmalloc_sizeof(weed_leaf_t, leaf); return NULL;}
518
519 pthread_rwlock_init(&ldata->chain_lock, NULL);
520 pthread_rwlock_init(&ldata->data_lock, NULL);
521 pthread_mutex_init(&ldata->data_mutex, NULL);
522 leaf->private_data = (void *)ldata;
523 }
524 return leaf;
525 }
526
weed_leaf_append(weed_plant_t * plant,weed_leaf_t * newleaf)527 static inline weed_error_t weed_leaf_append(weed_plant_t *plant, weed_leaf_t *newleaf) {
528 newleaf->next = plant->next;
529 plant->next = newleaf;
530 return WEED_SUCCESS;
531 }
532
_weed_plant_free(weed_plant_t * plant)533 static weed_error_t _weed_plant_free(weed_plant_t *plant) {
534 weed_leaf_t *leaf, *leafprev = plant, *leafnext;
535 if (!plant) return WEED_SUCCESS;
536
537 if (plant->flags & WEED_FLAG_UNDELETABLE) return WEED_ERROR_UNDELETABLE;
538
539 // see: weed_leaf_delete
540 chain_lock_upgrade(plant, 0, 1);
541
542 reader_count_wait(plant);
543
544 /// hold on to mutex until we are done
545 //rwt_mutex_unlock(plant);
546 leafnext = plant->next;
547 while ((leaf = leafnext)) {
548 leafnext = leaf->next;
549 if (leaf->flags & WEED_FLAG_UNDELETABLE) {
550 leafprev = leaf;
551 }
552 else {
553 leafprev->next = leafnext;
554 data_lock_readlock(leaf);
555 weed_leaf_free(leaf);
556 }}
557
558 if (!plant->next) {
559 // remove lock temporarily just in case other threads were trying to grab a read lock
560 chain_lock_unlock(plant);
561 structure_mutex_unlock(plant);
562
563 chain_lock_upgrade(plant, 0, 1);
564 reader_count_wait(plant);
565 chain_lock_unlock(plant);
566 structure_mutex_unlock(plant);
567
568 data_lock_readlock(plant);
569 data_lock_upgrade(plant, 1);
570 weed_leaf_free(plant);
571 return WEED_SUCCESS;
572 }
573 plant->flags ^= WEED_FLAG_OP_DELETE;
574 chain_lock_unlock(plant);
575 structure_mutex_unlock(plant);
576 return WEED_ERROR_UNDELETABLE;
577 }
578
_weed_leaf_delete(weed_plant_t * plant,const char * key)579 static weed_error_t _weed_leaf_delete(weed_plant_t *plant, const char *key) {
580 weed_leaf_t *leaf, *leafprev = plant;
581 uint32_t hash = weed_hash(key);
582
583 // lock out all other deleters, setters
584 ///
585 /// why do we do this ?
586 /// - we lock out other deleters because otherwise it becomes too complex
587 /// another deleter may delete our prev. node or our target
588 /// - we lock out setters to avoid the possibility that we are deleting the leaf following
589 /// TODO:
590 /// once we have passed the first leaf we can then allow setters again. There is the chance
591 /// that a setter will set the value of a leaf, and then we delete it.
592 /// It is thus up to the calling application to handle this possibility.
593
594 // we will grab the mutex, forcing other rivals to drop their readlocks
595 // (which actually none of them will have in the present implementation)
596 // and then block.
597 // and temporarily stop the flow of new readers
598 // then we get writelock, and release the mutex. This allows new readers in
599 // prior to this, we set
600 // WEED_FLAG_OP_DELETE, forcing new readers to run in checkmode, locking
601 // and unlocking the the travel rwlock as they go
602 // readers which are running in non-check mode will be counted in count lock
603 // so before doing any updates we will first wait for count to reach zero
604
605 // Before deleting the target, we will witelock the prev node travel mutex.
606 // Since readers are now in checkmode, they will be blocked there.
607 // once we get that writelock, we know that there can be no readers on prev node
608 // this is to guard against edge cases where a reader has read next link from the previous
609 /// node but has not yet locked the the travel rwlock on the target node/
610 // we can now repoint the prev node and unlock the prev node travel writelock
611 // knowing that further readers will now be routed past the leaf to be deleted
612 // We can also unlock the plant, since new readers no longer need to run in check mode.
613 // finally, before deleting leaf, we must ensure there are no reamaining readers on it
614 // we do this by first obtaining a travel rwlock write lock on it, then obtaining a normal
615 // data writelock (there sholdnt be any writers anyway, since we locked out new writers at the
616 /// start, and waited for count to reach zero)
617 // we then know it is safe to delete leaf !
618
619 chain_lock_upgrade(plant, 0, 1);
620
621 leaf = plant;
622
623 while (leaf && (leaf->key_hash != hash || weed_strcmp((char *)leaf->key, (char *)key))) {
624 // no match
625
626 // still have rwtlock on leafprev
627 // still have rwtlock on leaf
628 // we will grab rwtlock on next leaf
629 if (leaf != plant) {
630 if (leafprev != plant) chain_lock_unlock(leafprev);
631 leafprev = leaf; // leafprev is still locked
632 }
633 leaf = leaf->next;
634 chain_lock_readlock(leaf); // does nothing if leaf is NULL
635 }
636 // finish with rwtlock on prevprev. prev amd leaf
637 if (!leaf || leaf == plant) {
638 chain_lock_unlock(plant);
639 if (leafprev != plant) chain_lock_unlock(leafprev);
640 structure_mutex_unlock(plant);
641 return WEED_ERROR_NOSUCH_LEAF;
642 }
643
644 if (leaf->flags & WEED_FLAG_UNDELETABLE) {
645 chain_lock_unlock(plant);
646 if (leafprev != leaf && leafprev != plant) chain_lock_unlock(leafprev);
647 if (leaf != plant) chain_lock_unlock(leaf);
648 structure_mutex_unlock(plant);
649 return WEED_ERROR_UNDELETABLE;
650 }
651
652 // we dont update link until we have write trans. lock on leafprev
653 // - after that, new readers will only get the new value, so we can be sure that
654 // if we get trans write lock and data write lock on leaf then it is safe to free it
655 // there can still be read / write locks on leafprev but we dont care about that
656
657 // first, wait for non-checking readers to complete
658 reader_count_wait(plant);
659
660 // block readers at leafprev
661 if (leafprev != plant) chain_lock_upgrade(leafprev, 1, 0);
662
663 // adjust the link
664 leafprev->next = leaf->next;
665
666 // and that is it, job done. Now we can free leaf at leisure
667 plant->flags ^= WEED_FLAG_OP_DELETE;
668 chain_lock_unlock(plant);
669 if (leafprev != leaf && leafprev != plant) chain_lock_unlock(leafprev);
670 structure_mutex_unlock(plant);
671
672 // get a trans write link on leaf, once we have this, all readers have moved to the next
673 // leaf, and we are almosy done
674 chain_lock_upgrade(leaf, 1, 0);
675 chain_lock_unlock(leaf);
676
677 // wait for all readers / writers on leaf to complete
678 data_lock_writelock(leaf);
679 weed_leaf_free(leaf);
680
681 return WEED_SUCCESS;
682 }
683
_weed_leaf_set_flags(weed_plant_t * plant,const char * key,uint32_t flags)684 static weed_error_t _weed_leaf_set_flags(weed_plant_t *plant, const char *key, uint32_t flags) {
685 weed_leaf_t *leaf;
686 // strip any reserved bits from flags
687 if (!(leaf = weed_find_leaf(plant, key, NULL))) return WEED_ERROR_NOSUCH_LEAF;
688 // block here, flags are important
689 data_lock_upgrade(leaf, 1);
690 leaf->flags = (leaf->flags & WEED_FLAGBITS_RESERVED) | (flags & ~WEED_FLAGBITS_RESERVED);
691 return_unlock(leaf, WEED_SUCCESS);
692 }
693
_weed_leaf_set_private_data(weed_plant_t * plant,const char * key,void * data)694 static weed_error_t _weed_leaf_set_private_data(weed_plant_t *plant, const char *key, void *data) {
695 weed_leaf_t *leaf;
696 if (!(leaf = weed_find_leaf(plant, key, NULL))) return WEED_ERROR_NOSUCH_LEAF;
697 return_unlock(leaf, WEED_ERROR_CONCURRENCY);
698 }
699
_weed_plant_new(int32_t plant_type)700 static weed_plant_t *_weed_plant_new(int32_t plant_type) {
701 weed_leaf_t *leaf = weed_leaf_new(WEED_LEAF_TYPE, WEED_SEED_INT, WEED_MAGIC_HASH);
702 if (!leaf) return NULL;
703 leaf->data = weed_data_new(WEED_SEED_INT, 1, &plant_type);
704 if (!leaf->data) return weed_leaf_free(leaf);
705 leaf->num_elements = 1;
706 leaf->flags = WEED_FLAG_IMMUTABLE;
707 return leaf;
708 }
709
_weed_plant_list_leaves(weed_plant_t * plant,weed_size_t * nleaves)710 static char **_weed_plant_list_leaves(weed_plant_t *plant, weed_size_t *nleaves) {
711 // must use normal malloc, strdup here since the caller will free the strings
712 weed_leaf_t *leaf = plant;
713 char **leaflist;
714 int i = 1, j = 0;
715 if (nleaves) *nleaves = 0;
716 chain_lock_upgrade(plant, 0, 0);
717
718 for (; leaf; i++) leaf = leaf->next;
719 if (!(leaflist = (char **)malloc(i * sizeof(char *)))) {
720 chain_lock_unlock(plant);
721 return NULL;
722 }
723 for (leaf = plant; leaf; leaf = leaf->next) {
724 leaflist[j++] = strdup(leaf->key);
725 if (!leaflist[j - 1]) {
726 chain_lock_unlock(plant);
727 for (--j; j > 0; free(leaflist[--j]));
728 free(leaflist);
729 return NULL;
730 }}
731 chain_lock_unlock(plant);
732 leaflist[j] = NULL;
733 if (nleaves) *nleaves = j;
734 return leaflist;
735 }
736
_weed_leaf_set(weed_plant_t * plant,const char * key,uint32_t seed_type,weed_size_t num_elems,weed_voidptr_t values)737 static weed_error_t _weed_leaf_set(weed_plant_t *plant, const char *key,
738 uint32_t seed_type, weed_size_t num_elems,
739 weed_voidptr_t values) {
740 weed_data_t **data = NULL;
741 weed_leaf_t *leaf;
742 uint32_t hash;
743 int isnew = 0;
744 weed_size_t old_num_elems = 0;
745 weed_data_t **old_data = NULL;
746
747 if (!plant) return WEED_ERROR_NOSUCH_LEAF;
748 if (!IS_VALID_SEED_TYPE(seed_type)) return WEED_ERROR_WRONG_SEED_TYPE;
749
750 // lock out other setters
751 chain_lock_upgrade(plant, 0, 0);
752
753 if (!(leaf = weed_find_leaf(plant, key, &hash))) {
754 if (!(leaf = weed_leaf_new(key, seed_type, hash))) {
755 chain_lock_unlock(plant);
756 return WEED_ERROR_MEMORY_ALLOCATION;
757 }
758 isnew = 1;
759 } else {
760 // we hold a readlock on the leaf, we will to grab the mutex and upgrade to a writelock
761 // if we fail, too bad the other thread has priority
762
763 if (seed_type != leaf->seed_type) {
764 chain_lock_unlock(plant);
765 return_unlock(leaf, WEED_ERROR_WRONG_SEED_TYPE);
766 }
767 if (leaf->flags & WEED_FLAG_IMMUTABLE) {
768 chain_lock_unlock(plant);
769 return_unlock(leaf, WEED_ERROR_IMMUTABLE);
770 }
771 if (leaf == plant && num_elems != 1) {
772 chain_lock_unlock(plant);
773 return_unlock(leaf, WEED_ERROR_NOSUCH_ELEMENT); ///< type leaf must always have exactly 1 value
774 }
775 if (data_lock_upgrade(leaf, 0)) {
776 data_lock_unlock(leaf);
777 chain_lock_unlock(plant);
778 return_unlock(leaf, WEED_ERROR_CONCURRENCY);
779 }
780
781 chain_lock_unlock(plant);
782 old_num_elems = leaf->num_elements;
783 old_data = leaf->data;
784 }
785
786 if (num_elems) {
787 data = (weed_data_t **)weed_data_new(seed_type, num_elems, values);
788 if (!data) {
789 // memory failure...
790 if (isnew) {
791 chain_lock_unlock(plant);
792 weed_leaf_free(leaf);
793 leaf = NULL;
794 }
795 return_unlock(leaf, WEED_ERROR_MEMORY_ALLOCATION);
796 }
797 }
798
799 leaf->data = data;
800 leaf->num_elements = num_elems;
801
802 if (isnew) {
803 weed_leaf_append(plant, leaf);
804 chain_lock_unlock(plant);
805 }
806 else data_lock_unlock(leaf);
807
808 if (old_data) weed_data_free(old_data, old_num_elems, old_num_elems, seed_type);
809
810 return WEED_SUCCESS;
811 }
812
_weed_leaf_get(weed_plant_t * plant,const char * key,int32_t idx,weed_voidptr_t value)813 static weed_error_t _weed_leaf_get(weed_plant_t *plant, const char *key, int32_t idx,
814 weed_voidptr_t value) {
815 weed_data_t **data;
816 uint32_t type;
817 weed_leaf_t *leaf;
818
819 if (!(leaf = weed_find_leaf(plant, key, NULL))) {
820 return WEED_ERROR_NOSUCH_LEAF;
821 }
822
823 if (idx >= leaf->num_elements) {
824 return_unlock(leaf, WEED_ERROR_NOSUCH_ELEMENT);
825 }
826 if (!value) return_unlock(leaf, WEED_SUCCESS);
827
828 type = leaf->seed_type;
829 data = leaf->data;
830
831 if (type == WEED_SEED_FUNCPTR) memcpy(value, &(data[idx])->value.funcptr, WEED_FUNCPTR_SIZE);
832 else {
833 if (weed_seed_is_ptr(type)) memcpy(value, &(data[idx])->value.voidptr, WEED_VOIDPTR_SIZE);
834 else {
835 if (type == WEED_SEED_STRING) {
836 size_t size = (size_t)data[idx]->size;
837 char **valuecharptrptr = (char **)value;
838 if (size > 0) memcpy(*valuecharptrptr, data[idx]->value.voidptr, size);
839 (*valuecharptrptr)[size] = 0;
840 } else memcpy(value, data[idx]->value.voidptr, leaf->data[idx]->size);
841 }}
842
843 return_unlock(leaf, WEED_SUCCESS);
844 }
845
_weed_leaf_num_elements(weed_plant_t * plant,const char * key)846 static weed_size_t _weed_leaf_num_elements(weed_plant_t *plant, const char *key) {
847 weed_leaf_t *leaf;
848 if (!(leaf = weed_find_leaf(plant, key, NULL))) return 0;
849 return_unlock(leaf, leaf->num_elements);
850 }
851
852
_weed_leaf_element_size(weed_plant_t * plant,const char * key,int32_t idx)853 static weed_size_t _weed_leaf_element_size(weed_plant_t *plant, const char *key, int32_t idx) {
854 weed_leaf_t *leaf;
855 if (!(leaf = weed_find_leaf(plant, key, NULL))) return 0;
856 if (idx > leaf->num_elements) return_unlock(leaf, 0);
857 return_unlock(leaf, leaf->data[idx]->size);
858 }
859
_weed_leaf_seed_type(weed_plant_t * plant,const char * key)860 static uint32_t _weed_leaf_seed_type(weed_plant_t *plant, const char *key) {
861 weed_leaf_t *leaf;
862 if (!(leaf = weed_find_leaf(plant, key, NULL))) return WEED_SEED_INVALID;
863 return_unlock(leaf, leaf->seed_type);
864 }
865
_weed_leaf_get_flags(weed_plant_t * plant,const char * key)866 static uint32_t _weed_leaf_get_flags(weed_plant_t *plant, const char *key) {
867 weed_leaf_t *leaf;
868 if (!(leaf = weed_find_leaf(plant, key, NULL))) return 0;
869 return_unlock(leaf, (uint32_t)(leaf->flags & ~WEED_FLAGBITS_RESERVED));
870 }
871
_weed_leaf_get_private_data(weed_plant_t * plant,const char * key,void ** data_return)872 static weed_error_t _weed_leaf_get_private_data(weed_plant_t *plant, const char *key,
873 void **data_return) {
874 weed_leaf_t *leaf;
875 if (!(leaf = weed_find_leaf(plant, key, NULL))) return WEED_ERROR_NOSUCH_LEAF;
876 return_unlock(leaf, WEED_ERROR_CONCURRENCY);
877 }
878