Date: Mon, 2 Mar 2015 21:35:32 +0000 (UTC) From: Baptiste Daroussin <bapt@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-vendor@freebsd.org Subject: svn commit: r279546 - in vendor/libucl/dist: . cmake doc include klib m4 src tests tests/basic uthash Message-ID: <201503022135.t22LZWo1014824@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: bapt Date: Mon Mar 2 21:35:31 2015 New Revision: 279546 URL: https://svnweb.freebsd.org/changeset/base/279546 Log: Update libucl to git version 8d3b186 Added: vendor/libucl/dist/klib/ vendor/libucl/dist/klib/khash.h (contents, props changed) vendor/libucl/dist/klib/kvec.h (contents, props changed) vendor/libucl/dist/tests/basic/14.in (contents, props changed) vendor/libucl/dist/tests/basic/14.res Deleted: vendor/libucl/dist/m4/ Modified: vendor/libucl/dist/ChangeLog.md vendor/libucl/dist/Makefile.am vendor/libucl/dist/README.md vendor/libucl/dist/cmake/CMakeLists.txt vendor/libucl/dist/configure.ac vendor/libucl/dist/doc/Makefile.am vendor/libucl/dist/doc/api.md vendor/libucl/dist/doc/libucl.3 vendor/libucl/dist/doc/pandoc.template vendor/libucl/dist/include/ucl.h vendor/libucl/dist/src/Makefile.am vendor/libucl/dist/src/ucl_emitter.c vendor/libucl/dist/src/ucl_emitter_utils.c vendor/libucl/dist/src/ucl_hash.c vendor/libucl/dist/src/ucl_hash.h vendor/libucl/dist/src/ucl_internal.h vendor/libucl/dist/src/ucl_parser.c vendor/libucl/dist/src/ucl_schema.c vendor/libucl/dist/src/ucl_util.c vendor/libucl/dist/tests/schema.test vendor/libucl/dist/tests/test_generate.c vendor/libucl/dist/tests/test_schema.c vendor/libucl/dist/uthash/utstring.h Modified: vendor/libucl/dist/ChangeLog.md ============================================================================== --- vendor/libucl/dist/ChangeLog.md Mon Mar 2 21:00:54 2015 (r279545) +++ vendor/libucl/dist/ChangeLog.md Mon Mar 2 21:35:31 2015 (r279546) @@ -20,3 +20,15 @@ ### Libucl 0.6.1 - Various utilities fixes + +### Libucl 0.7.0 + +- Move to klib library from uthash to reduce memory overhead and increase performance + +### Libucl 0.7.1 + +- Added safe iterators API + +### Libucl 0.7.2 + +- Fixed serious bugs in schema and arrays iteration Modified: vendor/libucl/dist/Makefile.am ============================================================================== --- vendor/libucl/dist/Makefile.am Mon Mar 2 21:00:54 2015 (r279545) +++ vendor/libucl/dist/Makefile.am Mon Mar 2 21:35:31 2015 (r279546) @@ -1,5 +1,5 @@ ACLOCAL_AMFLAGS = -I m4 -EXTRA_DIST = uthash README.md +EXTRA_DIST = uthash klib README.md pkgconfigdir = $(libdir)/pkgconfig pkgconfig_DATA = libucl.pc Modified: vendor/libucl/dist/README.md ============================================================================== --- vendor/libucl/dist/README.md Mon Mar 2 21:00:54 2015 (r279545) +++ vendor/libucl/dist/README.md Mon Mar 2 21:35:31 2015 (r279546) @@ -1,6 +1,6 @@ # LIBUCL -[](https://travis-ci.org/vstakhov/libucl) +[](https://travis-ci.org/vstakhov/libucl)[](https://scan.coverity.com/projects/4138) **Table of Contents** *generated with [DocToc](http://doctoc.herokuapp.com/)* @@ -156,10 +156,10 @@ is converted to the following object: ```nginx section { blah { - key = value; + key = value; } foo { - key = value; + key = value; } } ``` @@ -177,9 +177,9 @@ is presented as: ```nginx section { blah { - foo { - key = value; - } + foo { + key = value; + } } } ``` @@ -219,8 +219,8 @@ UCL supports external macros both multil ```nginx .macro "sometext"; .macro { - Some long text - .... + Some long text + .... }; ``` Modified: vendor/libucl/dist/cmake/CMakeLists.txt ============================================================================== --- vendor/libucl/dist/cmake/CMakeLists.txt Mon Mar 2 21:00:54 2015 (r279545) +++ vendor/libucl/dist/cmake/CMakeLists.txt Mon Mar 2 21:35:31 2015 (r279546) @@ -82,6 +82,7 @@ ENDIF(ENABLE_URL_SIGN MATCHES "ON") INCLUDE_DIRECTORIES("${CMAKE_CURRENT_SOURCE_DIR}/../src") INCLUDE_DIRECTORIES("${CMAKE_CURRENT_SOURCE_DIR}/../include") INCLUDE_DIRECTORIES("${CMAKE_CURRENT_SOURCE_DIR}/../uthash") +INCLUDE_DIRECTORIES("${CMAKE_CURRENT_SOURCE_DIR}/../klib") SET(UCLSRC ../src/ucl_util.c ../src/ucl_parser.c Modified: vendor/libucl/dist/configure.ac ============================================================================== --- vendor/libucl/dist/configure.ac Mon Mar 2 21:00:54 2015 (r279545) +++ vendor/libucl/dist/configure.ac Mon Mar 2 21:35:31 2015 (r279546) @@ -1,7 +1,7 @@ m4_define([maj_ver], [0]) -m4_define([med_ver], [6]) -m4_define([min_ver], [1]) -m4_define([so_version], [3:0:1]) +m4_define([med_ver], [7]) +m4_define([min_ver], [2]) +m4_define([so_version], [5:0:1]) m4_define([ucl_version], [maj_ver.med_ver.min_ver]) AC_INIT([libucl],[ucl_version],[https://github.com/vstakhov/libucl],[libucl]) Modified: vendor/libucl/dist/doc/Makefile.am ============================================================================== --- vendor/libucl/dist/doc/Makefile.am Mon Mar 2 21:00:54 2015 (r279545) +++ vendor/libucl/dist/doc/Makefile.am Mon Mar 2 21:35:31 2015 (r279546) @@ -4,5 +4,6 @@ dist_man_MANS = libucl.3 gen-man: @PANDOC@ tail -n +$$(grep -n '# Synopsis' api.md | cut -d':' -f1) api.md | \ - cat pandoc.template - | sed -e 's/^# \(.*\)/# \U\1/' | \ + cat pandoc.template - | sed -e 's/^# \(.*\)/# \U\1/' \ + -e "s/%%date%%/$$(LANG=C date +'%d %B, %Y')/" | \ @PANDOC@ -s -f markdown -t man -o libucl.3 \ No newline at end of file Modified: vendor/libucl/dist/doc/api.md ============================================================================== --- vendor/libucl/dist/doc/api.md Mon Mar 2 21:00:54 2015 (r279545) +++ vendor/libucl/dist/doc/api.md Mon Mar 2 21:35:31 2015 (r279546) @@ -377,7 +377,9 @@ If parsing operations fail then the resu # Iteration functions -Iteration are used to iterate over UCL compound types: arrays and objects. Moreover, iterations could be performed over the keys with multiple values (implicit arrays). To iterate over an object, an array or a key with multiple values there is a function `ucl_iterate_object`. +Iteration are used to iterate over UCL compound types: arrays and objects. Moreover, iterations could be performed over the keys with multiple values (implicit arrays). +There are two types of iterators API: old and unsafe one via `ucl_iterate_object` and the proposed interface of safe iterators. + ## ucl_iterate_object ~~~C @@ -402,6 +404,60 @@ while ((obj = ucl_iterate_object (top, & } ~~~ +## Safe iterators API + +Safe iterators are defined to clarify iterating over UCL objects and simplify flattening of UCL objects in non-trivial cases. +For example, if there is an implicit array that contains another array and a boolean value it is extremely unclear how to iterate over +such an object. Safe iterators are desinged to define two sorts of iteration: + +1. Iteration over complex objects with expanding all values +2. Iteration over complex objects without expanding of values + +The following example demonstrates the difference between these two types of iteration: + +~~~ +key = 1; +key = [2, 3, 4]; + +Iteration with expansion: + +1, 2, 3, 4 + +Iteration without expansion: + +1, [2, 3, 4] +~~~ + +UCL defines the following functions to manage safe iterators: + +- `ucl_object_iterate_new` - creates new safe iterator +- `ucl_object_iterate_reset` - resets iterator to a new object +- `ucl_object_iterate_safe` - safely iterate the object inside iterator +- `ucl_object_iterate_free` - free memory associated with the safe iterator + +Please note that unlike unsafe iterators, safe iterators *must* be explicitly initialized and freed. +An assert is likely generated if you use uninitialized or `NULL` iterator in all safe iterators functions. + +~~~C +ucl_object_iter_t it; +const ucl_object_t *cur; + +it = ucl_object_iterate_new (obj); + +while ((cur = ucl_object_iterate_safe (it, true)) != NULL) { + /* Do something */ +} + +/* Switch to another object */ +it = ucl_object_iterate_reset (it, another_obj); + +while ((cur = ucl_object_iterate_safe (it, true)) != NULL) { + /* Do something else */ +} + +ucl_object_iterate_free (it); +~~~ + # Validation functions Currently, there is only one validation function called `ucl_object_validate`. It performs validation of object using the specified schema. This function is defined as following: Modified: vendor/libucl/dist/doc/libucl.3 ============================================================================== --- vendor/libucl/dist/doc/libucl.3 Mon Mar 2 21:00:54 2015 (r279545) +++ vendor/libucl/dist/doc/libucl.3 Mon Mar 2 21:35:31 2015 (r279546) @@ -1,4 +1,4 @@ -.TH "LIBUCL" "3" "July 26, 2014" "Libucl manual" "" +.TH "LIBUCL" "3" "27 December, 2014" "Libucl manual" "" .SH NAME .PP \f[B]ucl_parser_new\f[], \f[B]ucl_parser_register_macro\f[], @@ -528,8 +528,9 @@ Iteration are used to iterate over UCL c objects. Moreover, iterations could be performed over the keys with multiple values (implicit arrays). -To iterate over an object, an array or a key with multiple values there -is a function \f[C]ucl_iterate_object\f[]. +There are two types of iterators API: old and unsafe one via +\f[C]ucl_iterate_object\f[] and the proposed interface of safe +iterators. .SS ucl_iterate_object .IP .nf @@ -578,6 +579,75 @@ while\ ((obj\ =\ ucl_iterate_object\ (to } \f[] .fi +.SS Safe iterators API +.PP +Safe iterators are defined to clarify iterating over UCL objects and +simplify flattening of UCL objects in non\-trivial cases. +For example, if there is an implicit array that contains another array +and a boolean value it is extremely unclear how to iterate over such an +object. +Safe iterators are desinged to define two sorts of iteration: +.IP "1." 3 +Iteration over complex objects with expanding all values +.IP "2." 3 +Iteration over complex objects without expanding of values +.PP +The following example demonstrates the difference between these two +types of iteration: +.IP +.nf +\f[C] +key\ =\ 1; +key\ =\ [2,\ 3,\ 4]; + +Iteration\ with\ expansion: + +1,\ 2,\ 3,\ 4 + +Iteration\ without\ expansion: + +1,\ [2,\ 3,\ 4] +\f[] +.fi +.PP +UCL defines the following functions to manage safe iterators: +.IP \[bu] 2 +\f[C]ucl_object_iterate_new\f[] \- creates new safe iterator +.IP \[bu] 2 +\f[C]ucl_object_iterate_reset\f[] \- resets iterator to a new object +.IP \[bu] 2 +\f[C]ucl_object_iterate_safe\f[] \- safely iterate the object inside +iterator +.IP \[bu] 2 +\f[C]ucl_object_iterate_free\f[] \- free memory associated with the safe +iterator +.PP +Please note that unlike unsafe iterators, safe iterators \f[I]must\f[] +be explicitly initialized and freed. +An assert is likely generated if you use uninitialized or \f[C]NULL\f[] +iterator in all safe iterators functions. +.IP +.nf +\f[C] +ucl_object_iter_t\ it; +const\ ucl_object_t\ *cur; + +it\ =\ ucl_object_iterate_new\ (obj); + +while\ ((cur\ =\ ucl_object_iterate_safe\ (it,\ true))\ !=\ NULL)\ { +\ \ \ \ /*\ Do\ something\ */ +} + +/*\ Switch\ to\ another\ object\ */ +it\ =\ ucl_object_iterate_reset\ (it,\ another_obj); + +while\ ((cur\ =\ ucl_object_iterate_safe\ (it,\ true))\ !=\ NULL)\ { +\ \ \ \ /*\ Do\ something\ else\ */ +} + +ucl_object_iterate_free\ (it); +\f[] +.fi .SH VALIDATION FUNCTIONS .PP Currently, there is only one validation function called Modified: vendor/libucl/dist/doc/pandoc.template ============================================================================== --- vendor/libucl/dist/doc/pandoc.template Mon Mar 2 21:00:54 2015 (r279545) +++ vendor/libucl/dist/doc/pandoc.template Mon Mar 2 21:35:31 2015 (r279546) @@ -1,6 +1,6 @@ % LIBUCL(3) Libucl manual % Vsevolod Stakhov <vsevolod@highsecure.ru> -% July 26, 2014 +% %%date%% # Name Modified: vendor/libucl/dist/include/ucl.h ============================================================================== --- vendor/libucl/dist/include/ucl.h Mon Mar 2 21:00:54 2015 (r279545) +++ vendor/libucl/dist/include/ucl.h Mon Mar 2 21:35:31 2015 (r279546) @@ -192,7 +192,7 @@ typedef struct ucl_object_s { int64_t iv; /**< Int value of an object */ const char *sv; /**< String value of an object */ double dv; /**< Double value of an object */ - struct ucl_object_s *av; /**< Array */ + void *av; /**< Array */ void *ov; /**< Object */ void* ud; /**< Opaque user data */ } value; @@ -715,6 +715,37 @@ typedef void* ucl_object_iter_t; */ UCL_EXTERN const ucl_object_t* ucl_iterate_object (const ucl_object_t *obj, ucl_object_iter_t *iter, bool expand_values); + +/** + * Create new safe iterator for the specified object + * @param obj object to iterate + * @return new iterator object that should be used with safe iterators API only + */ +UCL_EXTERN ucl_object_iter_t ucl_object_iterate_new (const ucl_object_t *obj) + UCL_WARN_UNUSED_RESULT; +/** + * Reset initialized iterator to a new object + * @param obj new object to iterate + * @return modified iterator object + */ +UCL_EXTERN ucl_object_iter_t ucl_object_iterate_reset (ucl_object_iter_t it, + const ucl_object_t *obj); + +/** + * Get the next object from the `obj`. This fucntion iterates over arrays, objects + * and implicit arrays + * @param iter safe iterator + * @return the next object in sequence + */ +UCL_EXTERN const ucl_object_t* ucl_object_iterate_safe (ucl_object_iter_t iter, + bool expand_values); + +/** + * Free memory associated with the safe iterator + * @param it safe iterator object + */ +UCL_EXTERN void ucl_object_iterate_free (ucl_object_iter_t it); + /** @} */ @@ -854,6 +885,13 @@ UCL_EXTERN ucl_object_t* ucl_parser_get_ * @param parser parser object */ UCL_EXTERN const char *ucl_parser_get_error(struct ucl_parser *parser); + +/** + * Clear the error in the parser + * @param parser parser object + */ +UCL_EXTERN void ucl_parser_clear_error(struct ucl_parser *parser); + /** * Free ucl parser object * @param parser parser object Added: vendor/libucl/dist/klib/khash.h ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ vendor/libucl/dist/klib/khash.h Mon Mar 2 21:35:31 2015 (r279546) @@ -0,0 +1,627 @@ +/* The MIT License + + Copyright (c) 2008, 2009, 2011 by Attractive Chaos <attractor@live.co.uk> + + Permission is hereby granted, free of charge, to any person obtaining + a copy of this software and associated documentation files (the + "Software"), to deal in the Software without restriction, including + without limitation the rights to use, copy, modify, merge, publish, + distribute, sublicense, and/or sell copies of the Software, and to + permit persons to whom the Software is furnished to do so, subject to + the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + SOFTWARE. +*/ + +/* + An example: + +#include "khash.h" +KHASH_MAP_INIT_INT(32, char) +int main() { + int ret, is_missing; + khiter_t k; + khash_t(32) *h = kh_init(32); + k = kh_put(32, h, 5, &ret); + kh_value(h, k) = 10; + k = kh_get(32, h, 10); + is_missing = (k == kh_end(h)); + k = kh_get(32, h, 5); + kh_del(32, h, k); + for (k = kh_begin(h); k != kh_end(h); ++k) + if (kh_exist(h, k)) kh_value(h, k) = 1; + kh_destroy(32, h); + return 0; +} +*/ + +/* + 2013-05-02 (0.2.8): + + * Use quadratic probing. When the capacity is power of 2, stepping function + i*(i+1)/2 guarantees to traverse each bucket. It is better than double + hashing on cache performance and is more robust than linear probing. + + In theory, double hashing should be more robust than quadratic probing. + However, my implementation is probably not for large hash tables, because + the second hash function is closely tied to the first hash function, + which reduce the effectiveness of double hashing. + + Reference: http://research.cs.vt.edu/AVresearch/hashing/quadratic.php + + 2011-12-29 (0.2.7): + + * Minor code clean up; no actual effect. + + 2011-09-16 (0.2.6): + + * The capacity is a power of 2. This seems to dramatically improve the + speed for simple keys. Thank Zilong Tan for the suggestion. Reference: + + - http://code.google.com/p/ulib/ + - http://nothings.org/computer/judy/ + + * Allow to optionally use linear probing which usually has better + performance for random input. Double hashing is still the default as it + is more robust to certain non-random input. + + * Added Wang's integer hash function (not used by default). This hash + function is more robust to certain non-random input. + + 2011-02-14 (0.2.5): + + * Allow to declare global functions. + + 2009-09-26 (0.2.4): + + * Improve portability + + 2008-09-19 (0.2.3): + + * Corrected the example + * Improved interfaces + + 2008-09-11 (0.2.2): + + * Improved speed a little in kh_put() + + 2008-09-10 (0.2.1): + + * Added kh_clear() + * Fixed a compiling error + + 2008-09-02 (0.2.0): + + * Changed to token concatenation which increases flexibility. + + 2008-08-31 (0.1.2): + + * Fixed a bug in kh_get(), which has not been tested previously. + + 2008-08-31 (0.1.1): + + * Added destructor +*/ + + +#ifndef __AC_KHASH_H +#define __AC_KHASH_H + +/*! + @header + + Generic hash table library. + */ + +#define AC_VERSION_KHASH_H "0.2.8" + +#include <stdlib.h> +#include <string.h> +#include <limits.h> + +/* compiler specific configuration */ + +#if UINT_MAX == 0xffffffffu +typedef unsigned int khint32_t; +#elif ULONG_MAX == 0xffffffffu +typedef unsigned long khint32_t; +#endif + +#if ULONG_MAX == ULLONG_MAX +typedef unsigned long khint64_t; +#else +typedef unsigned long long khint64_t; +#endif + +#ifndef kh_inline +#ifdef _MSC_VER +#define kh_inline __inline +#else +#define kh_inline inline +#endif +#endif /* kh_inline */ + +#ifndef kh_unused +# ifdef __GNUC__ +# define kh_unused(x) __attribute__((__unused__)) x +# else +# define kh_unused(x) x +# endif +#endif + +typedef khint32_t khint_t; +typedef khint_t khiter_t; + +#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2) +#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1) +#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3) +#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1))) +#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1))) +#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1))) +#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1)) + +#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4) + +#ifndef kroundup32 +#define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x)) +#endif + +#ifndef kcalloc +#define kcalloc(N,Z) calloc(N,Z) +#endif +#ifndef kmalloc +#define kmalloc(Z) malloc(Z) +#endif +#ifndef krealloc +#define krealloc(P,Z) realloc(P,Z) +#endif +#ifndef kfree +#define kfree(P) free(P) +#endif + +static const double __ac_HASH_UPPER = 0.77; + +#define __KHASH_TYPE(name, khkey_t, khval_t) \ + typedef struct kh_##name##_s { \ + khint_t n_buckets, size, n_occupied, upper_bound; \ + khint32_t *flags; \ + khkey_t *keys; \ + khval_t *vals; \ + } kh_##name##_t; + +#define __KHASH_PROTOTYPES(name, khkey_t, khval_t) \ + extern kh_##name##_t * kh_init_##name(void); \ + extern void kh_destroy_##name(kh_##name##_t *h); \ + extern void kh_clear_##name(kh_##name##_t *h); \ + extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \ + extern int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \ + extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \ + extern void kh_del_##name(kh_##name##_t *h, khint_t x); + +#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ + SCOPE kh_##name##_t *kh_init_##name(void) { \ + return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \ + } \ + SCOPE void kh_destroy_##name(kh_##name##_t *h) \ + { \ + if (h) { \ + kfree((void *)h->keys); kfree(h->flags); \ + kfree((void *)h->vals); \ + kfree(h); \ + } \ + } \ + SCOPE void kh_unused(kh_clear_##name)(kh_##name##_t *h) \ + { \ + if (h && h->flags) { \ + memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \ + h->size = h->n_occupied = 0; \ + } \ + } \ + SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \ + { \ + if (h->n_buckets) { \ + khint_t k, i, last, mask, step = 0; \ + mask = h->n_buckets - 1; \ + k = __hash_func(key); i = k & mask; \ + last = i; \ + while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ + i = (i + (++step)) & mask; \ + if (i == last) return h->n_buckets; \ + } \ + return __ac_iseither(h->flags, i)? h->n_buckets : i; \ + } else return 0; \ + } \ + SCOPE int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \ + { /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \ + khint32_t *new_flags = 0; \ + khint_t j = 1; \ + { \ + kroundup32(new_n_buckets); \ + if (new_n_buckets < 4) new_n_buckets = 4; \ + if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \ + else { /* hash table size to be changed (shrink or expand); rehash */ \ + new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ + if (!new_flags) return -1; \ + memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \ + if (h->n_buckets < new_n_buckets) { /* expand */ \ + khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ + if (!new_keys) { kfree(new_flags); return -1; } \ + h->keys = new_keys; \ + if (kh_is_map) { \ + khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ + if (!new_vals) { kfree(new_flags); return -1; } \ + h->vals = new_vals; \ + } \ + } /* otherwise shrink */ \ + } \ + } \ + if (j) { /* rehashing is needed */ \ + for (j = 0; j != h->n_buckets; ++j) { \ + if (__ac_iseither(h->flags, j) == 0) { \ + khkey_t key = h->keys[j]; \ + khval_t val; \ + khint_t new_mask; \ + new_mask = new_n_buckets - 1; \ + if (kh_is_map) val = h->vals[j]; \ + __ac_set_isdel_true(h->flags, j); \ + while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \ + khint_t k, i, step = 0; \ + k = __hash_func(key); \ + i = k & new_mask; \ + while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \ + __ac_set_isempty_false(new_flags, i); \ + if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \ + { khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \ + if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \ + __ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \ + } else { /* write the element and jump out of the loop */ \ + h->keys[i] = key; \ + if (kh_is_map) h->vals[i] = val; \ + break; \ + } \ + } \ + } \ + } \ + if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \ + h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ + if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \ + } \ + kfree(h->flags); /* free the working space */ \ + h->flags = new_flags; \ + h->n_buckets = new_n_buckets; \ + h->n_occupied = h->size; \ + h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \ + } \ + return 0; \ + } \ + SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \ + { \ + khint_t x; \ + if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \ + if (h->n_buckets > (h->size<<1)) { \ + if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \ + *ret = -1; return h->n_buckets; \ + } \ + } else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \ + *ret = -1; return h->n_buckets; \ + } \ + } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ + { \ + khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \ + x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \ + if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \ + else { \ + last = i; \ + while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \ + if (__ac_isdel(h->flags, i)) site = i; \ + i = (i + (++step)) & mask; \ + if (i == last) { x = site; break; } \ + } \ + if (x == h->n_buckets) { \ + if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \ + else x = i; \ + } \ + } \ + } \ + if (__ac_isempty(h->flags, x)) { /* not present at all */ \ + h->keys[x] = key; \ + __ac_set_isboth_false(h->flags, x); \ + ++h->size; ++h->n_occupied; \ + *ret = 1; \ + } else if (__ac_isdel(h->flags, x)) { /* deleted */ \ + h->keys[x] = key; \ + __ac_set_isboth_false(h->flags, x); \ + ++h->size; \ + *ret = 2; \ + } else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \ + return x; \ + } \ + SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \ + { \ + if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \ + __ac_set_isdel_true(h->flags, x); \ + --h->size; \ + } \ + } + +#define KHASH_DECLARE(name, khkey_t, khval_t) \ + __KHASH_TYPE(name, khkey_t, khval_t) \ + __KHASH_PROTOTYPES(name, khkey_t, khval_t) + +#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ + __KHASH_TYPE(name, khkey_t, khval_t) \ + __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) + +#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \ + KHASH_INIT2(name, static kh_inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) + +/* --- BEGIN OF HASH FUNCTIONS --- */ + +/*! @function + @abstract Integer hash function + @param key The integer [khint32_t] + @return The hash value [khint_t] + */ +#define kh_int_hash_func(key) (khint32_t)(key) +/*! @function + @abstract Integer comparison function + */ +#define kh_int_hash_equal(a, b) ((a) == (b)) +/*! @function + @abstract 64-bit integer hash function + @param key The integer [khint64_t] + @return The hash value [khint_t] + */ +#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11) +/*! @function + @abstract 64-bit integer comparison function + */ +#define kh_int64_hash_equal(a, b) ((a) == (b)) +/*! @function + @abstract const char* hash function + @param s Pointer to a null terminated string + @return The hash value + */ +static kh_inline khint_t __ac_X31_hash_string(const char *s) +{ + khint_t h = (khint_t)*s; + if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s; + return h; +} +/*! @function + @abstract Another interface to const char* hash function + @param key Pointer to a null terminated string [const char*] + @return The hash value [khint_t] + */ +#define kh_str_hash_func(key) __ac_X31_hash_string(key) +/*! @function + @abstract Const char* comparison function + */ +#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0) + +static kh_inline khint_t __ac_Wang_hash(khint_t key) +{ + key += ~(key << 15); + key ^= (key >> 10); + key += (key << 3); + key ^= (key >> 6); + key += ~(key << 11); + key ^= (key >> 16); + return key; +} +#define kh_int_hash_func2(k) __ac_Wang_hash((khint_t)key) + +/* --- END OF HASH FUNCTIONS --- */ + +/* Other convenient macros... */ + +/*! + @abstract Type of the hash table. + @param name Name of the hash table [symbol] + */ +#define khash_t(name) kh_##name##_t + +/*! @function + @abstract Initiate a hash table. + @param name Name of the hash table [symbol] + @return Pointer to the hash table [khash_t(name)*] + */ +#define kh_init(name) kh_init_##name() + +/*! @function + @abstract Destroy a hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + */ +#define kh_destroy(name, h) kh_destroy_##name(h) + +/*! @function + @abstract Reset a hash table without deallocating memory. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + */ +#define kh_clear(name, h) kh_clear_##name(h) + +/*! @function + @abstract Resize a hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param s New size [khint_t] + */ +#define kh_resize(name, h, s) kh_resize_##name(h, s) + +/*! @function + @abstract Insert a key to the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Key [type of keys] + @param r Extra return code: -1 if the operation failed; + 0 if the key is present in the hash table; + 1 if the bucket is empty (never used); 2 if the element in + the bucket has been deleted [int*] + @return Iterator to the inserted element [khint_t] + */ +#define kh_put(name, h, k, r) kh_put_##name(h, k, r) + +/*! @function + @abstract Retrieve a key from the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Key [type of keys] + @return Iterator to the found element, or kh_end(h) if the element is absent [khint_t] + */ +#define kh_get(name, h, k) kh_get_##name(h, k) + +/*! @function + @abstract Remove a key from the hash table. + @param name Name of the hash table [symbol] + @param h Pointer to the hash table [khash_t(name)*] + @param k Iterator to the element to be deleted [khint_t] + */ +#define kh_del(name, h, k) kh_del_##name(h, k) + +/*! @function + @abstract Test whether a bucket contains data. + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return 1 if containing data; 0 otherwise [int] + */ +#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x))) + +/*! @function + @abstract Get key given an iterator + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return Key [type of keys] + */ +#define kh_key(h, x) ((h)->keys[x]) + +/*! @function + @abstract Get value given an iterator + @param h Pointer to the hash table [khash_t(name)*] + @param x Iterator to the bucket [khint_t] + @return Value [type of values] + @discussion For hash sets, calling this results in segfault. + */ +#define kh_val(h, x) ((h)->vals[x]) + +/*! @function + @abstract Alias of kh_val() + */ +#define kh_value(h, x) ((h)->vals[x]) + +/*! @function + @abstract Get the start iterator + @param h Pointer to the hash table [khash_t(name)*] + @return The start iterator [khint_t] + */ +#define kh_begin(h) (khint_t)(0) + +/*! @function + @abstract Get the end iterator + @param h Pointer to the hash table [khash_t(name)*] + @return The end iterator [khint_t] + */ +#define kh_end(h) ((h)->n_buckets) + +/*! @function + @abstract Get the number of elements in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @return Number of elements in the hash table [khint_t] + */ +#define kh_size(h) ((h)->size) + +/*! @function + @abstract Get the number of buckets in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @return Number of buckets in the hash table [khint_t] + */ +#define kh_n_buckets(h) ((h)->n_buckets) + +/*! @function + @abstract Iterate over the entries in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @param kvar Variable to which key will be assigned + @param vvar Variable to which value will be assigned + @param code Block of code to execute + */ +#define kh_foreach(h, kvar, vvar, code) { khint_t __i; \ + for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ + if (!kh_exist(h,__i)) continue; \ + (kvar) = kh_key(h,__i); \ + (vvar) = kh_val(h,__i); \ + code; \ + } } + +/*! @function + @abstract Iterate over the values in the hash table + @param h Pointer to the hash table [khash_t(name)*] + @param vvar Variable to which value will be assigned + @param code Block of code to execute + */ +#define kh_foreach_value(h, vvar, code) { khint_t __i; \ + for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \ + if (!kh_exist(h,__i)) continue; \ + (vvar) = kh_val(h,__i); \ + code; \ + } } + +/* More conenient interfaces */ + +/*! @function + @abstract Instantiate a hash set containing integer keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_INT(name) \ + KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing integer keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_INT(name, khval_t) \ + KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing 64-bit integer keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_INT64(name) \ + KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing 64-bit integer keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_INT64(name, khval_t) \ + KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal) + +typedef const char *kh_cstr_t; +/*! @function + @abstract Instantiate a hash map containing const char* keys + @param name Name of the hash table [symbol] + */ +#define KHASH_SET_INIT_STR(name) \ + KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal) + +/*! @function + @abstract Instantiate a hash map containing const char* keys + @param name Name of the hash table [symbol] + @param khval_t Type of values [type] + */ +#define KHASH_MAP_INIT_STR(name, khval_t) \ + KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal) + +#endif /* __AC_KHASH_H */ Added: vendor/libucl/dist/klib/kvec.h ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ vendor/libucl/dist/klib/kvec.h Mon Mar 2 21:35:31 2015 (r279546) @@ -0,0 +1,103 @@ +/* The MIT License + + Copyright (c) 2008, by Attractive Chaos <attractor@live.co.uk> + + Permission is hereby granted, free of charge, to any person obtaining + a copy of this software and associated documentation files (the + "Software"), to deal in the Software without restriction, including + without limitation the rights to use, copy, modify, merge, publish, + distribute, sublicense, and/or sell copies of the Software, and to + permit persons to whom the Software is furnished to do so, subject to + the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***
](https://travis-ci.org/vstakhov/libucl){kind=link}
[](https://scan.coverity.com/projects/4138](https://travis-ci.org/vstakhov/libucl.svg?branch=master)](https://travis-ci.org/vstakhov/libucl)[](https://scan.coverity.com/projects/4138){kind=link}
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201503022135.t22LZWo1014824>