diff options
Diffstat (limited to 'ccan')
41 files changed, 6173 insertions, 0 deletions
diff --git a/ccan/ccan/build_assert/LICENSE b/ccan/ccan/build_assert/LICENSE new file mode 120000 index 0000000..b7951da --- /dev/null +++ b/ccan/ccan/build_assert/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0
\ No newline at end of file diff --git a/ccan/ccan/build_assert/build_assert.h b/ccan/ccan/build_assert/build_assert.h new file mode 100644 index 0000000..b9ecd84 --- /dev/null +++ b/ccan/ccan/build_assert/build_assert.h @@ -0,0 +1,40 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#ifndef CCAN_BUILD_ASSERT_H +#define CCAN_BUILD_ASSERT_H + +/** + * BUILD_ASSERT - assert a build-time dependency. + * @cond: the compile-time condition which must be true. + * + * Your compile will fail if the condition isn't true, or can't be evaluated + * by the compiler. This can only be used within a function. + * + * Example: + * #include <stddef.h> + * ... + * static char *foo_to_char(struct foo *foo) + * { + * // This code needs string to be at start of foo. + * BUILD_ASSERT(offsetof(struct foo, string) == 0); + * return (char *)foo; + * } + */ +#define BUILD_ASSERT(cond) \ + do { (void) sizeof(char [1 - 2*!(cond)]); } while(0) + +/** + * BUILD_ASSERT_OR_ZERO - assert a build-time dependency, as an expression. + * @cond: the compile-time condition which must be true. + * + * Your compile will fail if the condition isn't true, or can't be evaluated + * by the compiler. This can be used in an expression: its value is "0". + * + * Example: + * #define foo_to_char(foo) \ + * ((char *)(foo) \ + * + BUILD_ASSERT_OR_ZERO(offsetof(struct foo, string) == 0)) + */ +#define BUILD_ASSERT_OR_ZERO(cond) \ + (sizeof(char [1 - 2*!(cond)]) - 1) + +#endif /* CCAN_BUILD_ASSERT_H */ diff --git a/ccan/ccan/check_type/LICENSE b/ccan/ccan/check_type/LICENSE new file mode 120000 index 0000000..b7951da --- /dev/null +++ b/ccan/ccan/check_type/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0
\ No newline at end of file diff --git a/ccan/ccan/check_type/check_type.h b/ccan/ccan/check_type/check_type.h new file mode 100644 index 0000000..837aef7 --- /dev/null +++ b/ccan/ccan/check_type/check_type.h @@ -0,0 +1,64 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#ifndef CCAN_CHECK_TYPE_H +#define CCAN_CHECK_TYPE_H +#include "config.h" + +/** + * check_type - issue a warning or build failure if type is not correct. + * @expr: the expression whose type we should check (not evaluated). + * @type: the exact type we expect the expression to be. + * + * This macro is usually used within other macros to try to ensure that a macro + * argument is of the expected type. No type promotion of the expression is + * done: an unsigned int is not the same as an int! + * + * check_type() always evaluates to 0. + * + * If your compiler does not support typeof, then the best we can do is fail + * to compile if the sizes of the types are unequal (a less complete check). + * + * Example: + * // They should always pass a 64-bit value to _set_some_value! + * #define set_some_value(expr) \ + * _set_some_value((check_type((expr), uint64_t), (expr))) + */ + +/** + * check_types_match - issue a warning or build failure if types are not same. + * @expr1: the first expression (not evaluated). + * @expr2: the second expression (not evaluated). + * + * This macro is usually used within other macros to try to ensure that + * arguments are of identical types. No type promotion of the expressions is + * done: an unsigned int is not the same as an int! + * + * check_types_match() always evaluates to 0. + * + * If your compiler does not support typeof, then the best we can do is fail + * to compile if the sizes of the types are unequal (a less complete check). + * + * Example: + * // Do subtraction to get to enclosing type, but make sure that + * // pointer is of correct type for that member. + * #define container_of(mbr_ptr, encl_type, mbr) \ + * (check_types_match((mbr_ptr), &((encl_type *)0)->mbr), \ + * ((encl_type *) \ + * ((char *)(mbr_ptr) - offsetof(encl_type, mbr)))) + */ +#if HAVE_TYPEOF +#define check_type(expr, type) \ + ((typeof(expr) *)0 != (type *)0) + +#define check_types_match(expr1, expr2) \ + ((typeof(expr1) *)0 != (typeof(expr2) *)0) +#else +#include <ccan/build_assert/build_assert.h> +/* Without typeof, we can only test the sizes. */ +#define check_type(expr, type) \ + BUILD_ASSERT_OR_ZERO(sizeof(expr) == sizeof(type)) + +#define check_types_match(expr1, expr2) \ + BUILD_ASSERT_OR_ZERO(sizeof(expr1) == sizeof(expr2)) +#endif /* HAVE_TYPEOF */ + +#endif /* CCAN_CHECK_TYPE_H */ diff --git a/ccan/ccan/compiler/LICENSE b/ccan/ccan/compiler/LICENSE new file mode 120000 index 0000000..b7951da --- /dev/null +++ b/ccan/ccan/compiler/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0
\ No newline at end of file diff --git a/ccan/ccan/compiler/compiler.h b/ccan/ccan/compiler/compiler.h new file mode 100644 index 0000000..562b29e --- /dev/null +++ b/ccan/ccan/compiler/compiler.h @@ -0,0 +1,317 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#ifndef CCAN_COMPILER_H +#define CCAN_COMPILER_H +#include "config.h" + +#ifndef COLD +#if HAVE_ATTRIBUTE_COLD +/** + * COLD - a function is unlikely to be called. + * + * Used to mark an unlikely code path and optimize appropriately. + * It is usually used on logging or error routines. + * + * Example: + * static void COLD moan(const char *reason) + * { + * fprintf(stderr, "Error: %s (%s)\n", reason, strerror(errno)); + * } + */ +#define COLD __attribute__((__cold__)) +#else +#define COLD +#endif +#endif + +#ifndef NORETURN +#if HAVE_ATTRIBUTE_NORETURN +/** + * NORETURN - a function does not return + * + * Used to mark a function which exits; useful for suppressing warnings. + * + * Example: + * static void NORETURN fail(const char *reason) + * { + * fprintf(stderr, "Error: %s (%s)\n", reason, strerror(errno)); + * exit(1); + * } + */ +#define NORETURN __attribute__((__noreturn__)) +#else +#define NORETURN +#endif +#endif + +#ifndef PRINTF_FMT +#if HAVE_ATTRIBUTE_PRINTF +/** + * PRINTF_FMT - a function takes printf-style arguments + * @nfmt: the 1-based number of the function's format argument. + * @narg: the 1-based number of the function's first variable argument. + * + * This allows the compiler to check your parameters as it does for printf(). + * + * Example: + * void PRINTF_FMT(2,3) my_printf(const char *prefix, const char *fmt, ...); + */ +#define PRINTF_FMT(nfmt, narg) \ + __attribute__((format(__printf__, nfmt, narg))) +#else +#define PRINTF_FMT(nfmt, narg) +#endif +#endif + +#ifndef CONST_FUNCTION +#if HAVE_ATTRIBUTE_CONST +/** + * CONST_FUNCTION - a function's return depends only on its argument + * + * This allows the compiler to assume that the function will return the exact + * same value for the exact same arguments. This implies that the function + * must not use global variables, or dereference pointer arguments. + */ +#define CONST_FUNCTION __attribute__((__const__)) +#else +#define CONST_FUNCTION +#endif + +#ifndef PURE_FUNCTION +#if HAVE_ATTRIBUTE_PURE +/** + * PURE_FUNCTION - a function is pure + * + * A pure function is one that has no side effects other than it's return value + * and uses no inputs other than it's arguments and global variables. + */ +#define PURE_FUNCTION __attribute__((__pure__)) +#else +#define PURE_FUNCTION +#endif +#endif +#endif + +#if HAVE_ATTRIBUTE_UNUSED +#ifndef UNNEEDED +/** + * UNNEEDED - a variable/function may not be needed + * + * This suppresses warnings about unused variables or functions, but tells + * the compiler that if it is unused it need not emit it into the source code. + * + * Example: + * // With some preprocessor options, this is unnecessary. + * static UNNEEDED int counter; + * + * // With some preprocessor options, this is unnecessary. + * static UNNEEDED void add_to_counter(int add) + * { + * counter += add; + * } + */ +#define UNNEEDED __attribute__((__unused__)) +#endif + +#ifndef NEEDED +#if HAVE_ATTRIBUTE_USED +/** + * NEEDED - a variable/function is needed + * + * This suppresses warnings about unused variables or functions, but tells + * the compiler that it must exist even if it (seems) unused. + * + * Example: + * // Even if this is unused, these are vital for debugging. + * static NEEDED int counter; + * static NEEDED void dump_counter(void) + * { + * printf("Counter is %i\n", counter); + * } + */ +#define NEEDED __attribute__((__used__)) +#else +/* Before used, unused functions and vars were always emitted. */ +#define NEEDED __attribute__((__unused__)) +#endif +#endif + +#ifndef UNUSED +/** + * UNUSED - a parameter is unused + * + * Some compilers (eg. gcc with -W or -Wunused) warn about unused + * function parameters. This suppresses such warnings and indicates + * to the reader that it's deliberate. + * + * Example: + * // This is used as a callback, so needs to have this prototype. + * static int some_callback(void *unused UNUSED) + * { + * return 0; + * } + */ +#define UNUSED __attribute__((__unused__)) +#endif +#else +#ifndef UNNEEDED +#define UNNEEDED +#endif +#ifndef NEEDED +#define NEEDED +#endif +#ifndef UNUSED +#define UNUSED +#endif +#endif + +#ifndef IS_COMPILE_CONSTANT +#if HAVE_BUILTIN_CONSTANT_P +/** + * IS_COMPILE_CONSTANT - does the compiler know the value of this expression? + * @expr: the expression to evaluate + * + * When an expression manipulation is complicated, it is usually better to + * implement it in a function. However, if the expression being manipulated is + * known at compile time, it is better to have the compiler see the entire + * expression so it can simply substitute the result. + * + * This can be done using the IS_COMPILE_CONSTANT() macro. + * + * Example: + * enum greek { ALPHA, BETA, GAMMA, DELTA, EPSILON }; + * + * // Out-of-line version. + * const char *greek_name(enum greek greek); + * + * // Inline version. + * static inline const char *_greek_name(enum greek greek) + * { + * switch (greek) { + * case ALPHA: return "alpha"; + * case BETA: return "beta"; + * case GAMMA: return "gamma"; + * case DELTA: return "delta"; + * case EPSILON: return "epsilon"; + * default: return "**INVALID**"; + * } + * } + * + * // Use inline if compiler knows answer. Otherwise call function + * // to avoid copies of the same code everywhere. + * #define greek_name(g) \ + * (IS_COMPILE_CONSTANT(greek) ? _greek_name(g) : greek_name(g)) + */ +#define IS_COMPILE_CONSTANT(expr) __builtin_constant_p(expr) +#else +/* If we don't know, assume it's not. */ +#define IS_COMPILE_CONSTANT(expr) 0 +#endif +#endif + +#ifndef WARN_UNUSED_RESULT +#if HAVE_WARN_UNUSED_RESULT +/** + * WARN_UNUSED_RESULT - warn if a function return value is unused. + * + * Used to mark a function where it is extremely unlikely that the caller + * can ignore the result, eg realloc(). + * + * Example: + * // buf param may be freed by this; need return value! + * static char *WARN_UNUSED_RESULT enlarge(char *buf, unsigned *size) + * { + * return realloc(buf, (*size) *= 2); + * } + */ +#define WARN_UNUSED_RESULT __attribute__((__warn_unused_result__)) +#else +#define WARN_UNUSED_RESULT +#endif +#endif + + +#if HAVE_ATTRIBUTE_DEPRECATED +/** + * WARN_DEPRECATED - warn that a function/type/variable is deprecated when used. + * + * Used to mark a function, type or variable should not be used. + * + * Example: + * WARN_DEPRECATED char *oldfunc(char *buf); + */ +#define WARN_DEPRECATED __attribute__((__deprecated__)) +#else +#define WARN_DEPRECATED +#endif + + +#if HAVE_ATTRIBUTE_NONNULL +/** + * NO_NULL_ARGS - specify that no arguments to this function can be NULL. + * + * The compiler will warn if any pointer args are NULL. + * + * Example: + * NO_NULL_ARGS char *my_copy(char *buf); + */ +#define NO_NULL_ARGS __attribute__((__nonnull__)) + +/** + * NON_NULL_ARGS - specify that some arguments to this function can't be NULL. + * @...: 1-based argument numbers for which args can't be NULL. + * + * The compiler will warn if any of the specified pointer args are NULL. + * + * Example: + * char *my_copy2(char *buf, char *maybenull) NON_NULL_ARGS(1); + */ +#define NON_NULL_ARGS(...) __attribute__((__nonnull__(__VA_ARGS__))) +#else +#define NO_NULL_ARGS +#define NON_NULL_ARGS(...) +#endif + +#if HAVE_ATTRIBUTE_RETURNS_NONNULL +/** + * RETURNS_NONNULL - specify that this function cannot return NULL. + * + * Mainly an optimization opportunity, but can also suppress warnings. + * + * Example: + * RETURNS_NONNULL char *my_copy(char *buf); + */ +#define RETURNS_NONNULL __attribute__((__returns_nonnull__)) +#else +#define RETURNS_NONNULL +#endif + +#if HAVE_ATTRIBUTE_SENTINEL +/** + * LAST_ARG_NULL - specify the last argument of a variadic function must be NULL. + * + * The compiler will warn if the last argument isn't NULL. + * + * Example: + * char *join_string(char *buf, ...) LAST_ARG_NULL; + */ +#define LAST_ARG_NULL __attribute__((__sentinel__)) +#else +#define LAST_ARG_NULL +#endif + +#if HAVE_BUILTIN_CPU_SUPPORTS +/** + * cpu_supports - test if current CPU supports the named feature. + * + * This takes a literal string, and currently only works on glibc platforms. + * + * Example: + * if (cpu_supports("mmx")) + * printf("MMX support engaged!\n"); + */ +#define cpu_supports(x) __builtin_cpu_supports(x) +#else +#define cpu_supports(x) 0 +#endif /* HAVE_BUILTIN_CPU_SUPPORTS */ + +#endif /* CCAN_COMPILER_H */ diff --git a/ccan/ccan/container_of/LICENSE b/ccan/ccan/container_of/LICENSE new file mode 120000 index 0000000..b7951da --- /dev/null +++ b/ccan/ccan/container_of/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0
\ No newline at end of file diff --git a/ccan/ccan/container_of/container_of.h b/ccan/ccan/container_of/container_of.h new file mode 100644 index 0000000..47a34d8 --- /dev/null +++ b/ccan/ccan/container_of/container_of.h @@ -0,0 +1,145 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#ifndef CCAN_CONTAINER_OF_H +#define CCAN_CONTAINER_OF_H +#include <stddef.h> + +#include "config.h" +#include <ccan/check_type/check_type.h> + +/** + * container_of - get pointer to enclosing structure + * @member_ptr: pointer to the structure member + * @containing_type: the type this member is within + * @member: the name of this member within the structure. + * + * Given a pointer to a member of a structure, this macro does pointer + * subtraction to return the pointer to the enclosing type. + * + * Example: + * struct foo { + * int fielda, fieldb; + * // ... + * }; + * struct info { + * int some_other_field; + * struct foo my_foo; + * }; + * + * static struct info *foo_to_info(struct foo *foo) + * { + * return container_of(foo, struct info, my_foo); + * } + */ +#define container_of(member_ptr, containing_type, member) \ + ((containing_type *) \ + ((char *)(member_ptr) \ + - container_off(containing_type, member)) \ + + check_types_match(*(member_ptr), ((containing_type *)0)->member)) + + +/** + * container_of_or_null - get pointer to enclosing structure, or NULL + * @member_ptr: pointer to the structure member + * @containing_type: the type this member is within + * @member: the name of this member within the structure. + * + * Given a pointer to a member of a structure, this macro does pointer + * subtraction to return the pointer to the enclosing type, unless it + * is given NULL, in which case it also returns NULL. + * + * Example: + * struct foo { + * int fielda, fieldb; + * // ... + * }; + * struct info { + * int some_other_field; + * struct foo my_foo; + * }; + * + * static struct info *foo_to_info_allowing_null(struct foo *foo) + * { + * return container_of_or_null(foo, struct info, my_foo); + * } + */ +static inline char *container_of_or_null_(void *member_ptr, size_t offset) +{ + return member_ptr ? (char *)member_ptr - offset : NULL; +} +#define container_of_or_null(member_ptr, containing_type, member) \ + ((containing_type *) \ + container_of_or_null_(member_ptr, \ + container_off(containing_type, member)) \ + + check_types_match(*(member_ptr), ((containing_type *)0)->member)) + +/** + * container_off - get offset to enclosing structure + * @containing_type: the type this member is within + * @member: the name of this member within the structure. + * + * Given a pointer to a member of a structure, this macro does + * typechecking and figures out the offset to the enclosing type. + * + * Example: + * struct foo { + * int fielda, fieldb; + * // ... + * }; + * struct info { + * int some_other_field; + * struct foo my_foo; + * }; + * + * static struct info *foo_to_info(struct foo *foo) + * { + * size_t off = container_off(struct info, my_foo); + * return (void *)((char *)foo - off); + * } + */ +#define container_off(containing_type, member) \ + offsetof(containing_type, member) + +/** + * container_of_var - get pointer to enclosing structure using a variable + * @member_ptr: pointer to the structure member + * @container_var: a pointer of same type as this member's container + * @member: the name of this member within the structure. + * + * Given a pointer to a member of a structure, this macro does pointer + * subtraction to return the pointer to the enclosing type. + * + * Example: + * static struct info *foo_to_i(struct foo *foo) + * { + * struct info *i = container_of_var(foo, i, my_foo); + * return i; + * } + */ +#if HAVE_TYPEOF +#define container_of_var(member_ptr, container_var, member) \ + container_of(member_ptr, typeof(*container_var), member) +#else +#define container_of_var(member_ptr, container_var, member) \ + ((void *)((char *)(member_ptr) - \ + container_off_var(container_var, member))) +#endif + +/** + * container_off_var - get offset of a field in enclosing structure + * @container_var: a pointer to a container structure + * @member: the name of a member within the structure. + * + * Given (any) pointer to a structure and a its member name, this + * macro does pointer subtraction to return offset of member in a + * structure memory layout. + * + */ +#if HAVE_TYPEOF +#define container_off_var(var, member) \ + container_off(typeof(*var), member) +#else +#define container_off_var(var, member) \ + ((const char *)&(var)->member - (const char *)(var)) +#endif + +#endif /* CCAN_CONTAINER_OF_H */ diff --git a/ccan/ccan/endian/LICENSE b/ccan/ccan/endian/LICENSE new file mode 120000 index 0000000..b7951da --- /dev/null +++ b/ccan/ccan/endian/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0
\ No newline at end of file diff --git a/ccan/ccan/endian/endian.h b/ccan/ccan/endian/endian.h new file mode 100644 index 0000000..3753f49 --- /dev/null +++ b/ccan/ccan/endian/endian.h @@ -0,0 +1,363 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#ifndef CCAN_ENDIAN_H +#define CCAN_ENDIAN_H +#include <stdint.h> +#include "config.h" + +/** + * BSWAP_16 - reverse bytes in a constant uint16_t value. + * @val: constant value whose bytes to swap. + * + * Designed to be usable in constant-requiring initializers. + * + * Example: + * struct mystruct { + * char buf[BSWAP_16(0x1234)]; + * }; + */ +#define BSWAP_16(val) \ + ((((uint16_t)(val) & 0x00ff) << 8) \ + | (((uint16_t)(val) & 0xff00) >> 8)) + +/** + * BSWAP_32 - reverse bytes in a constant uint32_t value. + * @val: constant value whose bytes to swap. + * + * Designed to be usable in constant-requiring initializers. + * + * Example: + * struct mystruct { + * char buf[BSWAP_32(0xff000000)]; + * }; + */ +#define BSWAP_32(val) \ + ((((uint32_t)(val) & 0x000000ff) << 24) \ + | (((uint32_t)(val) & 0x0000ff00) << 8) \ + | (((uint32_t)(val) & 0x00ff0000) >> 8) \ + | (((uint32_t)(val) & 0xff000000) >> 24)) + +/** + * BSWAP_64 - reverse bytes in a constant uint64_t value. + * @val: constantvalue whose bytes to swap. + * + * Designed to be usable in constant-requiring initializers. + * + * Example: + * struct mystruct { + * char buf[BSWAP_64(0xff00000000000000ULL)]; + * }; + */ +#define BSWAP_64(val) \ + ((((uint64_t)(val) & 0x00000000000000ffULL) << 56) \ + | (((uint64_t)(val) & 0x000000000000ff00ULL) << 40) \ + | (((uint64_t)(val) & 0x0000000000ff0000ULL) << 24) \ + | (((uint64_t)(val) & 0x00000000ff000000ULL) << 8) \ + | (((uint64_t)(val) & 0x000000ff00000000ULL) >> 8) \ + | (((uint64_t)(val) & 0x0000ff0000000000ULL) >> 24) \ + | (((uint64_t)(val) & 0x00ff000000000000ULL) >> 40) \ + | (((uint64_t)(val) & 0xff00000000000000ULL) >> 56)) + +#if HAVE_BYTESWAP_H +#include <byteswap.h> +#else +/** + * bswap_16 - reverse bytes in a uint16_t value. + * @val: value whose bytes to swap. + * + * Example: + * // Output contains "1024 is 4 as two bytes reversed" + * printf("1024 is %u as two bytes reversed\n", bswap_16(1024)); + */ +static inline uint16_t bswap_16(uint16_t val) +{ + return BSWAP_16(val); +} + +/** + * bswap_32 - reverse bytes in a uint32_t value. + * @val: value whose bytes to swap. + * + * Example: + * // Output contains "1024 is 262144 as four bytes reversed" + * printf("1024 is %u as four bytes reversed\n", bswap_32(1024)); + */ +static inline uint32_t bswap_32(uint32_t val) +{ + return BSWAP_32(val); +} +#endif /* !HAVE_BYTESWAP_H */ + +#if !HAVE_BSWAP_64 +/** + * bswap_64 - reverse bytes in a uint64_t value. + * @val: value whose bytes to swap. + * + * Example: + * // Output contains "1024 is 1125899906842624 as eight bytes reversed" + * printf("1024 is %llu as eight bytes reversed\n", + * (unsigned long long)bswap_64(1024)); + */ +static inline uint64_t bswap_64(uint64_t val) +{ + return BSWAP_64(val); +} +#endif + +/* Needed for Glibc like endiness check */ +#define __LITTLE_ENDIAN 1234 +#define __BIG_ENDIAN 4321 + +/* Sanity check the defines. We don't handle weird endianness. */ +#if !HAVE_LITTLE_ENDIAN && !HAVE_BIG_ENDIAN +#error "Unknown endian" +#elif HAVE_LITTLE_ENDIAN && HAVE_BIG_ENDIAN +#error "Can't compile for both big and little endian." +#elif HAVE_LITTLE_ENDIAN +#ifndef __BYTE_ORDER +#define __BYTE_ORDER __LITTLE_ENDIAN +#elif __BYTE_ORDER != __LITTLE_ENDIAN +#error "__BYTE_ORDER already defined, but not equal to __LITTLE_ENDIAN" +#endif +#elif HAVE_BIG_ENDIAN +#ifndef __BYTE_ORDER +#define __BYTE_ORDER __BIG_ENDIAN +#elif __BYTE_ORDER != __BIG_ENDIAN +#error "__BYTE_ORDER already defined, but not equal to __BIG_ENDIAN" +#endif +#endif + + +#ifdef __CHECKER__ +/* sparse needs forcing to remove bitwise attribute from ccan/short_types */ +#define ENDIAN_CAST __attribute__((force)) +#define ENDIAN_TYPE __attribute__((bitwise)) +#else +#define ENDIAN_CAST +#define ENDIAN_TYPE +#endif + +typedef uint64_t ENDIAN_TYPE leint64_t; +typedef uint64_t ENDIAN_TYPE beint64_t; +typedef uint32_t ENDIAN_TYPE leint32_t; +typedef uint32_t ENDIAN_TYPE beint32_t; +typedef uint16_t ENDIAN_TYPE leint16_t; +typedef uint16_t ENDIAN_TYPE beint16_t; + +#if HAVE_LITTLE_ENDIAN +/** + * CPU_TO_LE64 - convert a constant uint64_t value to little-endian + * @native: constant to convert + */ +#define CPU_TO_LE64(native) ((ENDIAN_CAST leint64_t)(native)) + +/** + * CPU_TO_LE32 - convert a constant uint32_t value to little-endian + * @native: constant to convert + */ +#define CPU_TO_LE32(native) ((ENDIAN_CAST leint32_t)(native)) + +/** + * CPU_TO_LE16 - convert a constant uint16_t value to little-endian + * @native: constant to convert + */ +#define CPU_TO_LE16(native) ((ENDIAN_CAST leint16_t)(native)) + +/** + * LE64_TO_CPU - convert a little-endian uint64_t constant + * @le_val: little-endian constant to convert + */ +#define LE64_TO_CPU(le_val) ((ENDIAN_CAST uint64_t)(le_val)) + +/** + * LE32_TO_CPU - convert a little-endian uint32_t constant + * @le_val: little-endian constant to convert + */ +#define LE32_TO_CPU(le_val) ((ENDIAN_CAST uint32_t)(le_val)) + +/** + * LE16_TO_CPU - convert a little-endian uint16_t constant + * @le_val: little-endian constant to convert + */ +#define LE16_TO_CPU(le_val) ((ENDIAN_CAST uint16_t)(le_val)) + +#else /* ... HAVE_BIG_ENDIAN */ +#define CPU_TO_LE64(native) ((ENDIAN_CAST leint64_t)BSWAP_64(native)) +#define CPU_TO_LE32(native) ((ENDIAN_CAST leint32_t)BSWAP_32(native)) +#define CPU_TO_LE16(native) ((ENDIAN_CAST leint16_t)BSWAP_16(native)) +#define LE64_TO_CPU(le_val) BSWAP_64((ENDIAN_CAST uint64_t)le_val) +#define LE32_TO_CPU(le_val) BSWAP_32((ENDIAN_CAST uint32_t)le_val) +#define LE16_TO_CPU(le_val) BSWAP_16((ENDIAN_CAST uint16_t)le_val) +#endif /* HAVE_BIG_ENDIAN */ + +#if HAVE_BIG_ENDIAN +/** + * CPU_TO_BE64 - convert a constant uint64_t value to big-endian + * @native: constant to convert + */ +#define CPU_TO_BE64(native) ((ENDIAN_CAST beint64_t)(native)) + +/** + * CPU_TO_BE32 - convert a constant uint32_t value to big-endian + * @native: constant to convert + */ +#define CPU_TO_BE32(native) ((ENDIAN_CAST beint32_t)(native)) + +/** + * CPU_TO_BE16 - convert a constant uint16_t value to big-endian + * @native: constant to convert + */ +#define CPU_TO_BE16(native) ((ENDIAN_CAST beint16_t)(native)) + +/** + * BE64_TO_CPU - convert a big-endian uint64_t constant + * @le_val: big-endian constant to convert + */ +#define BE64_TO_CPU(le_val) ((ENDIAN_CAST uint64_t)(le_val)) + +/** + * BE32_TO_CPU - convert a big-endian uint32_t constant + * @le_val: big-endian constant to convert + */ +#define BE32_TO_CPU(le_val) ((ENDIAN_CAST uint32_t)(le_val)) + +/** + * BE16_TO_CPU - convert a big-endian uint16_t constant + * @le_val: big-endian constant to convert + */ +#define BE16_TO_CPU(le_val) ((ENDIAN_CAST uint16_t)(le_val)) + +#else /* ... HAVE_LITTLE_ENDIAN */ +#define CPU_TO_BE64(native) ((ENDIAN_CAST beint64_t)BSWAP_64(native)) +#define CPU_TO_BE32(native) ((ENDIAN_CAST beint32_t)BSWAP_32(native)) +#define CPU_TO_BE16(native) ((ENDIAN_CAST beint16_t)BSWAP_16(native)) +#define BE64_TO_CPU(le_val) BSWAP_64((ENDIAN_CAST uint64_t)le_val) +#define BE32_TO_CPU(le_val) BSWAP_32((ENDIAN_CAST uint32_t)le_val) +#define BE16_TO_CPU(le_val) BSWAP_16((ENDIAN_CAST uint16_t)le_val) +#endif /* HAVE_LITTE_ENDIAN */ + + +/** + * cpu_to_le64 - convert a uint64_t value to little-endian + * @native: value to convert + */ +static inline leint64_t cpu_to_le64(uint64_t native) +{ + return CPU_TO_LE64(native); +} + +/** + * cpu_to_le32 - convert a uint32_t value to little-endian + * @native: value to convert + */ +static inline leint32_t cpu_to_le32(uint32_t native) +{ + return CPU_TO_LE32(native); +} + +/** + * cpu_to_le16 - convert a uint16_t value to little-endian + * @native: value to convert + */ +static inline leint16_t cpu_to_le16(uint16_t native) +{ + return CPU_TO_LE16(native); +} + +/** + * le64_to_cpu - convert a little-endian uint64_t value + * @le_val: little-endian value to convert + */ +static inline uint64_t le64_to_cpu(leint64_t le_val) +{ + return LE64_TO_CPU(le_val); +} + +/** + * le32_to_cpu - convert a little-endian uint32_t value + * @le_val: little-endian value to convert + */ +static inline uint32_t le32_to_cpu(leint32_t le_val) +{ + return LE32_TO_CPU(le_val); +} + +/** + * le16_to_cpu - convert a little-endian uint16_t value + * @le_val: little-endian value to convert + */ +static inline uint16_t le16_to_cpu(leint16_t le_val) +{ + return LE16_TO_CPU(le_val); +} + +/** + * cpu_to_be64 - convert a uint64_t value to big endian. + * @native: value to convert + */ +static inline beint64_t cpu_to_be64(uint64_t native) +{ + return CPU_TO_BE64(native); +} + +/** + * cpu_to_be32 - convert a uint32_t value to big endian. + * @native: value to convert + */ +static inline beint32_t cpu_to_be32(uint32_t native) +{ + return CPU_TO_BE32(native); +} + +/** + * cpu_to_be16 - convert a uint16_t value to big endian. + * @native: value to convert + */ +static inline beint16_t cpu_to_be16(uint16_t native) +{ + return CPU_TO_BE16(native); +} + +/** + * be64_to_cpu - convert a big-endian uint64_t value + * @be_val: big-endian value to convert + */ +static inline uint64_t be64_to_cpu(beint64_t be_val) +{ + return BE64_TO_CPU(be_val); +} + +/** + * be32_to_cpu - convert a big-endian uint32_t value + * @be_val: big-endian value to convert + */ +static inline uint32_t be32_to_cpu(beint32_t be_val) +{ + return BE32_TO_CPU(be_val); +} + +/** + * be16_to_cpu - convert a big-endian uint16_t value + * @be_val: big-endian value to convert + */ +static inline uint16_t be16_to_cpu(beint16_t be_val) +{ + return BE16_TO_CPU(be_val); +} + +/* Whichever they include first, they get these definitions. */ +#ifdef CCAN_SHORT_TYPES_H +/** + * be64/be32/be16 - 64/32/16 bit big-endian representation. + */ +typedef beint64_t be64; +typedef beint32_t be32; +typedef beint16_t be16; + +/** + * le64/le32/le16 - 64/32/16 bit little-endian representation. + */ +typedef leint64_t le64; +typedef leint32_t le32; +typedef leint16_t le16; +#endif +#endif /* CCAN_ENDIAN_H */ diff --git a/ccan/ccan/hash/LICENSE b/ccan/ccan/hash/LICENSE new file mode 120000 index 0000000..b7951da --- /dev/null +++ b/ccan/ccan/hash/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0
\ No newline at end of file diff --git a/ccan/ccan/hash/hash.c b/ccan/ccan/hash/hash.c new file mode 100644 index 0000000..88d88fc --- /dev/null +++ b/ccan/ccan/hash/hash.c @@ -0,0 +1,926 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +/* +------------------------------------------------------------------------------- +lookup3.c, by Bob Jenkins, May 2006, Public Domain. + +These are functions for producing 32-bit hashes for hash table lookup. +hash_word(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() +are externally useful functions. Routines to test the hash are included +if SELF_TEST is defined. You can use this free for any purpose. It's in +the public domain. It has no warranty. + +You probably want to use hashlittle(). hashlittle() and hashbig() +hash byte arrays. hashlittle() is is faster than hashbig() on +little-endian machines. Intel and AMD are little-endian machines. +On second thought, you probably want hashlittle2(), which is identical to +hashlittle() except it returns two 32-bit hashes for the price of one. +You could implement hashbig2() if you wanted but I haven't bothered here. + +If you want to find a hash of, say, exactly 7 integers, do + a = i1; b = i2; c = i3; + mix(a,b,c); + a += i4; b += i5; c += i6; + mix(a,b,c); + a += i7; + final(a,b,c); +then use c as the hash value. If you have a variable length array of +4-byte integers to hash, use hash_word(). If you have a byte array (like +a character string), use hashlittle(). If you have several byte arrays, or +a mix of things, see the comments above hashlittle(). + +Why is this so big? I read 12 bytes at a time into 3 4-byte integers, +then mix those integers. This is fast (you can do a lot more thorough +mixing with 12*3 instructions on 3 integers than you can with 3 instructions +on 1 byte), but shoehorning those bytes into integers efficiently is messy. +------------------------------------------------------------------------------- +*/ +//#define SELF_TEST 1 + +#if 0 +#include <stdio.h> /* defines printf for tests */ +#include <time.h> /* defines time_t for timings in the test */ +#include <stdint.h> /* defines uint32_t etc */ +#include <sys/param.h> /* attempt to define endianness */ + +#ifdef linux +# include <endian.h> /* attempt to define endianness */ +#endif + +/* + * My best guess at if you are big-endian or little-endian. This may + * need adjustment. + */ +#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \ + __BYTE_ORDER == __LITTLE_ENDIAN) || \ + (defined(i386) || defined(__i386__) || defined(__i486__) || \ + defined(__i586__) || defined(__i686__) || defined(__x86_64) || \ + defined(vax) || defined(MIPSEL)) +# define HASH_LITTLE_ENDIAN 1 +# define HASH_BIG_ENDIAN 0 +#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \ + __BYTE_ORDER == __BIG_ENDIAN) || \ + (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel)) +# define HASH_LITTLE_ENDIAN 0 +# define HASH_BIG_ENDIAN 1 +#else +# error Unknown endian +#endif +#endif /* old hash.c headers. */ + +#include "hash.h" + +#if HAVE_LITTLE_ENDIAN +#define HASH_LITTLE_ENDIAN 1 +#define HASH_BIG_ENDIAN 0 +#elif HAVE_BIG_ENDIAN +#define HASH_LITTLE_ENDIAN 0 +#define HASH_BIG_ENDIAN 1 +#else +#error Unknown endian +#endif + +#define hashsize(n) ((uint32_t)1<<(n)) +#define hashmask(n) (hashsize(n)-1) +#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) + +/* +------------------------------------------------------------------------------- +mix -- mix 3 32-bit values reversibly. + +This is reversible, so any information in (a,b,c) before mix() is +still in (a,b,c) after mix(). + +If four pairs of (a,b,c) inputs are run through mix(), or through +mix() in reverse, there are at least 32 bits of the output that +are sometimes the same for one pair and different for another pair. +This was tested for: +* pairs that differed by one bit, by two bits, in any combination + of top bits of (a,b,c), or in any combination of bottom bits of + (a,b,c). +* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed + the output delta to a Gray code (a^(a>>1)) so a string of 1's (as + is commonly produced by subtraction) look like a single 1-bit + difference. +* the base values were pseudorandom, all zero but one bit set, or + all zero plus a counter that starts at zero. + +Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that +satisfy this are + 4 6 8 16 19 4 + 9 15 3 18 27 15 + 14 9 3 7 17 3 +Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing +for "differ" defined as + with a one-bit base and a two-bit delta. I +used http://burtleburtle.net/bob/hash/avalanche.html to choose +the operations, constants, and arrangements of the variables. + +This does not achieve avalanche. There are input bits of (a,b,c) +that fail to affect some output bits of (a,b,c), especially of a. The +most thoroughly mixed value is c, but it doesn't really even achieve +avalanche in c. + +This allows some parallelism. Read-after-writes are good at doubling +the number of bits affected, so the goal of mixing pulls in the opposite +direction as the goal of parallelism. I did what I could. Rotates +seem to cost as much as shifts on every machine I could lay my hands +on, and rotates are much kinder to the top and bottom bits, so I used +rotates. +------------------------------------------------------------------------------- +*/ +#define mix(a,b,c) \ +{ \ + a -= c; a ^= rot(c, 4); c += b; \ + b -= a; b ^= rot(a, 6); a += c; \ + c -= b; c ^= rot(b, 8); b += a; \ + a -= c; a ^= rot(c,16); c += b; \ + b -= a; b ^= rot(a,19); a += c; \ + c -= b; c ^= rot(b, 4); b += a; \ +} + +/* +------------------------------------------------------------------------------- +final -- final mixing of 3 32-bit values (a,b,c) into c + +Pairs of (a,b,c) values differing in only a few bits will usually +produce values of c that look totally different. This was tested for +* pairs that differed by one bit, by two bits, in any combination + of top bits of (a,b,c), or in any combination of bottom bits of + (a,b,c). +* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed + the output delta to a Gray code (a^(a>>1)) so a string of 1's (as + is commonly produced by subtraction) look like a single 1-bit + difference. +* the base values were pseudorandom, all zero but one bit set, or + all zero plus a counter that starts at zero. + +These constants passed: + 14 11 25 16 4 14 24 + 12 14 25 16 4 14 24 +and these came close: + 4 8 15 26 3 22 24 + 10 8 15 26 3 22 24 + 11 8 15 26 3 22 24 +------------------------------------------------------------------------------- +*/ +#define final(a,b,c) \ +{ \ + c ^= b; c -= rot(b,14); \ + a ^= c; a -= rot(c,11); \ + b ^= a; b -= rot(a,25); \ + c ^= b; c -= rot(b,16); \ + a ^= c; a -= rot(c,4); \ + b ^= a; b -= rot(a,14); \ + c ^= b; c -= rot(b,24); \ +} + +/* +-------------------------------------------------------------------- + This works on all machines. To be useful, it requires + -- that the key be an array of uint32_t's, and + -- that the length be the number of uint32_t's in the key + + The function hash_word() is identical to hashlittle() on little-endian + machines, and identical to hashbig() on big-endian machines, + except that the length has to be measured in uint32_ts rather than in + bytes. hashlittle() is more complicated than hash_word() only because + hashlittle() has to dance around fitting the key bytes into registers. +-------------------------------------------------------------------- +*/ +uint32_t hash_u32( +const uint32_t *k, /* the key, an array of uint32_t values */ +size_t length, /* the length of the key, in uint32_ts */ +uint32_t initval) /* the previous hash, or an arbitrary value */ +{ + uint32_t a,b,c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval; + + /*------------------------------------------------- handle most of the key */ + while (length > 3) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + length -= 3; + k += 3; + } + + /*------------------------------------------- handle the last 3 uint32_t's */ + switch(length) /* all the case statements fall through */ + { + case 3 : c+=k[2]; + case 2 : b+=k[1]; + case 1 : a+=k[0]; + final(a,b,c); + case 0: /* case 0: nothing left to add */ + break; + } + /*------------------------------------------------------ report the result */ + return c; +} + +/* +------------------------------------------------------------------------------- +hashlittle() -- hash a variable-length key into a 32-bit value + k : the key (the unaligned variable-length array of bytes) + length : the length of the key, counting by bytes + val2 : IN: can be any 4-byte value OUT: second 32 bit hash. +Returns a 32-bit value. Every bit of the key affects every bit of +the return value. Two keys differing by one or two bits will have +totally different hash values. Note that the return value is better +mixed than val2, so use that first. + +The best hash table sizes are powers of 2. There is no need to do +mod a prime (mod is sooo slow!). If you need less than 32 bits, +use a bitmask. For example, if you need only 10 bits, do + h = (h & hashmask(10)); +In which case, the hash table should have hashsize(10) elements. + +If you are hashing n strings (uint8_t **)k, do it like this: + for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h); + +By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this +code any way you wish, private, educational, or commercial. It's free. + +Use for hash table lookup, or anything where one collision in 2^^32 is +acceptable. Do NOT use for cryptographic purposes. +------------------------------------------------------------------------------- +*/ + +static uint32_t hashlittle( const void *key, size_t length, uint32_t *val2 ) +{ + uint32_t a,b,c; /* internal state */ + union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2; + + u.ptr = key; + if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { + const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ + const uint8_t *k8; + + /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ + while (length > 12) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + length -= 12; + k += 3; + } + + /*----------------------------- handle the last (probably partial) block */ + /* + * "k[2]&0xffffff" actually reads beyond the end of the string, but + * then masks off the part it's not allowed to read. Because the + * string is aligned, the masked-off tail is in the same word as the + * rest of the string. Every machine with memory protection I've seen + * does it on word boundaries, so is OK with this. But VALGRIND will + * still catch it and complain. The masking trick does make the hash + * noticeably faster for short strings (like English words). + * + * Not on my testing with gcc 4.5 on an intel i5 CPU, at least --RR. + */ +#if 0 + switch(length) + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; + case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; + case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=k[1]&0xffffff; a+=k[0]; break; + case 6 : b+=k[1]&0xffff; a+=k[0]; break; + case 5 : b+=k[1]&0xff; a+=k[0]; break; + case 4 : a+=k[0]; break; + case 3 : a+=k[0]&0xffffff; break; + case 2 : a+=k[0]&0xffff; break; + case 1 : a+=k[0]&0xff; break; + case 0 : return c; /* zero length strings require no mixing */ + } + +#else /* make valgrind happy */ + + k8 = (const uint8_t *)k; + switch(length) + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ + case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ + case 9 : c+=k8[8]; /* fall through */ + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ + case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ + case 5 : b+=k8[4]; /* fall through */ + case 4 : a+=k[0]; break; + case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ + case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ + case 1 : a+=k8[0]; break; + case 0 : return c; + } + +#endif /* !valgrind */ + + } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { + const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ + const uint8_t *k8; + + /*--------------- all but last block: aligned reads and different mixing */ + while (length > 12) + { + a += k[0] + (((uint32_t)k[1])<<16); + b += k[2] + (((uint32_t)k[3])<<16); + c += k[4] + (((uint32_t)k[5])<<16); + mix(a,b,c); + length -= 12; + k += 6; + } + + /*----------------------------- handle the last (probably partial) block */ + k8 = (const uint8_t *)k; + switch(length) + { + case 12: c+=k[4]+(((uint32_t)k[5])<<16); + b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ + case 10: c+=k[4]; + b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 9 : c+=k8[8]; /* fall through */ + case 8 : b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ + case 6 : b+=k[2]; + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 5 : b+=k8[4]; /* fall through */ + case 4 : a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ + case 2 : a+=k[0]; + break; + case 1 : a+=k8[0]; + break; + case 0 : return c; /* zero length requires no mixing */ + } + + } else { /* need to read the key one byte at a time */ + const uint8_t *k = (const uint8_t *)key; + + /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ + while (length > 12) + { + a += k[0]; + a += ((uint32_t)k[1])<<8; + a += ((uint32_t)k[2])<<16; + a += ((uint32_t)k[3])<<24; + b += k[4]; + b += ((uint32_t)k[5])<<8; + b += ((uint32_t)k[6])<<16; + b += ((uint32_t)k[7])<<24; + c += k[8]; + c += ((uint32_t)k[9])<<8; + c += ((uint32_t)k[10])<<16; + c += ((uint32_t)k[11])<<24; + mix(a,b,c); + length -= 12; + k += 12; + } + + /*-------------------------------- last block: affect all 32 bits of (c) */ + switch(length) /* all the case statements fall through */ + { + case 12: c+=((uint32_t)k[11])<<24; + case 11: c+=((uint32_t)k[10])<<16; + case 10: c+=((uint32_t)k[9])<<8; + case 9 : c+=k[8]; + case 8 : b+=((uint32_t)k[7])<<24; + case 7 : b+=((uint32_t)k[6])<<16; + case 6 : b+=((uint32_t)k[5])<<8; + case 5 : b+=k[4]; + case 4 : a+=((uint32_t)k[3])<<24; + case 3 : a+=((uint32_t)k[2])<<16; + case 2 : a+=((uint32_t)k[1])<<8; + case 1 : a+=k[0]; + break; + case 0 : return c; + } + } + + final(a,b,c); + *val2 = b; + return c; +} + +/* + * hashbig(): + * This is the same as hash_word() on big-endian machines. It is different + * from hashlittle() on all machines. hashbig() takes advantage of + * big-endian byte ordering. + */ +static uint32_t hashbig( const void *key, size_t length, uint32_t *val2) +{ + uint32_t a,b,c; + union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */ + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2; + + u.ptr = key; + if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) { + const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ + const uint8_t *k8; + + /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ + while (length > 12) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + length -= 12; + k += 3; + } + + /*----------------------------- handle the last (probably partial) block */ + /* + * "k[2]<<8" actually reads beyond the end of the string, but + * then shifts out the part it's not allowed to read. Because the + * string is aligned, the illegal read is in the same word as the + * rest of the string. Every machine with memory protection I've seen + * does it on word boundaries, so is OK with this. But VALGRIND will + * still catch it and complain. The masking trick does make the hash + * noticeably faster for short strings (like English words). + * + * Not on my testing with gcc 4.5 on an intel i5 CPU, at least --RR. + */ +#if 0 + switch(length) + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break; + case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break; + case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break; + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=k[1]&0xffffff00; a+=k[0]; break; + case 6 : b+=k[1]&0xffff0000; a+=k[0]; break; + case 5 : b+=k[1]&0xff000000; a+=k[0]; break; + case 4 : a+=k[0]; break; + case 3 : a+=k[0]&0xffffff00; break; + case 2 : a+=k[0]&0xffff0000; break; + case 1 : a+=k[0]&0xff000000; break; + case 0 : return c; /* zero length strings require no mixing */ + } + +#else /* make valgrind happy */ + + k8 = (const uint8_t *)k; + switch(length) /* all the case statements fall through */ + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=((uint32_t)k8[10])<<8; /* fall through */ + case 10: c+=((uint32_t)k8[9])<<16; /* fall through */ + case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */ + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */ + case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */ + case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */ + case 4 : a+=k[0]; break; + case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */ + case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */ + case 1 : a+=((uint32_t)k8[0])<<24; break; + case 0 : return c; + } + +#endif /* !VALGRIND */ + + } else { /* need to read the key one byte at a time */ + const uint8_t *k = (const uint8_t *)key; + + /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ + while (length > 12) + { + a += ((uint32_t)k[0])<<24; + a += ((uint32_t)k[1])<<16; + a += ((uint32_t)k[2])<<8; + a += ((uint32_t)k[3]); + b += ((uint32_t)k[4])<<24; + b += ((uint32_t)k[5])<<16; + b += ((uint32_t)k[6])<<8; + b += ((uint32_t)k[7]); + c += ((uint32_t)k[8])<<24; + c += ((uint32_t)k[9])<<16; + c += ((uint32_t)k[10])<<8; + c += ((uint32_t)k[11]); + mix(a,b,c); + length -= 12; + k += 12; + } + + /*-------------------------------- last block: affect all 32 bits of (c) */ + switch(length) /* all the case statements fall through */ + { + case 12: c+=k[11]; + case 11: c+=((uint32_t)k[10])<<8; + case 10: c+=((uint32_t)k[9])<<16; + case 9 : c+=((uint32_t)k[8])<<24; + case 8 : b+=k[7]; + case 7 : b+=((uint32_t)k[6])<<8; + case 6 : b+=((uint32_t)k[5])<<16; + case 5 : b+=((uint32_t)k[4])<<24; + case 4 : a+=k[3]; + case 3 : a+=((uint32_t)k[2])<<8; + case 2 : a+=((uint32_t)k[1])<<16; + case 1 : a+=((uint32_t)k[0])<<24; + break; + case 0 : return c; + } + } + + final(a,b,c); + *val2 = b; + return c; +} + +/* I basically use hashlittle here, but use native endian within each + * element. This delivers least-surprise: hash such as "int arr[] = { + * 1, 2 }; hash_stable(arr, 2, 0);" will be the same on big and little + * endian machines, even though a bytewise hash wouldn't be. */ +uint64_t hash64_stable_64(const void *key, size_t n, uint64_t base) +{ + const uint64_t *k = key; + uint32_t a,b,c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)n*8) + (base >> 32) + base; + + while (n > 3) { + a += (uint32_t)k[0]; + b += (uint32_t)(k[0] >> 32); + c += (uint32_t)k[1]; + mix(a,b,c); + a += (uint32_t)(k[1] >> 32); + b += (uint32_t)k[2]; + c += (uint32_t)(k[2] >> 32); + mix(a,b,c); + n -= 3; + k += 3; + } + switch (n) { + case 2: + a += (uint32_t)k[0]; + b += (uint32_t)(k[0] >> 32); + c += (uint32_t)k[1]; + mix(a,b,c); + a += (uint32_t)(k[1] >> 32); + break; + case 1: + a += (uint32_t)k[0]; + b += (uint32_t)(k[0] >> 32); + break; + case 0: + return c; + } + final(a,b,c); + return ((uint64_t)b << 32) | c; +} + +uint64_t hash64_stable_32(const void *key, size_t n, uint64_t base) +{ + const uint32_t *k = key; + uint32_t a,b,c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)n*4) + (base >> 32) + base; + + while (n > 3) { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + + n -= 3; + k += 3; + } + switch (n) { + case 2: + b += (uint32_t)k[1]; + case 1: + a += (uint32_t)k[0]; + break; + case 0: + return c; + } + final(a,b,c); + return ((uint64_t)b << 32) | c; +} + +uint64_t hash64_stable_16(const void *key, size_t n, uint64_t base) +{ + const uint16_t *k = key; + uint32_t a,b,c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)n*2) + (base >> 32) + base; + + while (n > 6) { + a += (uint32_t)k[0] + ((uint32_t)k[1] << 16); + b += (uint32_t)k[2] + ((uint32_t)k[3] << 16); + c += (uint32_t)k[4] + ((uint32_t)k[5] << 16); + mix(a,b,c); + + n -= 6; + k += 6; + } + + switch (n) { + case 5: + c += (uint32_t)k[4]; + case 4: + b += ((uint32_t)k[3] << 16); + case 3: + b += (uint32_t)k[2]; + case 2: + a += ((uint32_t)k[1] << 16); + case 1: + a += (uint32_t)k[0]; + break; + case 0: + return c; + } + final(a,b,c); + return ((uint64_t)b << 32) | c; +} + +uint64_t hash64_stable_8(const void *key, size_t n, uint64_t base) +{ + uint32_t b32 = base + (base >> 32); + uint32_t lower = hashlittle(key, n, &b32); + + return ((uint64_t)b32 << 32) | lower; +} + +uint32_t hash_any(const void *key, size_t length, uint32_t base) +{ + if (HASH_BIG_ENDIAN) + return hashbig(key, length, &base); + else + return hashlittle(key, length, &base); +} + +uint32_t hash_stable_64(const void *key, size_t n, uint32_t base) +{ + return hash64_stable_64(key, n, base); +} + +uint32_t hash_stable_32(const void *key, size_t n, uint32_t base) +{ + return hash64_stable_32(key, n, base); +} + +uint32_t hash_stable_16(const void *key, size_t n, uint32_t base) +{ + return hash64_stable_16(key, n, base); +} + +uint32_t hash_stable_8(const void *key, size_t n, uint32_t base) +{ + return hashlittle(key, n, &base); +} + +/* Jenkins' lookup8 is a 64 bit hash, but he says it's obsolete. Use + * the plain one and recombine into 64 bits. */ +uint64_t hash64_any(const void *key, size_t length, uint64_t base) +{ + uint32_t b32 = base + (base >> 32); + uint32_t lower; + + if (HASH_BIG_ENDIAN) + lower = hashbig(key, length, &b32); + else + lower = hashlittle(key, length, &b32); + + return ((uint64_t)b32 << 32) | lower; +} + +#ifdef SELF_TEST + +/* used for timings */ +void driver1() +{ + uint8_t buf[256]; + uint32_t i; + uint32_t h=0; + time_t a,z; + + time(&a); + for (i=0; i<256; ++i) buf[i] = 'x'; + for (i=0; i<1; ++i) + { + h = hashlittle(&buf[0],1,h); + } + time(&z); + if (z-a > 0) printf("time %d %.8x\n", z-a, h); +} + +/* check that every input bit changes every output bit half the time */ +#define HASHSTATE 1 +#define HASHLEN 1 +#define MAXPAIR 60 +#define MAXLEN 70 +void driver2() +{ + uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1]; + uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z; + uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE]; + uint32_t x[HASHSTATE],y[HASHSTATE]; + uint32_t hlen; + + printf("No more than %d trials should ever be needed \n",MAXPAIR/2); + for (hlen=0; hlen < MAXLEN; ++hlen) + { + z=0; + for (i=0; i<hlen; ++i) /*----------------------- for each input byte, */ + { + for (j=0; j<8; ++j) /*------------------------ for each input bit, */ + { + for (m=1; m<8; ++m) /*------------ for several possible initvals, */ + { + for (l=0; l<HASHSTATE; ++l) + e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0); + + /*---- check that every output bit is affected by that input bit */ + for (k=0; k<MAXPAIR; k+=2) + { + uint32_t finished=1; + /* keys have one bit different */ + for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;} + /* have a and b be two keys differing in only one bit */ + a[i] ^= (k<<j); + a[i] ^= (k>>(8-j)); + c[0] = hashlittle(a, hlen, m); + b[i] ^= ((k+1)<<j); + b[i] ^= ((k+1)>>(8-j)); + d[0] = hashlittle(b, hlen, m); + /* check every bit is 1, 0, set, and not set at least once */ + for (l=0; l<HASHSTATE; ++l) + { + e[l] &= (c[l]^d[l]); + f[l] &= ~(c[l]^d[l]); + g[l] &= c[l]; + h[l] &= ~c[l]; + x[l] &= d[l]; + y[l] &= ~d[l]; + if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0; + } + if (finished) break; + } + if (k>z) z=k; + if (k==MAXPAIR) + { + printf("Some bit didn't change: "); + printf("%.8x %.8x %.8x %.8x %.8x %.8x ", + e[0],f[0],g[0],h[0],x[0],y[0]); + printf("i %d j %d m %d len %d\n", i, j, m, hlen); + } + if (z==MAXPAIR) goto done; + } + } + } + done: + if (z < MAXPAIR) + { + printf("Mix success %2d bytes %2d initvals ",i,m); + printf("required %d trials\n", z/2); + } + } + printf("\n"); +} + +/* Check for reading beyond the end of the buffer and alignment problems */ +void driver3() +{ + uint8_t buf[MAXLEN+20], *b; + uint32_t len; + uint8_t q[] = "This is the time for all good men to come to the aid of their country..."; + uint32_t h; + uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country..."; + uint32_t i; + uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country..."; + uint32_t j; + uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country..."; + uint32_t ref,x,y; + uint8_t *p; + + printf("Endianness. These lines should all be the same (for values filled in):\n"); + printf("%.8x %.8x %.8x\n", + hash_word((const uint32_t *)q, (sizeof(q)-1)/4, 13), + hash_word((const uint32_t *)q, (sizeof(q)-5)/4, 13), + hash_word((const uint32_t *)q, (sizeof(q)-9)/4, 13)); + p = q; + printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", + hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), + hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), + hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), + hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), + hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), + hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); + p = &qq[1]; + printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", + hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), + hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), + hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), + hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), + hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), + hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); + p = &qqq[2]; + printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", + hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), + hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), + hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), + hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), + hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), + hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); + p = &qqqq[3]; + printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", + hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), + hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), + hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), + hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), + hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), + hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); + printf("\n"); + + /* check that hashlittle2 and hashlittle produce the same results */ + i=47; j=0; + hashlittle2(q, sizeof(q), &i, &j); + if (hashlittle(q, sizeof(q), 47) != i) + printf("hashlittle2 and hashlittle mismatch\n"); + + /* check that hash_word2 and hash_word produce the same results */ + len = 0xdeadbeef; + i=47, j=0; + hash_word2(&len, 1, &i, &j); + if (hash_word(&len, 1, 47) != i) + printf("hash_word2 and hash_word mismatch %x %x\n", + i, hash_word(&len, 1, 47)); + + /* check hashlittle doesn't read before or after the ends of the string */ + for (h=0, b=buf+1; h<8; ++h, ++b) + { + for (i=0; i<MAXLEN; ++i) + { + len = i; + for (j=0; j<i; ++j) *(b+j)=0; + + /* these should all be equal */ + ref = hashlittle(b, len, (uint32_t)1); + *(b+i)=(uint8_t)~0; + *(b-1)=(uint8_t)~0; + x = hashlittle(b, len, (uint32_t)1); + y = hashlittle(b, len, (uint32_t)1); + if ((ref != x) || (ref != y)) + { + printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y, + h, i); + } + } + } +} + +/* check for problems with nulls */ + void driver4() +{ + uint8_t buf[1]; + uint32_t h,i,state[HASHSTATE]; + + + buf[0] = ~0; + for (i=0; i<HASHSTATE; ++i) state[i] = 1; + printf("These should all be different\n"); + for (i=0, h=0; i<8; ++i) + { + h = hashlittle(buf, 0, h); + printf("%2ld 0-byte strings, hash is %.8x\n", i, h); + } +} + + +int main() +{ + driver1(); /* test that the key is hashed: used for timings */ + driver2(); /* test that whole key is hashed thoroughly */ + driver3(); /* test that nothing but the key is hashed */ + driver4(); /* test hashing multiple buffers (all buffers are null) */ + return 1; +} + +#endif /* SELF_TEST */ diff --git a/ccan/ccan/hash/hash.h b/ccan/ccan/hash/hash.h new file mode 100644 index 0000000..2170684 --- /dev/null +++ b/ccan/ccan/hash/hash.h @@ -0,0 +1,313 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#ifndef CCAN_HASH_H +#define CCAN_HASH_H +#include "config.h" +#include <stdint.h> +#include <stdlib.h> +#include <ccan/build_assert/build_assert.h> + +/* Stolen mostly from: lookup3.c, by Bob Jenkins, May 2006, Public Domain. + * + * http://burtleburtle.net/bob/c/lookup3.c + */ + +/** + * hash - fast hash of an array for internal use + * @p: the array or pointer to first element + * @num: the number of elements to hash + * @base: the base number to roll into the hash (usually 0) + * + * The memory region pointed to by p is combined with the base to form + * a 32-bit hash. + * + * This hash will have different results on different machines, so is + * only useful for internal hashes (ie. not hashes sent across the + * network or saved to disk). + * + * It may also change with future versions: it could even detect at runtime + * what the fastest hash to use is. + * + * See also: hash64, hash_stable. + * + * Example: + * #include <ccan/hash/hash.h> + * #include <err.h> + * #include <stdio.h> + * #include <string.h> + * + * // Simple demonstration: idential strings will have the same hash, but + * // two different strings will probably not. + * int main(int argc, char *argv[]) + * { + * uint32_t hash1, hash2; + * + * if (argc != 3) + * err(1, "Usage: %s <string1> <string2>", argv[0]); + * + * hash1 = hash(argv[1], strlen(argv[1]), 0); + * hash2 = hash(argv[2], strlen(argv[2]), 0); + * printf("Hash is %s\n", hash1 == hash2 ? "same" : "different"); + * return 0; + * } + */ +#define hash(p, num, base) hash_any((p), (num)*sizeof(*(p)), (base)) + +/** + * hash_stable - hash of an array for external use + * @p: the array or pointer to first element + * @num: the number of elements to hash + * @base: the base number to roll into the hash (usually 0) + * + * The array of simple integer types pointed to by p is combined with + * the base to form a 32-bit hash. + * + * This hash will have the same results on different machines, so can + * be used for external hashes (ie. hashes sent across the network or + * saved to disk). The results will not change in future versions of + * this module. + * + * Note that it is only legal to hand an array of simple integer types + * to this hash (ie. char, uint16_t, int64_t, etc). In these cases, + * the same values will have the same hash result, even though the + * memory representations of integers depend on the machine + * endianness. + * + * See also: + * hash64_stable + * + * Example: + * #include <ccan/hash/hash.h> + * #include <err.h> + * #include <stdio.h> + * #include <string.h> + * + * int main(int argc, char *argv[]) + * { + * if (argc != 2) + * err(1, "Usage: %s <string-to-hash>", argv[0]); + * + * printf("Hash stable result is %u\n", + * hash_stable(argv[1], strlen(argv[1]), 0)); + * return 0; + * } + */ +#define hash_stable(p, num, base) \ + (BUILD_ASSERT_OR_ZERO(sizeof(*(p)) == 8 || sizeof(*(p)) == 4 \ + || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \ + sizeof(*(p)) == 8 ? hash_stable_64((p), (num), (base)) \ + : sizeof(*(p)) == 4 ? hash_stable_32((p), (num), (base)) \ + : sizeof(*(p)) == 2 ? hash_stable_16((p), (num), (base)) \ + : hash_stable_8((p), (num), (base))) + +/** + * hash_u32 - fast hash an array of 32-bit values for internal use + * @key: the array of uint32_t + * @num: the number of elements to hash + * @base: the base number to roll into the hash (usually 0) + * + * The array of uint32_t pointed to by @key is combined with the base + * to form a 32-bit hash. This is 2-3 times faster than hash() on small + * arrays, but the advantage vanishes over large hashes. + * + * This hash will have different results on different machines, so is + * only useful for internal hashes (ie. not hashes sent across the + * network or saved to disk). + */ +uint32_t hash_u32(const uint32_t *key, size_t num, uint32_t base); + +/** + * hash_string - very fast hash of an ascii string + * @str: the nul-terminated string + * + * The string is hashed, using a hash function optimized for ASCII and + * similar strings. It's weaker than the other hash functions. + * + * This hash may have different results on different machines, so is + * only useful for internal hashes (ie. not hashes sent across the + * network or saved to disk). The results will be different from the + * other hash functions in this module, too. + */ +static inline uint32_t hash_string(const char *string) +{ + /* This is Karl Nelson <kenelson@ece.ucdavis.edu>'s X31 hash. + * It's a little faster than the (much better) lookup3 hash(): 56ns vs + * 84ns on my 2GHz Intel Core Duo 2 laptop for a 10 char string. */ + uint32_t ret; + + for (ret = 0; *string; string++) + ret = (ret << 5) - ret + *string; + + return ret; +} + +/** + * hash64 - fast 64-bit hash of an array for internal use + * @p: the array or pointer to first element + * @num: the number of elements to hash + * @base: the 64-bit base number to roll into the hash (usually 0) + * + * The memory region pointed to by p is combined with the base to form + * a 64-bit hash. + * + * This hash will have different results on different machines, so is + * only useful for internal hashes (ie. not hashes sent across the + * network or saved to disk). + * + * It may also change with future versions: it could even detect at runtime + * what the fastest hash to use is. + * + * See also: hash. + * + * Example: + * #include <ccan/hash/hash.h> + * #include <err.h> + * #include <stdio.h> + * #include <string.h> + * + * // Simple demonstration: idential strings will have the same hash, but + * // two different strings will probably not. + * int main(int argc, char *argv[]) + * { + * uint64_t hash1, hash2; + * + * if (argc != 3) + * err(1, "Usage: %s <string1> <string2>", argv[0]); + * + * hash1 = hash64(argv[1], strlen(argv[1]), 0); + * hash2 = hash64(argv[2], strlen(argv[2]), 0); + * printf("Hash is %s\n", hash1 == hash2 ? "same" : "different"); + * return 0; + * } + */ +#define hash64(p, num, base) hash64_any((p), (num)*sizeof(*(p)), (base)) + +/** + * hash64_stable - 64 bit hash of an array for external use + * @p: the array or pointer to first element + * @num: the number of elements to hash + * @base: the base number to roll into the hash (usually 0) + * + * The array of simple integer types pointed to by p is combined with + * the base to form a 64-bit hash. + * + * This hash will have the same results on different machines, so can + * be used for external hashes (ie. hashes sent across the network or + * saved to disk). The results will not change in future versions of + * this module. + * + * Note that it is only legal to hand an array of simple integer types + * to this hash (ie. char, uint16_t, int64_t, etc). In these cases, + * the same values will have the same hash result, even though the + * memory representations of integers depend on the machine + * endianness. + * + * See also: + * hash_stable + * + * Example: + * #include <ccan/hash/hash.h> + * #include <err.h> + * #include <stdio.h> + * #include <string.h> + * + * int main(int argc, char *argv[]) + * { + * if (argc != 2) + * err(1, "Usage: %s <string-to-hash>", argv[0]); + * + * printf("Hash stable result is %llu\n", + * (long long)hash64_stable(argv[1], strlen(argv[1]), 0)); + * return 0; + * } + */ +#define hash64_stable(p, num, base) \ + (BUILD_ASSERT_OR_ZERO(sizeof(*(p)) == 8 || sizeof(*(p)) == 4 \ + || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \ + sizeof(*(p)) == 8 ? hash64_stable_64((p), (num), (base)) \ + : sizeof(*(p)) == 4 ? hash64_stable_32((p), (num), (base)) \ + : sizeof(*(p)) == 2 ? hash64_stable_16((p), (num), (base)) \ + : hash64_stable_8((p), (num), (base))) + + +/** + * hashl - fast 32/64-bit hash of an array for internal use + * @p: the array or pointer to first element + * @num: the number of elements to hash + * @base: the base number to roll into the hash (usually 0) + * + * This is either hash() or hash64(), on 32/64 bit long machines. + */ +#define hashl(p, num, base) \ + (BUILD_ASSERT_OR_ZERO(sizeof(long) == sizeof(uint32_t) \ + || sizeof(long) == sizeof(uint64_t)) + \ + (sizeof(long) == sizeof(uint64_t) \ + ? hash64((p), (num), (base)) : hash((p), (num), (base)))) + +/* Our underlying operations. */ +uint32_t hash_any(const void *key, size_t length, uint32_t base); +uint32_t hash_stable_64(const void *key, size_t n, uint32_t base); +uint32_t hash_stable_32(const void *key, size_t n, uint32_t base); +uint32_t hash_stable_16(const void *key, size_t n, uint32_t base); +uint32_t hash_stable_8(const void *key, size_t n, uint32_t base); +uint64_t hash64_any(const void *key, size_t length, uint64_t base); +uint64_t hash64_stable_64(const void *key, size_t n, uint64_t base); +uint64_t hash64_stable_32(const void *key, size_t n, uint64_t base); +uint64_t hash64_stable_16(const void *key, size_t n, uint64_t base); +uint64_t hash64_stable_8(const void *key, size_t n, uint64_t base); + +/** + * hash_pointer - hash a pointer for internal use + * @p: the pointer value to hash + * @base: the base number to roll into the hash (usually 0) + * + * The pointer p (not what p points to!) is combined with the base to form + * a 32-bit hash. + * + * This hash will have different results on different machines, so is + * only useful for internal hashes (ie. not hashes sent across the + * network or saved to disk). + * + * Example: + * #include <ccan/hash/hash.h> + * + * // Code to keep track of memory regions. + * struct region { + * struct region *chain; + * void *start; + * unsigned int size; + * }; + * // We keep a simple hash table. + * static struct region *region_hash[128]; + * + * static void add_region(struct region *r) + * { + * unsigned int h = hash_pointer(r->start, 0); + * + * r->chain = region_hash[h]; + * region_hash[h] = r->chain; + * } + * + * static struct region *find_region(const void *start) + * { + * struct region *r; + * + * for (r = region_hash[hash_pointer(start, 0)]; r; r = r->chain) + * if (r->start == start) + * return r; + * return NULL; + * } + */ +static inline uint32_t hash_pointer(const void *p, uint32_t base) +{ + if (sizeof(p) % sizeof(uint32_t) == 0) { + /* This convoluted union is the right way of aliasing. */ + union { + uint32_t a[sizeof(p) / sizeof(uint32_t)]; + const void *p; + } u; + u.p = p; + return hash_u32(u.a, sizeof(p) / sizeof(uint32_t), base); + } else + return hash(&p, 1, base); +} +#endif /* HASH_H */ diff --git a/ccan/ccan/htable/LICENSE b/ccan/ccan/htable/LICENSE new file mode 120000 index 0000000..dc314ec --- /dev/null +++ b/ccan/ccan/htable/LICENSE @@ -0,0 +1 @@ +../../licenses/LGPL-2.1
\ No newline at end of file diff --git a/ccan/ccan/htable/htable.c b/ccan/ccan/htable/htable.c new file mode 100644 index 0000000..f631ffe --- /dev/null +++ b/ccan/ccan/htable/htable.c @@ -0,0 +1,491 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#include <ccan/htable/htable.h> +#include <ccan/compiler/compiler.h> +#include <stdlib.h> +#include <stdio.h> +#include <limits.h> +#include <stdbool.h> +#include <assert.h> +#include <string.h> + +/* We use 0x1 as deleted marker. */ +#define HTABLE_DELETED (0x1) + +/* perfect_bitnum 63 means there's no perfect bitnum */ +#define NO_PERFECT_BIT (sizeof(uintptr_t) * CHAR_BIT - 1) + +static void *htable_default_alloc(struct htable *ht, size_t len) +{ + return calloc(len, 1); +} + +static void htable_default_free(struct htable *ht, void *p) +{ + free(p); +} + +static void *(*htable_alloc)(struct htable *, size_t) = htable_default_alloc; +static void (*htable_free)(struct htable *, void *) = htable_default_free; + +void htable_set_allocator(void *(*alloc)(struct htable *, size_t len), + void (*free)(struct htable *, void *p)) +{ + if (!alloc) + alloc = htable_default_alloc; + if (!free) + free = htable_default_free; + htable_alloc = alloc; + htable_free = free; +} + +/* We clear out the bits which are always the same, and put metadata there. */ +static inline uintptr_t get_extra_ptr_bits(const struct htable *ht, + uintptr_t e) +{ + return e & ht->common_mask; +} + +static inline void *get_raw_ptr(const struct htable *ht, uintptr_t e) +{ + return (void *)((e & ~ht->common_mask) | ht->common_bits); +} + +static inline uintptr_t make_hval(const struct htable *ht, + const void *p, uintptr_t bits) +{ + return ((uintptr_t)p & ~ht->common_mask) | bits; +} + +static inline bool entry_is_valid(uintptr_t e) +{ + return e > HTABLE_DELETED; +} + +static inline uintptr_t ht_perfect_mask(const struct htable *ht) +{ + return (uintptr_t)2 << ht->perfect_bitnum; +} + +static inline uintptr_t get_hash_ptr_bits(const struct htable *ht, + size_t hash) +{ + /* Shuffling the extra bits (as specified in mask) down the + * end is quite expensive. But the lower bits are redundant, so + * we fold the value first. */ + return (hash ^ (hash >> ht->bits)) + & ht->common_mask & ~ht_perfect_mask(ht); +} + +void htable_init(struct htable *ht, + size_t (*rehash)(const void *elem, void *priv), void *priv) +{ + struct htable empty = HTABLE_INITIALIZER(empty, NULL, NULL); + *ht = empty; + ht->rehash = rehash; + ht->priv = priv; + ht->table = &ht->common_bits; +} + +/* Fill to 87.5% */ +static inline size_t ht_max(const struct htable *ht) +{ + return ((size_t)7 << ht->bits) / 8; +} + +/* Clean deleted if we're full, and more than 12.5% deleted */ +static inline size_t ht_max_deleted(const struct htable *ht) +{ + return ((size_t)1 << ht->bits) / 8; +} + +bool htable_init_sized(struct htable *ht, + size_t (*rehash)(const void *, void *), + void *priv, size_t expect) +{ + htable_init(ht, rehash, priv); + + /* Don't go insane with sizing. */ + for (ht->bits = 1; ht_max(ht) < expect; ht->bits++) { + if (ht->bits == 30) + break; + } + + ht->table = htable_alloc(ht, sizeof(size_t) << ht->bits); + if (!ht->table) { + ht->table = &ht->common_bits; + return false; + } + (void)htable_debug(ht, HTABLE_LOC); + return true; +} + +void htable_clear(struct htable *ht) +{ + if (ht->table != &ht->common_bits) + htable_free(ht, (void *)ht->table); + htable_init(ht, ht->rehash, ht->priv); +} + +bool htable_copy_(struct htable *dst, const struct htable *src) +{ + uintptr_t *htable = htable_alloc(dst, sizeof(size_t) << src->bits); + + if (!htable) + return false; + + *dst = *src; + dst->table = htable; + memcpy(dst->table, src->table, sizeof(size_t) << src->bits); + return true; +} + +static size_t hash_bucket(const struct htable *ht, size_t h) +{ + return h & ((1 << ht->bits)-1); +} + +static void *htable_val(const struct htable *ht, + struct htable_iter *i, size_t hash, uintptr_t perfect) +{ + uintptr_t h2 = get_hash_ptr_bits(ht, hash) | perfect; + + while (ht->table[i->off]) { + if (ht->table[i->off] != HTABLE_DELETED) { + if (get_extra_ptr_bits(ht, ht->table[i->off]) == h2) + return get_raw_ptr(ht, ht->table[i->off]); + } + i->off = (i->off + 1) & ((1 << ht->bits)-1); + h2 &= ~perfect; + } + return NULL; +} + +void *htable_firstval_(const struct htable *ht, + struct htable_iter *i, size_t hash) +{ + i->off = hash_bucket(ht, hash); + return htable_val(ht, i, hash, ht_perfect_mask(ht)); +} + +void *htable_nextval_(const struct htable *ht, + struct htable_iter *i, size_t hash) +{ + i->off = (i->off + 1) & ((1 << ht->bits)-1); + return htable_val(ht, i, hash, 0); +} + +void *htable_first_(const struct htable *ht, struct htable_iter *i) +{ + for (i->off = 0; i->off < (size_t)1 << ht->bits; i->off++) { + if (entry_is_valid(ht->table[i->off])) + return get_raw_ptr(ht, ht->table[i->off]); + } + return NULL; +} + +void *htable_next_(const struct htable *ht, struct htable_iter *i) +{ + for (i->off++; i->off < (size_t)1 << ht->bits; i->off++) { + if (entry_is_valid(ht->table[i->off])) + return get_raw_ptr(ht, ht->table[i->off]); + } + return NULL; +} + +void *htable_prev_(const struct htable *ht, struct htable_iter *i) +{ + for (;;) { + if (!i->off) + return NULL; + i->off--; + if (entry_is_valid(ht->table[i->off])) + return get_raw_ptr(ht, ht->table[i->off]); + } +} + +/* Another bit currently in mask needs to be exposed, so that a bucket with p in + * it won't appear invalid */ +static COLD void unset_another_common_bit(struct htable *ht, + uintptr_t *maskdiff, + const void *p) +{ + size_t i; + + for (i = sizeof(uintptr_t) * CHAR_BIT - 1; i > 0; i--) { + if (((uintptr_t)p & ((uintptr_t)1 << i)) + && ht->common_mask & ~*maskdiff & ((uintptr_t)1 << i)) + break; + } + /* There must have been one, right? */ + assert(i > 0); + + *maskdiff |= ((uintptr_t)1 << i); +} + +/* We want to change the common mask: this fixes up the table */ +static COLD void fixup_table_common(struct htable *ht, uintptr_t maskdiff) +{ + size_t i; + uintptr_t bitsdiff; + +again: + bitsdiff = ht->common_bits & maskdiff; + + for (i = 0; i < (size_t)1 << ht->bits; i++) { + uintptr_t e; + if (!entry_is_valid(e = ht->table[i])) + continue; + + /* Clear the bits no longer in the mask, set them as + * expected. */ + e &= ~maskdiff; + e |= bitsdiff; + /* If this made it invalid, restart with more exposed */ + if (!entry_is_valid(e)) { + unset_another_common_bit(ht, &maskdiff, get_raw_ptr(ht, e)); + goto again; + } + ht->table[i] = e; + } + + /* Take away those bits from our mask, bits and perfect bit. */ + ht->common_mask &= ~maskdiff; + ht->common_bits &= ~maskdiff; + if (ht_perfect_mask(ht) & maskdiff) + ht->perfect_bitnum = NO_PERFECT_BIT; +} + +/* Limited recursion */ +static void ht_add(struct htable *ht, const void *new, size_t h); + +/* We tried to add this entry, but it looked invalid! We need to + * let another pointer bit through mask */ +static COLD void update_common_fix_invalid(struct htable *ht, const void *p, size_t h) +{ + uintptr_t maskdiff; + + assert(ht->elems != 0); + + maskdiff = 0; + unset_another_common_bit(ht, &maskdiff, p); + fixup_table_common(ht, maskdiff); + + /* Now won't recurse */ + ht_add(ht, p, h); +} + +/* This does not expand the hash table, that's up to caller. */ +static void ht_add(struct htable *ht, const void *new, size_t h) +{ + size_t i; + uintptr_t perfect = ht_perfect_mask(ht); + + i = hash_bucket(ht, h); + + while (entry_is_valid(ht->table[i])) { + perfect = 0; + i = (i + 1) & ((1 << ht->bits)-1); + } + ht->table[i] = make_hval(ht, new, get_hash_ptr_bits(ht, h)|perfect); + if (!entry_is_valid(ht->table[i])) + update_common_fix_invalid(ht, new, h); +} + +static COLD bool double_table(struct htable *ht) +{ + unsigned int i; + size_t oldnum = (size_t)1 << ht->bits; + uintptr_t *oldtable, e; + + oldtable = ht->table; + ht->table = htable_alloc(ht, sizeof(size_t) << (ht->bits+1)); + if (!ht->table) { + ht->table = oldtable; + return false; + } + ht->bits++; + + /* If we lost our "perfect bit", get it back now. */ + if (ht->perfect_bitnum == NO_PERFECT_BIT && ht->common_mask) { + for (i = 0; i < sizeof(ht->common_mask) * CHAR_BIT; i++) { + if (ht->common_mask & ((size_t)2 << i)) { + ht->perfect_bitnum = i; + break; + } + } + } + + if (oldtable != &ht->common_bits) { + for (i = 0; i < oldnum; i++) { + if (entry_is_valid(e = oldtable[i])) { + void *p = get_raw_ptr(ht, e); + ht_add(ht, p, ht->rehash(p, ht->priv)); + } + } + htable_free(ht, oldtable); + } + ht->deleted = 0; + + (void)htable_debug(ht, HTABLE_LOC); + return true; +} + +static COLD void rehash_table(struct htable *ht) +{ + size_t start, i; + uintptr_t e, perfect = ht_perfect_mask(ht); + + /* Beware wrap cases: we need to start from first empty bucket. */ + for (start = 0; ht->table[start]; start++); + + for (i = 0; i < (size_t)1 << ht->bits; i++) { + size_t h = (i + start) & ((1 << ht->bits)-1); + e = ht->table[h]; + if (!e) + continue; + if (e == HTABLE_DELETED) + ht->table[h] = 0; + else if (!(e & perfect)) { + void *p = get_raw_ptr(ht, e); + ht->table[h] = 0; + ht_add(ht, p, ht->rehash(p, ht->priv)); + } + } + ht->deleted = 0; + (void)htable_debug(ht, HTABLE_LOC); +} + +/* We stole some bits, now we need to put them back... */ +static COLD void update_common(struct htable *ht, const void *p) +{ + uintptr_t maskdiff; + + if (ht->elems == 0) { + ht->common_mask = -1; + ht->common_bits = ((uintptr_t)p & ht->common_mask); + ht->perfect_bitnum = 0; + (void)htable_debug(ht, HTABLE_LOC); + return; + } + + /* Find bits which are unequal to old common set. */ + maskdiff = ht->common_bits ^ ((uintptr_t)p & ht->common_mask); + + fixup_table_common(ht, maskdiff); + (void)htable_debug(ht, HTABLE_LOC); +} + +bool htable_add_(struct htable *ht, size_t hash, const void *p) +{ + /* Cannot insert NULL, or (void *)1. */ + assert(p); + assert(entry_is_valid((uintptr_t)p)); + + /* Getting too full? */ + if (ht->elems+1 + ht->deleted > ht_max(ht)) { + /* If we're more than 1/8 deleted, clean those, + * otherwise double table size. */ + if (ht->deleted > ht_max_deleted(ht)) + rehash_table(ht); + else if (!double_table(ht)) + return false; + } + if (((uintptr_t)p & ht->common_mask) != ht->common_bits) + update_common(ht, p); + + ht_add(ht, p, hash); + ht->elems++; + return true; +} + +bool htable_del_(struct htable *ht, size_t h, const void *p) +{ + struct htable_iter i; + void *c; + + for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) { + if (c == p) { + htable_delval(ht, &i); + return true; + } + } + return false; +} + +void htable_delval_(struct htable *ht, struct htable_iter *i) +{ + assert(i->off < (size_t)1 << ht->bits); + assert(entry_is_valid(ht->table[i->off])); + + ht->elems--; + /* Cheap test: if the next bucket is empty, don't need delete marker */ + if (ht->table[hash_bucket(ht, i->off+1)] != 0) { + ht->table[i->off] = HTABLE_DELETED; + ht->deleted++; + } else + ht->table[i->off] = 0; +} + +void *htable_pick_(const struct htable *ht, size_t seed, struct htable_iter *i) +{ + void *e; + struct htable_iter unwanted; + + if (!i) + i = &unwanted; + i->off = seed % ((size_t)1 << ht->bits); + e = htable_next(ht, i); + if (!e) + e = htable_first(ht, i); + return e; +} + +struct htable *htable_check(const struct htable *ht, const char *abortstr) +{ + void *p; + struct htable_iter i; + size_t n = 0; + + /* Use non-DEBUG versions here, to avoid infinite recursion with + * CCAN_HTABLE_DEBUG! */ + for (p = htable_first_(ht, &i); p; p = htable_next_(ht, &i)) { + struct htable_iter i2; + void *c; + size_t h = ht->rehash(p, ht->priv); + bool found = false; + + n++; + + /* Open-code htable_get to avoid CCAN_HTABLE_DEBUG */ + for (c = htable_firstval_(ht, &i2, h); + c; + c = htable_nextval_(ht, &i2, h)) { + if (c == p) { + found = true; + break; + } + } + + if (!found) { + if (abortstr) { + fprintf(stderr, + "%s: element %p in position %zu" + " cannot find itself\n", + abortstr, p, i.off); + abort(); + } + return NULL; + } + } + if (n != ht->elems) { + if (abortstr) { + fprintf(stderr, + "%s: found %zu elems, expected %zu\n", + abortstr, n, ht->elems); + abort(); + } + return NULL; + } + + return (struct htable *)ht; +} diff --git a/ccan/ccan/htable/htable.h b/ccan/ccan/htable/htable.h new file mode 100644 index 0000000..faaf541 --- /dev/null +++ b/ccan/ccan/htable/htable.h @@ -0,0 +1,290 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#ifndef CCAN_HTABLE_H +#define CCAN_HTABLE_H +#include "config.h" +#include <ccan/str/str.h> +#include <stdint.h> +#include <stdbool.h> +#include <stdlib.h> + +/* Define CCAN_HTABLE_DEBUG for expensive debugging checks on each call. */ +#define HTABLE_LOC __FILE__ ":" stringify(__LINE__) +#ifdef CCAN_HTABLE_DEBUG +#define htable_debug(h, loc) htable_check((h), loc) +#else +#define htable_debug(h, loc) ((void)loc, h) +#endif + +/** + * struct htable - private definition of a htable. + * + * It's exposed here so you can put it in your structures and so we can + * supply inline functions. + */ +struct htable { + size_t (*rehash)(const void *elem, void *priv); + void *priv; + unsigned int bits, perfect_bitnum; + size_t elems, deleted; + /* These are the bits which are the same in all pointers. */ + uintptr_t common_mask, common_bits; + uintptr_t *table; +}; + +/** + * HTABLE_INITIALIZER - static initialization for a hash table. + * @name: name of this htable. + * @rehash: hash function to use for rehashing. + * @priv: private argument to @rehash function. + * + * This is useful for setting up static and global hash tables. + * + * Example: + * // For simplicity's sake, say hash value is contents of elem. + * static size_t rehash(const void *elem, void *unused) + * { + * (void)unused; + * return *(size_t *)elem; + * } + * static struct htable ht = HTABLE_INITIALIZER(ht, rehash, NULL); + */ +#define HTABLE_INITIALIZER(name, rehash, priv) \ + { rehash, priv, 0, 0, 0, 0, -1, 0, &name.common_bits } + +/** + * htable_init - initialize an empty hash table. + * @ht: the hash table to initialize + * @rehash: hash function to use for rehashing. + * @priv: private argument to @rehash function. + */ +void htable_init(struct htable *ht, + size_t (*rehash)(const void *elem, void *priv), void *priv); + +/** + * htable_init_sized - initialize an empty hash table of given size. + * @ht: the hash table to initialize + * @rehash: hash function to use for rehashing. + * @priv: private argument to @rehash function. + * @size: the number of element. + * + * If this returns false, @ht is still usable, but may need to do reallocation + * upon an add. If this returns true, it will not need to reallocate within + * @size htable_adds. + */ +bool htable_init_sized(struct htable *ht, + size_t (*rehash)(const void *elem, void *priv), + void *priv, size_t size); + +/** + * htable_count - count number of entries in a hash table. + * @ht: the hash table + */ +static inline size_t htable_count(const struct htable *ht) +{ + return ht->elems; +} + +/** + * htable_clear - empty a hash table. + * @ht: the hash table to clear + * + * This doesn't do anything to any pointers left in it. + */ +void htable_clear(struct htable *ht); + + +/** + * htable_check - check hash table for consistency + * @ht: the htable + * @abortstr: the location to print on aborting, or NULL. + * + * Because hash tables have redundant information, consistency checking that + * each element is in the correct location can be done. This is useful as a + * debugging check. If @abortstr is non-NULL, that will be printed in a + * diagnostic if the htable is inconsistent, and the function will abort. + * + * Returns the htable if it is consistent, NULL if not (it can never return + * NULL if @abortstr is set). + */ +struct htable *htable_check(const struct htable *ht, const char *abortstr); + +/** + * htable_copy - duplicate a hash table. + * @dst: the hash table to overwrite + * @src: the hash table to copy + * + * Only fails on out-of-memory. + * + * Equivalent to (but faster than): + * if (!htable_init_sized(dst, src->rehash, src->priv, 1U << src->bits)) + * return false; + * v = htable_first(src, &i); + * while (v) { + * htable_add(dst, v); + * v = htable_next(src, i); + * } + * return true; + */ +#define htable_copy(dst, src) htable_copy_(dst, htable_debug(src, HTABLE_LOC)) +bool htable_copy_(struct htable *dst, const struct htable *src); + +/** + * htable_add - add a pointer into a hash table. + * @ht: the htable + * @hash: the hash value of the object + * @p: the non-NULL pointer (also cannot be (void *)1). + * + * Also note that this can only fail due to allocation failure. Otherwise, it + * returns true. + */ +#define htable_add(ht, hash, p) \ + htable_add_(htable_debug(ht, HTABLE_LOC), hash, p) +bool htable_add_(struct htable *ht, size_t hash, const void *p); + +/** + * htable_del - remove a pointer from a hash table + * @ht: the htable + * @hash: the hash value of the object + * @p: the pointer + * + * Returns true if the pointer was found (and deleted). + */ +#define htable_del(ht, hash, p) \ + htable_del_(htable_debug(ht, HTABLE_LOC), hash, p) +bool htable_del_(struct htable *ht, size_t hash, const void *p); + +/** + * struct htable_iter - iterator or htable_first or htable_firstval etc. + * + * This refers to a location inside the hashtable. + */ +struct htable_iter { + size_t off; +}; + +/** + * htable_firstval - find a candidate for a given hash value + * @htable: the hashtable + * @i: the struct htable_iter to initialize + * @hash: the hash value + * + * You'll need to check the value is what you want; returns NULL if none. + * See Also: + * htable_delval() + */ +#define htable_firstval(htable, i, hash) \ + htable_firstval_(htable_debug(htable, HTABLE_LOC), i, hash) + +void *htable_firstval_(const struct htable *htable, + struct htable_iter *i, size_t hash); + +/** + * htable_nextval - find another candidate for a given hash value + * @htable: the hashtable + * @i: the struct htable_iter to initialize + * @hash: the hash value + * + * You'll need to check the value is what you want; returns NULL if no more. + */ +#define htable_nextval(htable, i, hash) \ + htable_nextval_(htable_debug(htable, HTABLE_LOC), i, hash) +void *htable_nextval_(const struct htable *htable, + struct htable_iter *i, size_t hash); + +/** + * htable_get - find an entry in the hash table + * @ht: the hashtable + * @h: the hash value of the entry + * @cmp: the comparison function + * @ptr: the pointer to hand to the comparison function. + * + * Convenient inline wrapper for htable_firstval/htable_nextval loop. + */ +static inline void *htable_get(const struct htable *ht, + size_t h, + bool (*cmp)(const void *candidate, void *ptr), + const void *ptr) +{ + struct htable_iter i; + void *c; + + for (c = htable_firstval(ht,&i,h); c; c = htable_nextval(ht,&i,h)) { + if (cmp(c, (void *)ptr)) + return c; + } + return NULL; +} + +/** + * htable_first - find an entry in the hash table + * @ht: the hashtable + * @i: the struct htable_iter to initialize + * + * Get an entry in the hashtable; NULL if empty. + */ +#define htable_first(htable, i) \ + htable_first_(htable_debug(htable, HTABLE_LOC), i) +void *htable_first_(const struct htable *htable, struct htable_iter *i); + +/** + * htable_next - find another entry in the hash table + * @ht: the hashtable + * @i: the struct htable_iter to use + * + * Get another entry in the hashtable; NULL if all done. + * This is usually used after htable_first or prior non-NULL htable_next. + */ +#define htable_next(htable, i) \ + htable_next_(htable_debug(htable, HTABLE_LOC), i) +void *htable_next_(const struct htable *htable, struct htable_iter *i); + +/** + * htable_prev - find the previous entry in the hash table + * @ht: the hashtable + * @i: the struct htable_iter to use + * + * Get previous entry in the hashtable; NULL if all done. + * + * "previous" here only means the item that would have been returned by + * htable_next() before the item it returned most recently. + * + * This is usually used in the middle of (or after) a htable_next iteration and + * to "unwind" actions taken. + */ +#define htable_prev(htable, i) \ + htable_prev_(htable_debug(htable, HTABLE_LOC), i) +void *htable_prev_(const struct htable *htable, struct htable_iter *i); + +/** + * htable_delval - remove an iterated pointer from a hash table + * @ht: the htable + * @i: the htable_iter + * + * Usually used to delete a hash entry after it has been found with + * htable_firstval etc. + */ +#define htable_delval(htable, i) \ + htable_delval_(htable_debug(htable, HTABLE_LOC), i) +void htable_delval_(struct htable *ht, struct htable_iter *i); + +/** + * htable_pick - set iterator to a random valid entry. + * @ht: the htable + * @seed: a random number to use. + * @i: the htable_iter which is output (or NULL). + * + * Usually used with htable_delval to delete a random entry. Returns + * NULL iff the table is empty, otherwise a random entry. + */ +#define htable_pick(htable, seed, i) \ + htable_pick_(htable_debug(htable, HTABLE_LOC), seed, i) +void *htable_pick_(const struct htable *ht, size_t seed, struct htable_iter *i); + +/** + * htable_set_allocator - set calloc/free functions. + * @alloc: allocator to use, must zero memory! + * @free: unallocator to use (@p is NULL or a return from @alloc) + */ +void htable_set_allocator(void *(*alloc)(struct htable *, size_t len), + void (*free)(struct htable *, void *p)); +#endif /* CCAN_HTABLE_H */ diff --git a/ccan/ccan/htable/htable_type.h b/ccan/ccan/htable/htable_type.h new file mode 100644 index 0000000..0aacb7f --- /dev/null +++ b/ccan/ccan/htable/htable_type.h @@ -0,0 +1,188 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#ifndef CCAN_HTABLE_TYPE_H +#define CCAN_HTABLE_TYPE_H +#include <ccan/htable/htable.h> +#include <ccan/compiler/compiler.h> +#include "config.h" + +/** + * HTABLE_DEFINE_TYPE - create a set of htable ops for a type + * @type: a type whose pointers will be values in the hash. + * @keyof: a function/macro to extract a key: <keytype> @keyof(const type *elem) + * @hashfn: a hash function for a @key: size_t @hashfn(const <keytype> *) + * @eqfn: an equality function keys: bool @eqfn(const type *, const <keytype> *) + * @prefix: a prefix for all the functions to define (of form <name>_*) + * + * NULL values may not be placed into the hash table. + * + * This defines the type hashtable type and an iterator type: + * struct <name>; + * struct <name>_iter; + * + * It also defines initialization and freeing functions: + * void <name>_init(struct <name> *); + * bool <name>_init_sized(struct <name> *, size_t); + * void <name>_clear(struct <name> *); + * bool <name>_copy(struct <name> *dst, const struct <name> *src); + * + * Count entries: + * size_t <name>_count(const struct <name> *ht); + * + * Add function only fails if we run out of memory: + * bool <name>_add(struct <name> *ht, const <type> *e); + * + * Delete and delete-by key return true if it was in the set: + * bool <name>_del(struct <name> *ht, const <type> *e); + * bool <name>_delkey(struct <name> *ht, const <keytype> *k); + * + * Delete by iterator: + * bool <name>_delval(struct <name> *ht, struct <name>_iter *i); + * + * Find and return the (first) matching element, or NULL: + * type *<name>_get(const struct @name *ht, const <keytype> *k); + * + * Find and return all matching elements, or NULL: + * type *<name>_getfirst(const struct @name *ht, const <keytype> *k, + * struct <name>_iter *i); + * type *<name>_getnext(const struct @name *ht, const <keytype> *k, + * struct <name>_iter *i); + * + * Iteration over hashtable is also supported: + * type *<name>_first(const struct <name> *ht, struct <name>_iter *i); + * type *<name>_next(const struct <name> *ht, struct <name>_iter *i); + * type *<name>_prev(const struct <name> *ht, struct <name>_iter *i); + * type *<name>_pick(const struct <name> *ht, size_t seed, + * struct <name>_iter *i); + * It's currently safe to iterate over a changing hashtable, but you might + * miss an element. Iteration isn't very efficient, either. + * + * You can use HTABLE_INITIALIZER like so: + * struct <name> ht = { HTABLE_INITIALIZER(ht.raw, <name>_hash, NULL) }; + */ +#define HTABLE_DEFINE_TYPE(type, keyof, hashfn, eqfn, name) \ + struct name { struct htable raw; }; \ + struct name##_iter { struct htable_iter i; }; \ + static inline size_t name##_hash(const void *elem, void *priv) \ + { \ + (void)priv; \ + return hashfn(keyof((const type *)elem)); \ + } \ + static inline UNNEEDED void name##_init(struct name *ht) \ + { \ + htable_init(&ht->raw, name##_hash, NULL); \ + } \ + static inline UNNEEDED bool name##_init_sized(struct name *ht, \ + size_t s) \ + { \ + return htable_init_sized(&ht->raw, name##_hash, NULL, s); \ + } \ + static inline UNNEEDED size_t name##_count(const struct name *ht) \ + { \ + return htable_count(&ht->raw); \ + } \ + static inline UNNEEDED void name##_clear(struct name *ht) \ + { \ + htable_clear(&ht->raw); \ + } \ + static inline UNNEEDED bool name##_copy(struct name *dst, \ + const struct name *src) \ + { \ + return htable_copy(&dst->raw, &src->raw); \ + } \ + static inline bool name##_add(struct name *ht, const type *elem) \ + { \ + return htable_add(&ht->raw, hashfn(keyof(elem)), elem); \ + } \ + static inline UNNEEDED bool name##_del(struct name *ht, \ + const type *elem) \ + { \ + return htable_del(&ht->raw, hashfn(keyof(elem)), elem); \ + } \ + static inline UNNEEDED type *name##_get(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k) \ + { \ + struct htable_iter i; \ + size_t h = hashfn(k); \ + void *c; \ + \ + for (c = htable_firstval(&ht->raw,&i,h); \ + c; \ + c = htable_nextval(&ht->raw,&i,h)) { \ + if (eqfn(c, k)) \ + return c; \ + } \ + return NULL; \ + } \ + static inline UNNEEDED type *name##_getmatch_(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k, \ + size_t h, \ + type *v, \ + struct name##_iter *iter) \ + { \ + while (v) { \ + if (eqfn(v, k)) \ + break; \ + v = htable_nextval(&ht->raw, &iter->i, h); \ + } \ + return v; \ + } \ + static inline UNNEEDED type *name##_getfirst(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k, \ + struct name##_iter *iter) \ + { \ + size_t h = hashfn(k); \ + type *v = htable_firstval(&ht->raw, &iter->i, h); \ + return name##_getmatch_(ht, k, h, v, iter); \ + } \ + static inline UNNEEDED type *name##_getnext(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k, \ + struct name##_iter *iter) \ + { \ + size_t h = hashfn(k); \ + type *v = htable_nextval(&ht->raw, &iter->i, h); \ + return name##_getmatch_(ht, k, h, v, iter); \ + } \ + static inline UNNEEDED bool name##_delkey(struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k) \ + { \ + type *elem = name##_get(ht, k); \ + if (elem) \ + return name##_del(ht, elem); \ + return false; \ + } \ + static inline UNNEEDED void name##_delval(struct name *ht, \ + struct name##_iter *iter) \ + { \ + htable_delval(&ht->raw, &iter->i); \ + } \ + static inline UNNEEDED type *name##_pick(const struct name *ht, \ + size_t seed, \ + struct name##_iter *iter) \ + { \ + return htable_pick(&ht->raw, seed, iter ? &iter->i : NULL); \ + } \ + static inline UNNEEDED type *name##_first(const struct name *ht, \ + struct name##_iter *iter) \ + { \ + return htable_first(&ht->raw, &iter->i); \ + } \ + static inline UNNEEDED type *name##_next(const struct name *ht, \ + struct name##_iter *iter) \ + { \ + return htable_next(&ht->raw, &iter->i); \ + } \ + static inline UNNEEDED type *name##_prev(const struct name *ht, \ + struct name##_iter *iter) \ + { \ + return htable_prev(&ht->raw, &iter->i); \ + } + +#if HAVE_TYPEOF +#define HTABLE_KTYPE(keyof, type) typeof(keyof((const type *)NULL)) +#else +/* Assumes keys are a pointer: if not, override. */ +#ifndef HTABLE_KTYPE +#define HTABLE_KTYPE(keyof, type) void * +#endif +#endif +#endif /* CCAN_HTABLE_TYPE_H */ diff --git a/ccan/ccan/ilog/LICENSE b/ccan/ccan/ilog/LICENSE new file mode 120000 index 0000000..b7951da --- /dev/null +++ b/ccan/ccan/ilog/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0
\ No newline at end of file diff --git a/ccan/ccan/ilog/ilog.c b/ccan/ccan/ilog/ilog.c new file mode 100644 index 0000000..5f5122d --- /dev/null +++ b/ccan/ccan/ilog/ilog.c @@ -0,0 +1,141 @@ +/*(C) Timothy B. Terriberry (tterribe@xiph.org) 2001-2009 CC0 (Public domain). + * See LICENSE file for details. */ +#include "ilog.h" +#include <limits.h> + +/*The fastest fallback strategy for platforms with fast multiplication appears + to be based on de Bruijn sequences~\cite{LP98}. + Tests confirmed this to be true even on an ARM11, where it is actually faster + than using the native clz instruction. + Define ILOG_NODEBRUIJN to use a simpler fallback on platforms where + multiplication or table lookups are too expensive. + + @UNPUBLISHED{LP98, + author="Charles E. Leiserson and Harald Prokop", + title="Using de {Bruijn} Sequences to Index a 1 in a Computer Word", + month=Jun, + year=1998, + note="\url{http://supertech.csail.mit.edu/papers/debruijn.pdf}" + }*/ +static UNNEEDED const unsigned char DEBRUIJN_IDX32[32]={ + 0, 1,28, 2,29,14,24, 3,30,22,20,15,25,17, 4, 8, + 31,27,13,23,21,19,16, 7,26,12,18, 6,11, 5,10, 9 +}; + +/* We always compile these in, in case someone takes address of function. */ +#undef ilog32_nz +#undef ilog32 +#undef ilog64_nz +#undef ilog64 + +int ilog32(uint32_t _v){ +/*On a Pentium M, this branchless version tested as the fastest version without + multiplications on 1,000,000,000 random 32-bit integers, edging out a + similar version with branches, and a 256-entry LUT version.*/ +# if defined(ILOG_NODEBRUIJN) + int ret; + int m; + ret=_v>0; + m=(_v>0xFFFFU)<<4; + _v>>=m; + ret|=m; + m=(_v>0xFFU)<<3; + _v>>=m; + ret|=m; + m=(_v>0xFU)<<2; + _v>>=m; + ret|=m; + m=(_v>3)<<1; + _v>>=m; + ret|=m; + ret+=_v>1; + return ret; +/*This de Bruijn sequence version is faster if you have a fast multiplier.*/ +# else + int ret; + ret=_v>0; + _v|=_v>>1; + _v|=_v>>2; + _v|=_v>>4; + _v|=_v>>8; + _v|=_v>>16; + _v=(_v>>1)+1; + ret+=DEBRUIJN_IDX32[_v*0x77CB531U>>27&0x1F]; + return ret; +# endif +} + +int ilog32_nz(uint32_t _v) +{ + return ilog32(_v); +} + +int ilog64(uint64_t _v){ +# if defined(ILOG_NODEBRUIJN) + uint32_t v; + int ret; + int m; + ret=_v>0; + m=(_v>0xFFFFFFFFU)<<5; + v=(uint32_t)(_v>>m); + ret|=m; + m=(v>0xFFFFU)<<4; + v>>=m; + ret|=m; + m=(v>0xFFU)<<3; + v>>=m; + ret|=m; + m=(v>0xFU)<<2; + v>>=m; + ret|=m; + m=(v>3)<<1; + v>>=m; + ret|=m; + ret+=v>1; + return ret; +# else +/*If we don't have a 64-bit word, split it into two 32-bit halves.*/ +# if LONG_MAX<9223372036854775807LL + uint32_t v; + int ret; + int m; + ret=_v>0; + m=(_v>0xFFFFFFFFU)<<5; + v=(uint32_t)(_v>>m); + ret|=m; + v|=v>>1; + v|=v>>2; + v|=v>>4; + v|=v>>8; + v|=v>>16; + v=(v>>1)+1; + ret+=DEBRUIJN_IDX32[v*0x77CB531U>>27&0x1F]; + return ret; +/*Otherwise do it in one 64-bit operation.*/ +# else + static const unsigned char DEBRUIJN_IDX64[64]={ + 0, 1, 2, 7, 3,13, 8,19, 4,25,14,28, 9,34,20,40, + 5,17,26,38,15,46,29,48,10,31,35,54,21,50,41,57, + 63, 6,12,18,24,27,33,39,16,37,45,47,30,53,49,56, + 62,11,23,32,36,44,52,55,61,22,43,51,60,42,59,58 + }; + int ret; + ret=_v>0; + _v|=_v>>1; + _v|=_v>>2; + _v|=_v>>4; + _v|=_v>>8; + _v|=_v>>16; + _v|=_v>>32; + _v=(_v>>1)+1; + ret+=DEBRUIJN_IDX64[_v*0x218A392CD3D5DBF>>58&0x3F]; + return ret; +# endif +# endif +} + +int ilog64_nz(uint64_t _v) +{ + return ilog64(_v); +} + diff --git a/ccan/ccan/ilog/ilog.h b/ccan/ccan/ilog/ilog.h new file mode 100644 index 0000000..32702b1 --- /dev/null +++ b/ccan/ccan/ilog/ilog.h @@ -0,0 +1,154 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#if !defined(_ilog_H) +# define _ilog_H (1) +# include "config.h" +# include <stdint.h> +# include <limits.h> +# include <ccan/compiler/compiler.h> + +/** + * ilog32 - Integer binary logarithm of a 32-bit value. + * @_v: A 32-bit value. + * Returns floor(log2(_v))+1, or 0 if _v==0. + * This is the number of bits that would be required to represent _v in two's + * complement notation with all of the leading zeros stripped. + * Note that many uses will resolve to the fast macro version instead. + * + * See Also: + * ilog32_nz(), ilog64() + * + * Example: + * // Rounds up to next power of 2 (if not a power of 2). + * static uint32_t round_up32(uint32_t i) + * { + * assert(i != 0); + * return 1U << ilog32(i-1); + * } + */ +int ilog32(uint32_t _v) CONST_FUNCTION; + +/** + * ilog32_nz - Integer binary logarithm of a non-zero 32-bit value. + * @_v: A 32-bit value. + * Returns floor(log2(_v))+1, or undefined if _v==0. + * This is the number of bits that would be required to represent _v in two's + * complement notation with all of the leading zeros stripped. + * Note that many uses will resolve to the fast macro version instead. + * See Also: + * ilog32(), ilog64_nz() + * Example: + * // Find Last Set (ie. highest bit set, 0 to 31). + * static uint32_t fls32(uint32_t i) + * { + * assert(i != 0); + * return ilog32_nz(i) - 1; + * } + */ +int ilog32_nz(uint32_t _v) CONST_FUNCTION; + +/** + * ilog64 - Integer binary logarithm of a 64-bit value. + * @_v: A 64-bit value. + * Returns floor(log2(_v))+1, or 0 if _v==0. + * This is the number of bits that would be required to represent _v in two's + * complement notation with all of the leading zeros stripped. + * Note that many uses will resolve to the fast macro version instead. + * See Also: + * ilog64_nz(), ilog32() + */ +int ilog64(uint64_t _v) CONST_FUNCTION; + +/** + * ilog64_nz - Integer binary logarithm of a non-zero 64-bit value. + * @_v: A 64-bit value. + * Returns floor(log2(_v))+1, or undefined if _v==0. + * This is the number of bits that would be required to represent _v in two's + * complement notation with all of the leading zeros stripped. + * Note that many uses will resolve to the fast macro version instead. + * See Also: + * ilog64(), ilog32_nz() + */ +int ilog64_nz(uint64_t _v) CONST_FUNCTION; + +/** + * STATIC_ILOG_32 - The integer logarithm of an (unsigned, 32-bit) constant. + * @_v: A non-negative 32-bit constant. + * Returns floor(log2(_v))+1, or 0 if _v==0. + * This is the number of bits that would be required to represent _v in two's + * complement notation with all of the leading zeros stripped. + * This macro should only be used when you need a compile-time constant, + * otherwise ilog32 or ilog32_nz are just as fast and more flexible. + * + * Example: + * #define MY_PAGE_SIZE 4096 + * #define MY_PAGE_BITS (STATIC_ILOG_32(PAGE_SIZE) - 1) + */ +#define STATIC_ILOG_32(_v) (STATIC_ILOG5((uint32_t)(_v))) + +/** + * STATIC_ILOG_64 - The integer logarithm of an (unsigned, 64-bit) constant. + * @_v: A non-negative 64-bit constant. + * Returns floor(log2(_v))+1, or 0 if _v==0. + * This is the number of bits that would be required to represent _v in two's + * complement notation with all of the leading zeros stripped. + * This macro should only be used when you need a compile-time constant, + * otherwise ilog64 or ilog64_nz are just as fast and more flexible. + */ +#define STATIC_ILOG_64(_v) (STATIC_ILOG6((uint64_t)(_v))) + +/* Private implementation details */ + +/*Note the casts to (int) below: this prevents "upgrading" + the type of an entire expression to an (unsigned) size_t.*/ +#if INT_MAX>=2147483647 && HAVE_BUILTIN_CLZ +#define builtin_ilog32_nz(v) \ + (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clz(v)) +#elif LONG_MAX>=2147483647L && HAVE_BUILTIN_CLZL +#define builtin_ilog32_nz(v) \ + (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clzl(v)) +#endif + +#if INT_MAX>=9223372036854775807LL && HAVE_BUILTIN_CLZ +#define builtin_ilog64_nz(v) \ + (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clz(v)) +#elif LONG_MAX>=9223372036854775807LL && HAVE_BUILTIN_CLZL +#define builtin_ilog64_nz(v) \ + (((int)sizeof(unsigned long)*CHAR_BIT) - __builtin_clzl(v)) +#elif HAVE_BUILTIN_CLZLL +#define builtin_ilog64_nz(v) \ + (((int)sizeof(unsigned long long)*CHAR_BIT) - __builtin_clzll(v)) +#endif + +#ifdef builtin_ilog32_nz +/* This used to be builtin_ilog32_nz(_v)&-!!(_v), which means it zeroes out + * the undefined builtin_ilog32_nz(0) return. But clang UndefinedBehaviorSantizer + * complains, so do the branch: */ +#define ilog32(_v) ((_v) ? builtin_ilog32_nz(_v) : 0) +#define ilog32_nz(_v) builtin_ilog32_nz(_v) +#else +#define ilog32_nz(_v) ilog32(_v) +#define ilog32(_v) (IS_COMPILE_CONSTANT(_v) ? STATIC_ILOG_32(_v) : ilog32(_v)) +#endif /* builtin_ilog32_nz */ + +#ifdef builtin_ilog64_nz +#define ilog32(_v) ((_v) ? builtin_ilog32_nz(_v) : 0) +#define ilog64_nz(_v) builtin_ilog64_nz(_v) +#else +#define ilog64_nz(_v) ilog64(_v) +#define ilog64(_v) (IS_COMPILE_CONSTANT(_v) ? STATIC_ILOG_64(_v) : ilog64(_v)) +#endif /* builtin_ilog64_nz */ + +/* Macros for evaluating compile-time constant ilog. */ +# define STATIC_ILOG0(_v) (!!(_v)) +# define STATIC_ILOG1(_v) (((_v)&0x2)?2:STATIC_ILOG0(_v)) +# define STATIC_ILOG2(_v) (((_v)&0xC)?2+STATIC_ILOG1((_v)>>2):STATIC_ILOG1(_v)) +# define STATIC_ILOG3(_v) \ + (((_v)&0xF0)?4+STATIC_ILOG2((_v)>>4):STATIC_ILOG2(_v)) +# define STATIC_ILOG4(_v) \ + (((_v)&0xFF00)?8+STATIC_ILOG3((_v)>>8):STATIC_ILOG3(_v)) +# define STATIC_ILOG5(_v) \ + (((_v)&0xFFFF0000)?16+STATIC_ILOG4((_v)>>16):STATIC_ILOG4(_v)) +# define STATIC_ILOG6(_v) \ + (((_v)&0xFFFFFFFF00000000ULL)?32+STATIC_ILOG5((_v)>>32):STATIC_ILOG5(_v)) + +#endif /* _ilog_H */ diff --git a/ccan/ccan/likely/LICENSE b/ccan/ccan/likely/LICENSE new file mode 120000 index 0000000..b7951da --- /dev/null +++ b/ccan/ccan/likely/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0
\ No newline at end of file diff --git a/ccan/ccan/likely/likely.c b/ccan/ccan/likely/likely.c new file mode 100644 index 0000000..83e8d6f --- /dev/null +++ b/ccan/ccan/likely/likely.c @@ -0,0 +1,136 @@ +/* CC0 (Public domain) - see LICENSE file for details. */ +#ifdef CCAN_LIKELY_DEBUG +#include <ccan/likely/likely.h> +#include <ccan/hash/hash.h> +#include <ccan/htable/htable_type.h> +#include <stdlib.h> +#include <stdio.h> +struct trace { + const char *condstr; + const char *file; + unsigned int line; + bool expect; + unsigned long count, right; +}; + +static size_t hash_trace(const struct trace *trace) +{ + return hash(trace->condstr, strlen(trace->condstr), + hash(trace->file, strlen(trace->file), + trace->line + trace->expect)); +} + +static bool trace_eq(const struct trace *t1, const struct trace *t2) +{ + return t1->condstr == t2->condstr + && t1->file == t2->file + && t1->line == t2->line + && t1->expect == t2->expect; +} + +/* struct thash */ +HTABLE_DEFINE_TYPE(struct trace, (const struct trace *), hash_trace, trace_eq, + thash); + +static struct thash htable += { HTABLE_INITIALIZER(htable.raw, thash_hash, NULL) }; + +static void init_trace(struct trace *trace, + const char *condstr, const char *file, unsigned int line, + bool expect) +{ + trace->condstr = condstr; + trace->file = file; + trace->line = line; + trace->expect = expect; + trace->count = trace->right = 0; +} + +static struct trace *add_trace(const struct trace *t) +{ + struct trace *trace = malloc(sizeof(*trace)); + *trace = *t; + thash_add(&htable, trace); + return trace; +} + +long _likely_trace(bool cond, bool expect, + const char *condstr, + const char *file, unsigned int line) +{ + struct trace *p, trace; + + init_trace(&trace, condstr, file, line, expect); + p = thash_get(&htable, &trace); + if (!p) + p = add_trace(&trace); + + p->count++; + if (cond == expect) + p->right++; + + return cond; +} + +static double right_ratio(const struct trace *t) +{ + return (double)t->right / t->count; +} + +char *likely_stats(unsigned int min_hits, unsigned int percent) +{ + struct trace *worst; + double worst_ratio; + struct thash_iter i; + char *ret; + struct trace *t; + + worst = NULL; + worst_ratio = 2; + + /* This is O(n), but it's not likely called that often. */ + for (t = thash_first(&htable, &i); t; t = thash_next(&htable, &i)) { + if (t->count >= min_hits) { + if (right_ratio(t) < worst_ratio) { + worst = t; + worst_ratio = right_ratio(t); + } + } + } + + if (worst_ratio * 100 > percent) + return NULL; + + ret = malloc(strlen(worst->condstr) + + strlen(worst->file) + + sizeof(long int) * 8 + + sizeof("%s:%u:%slikely(%s) correct %u%% (%lu/%lu)")); + sprintf(ret, "%s:%u:%slikely(%s) correct %u%% (%lu/%lu)", + worst->file, worst->line, + worst->expect ? "" : "un", worst->condstr, + (unsigned)(worst_ratio * 100), + worst->right, worst->count); + + thash_del(&htable, worst); + free(worst); + + return ret; +} + +void likely_stats_reset(void) +{ + struct thash_iter i; + struct trace *t; + + /* This is a bit better than O(n^2), but we have to loop since + * first/next during delete is unreliable. */ + while ((t = thash_first(&htable, &i)) != NULL) { + for (; t; t = thash_next(&htable, &i)) { + thash_del(&htable, t); + free(t); + } + } + + thash_clear(&htable); +} +#endif /*CCAN_LIKELY_DEBUG*/ diff --git a/ccan/ccan/likely/likely.h b/ccan/ccan/likely/likely.h new file mode 100644 index 0000000..a8f003d --- /dev/null +++ b/ccan/ccan/likely/likely.h @@ -0,0 +1,111 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#ifndef CCAN_LIKELY_H +#define CCAN_LIKELY_H +#include "config.h" +#include <stdbool.h> + +#ifndef CCAN_LIKELY_DEBUG +#if HAVE_BUILTIN_EXPECT +/** + * likely - indicate that a condition is likely to be true. + * @cond: the condition + * + * This uses a compiler extension where available to indicate a likely + * code path and optimize appropriately; it's also useful for readers + * to quickly identify exceptional paths through functions. The + * threshold for "likely" is usually considered to be between 90 and + * 99%; marginal cases should not be marked either way. + * + * See Also: + * unlikely(), likely_stats() + * + * Example: + * // Returns false if we overflow. + * static inline bool inc_int(unsigned int *val) + * { + * (*val)++; + * if (likely(*val)) + * return true; + * return false; + * } + */ +#define likely(cond) __builtin_expect(!!(cond), 1) + +/** + * unlikely - indicate that a condition is unlikely to be true. + * @cond: the condition + * + * This uses a compiler extension where available to indicate an unlikely + * code path and optimize appropriately; see likely() above. + * + * See Also: + * likely(), likely_stats(), COLD (compiler.h) + * + * Example: + * // Prints a warning if we overflow. + * static inline void inc_int(unsigned int *val) + * { + * (*val)++; + * if (unlikely(*val == 0)) + * fprintf(stderr, "Overflow!"); + * } + */ +#define unlikely(cond) __builtin_expect(!!(cond), 0) +#else +#define likely(cond) (!!(cond)) +#define unlikely(cond) (!!(cond)) +#endif +#else /* CCAN_LIKELY_DEBUG versions */ +#include <ccan/str/str.h> + +#define likely(cond) \ + (_likely_trace(!!(cond), 1, stringify(cond), __FILE__, __LINE__)) +#define unlikely(cond) \ + (_likely_trace(!!(cond), 0, stringify(cond), __FILE__, __LINE__)) + +long _likely_trace(bool cond, bool expect, + const char *condstr, + const char *file, unsigned int line); +/** + * likely_stats - return description of abused likely()/unlikely() + * @min_hits: minimum number of hits + * @percent: maximum percentage correct + * + * When CCAN_LIKELY_DEBUG is defined, likely() and unlikely() trace their + * results: this causes a significant slowdown, but allows analysis of + * whether the branches are labelled correctly. + * + * This function returns a malloc'ed description of the least-correct + * usage of likely() or unlikely(). It ignores places which have been + * called less than @min_hits times, and those which were predicted + * correctly more than @percent of the time. It returns NULL when + * nothing meets those criteria. + * + * Note that this call is destructive; the returned offender is + * removed from the trace so that the next call to likely_stats() will + * return the next-worst likely()/unlikely() usage. + * + * Example: + * // Print every place hit more than twice which was wrong > 5%. + * static void report_stats(void) + * { + * #ifdef CCAN_LIKELY_DEBUG + * const char *bad; + * + * while ((bad = likely_stats(2, 95)) != NULL) { + * printf("Suspicious likely: %s", bad); + * free(bad); + * } + * #endif + * } + */ +char *likely_stats(unsigned int min_hits, unsigned int percent); + +/** + * likely_stats_reset - free up memory of likely()/unlikely() branches. + * + * This can also plug memory leaks. + */ +void likely_stats_reset(void); +#endif /* CCAN_LIKELY_DEBUG */ +#endif /* CCAN_LIKELY_H */ diff --git a/ccan/ccan/list/LICENSE b/ccan/ccan/list/LICENSE new file mode 120000 index 0000000..2354d12 --- /dev/null +++ b/ccan/ccan/list/LICENSE @@ -0,0 +1 @@ +../../licenses/BSD-MIT
\ No newline at end of file diff --git a/ccan/ccan/list/list.c b/ccan/ccan/list/list.c new file mode 100644 index 0000000..2717fa3 --- /dev/null +++ b/ccan/ccan/list/list.c @@ -0,0 +1,43 @@ +/* Licensed under BSD-MIT - see LICENSE file for details */ +#include <stdio.h> +#include <stdlib.h> +#include "list.h" + +static void *corrupt(const char *abortstr, + const struct list_node *head, + const struct list_node *node, + unsigned int count) +{ + if (abortstr) { + fprintf(stderr, + "%s: prev corrupt in node %p (%u) of %p\n", + abortstr, node, count, head); + abort(); + } + return NULL; +} + +struct list_node *list_check_node(const struct list_node *node, + const char *abortstr) +{ + const struct list_node *p, *n; + int count = 0; + + for (p = node, n = node->next; n != node; p = n, n = n->next) { + count++; + if (n->prev != p) + return corrupt(abortstr, node, n, count); + } + /* Check prev on head node. */ + if (node->prev != p) + return corrupt(abortstr, node, node, 0); + + return (struct list_node *)node; +} + +struct list_head *list_check(const struct list_head *h, const char *abortstr) +{ + if (!list_check_node(&h->n, abortstr)) + return NULL; + return (struct list_head *)h; +} diff --git a/ccan/ccan/list/list.h b/ccan/ccan/list/list.h new file mode 100644 index 0000000..a15321c --- /dev/null +++ b/ccan/ccan/list/list.h @@ -0,0 +1,842 @@ +/* Licensed under BSD-MIT - see LICENSE file for details */ +#ifndef CCAN_LIST_H +#define CCAN_LIST_H +//#define CCAN_LIST_DEBUG 1 +#include <stdbool.h> +#include <assert.h> +#include <ccan/str/str.h> +#include <ccan/container_of/container_of.h> +#include <ccan/check_type/check_type.h> + +/** + * struct list_node - an entry in a doubly-linked list + * @next: next entry (self if empty) + * @prev: previous entry (self if empty) + * + * This is used as an entry in a linked list. + * Example: + * struct child { + * const char *name; + * // Linked list of all us children. + * struct list_node list; + * }; + */ +struct list_node +{ + struct list_node *next, *prev; +}; + +/** + * struct list_head - the head of a doubly-linked list + * @h: the list_head (containing next and prev pointers) + * + * This is used as the head of a linked list. + * Example: + * struct parent { + * const char *name; + * struct list_head children; + * unsigned int num_children; + * }; + */ +struct list_head +{ + struct list_node n; +}; + +/** + * list_check - check head of a list for consistency + * @h: the list_head + * @abortstr: the location to print on aborting, or NULL. + * + * Because list_nodes have redundant information, consistency checking between + * the back and forward links can be done. This is useful as a debugging check. + * If @abortstr is non-NULL, that will be printed in a diagnostic if the list + * is inconsistent, and the function will abort. + * + * Returns the list head if the list is consistent, NULL if not (it + * can never return NULL if @abortstr is set). + * + * See also: list_check_node() + * + * Example: + * static void dump_parent(struct parent *p) + * { + * struct child *c; + * + * printf("%s (%u children):\n", p->name, p->num_children); + * list_check(&p->children, "bad child list"); + * list_for_each(&p->children, c, list) + * printf(" -> %s\n", c->name); + * } + */ +struct list_head *list_check(const struct list_head *h, const char *abortstr); + +/** + * list_check_node - check node of a list for consistency + * @n: the list_node + * @abortstr: the location to print on aborting, or NULL. + * + * Check consistency of the list node is in (it must be in one). + * + * See also: list_check() + * + * Example: + * static void dump_child(const struct child *c) + * { + * list_check_node(&c->list, "bad child list"); + * printf("%s\n", c->name); + * } + */ +struct list_node *list_check_node(const struct list_node *n, + const char *abortstr); + +#define LIST_LOC __FILE__ ":" stringify(__LINE__) +#ifdef CCAN_LIST_DEBUG +#define list_debug(h, loc) list_check((h), loc) +#define list_debug_node(n, loc) list_check_node((n), loc) +#else +#define list_debug(h, loc) ((void)loc, h) +#define list_debug_node(n, loc) ((void)loc, n) +#endif + +/** + * LIST_HEAD_INIT - initializer for an empty list_head + * @name: the name of the list. + * + * Explicit initializer for an empty list. + * + * See also: + * LIST_HEAD, list_head_init() + * + * Example: + * static struct list_head my_list = LIST_HEAD_INIT(my_list); + */ +#define LIST_HEAD_INIT(name) { { &(name).n, &(name).n } } + +/** + * LIST_HEAD - define and initialize an empty list_head + * @name: the name of the list. + * + * The LIST_HEAD macro defines a list_head and initializes it to an empty + * list. It can be prepended by "static" to define a static list_head. + * + * See also: + * LIST_HEAD_INIT, list_head_init() + * + * Example: + * static LIST_HEAD(my_global_list); + */ +#define LIST_HEAD(name) \ + struct list_head name = LIST_HEAD_INIT(name) + +/** + * list_head_init - initialize a list_head + * @h: the list_head to set to the empty list + * + * Example: + * ... + * struct parent *parent = malloc(sizeof(*parent)); + * + * list_head_init(&parent->children); + * parent->num_children = 0; + */ +static inline void list_head_init(struct list_head *h) +{ + h->n.next = h->n.prev = &h->n; +} + +/** + * list_node_init - initialize a list_node + * @n: the list_node to link to itself. + * + * You don't need to use this normally! But it lets you list_del(@n) + * safely. + */ +static inline void list_node_init(struct list_node *n) +{ + n->next = n->prev = n; +} + +/** + * list_add_after - add an entry after an existing node in a linked list + * @h: the list_head to add the node to (for debugging) + * @p: the existing list_node to add the node after + * @n: the new list_node to add to the list. + * + * The existing list_node must already be a member of the list. + * The new list_node does not need to be initialized; it will be overwritten. + * + * Example: + * struct child c1, c2, c3; + * LIST_HEAD(h); + * + * list_add_tail(&h, &c1.list); + * list_add_tail(&h, &c3.list); + * list_add_after(&h, &c1.list, &c2.list); + */ +#define list_add_after(h, p, n) list_add_after_(h, p, n, LIST_LOC) +static inline void list_add_after_(struct list_head *h, + struct list_node *p, + struct list_node *n, + const char *abortstr) +{ + n->next = p->next; + n->prev = p; + p->next->prev = n; + p->next = n; + (void)list_debug(h, abortstr); +} + +/** + * list_add - add an entry at the start of a linked list. + * @h: the list_head to add the node to + * @n: the list_node to add to the list. + * + * The list_node does not need to be initialized; it will be overwritten. + * Example: + * struct child *child = malloc(sizeof(*child)); + * + * child->name = "marvin"; + * list_add(&parent->children, &child->list); + * parent->num_children++; + */ +#define list_add(h, n) list_add_(h, n, LIST_LOC) +static inline void list_add_(struct list_head *h, + struct list_node *n, + const char *abortstr) +{ + list_add_after_(h, &h->n, n, abortstr); +} + +/** + * list_add_before - add an entry before an existing node in a linked list + * @h: the list_head to add the node to (for debugging) + * @p: the existing list_node to add the node before + * @n: the new list_node to add to the list. + * + * The existing list_node must already be a member of the list. + * The new list_node does not need to be initialized; it will be overwritten. + * + * Example: + * list_head_init(&h); + * list_add_tail(&h, &c1.list); + * list_add_tail(&h, &c3.list); + * list_add_before(&h, &c3.list, &c2.list); + */ +#define list_add_before(h, p, n) list_add_before_(h, p, n, LIST_LOC) +static inline void list_add_before_(struct list_head *h, + struct list_node *p, + struct list_node *n, + const char *abortstr) +{ + n->next = p; + n->prev = p->prev; + p->prev->next = n; + p->prev = n; + (void)list_debug(h, abortstr); +} + +/** + * list_add_tail - add an entry at the end of a linked list. + * @h: the list_head to add the node to + * @n: the list_node to add to the list. + * + * The list_node does not need to be initialized; it will be overwritten. + * Example: + * list_add_tail(&parent->children, &child->list); + * parent->num_children++; + */ +#define list_add_tail(h, n) list_add_tail_(h, n, LIST_LOC) +static inline void list_add_tail_(struct list_head *h, + struct list_node *n, + const char *abortstr) +{ + list_add_before_(h, &h->n, n, abortstr); +} + +/** + * list_empty - is a list empty? + * @h: the list_head + * + * If the list is empty, returns true. + * + * Example: + * assert(list_empty(&parent->children) == (parent->num_children == 0)); + */ +#define list_empty(h) list_empty_(h, LIST_LOC) +static inline bool list_empty_(const struct list_head *h, const char* abortstr) +{ + (void)list_debug(h, abortstr); + return h->n.next == &h->n; +} + +/** + * list_empty_nodebug - is a list empty (and don't perform debug checks)? + * @h: the list_head + * + * If the list is empty, returns true. + * This differs from list_empty() in that if CCAN_LIST_DEBUG is set it + * will NOT perform debug checks. Only use this function if you REALLY + * know what you're doing. + * + * Example: + * assert(list_empty_nodebug(&parent->children) == (parent->num_children == 0)); + */ +#ifndef CCAN_LIST_DEBUG +#define list_empty_nodebug(h) list_empty(h) +#else +static inline bool list_empty_nodebug(const struct list_head *h) +{ + return h->n.next == &h->n; +} +#endif + +/** + * list_empty_nocheck - is a list empty? + * @h: the list_head + * + * If the list is empty, returns true. This doesn't perform any + * debug check for list consistency, so it can be called without + * locks, racing with the list being modified. This is ok for + * checks where an incorrect result is not an issue (optimized + * bail out path for example). + */ +static inline bool list_empty_nocheck(const struct list_head *h) +{ + return h->n.next == &h->n; +} + +/** + * list_del - delete an entry from an (unknown) linked list. + * @n: the list_node to delete from the list. + * + * Note that this leaves @n in an undefined state; it can be added to + * another list, but not deleted again. + * + * See also: + * list_del_from(), list_del_init() + * + * Example: + * list_del(&child->list); + * parent->num_children--; + */ +#define list_del(n) list_del_(n, LIST_LOC) +static inline void list_del_(struct list_node *n, const char* abortstr) +{ + (void)list_debug_node(n, abortstr); + n->next->prev = n->prev; + n->prev->next = n->next; +#ifdef CCAN_LIST_DEBUG + /* Catch use-after-del. */ + n->next = n->prev = NULL; +#endif +} + +/** + * list_del_init - delete a node, and reset it so it can be deleted again. + * @n: the list_node to be deleted. + * + * list_del(@n) or list_del_init() again after this will be safe, + * which can be useful in some cases. + * + * See also: + * list_del_from(), list_del() + * + * Example: + * list_del_init(&child->list); + * parent->num_children--; + */ +#define list_del_init(n) list_del_init_(n, LIST_LOC) +static inline void list_del_init_(struct list_node *n, const char *abortstr) +{ + list_del_(n, abortstr); + list_node_init(n); +} + +/** + * list_del_from - delete an entry from a known linked list. + * @h: the list_head the node is in. + * @n: the list_node to delete from the list. + * + * This explicitly indicates which list a node is expected to be in, + * which is better documentation and can catch more bugs. + * + * See also: list_del() + * + * Example: + * list_del_from(&parent->children, &child->list); + * parent->num_children--; + */ +static inline void list_del_from(struct list_head *h, struct list_node *n) +{ +#ifdef CCAN_LIST_DEBUG + { + /* Thorough check: make sure it was in list! */ + struct list_node *i; + for (i = h->n.next; i != n; i = i->next) + assert(i != &h->n); + } +#endif /* CCAN_LIST_DEBUG */ + + /* Quick test that catches a surprising number of bugs. */ + assert(!list_empty(h)); + list_del(n); +} + +/** + * list_swap - swap out an entry from an (unknown) linked list for a new one. + * @o: the list_node to replace from the list. + * @n: the list_node to insert in place of the old one. + * + * Note that this leaves @o in an undefined state; it can be added to + * another list, but not deleted/swapped again. + * + * See also: + * list_del() + * + * Example: + * struct child x1, x2; + * LIST_HEAD(xh); + * + * list_add(&xh, &x1.list); + * list_swap(&x1.list, &x2.list); + */ +#define list_swap(o, n) list_swap_(o, n, LIST_LOC) +static inline void list_swap_(struct list_node *o, + struct list_node *n, + const char* abortstr) +{ + (void)list_debug_node(o, abortstr); + *n = *o; + n->next->prev = n; + n->prev->next = n; +#ifdef CCAN_LIST_DEBUG + /* Catch use-after-del. */ + o->next = o->prev = NULL; +#endif +} + +/** + * list_entry - convert a list_node back into the structure containing it. + * @n: the list_node + * @type: the type of the entry + * @member: the list_node member of the type + * + * Example: + * // First list entry is children.next; convert back to child. + * child = list_entry(parent->children.n.next, struct child, list); + * + * See Also: + * list_top(), list_for_each() + */ +#define list_entry(n, type, member) container_of(n, type, member) + +/** + * list_top - get the first entry in a list + * @h: the list_head + * @type: the type of the entry + * @member: the list_node member of the type + * + * If the list is empty, returns NULL. + * + * Example: + * struct child *first; + * first = list_top(&parent->children, struct child, list); + * if (!first) + * printf("Empty list!\n"); + */ +#define list_top(h, type, member) \ + ((type *)list_top_((h), list_off_(type, member))) + +static inline const void *list_top_(const struct list_head *h, size_t off) +{ + if (list_empty(h)) + return NULL; + return (const char *)h->n.next - off; +} + +/** + * list_pop - remove the first entry in a list + * @h: the list_head + * @type: the type of the entry + * @member: the list_node member of the type + * + * If the list is empty, returns NULL. + * + * Example: + * struct child *one; + * one = list_pop(&parent->children, struct child, list); + * if (!one) + * printf("Empty list!\n"); + */ +#define list_pop(h, type, member) \ + ((type *)list_pop_((h), list_off_(type, member))) + +static inline const void *list_pop_(const struct list_head *h, size_t off) +{ + struct list_node *n; + + if (list_empty(h)) + return NULL; + n = h->n.next; + list_del(n); + return (const char *)n - off; +} + +/** + * list_tail - get the last entry in a list + * @h: the list_head + * @type: the type of the entry + * @member: the list_node member of the type + * + * If the list is empty, returns NULL. + * + * Example: + * struct child *last; + * last = list_tail(&parent->children, struct child, list); + * if (!last) + * printf("Empty list!\n"); + */ +#define list_tail(h, type, member) \ + ((type *)list_tail_((h), list_off_(type, member))) + +static inline const void *list_tail_(const struct list_head *h, size_t off) +{ + if (list_empty(h)) + return NULL; + return (const char *)h->n.prev - off; +} + +/** + * list_for_each - iterate through a list. + * @h: the list_head (warning: evaluated multiple times!) + * @i: the structure containing the list_node + * @member: the list_node member of the structure + * + * This is a convenient wrapper to iterate @i over the entire list. It's + * a for loop, so you can break and continue as normal. + * + * Example: + * list_for_each(&parent->children, child, list) + * printf("Name: %s\n", child->name); + */ +#define list_for_each(h, i, member) \ + list_for_each_off(h, i, list_off_var_(i, member)) + +/** + * list_for_each_rev - iterate through a list backwards. + * @h: the list_head + * @i: the structure containing the list_node + * @member: the list_node member of the structure + * + * This is a convenient wrapper to iterate @i over the entire list. It's + * a for loop, so you can break and continue as normal. + * + * Example: + * list_for_each_rev(&parent->children, child, list) + * printf("Name: %s\n", child->name); + */ +#define list_for_each_rev(h, i, member) \ + list_for_each_rev_off(h, i, list_off_var_(i, member)) + +/** + * list_for_each_rev_safe - iterate through a list backwards, + * maybe during deletion + * @h: the list_head + * @i: the structure containing the list_node + * @nxt: the structure containing the list_node + * @member: the list_node member of the structure + * + * This is a convenient wrapper to iterate @i over the entire list backwards. + * It's a for loop, so you can break and continue as normal. The extra + * variable * @nxt is used to hold the next element, so you can delete @i + * from the list. + * + * Example: + * struct child *next; + * list_for_each_rev_safe(&parent->children, child, next, list) { + * printf("Name: %s\n", child->name); + * } + */ +#define list_for_each_rev_safe(h, i, nxt, member) \ + list_for_each_rev_safe_off(h, i, nxt, list_off_var_(i, member)) + +/** + * list_for_each_safe - iterate through a list, maybe during deletion + * @h: the list_head + * @i: the structure containing the list_node + * @nxt: the structure containing the list_node + * @member: the list_node member of the structure + * + * This is a convenient wrapper to iterate @i over the entire list. It's + * a for loop, so you can break and continue as normal. The extra variable + * @nxt is used to hold the next element, so you can delete @i from the list. + * + * Example: + * list_for_each_safe(&parent->children, child, next, list) { + * list_del(&child->list); + * parent->num_children--; + * } + */ +#define list_for_each_safe(h, i, nxt, member) \ + list_for_each_safe_off(h, i, nxt, list_off_var_(i, member)) + +/** + * list_next - get the next entry in a list + * @h: the list_head + * @i: a pointer to an entry in the list. + * @member: the list_node member of the structure + * + * If @i was the last entry in the list, returns NULL. + * + * Example: + * struct child *second; + * second = list_next(&parent->children, first, list); + * if (!second) + * printf("No second child!\n"); + */ +#define list_next(h, i, member) \ + ((list_typeof(i))list_entry_or_null(list_debug(h, \ + __FILE__ ":" stringify(__LINE__)), \ + (i)->member.next, \ + list_off_var_((i), member))) + +/** + * list_prev - get the previous entry in a list + * @h: the list_head + * @i: a pointer to an entry in the list. + * @member: the list_node member of the structure + * + * If @i was the first entry in the list, returns NULL. + * + * Example: + * first = list_prev(&parent->children, second, list); + * if (!first) + * printf("Can't go back to first child?!\n"); + */ +#define list_prev(h, i, member) \ + ((list_typeof(i))list_entry_or_null(list_debug(h, \ + __FILE__ ":" stringify(__LINE__)), \ + (i)->member.prev, \ + list_off_var_((i), member))) + +/** + * list_append_list - empty one list onto the end of another. + * @to: the list to append into + * @from: the list to empty. + * + * This takes the entire contents of @from and moves it to the end of + * @to. After this @from will be empty. + * + * Example: + * struct list_head adopter; + * + * list_append_list(&adopter, &parent->children); + * assert(list_empty(&parent->children)); + * parent->num_children = 0; + */ +#define list_append_list(t, f) list_append_list_(t, f, \ + __FILE__ ":" stringify(__LINE__)) +static inline void list_append_list_(struct list_head *to, + struct list_head *from, + const char *abortstr) +{ + struct list_node *from_tail = list_debug(from, abortstr)->n.prev; + struct list_node *to_tail = list_debug(to, abortstr)->n.prev; + + /* Sew in head and entire list. */ + to->n.prev = from_tail; + from_tail->next = &to->n; + to_tail->next = &from->n; + from->n.prev = to_tail; + + /* Now remove head. */ + list_del(&from->n); + list_head_init(from); +} + +/** + * list_prepend_list - empty one list into the start of another. + * @to: the list to prepend into + * @from: the list to empty. + * + * This takes the entire contents of @from and moves it to the start + * of @to. After this @from will be empty. + * + * Example: + * list_prepend_list(&adopter, &parent->children); + * assert(list_empty(&parent->children)); + * parent->num_children = 0; + */ +#define list_prepend_list(t, f) list_prepend_list_(t, f, LIST_LOC) +static inline void list_prepend_list_(struct list_head *to, + struct list_head *from, + const char *abortstr) +{ + struct list_node *from_tail = list_debug(from, abortstr)->n.prev; + struct list_node *to_head = list_debug(to, abortstr)->n.next; + + /* Sew in head and entire list. */ + to->n.next = &from->n; + from->n.prev = &to->n; + to_head->prev = from_tail; + from_tail->next = to_head; + + /* Now remove head. */ + list_del(&from->n); + list_head_init(from); +} + +/* internal macros, do not use directly */ +#define list_for_each_off_dir_(h, i, off, dir) \ + for (i = list_node_to_off_(list_debug(h, LIST_LOC)->n.dir, \ + (off)); \ + list_node_from_off_((void *)i, (off)) != &(h)->n; \ + i = list_node_to_off_(list_node_from_off_((void *)i, (off))->dir, \ + (off))) + +#define list_for_each_safe_off_dir_(h, i, nxt, off, dir) \ + for (i = list_node_to_off_(list_debug(h, LIST_LOC)->n.dir, \ + (off)), \ + nxt = list_node_to_off_(list_node_from_off_(i, (off))->dir, \ + (off)); \ + list_node_from_off_(i, (off)) != &(h)->n; \ + i = nxt, \ + nxt = list_node_to_off_(list_node_from_off_(i, (off))->dir, \ + (off))) + +/** + * list_for_each_off - iterate through a list of memory regions. + * @h: the list_head + * @i: the pointer to a memory region which contains list node data. + * @off: offset(relative to @i) at which list node data resides. + * + * This is a low-level wrapper to iterate @i over the entire list, used to + * implement all oher, more high-level, for-each constructs. It's a for loop, + * so you can break and continue as normal. + * + * WARNING! Being the low-level macro that it is, this wrapper doesn't know + * nor care about the type of @i. The only assumption made is that @i points + * to a chunk of memory that at some @offset, relative to @i, contains a + * properly filled `struct list_node' which in turn contains pointers to + * memory chunks and it's turtles all the way down. With all that in mind + * remember that given the wrong pointer/offset couple this macro will + * happily churn all you memory until SEGFAULT stops it, in other words + * caveat emptor. + * + * It is worth mentioning that one of legitimate use-cases for that wrapper + * is operation on opaque types with known offset for `struct list_node' + * member(preferably 0), because it allows you not to disclose the type of + * @i. + * + * Example: + * list_for_each_off(&parent->children, child, + * offsetof(struct child, list)) + * printf("Name: %s\n", child->name); + */ +#define list_for_each_off(h, i, off) \ + list_for_each_off_dir_((h),(i),(off),next) + +/** + * list_for_each_rev_off - iterate through a list of memory regions backwards + * @h: the list_head + * @i: the pointer to a memory region which contains list node data. + * @off: offset(relative to @i) at which list node data resides. + * + * See list_for_each_off for details + */ +#define list_for_each_rev_off(h, i, off) \ + list_for_each_off_dir_((h),(i),(off),prev) + +/** + * list_for_each_safe_off - iterate through a list of memory regions, maybe + * during deletion + * @h: the list_head + * @i: the pointer to a memory region which contains list node data. + * @nxt: the structure containing the list_node + * @off: offset(relative to @i) at which list node data resides. + * + * For details see `list_for_each_off' and `list_for_each_safe' + * descriptions. + * + * Example: + * list_for_each_safe_off(&parent->children, child, + * next, offsetof(struct child, list)) + * printf("Name: %s\n", child->name); + */ +#define list_for_each_safe_off(h, i, nxt, off) \ + list_for_each_safe_off_dir_((h),(i),(nxt),(off),next) + +/** + * list_for_each_rev_safe_off - iterate backwards through a list of + * memory regions, maybe during deletion + * @h: the list_head + * @i: the pointer to a memory region which contains list node data. + * @nxt: the structure containing the list_node + * @off: offset(relative to @i) at which list node data resides. + * + * For details see `list_for_each_rev_off' and `list_for_each_rev_safe' + * descriptions. + * + * Example: + * list_for_each_rev_safe_off(&parent->children, child, + * next, offsetof(struct child, list)) + * printf("Name: %s\n", child->name); + */ +#define list_for_each_rev_safe_off(h, i, nxt, off) \ + list_for_each_safe_off_dir_((h),(i),(nxt),(off),prev) + +/* Other -off variants. */ +#define list_entry_off(n, type, off) \ + ((type *)list_node_from_off_((n), (off))) + +#define list_head_off(h, type, off) \ + ((type *)list_head_off((h), (off))) + +#define list_tail_off(h, type, off) \ + ((type *)list_tail_((h), (off))) + +#define list_add_off(h, n, off) \ + list_add((h), list_node_from_off_((n), (off))) + +#define list_del_off(n, off) \ + list_del(list_node_from_off_((n), (off))) + +#define list_del_from_off(h, n, off) \ + list_del_from(h, list_node_from_off_((n), (off))) + +/* Offset helper functions so we only single-evaluate. */ +static inline void *list_node_to_off_(struct list_node *node, size_t off) +{ + return (void *)((char *)node - off); +} +static inline struct list_node *list_node_from_off_(void *ptr, size_t off) +{ + return (struct list_node *)((char *)ptr + off); +} + +/* Get the offset of the member, but make sure it's a list_node. */ +#define list_off_(type, member) \ + (container_off(type, member) + \ + check_type(((type *)0)->member, struct list_node)) + +#define list_off_var_(var, member) \ + (container_off_var(var, member) + \ + check_type(var->member, struct list_node)) + +#if HAVE_TYPEOF +#define list_typeof(var) typeof(var) +#else +#define list_typeof(var) void * +#endif + +/* Returns member, or NULL if at end of list. */ +static inline void *list_entry_or_null(const struct list_head *h, + const struct list_node *n, + size_t off) +{ + if (n == &h->n) + return NULL; + return (char *)n - off; +} +#endif /* CCAN_LIST_H */ diff --git a/ccan/ccan/short_types/LICENSE b/ccan/ccan/short_types/LICENSE new file mode 120000 index 0000000..b7951da --- /dev/null +++ b/ccan/ccan/short_types/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0
\ No newline at end of file diff --git a/ccan/ccan/short_types/short_types.h b/ccan/ccan/short_types/short_types.h new file mode 100644 index 0000000..175377e --- /dev/null +++ b/ccan/ccan/short_types/short_types.h @@ -0,0 +1,35 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#ifndef CCAN_SHORT_TYPES_H +#define CCAN_SHORT_TYPES_H +#include <stdint.h> + +/** + * u64/s64/u32/s32/u16/s16/u8/s8 - short names for explicitly-sized types. + */ +typedef uint64_t u64; +typedef int64_t s64; +typedef uint32_t u32; +typedef int32_t s32; +typedef uint16_t u16; +typedef int16_t s16; +typedef uint8_t u8; +typedef int8_t s8; + +/* Whichever they include first, they get these definitions. */ +#ifdef CCAN_ENDIAN_H +/** + * be64/be32/be16 - 64/32/16 bit big-endian representation. + */ +typedef beint64_t be64; +typedef beint32_t be32; +typedef beint16_t be16; + +/** + * le64/le32/le16 - 64/32/16 bit little-endian representation. + */ +typedef leint64_t le64; +typedef leint32_t le32; +typedef leint16_t le16; +#endif + +#endif /* CCAN_SHORT_TYPES_H */ diff --git a/ccan/ccan/str/LICENSE b/ccan/ccan/str/LICENSE new file mode 120000 index 0000000..b7951da --- /dev/null +++ b/ccan/ccan/str/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0
\ No newline at end of file diff --git a/ccan/ccan/str/debug.c b/ccan/ccan/str/debug.c new file mode 100644 index 0000000..8c51944 --- /dev/null +++ b/ccan/ccan/str/debug.c @@ -0,0 +1,108 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#include "config.h" +#include <ccan/str/str_debug.h> +#include <assert.h> +#include <ctype.h> +#include <string.h> + +#ifdef CCAN_STR_DEBUG +/* Because we mug the real ones with macros, we need our own wrappers. */ +int str_isalnum(int i) +{ + assert(i >= -1 && i < 256); + return isalnum(i); +} + +int str_isalpha(int i) +{ + assert(i >= -1 && i < 256); + return isalpha(i); +} + +int str_isascii(int i) +{ + assert(i >= -1 && i < 256); + return isascii(i); +} + +#if HAVE_ISBLANK +int str_isblank(int i) +{ + assert(i >= -1 && i < 256); + return isblank(i); +} +#endif + +int str_iscntrl(int i) +{ + assert(i >= -1 && i < 256); + return iscntrl(i); +} + +int str_isdigit(int i) +{ + assert(i >= -1 && i < 256); + return isdigit(i); +} + +int str_isgraph(int i) +{ + assert(i >= -1 && i < 256); + return isgraph(i); +} + +int str_islower(int i) +{ + assert(i >= -1 && i < 256); + return islower(i); +} + +int str_isprint(int i) +{ + assert(i >= -1 && i < 256); + return isprint(i); +} + +int str_ispunct(int i) +{ + assert(i >= -1 && i < 256); + return ispunct(i); +} + +int str_isspace(int i) +{ + assert(i >= -1 && i < 256); + return isspace(i); +} + +int str_isupper(int i) +{ + assert(i >= -1 && i < 256); + return isupper(i); +} + +int str_isxdigit(int i) +{ + assert(i >= -1 && i < 256); + return isxdigit(i); +} + +#undef strstr +#undef strchr +#undef strrchr + +char *str_strstr(const char *haystack, const char *needle) +{ + return strstr(haystack, needle); +} + +char *str_strchr(const char *haystack, int c) +{ + return strchr(haystack, c); +} + +char *str_strrchr(const char *haystack, int c) +{ + return strrchr(haystack, c); +} +#endif diff --git a/ccan/ccan/str/str.c b/ccan/ccan/str/str.c new file mode 100644 index 0000000..a9245c1 --- /dev/null +++ b/ccan/ccan/str/str.c @@ -0,0 +1,13 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#include <ccan/str/str.h> + +size_t strcount(const char *haystack, const char *needle) +{ + size_t i = 0, nlen = strlen(needle); + + while ((haystack = strstr(haystack, needle)) != NULL) { + i++; + haystack += nlen; + } + return i; +} diff --git a/ccan/ccan/str/str.h b/ccan/ccan/str/str.h new file mode 100644 index 0000000..d919b84 --- /dev/null +++ b/ccan/ccan/str/str.h @@ -0,0 +1,228 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#ifndef CCAN_STR_H +#define CCAN_STR_H +#include "config.h" +#include <string.h> +#include <stdbool.h> +#include <limits.h> +#include <ctype.h> + +/** + * streq - Are two strings equal? + * @a: first string + * @b: first string + * + * This macro is arguably more readable than "!strcmp(a, b)". + * + * Example: + * if (streq(somestring, "")) + * printf("String is empty!\n"); + */ +#define streq(a,b) (strcmp((a),(b)) == 0) + +/** + * strstarts - Does this string start with this prefix? + * @str: string to test + * @prefix: prefix to look for at start of str + * + * Example: + * if (strstarts(somestring, "foo")) + * printf("String %s begins with 'foo'!\n", somestring); + */ +#define strstarts(str,prefix) (strncmp((str),(prefix),strlen(prefix)) == 0) + +/** + * strends - Does this string end with this postfix? + * @str: string to test + * @postfix: postfix to look for at end of str + * + * Example: + * if (strends(somestring, "foo")) + * printf("String %s end with 'foo'!\n", somestring); + */ +static inline bool strends(const char *str, const char *postfix) +{ + if (strlen(str) < strlen(postfix)) + return false; + + return streq(str + strlen(str) - strlen(postfix), postfix); +} + +/** + * stringify - Turn expression into a string literal + * @expr: any C expression + * + * Example: + * #define PRINT_COND_IF_FALSE(cond) \ + * ((cond) || printf("%s is false!", stringify(cond))) + */ +#define stringify(expr) stringify_1(expr) +/* Double-indirection required to stringify expansions */ +#define stringify_1(expr) #expr + +/** + * strcount - Count number of (non-overlapping) occurrences of a substring. + * @haystack: a C string + * @needle: a substring + * + * Example: + * assert(strcount("aaa aaa", "a") == 6); + * assert(strcount("aaa aaa", "ab") == 0); + * assert(strcount("aaa aaa", "aa") == 2); + */ +size_t strcount(const char *haystack, const char *needle); + +/** + * STR_MAX_CHARS - Maximum possible size of numeric string for this type. + * @type_or_expr: a pointer or integer type or expression. + * + * This provides enough space for a nul-terminated string which represents the + * largest possible value for the type or expression. + * + * Note: The implementation adds extra space so hex values or negative + * values will fit (eg. sprintf(... "%p"). ) + * + * Example: + * char str[STR_MAX_CHARS(int)]; + * + * sprintf(str, "%i", 7); + */ +#define STR_MAX_CHARS(type_or_expr) \ + ((sizeof(type_or_expr) * CHAR_BIT + 8) / 9 * 3 + 2 \ + + STR_MAX_CHARS_TCHECK_(type_or_expr)) + +#if HAVE_TYPEOF +/* Only a simple type can have 0 assigned, so test that. */ +#define STR_MAX_CHARS_TCHECK_(type_or_expr) \ + (sizeof(({ typeof(type_or_expr) x = 0; x; }))*0) +#else +#define STR_MAX_CHARS_TCHECK_(type_or_expr) 0 +#endif + +/** + * cisalnum - isalnum() which takes a char (and doesn't accept EOF) + * @c: a character + * + * Surprisingly, the standard ctype.h isalnum() takes an int, which + * must have the value of EOF (-1) or an unsigned char. This variant + * takes a real char, and doesn't accept EOF. + */ +static inline bool cisalnum(char c) +{ + return isalnum((unsigned char)c); +} +static inline bool cisalpha(char c) +{ + return isalpha((unsigned char)c); +} +static inline bool cisascii(char c) +{ + return isascii((unsigned char)c); +} +#if HAVE_ISBLANK +static inline bool cisblank(char c) +{ + return isblank((unsigned char)c); +} +#endif +static inline bool ciscntrl(char c) +{ + return iscntrl((unsigned char)c); +} +static inline bool cisdigit(char c) +{ + return isdigit((unsigned char)c); +} +static inline bool cisgraph(char c) +{ + return isgraph((unsigned char)c); +} +static inline bool cislower(char c) +{ + return islower((unsigned char)c); +} +static inline bool cisprint(char c) +{ + return isprint((unsigned char)c); +} +static inline bool cispunct(char c) +{ + return ispunct((unsigned char)c); +} +static inline bool cisspace(char c) +{ + return isspace((unsigned char)c); +} +static inline bool cisupper(char c) +{ + return isupper((unsigned char)c); +} +static inline bool cisxdigit(char c) +{ + return isxdigit((unsigned char)c); +} + +#include <ccan/str/str_debug.h> + +/* These checks force things out of line, hence they are under DEBUG. */ +#ifdef CCAN_STR_DEBUG +#include <ccan/build_assert/build_assert.h> + +/* These are commonly misused: they take -1 or an *unsigned* char value. */ +#undef isalnum +#undef isalpha +#undef isascii +#undef isblank +#undef iscntrl +#undef isdigit +#undef isgraph +#undef islower +#undef isprint +#undef ispunct +#undef isspace +#undef isupper +#undef isxdigit + +/* You can use a char if char is unsigned. */ +#if HAVE_BUILTIN_TYPES_COMPATIBLE_P && HAVE_TYPEOF +#define str_check_arg_(i) \ + ((i) + BUILD_ASSERT_OR_ZERO(!__builtin_types_compatible_p(typeof(i), \ + char) \ + || (char)255 > 0)) +#else +#define str_check_arg_(i) (i) +#endif + +#define isalnum(i) str_isalnum(str_check_arg_(i)) +#define isalpha(i) str_isalpha(str_check_arg_(i)) +#define isascii(i) str_isascii(str_check_arg_(i)) +#if HAVE_ISBLANK +#define isblank(i) str_isblank(str_check_arg_(i)) +#endif +#define iscntrl(i) str_iscntrl(str_check_arg_(i)) +#define isdigit(i) str_isdigit(str_check_arg_(i)) +#define isgraph(i) str_isgraph(str_check_arg_(i)) +#define islower(i) str_islower(str_check_arg_(i)) +#define isprint(i) str_isprint(str_check_arg_(i)) +#define ispunct(i) str_ispunct(str_check_arg_(i)) +#define isspace(i) str_isspace(str_check_arg_(i)) +#define isupper(i) str_isupper(str_check_arg_(i)) +#define isxdigit(i) str_isxdigit(str_check_arg_(i)) + +#if HAVE_TYPEOF +/* With GNU magic, we can make const-respecting standard string functions. */ +#undef strstr +#undef strchr +#undef strrchr + +/* + 0 is needed to decay array into pointer. */ +#define strstr(haystack, needle) \ + ((typeof((haystack) + 0))str_strstr((haystack), (needle))) +#define strchr(haystack, c) \ + ((typeof((haystack) + 0))str_strchr((haystack), (c))) +#define strrchr(haystack, c) \ + ((typeof((haystack) + 0))str_strrchr((haystack), (c))) +#endif +#endif /* CCAN_STR_DEBUG */ + +#endif /* CCAN_STR_H */ diff --git a/ccan/ccan/str/str_debug.h b/ccan/ccan/str/str_debug.h new file mode 100644 index 0000000..92c10c4 --- /dev/null +++ b/ccan/ccan/str/str_debug.h @@ -0,0 +1,30 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#ifndef CCAN_STR_DEBUG_H +#define CCAN_STR_DEBUG_H + +/* #define CCAN_STR_DEBUG 1 */ + +#ifdef CCAN_STR_DEBUG +/* Because we mug the real ones with macros, we need our own wrappers. */ +int str_isalnum(int i); +int str_isalpha(int i); +int str_isascii(int i); +#if HAVE_ISBLANK +int str_isblank(int i); +#endif +int str_iscntrl(int i); +int str_isdigit(int i); +int str_isgraph(int i); +int str_islower(int i); +int str_isprint(int i); +int str_ispunct(int i); +int str_isspace(int i); +int str_isupper(int i); +int str_isxdigit(int i); + +char *str_strstr(const char *haystack, const char *needle); +char *str_strchr(const char *s, int c); +char *str_strrchr(const char *s, int c); +#endif /* CCAN_STR_DEBUG */ + +#endif /* CCAN_STR_DEBUG_H */ diff --git a/ccan/ccan/strset/strset.c b/ccan/ccan/strset/strset.c new file mode 100644 index 0000000..06b0d7a --- /dev/null +++ b/ccan/ccan/strset/strset.c @@ -0,0 +1,309 @@ +/* This code is based on the public domain code at + * http://github.com/agl/critbit writtem by Adam Langley + * <agl@imperialviolet.org>. + * + * Here are the main implementation differences: + * (1) We don't strdup the string on insert; we use the pointer we're given. + * (2) We use a straight bit number rather than a mask; it's simpler. + * (3) We don't use the bottom bit of the pointer, but instead use a leading + * zero to distinguish nodes from strings. + * (4) The empty string (which would look like a node) is handled + * using a special "empty node". + * (5) Delete returns the string, so you can free it if you want to. + * (6) Unions instead of void *, bool instead of int. + */ +#include <ccan/strset/strset.h> +#include <ccan/short_types/short_types.h> +#include <ccan/likely/likely.h> +#include <ccan/str/str.h> +#include <ccan/ilog/ilog.h> +#include <assert.h> +#include <stdlib.h> +#include <errno.h> + +struct node { + /* To differentiate us from strings. */ + char nul_byte; + /* The bit where these children differ. */ + u8 bit_num; + /* The byte number where first bit differs (-1 == empty string node). */ + size_t byte_num; + /* These point to strings or nodes. */ + struct strset child[2]; +}; + +/* Closest member to this in a non-empty set. */ +static const char *closest(struct strset n, const char *member) +{ + size_t len = strlen(member); + const u8 *bytes = (const u8 *)member; + + /* Anything with first byte 0 is a node. */ + while (!n.u.s[0]) { + u8 direction = 0; + + /* Special node which represents the empty string. */ + if (unlikely(n.u.n->byte_num == (size_t)-1)) { + n = n.u.n->child[0]; + break; + } + + if (n.u.n->byte_num < len) { + u8 c = bytes[n.u.n->byte_num]; + direction = (c >> n.u.n->bit_num) & 1; + } + n = n.u.n->child[direction]; + } + return n.u.s; +} + +char *strset_get(const struct strset *set, const char *member) +{ + const char *str; + + /* Non-empty set? */ + if (set->u.n) { + str = closest(*set, member); + if (streq(member, str)) + return (char *)str; + } + errno = ENOENT; + return NULL; +} + +static bool set_string(struct strset *set, + struct strset *n, const char *member) +{ + /* Substitute magic empty node if this is the empty string */ + if (unlikely(!member[0])) { + n->u.n = malloc(sizeof(*n->u.n)); + if (unlikely(!n->u.n)) { + errno = ENOMEM; + return false; + } + n->u.n->nul_byte = '\0'; + n->u.n->byte_num = (size_t)-1; + /* Attach the string to child[0] */ + n = &n->u.n->child[0]; + } + n->u.s = member; + return true; +} + +bool strset_add(struct strset *set, const char *member) +{ + size_t len = strlen(member); + const u8 *bytes = (const u8 *)member; + struct strset *np; + const char *str; + struct node *newn; + size_t byte_num; + u8 bit_num, new_dir; + + /* Empty set? */ + if (!set->u.n) { + return set_string(set, set, member); + } + + /* Find closest existing member. */ + str = closest(*set, member); + + /* Find where they differ. */ + for (byte_num = 0; str[byte_num] == member[byte_num]; byte_num++) { + if (member[byte_num] == '\0') { + /* All identical! */ + errno = EEXIST; + return false; + } + } + + /* Find which bit differs (if we had ilog8, we'd use it) */ + bit_num = ilog32_nz((u8)str[byte_num] ^ bytes[byte_num]) - 1; + assert(bit_num < CHAR_BIT); + + /* Which direction do we go at this bit? */ + new_dir = ((bytes[byte_num]) >> bit_num) & 1; + + /* Allocate new node. */ + newn = malloc(sizeof(*newn)); + if (!newn) { + errno = ENOMEM; + return false; + } + newn->nul_byte = '\0'; + newn->byte_num = byte_num; + newn->bit_num = bit_num; + if (unlikely(!set_string(set, &newn->child[new_dir], member))) { + free(newn); + return false; + } + + /* Find where to insert: not closest, but first which differs! */ + np = set; + while (!np->u.s[0]) { + u8 direction = 0; + + /* Special node which represents the empty string will + * break here too! */ + if (np->u.n->byte_num > byte_num) + break; + /* Subtle: bit numbers are "backwards" for comparison */ + if (np->u.n->byte_num == byte_num && np->u.n->bit_num < bit_num) + break; + + if (np->u.n->byte_num < len) { + u8 c = bytes[np->u.n->byte_num]; + direction = (c >> np->u.n->bit_num) & 1; + } + np = &np->u.n->child[direction]; + } + + newn->child[!new_dir]= *np; + np->u.n = newn; + return true; +} + +char *strset_del(struct strset *set, const char *member) +{ + size_t len = strlen(member); + const u8 *bytes = (const u8 *)member; + struct strset *parent = NULL, *n; + const char *ret = NULL; + u8 direction = 0; /* prevent bogus gcc warning. */ + + /* Empty set? */ + if (!set->u.n) { + errno = ENOENT; + return NULL; + } + + /* Find closest, but keep track of parent. */ + n = set; + /* Anything with first byte 0 is a node. */ + while (!n->u.s[0]) { + u8 c = 0; + + /* Special node which represents the empty string. */ + if (unlikely(n->u.n->byte_num == (size_t)-1)) { + const char *empty_str = n->u.n->child[0].u.s; + + if (member[0]) { + errno = ENOENT; + return NULL; + } + + /* Sew empty string back so remaining logic works */ + free(n->u.n); + n->u.s = empty_str; + break; + } + + parent = n; + if (n->u.n->byte_num < len) { + c = bytes[n->u.n->byte_num]; + direction = (c >> n->u.n->bit_num) & 1; + } else + direction = 0; + n = &n->u.n->child[direction]; + } + + /* Did we find it? */ + if (!streq(member, n->u.s)) { + errno = ENOENT; + return NULL; + } + + ret = n->u.s; + + if (!parent) { + /* We deleted last node. */ + set->u.n = NULL; + } else { + struct node *old = parent->u.n; + /* Raise other node to parent. */ + *parent = old->child[!direction]; + free(old); + } + + return (char *)ret; +} + +static bool iterate(struct strset n, + bool (*handle)(const char *, void *), const void *data) +{ + if (n.u.s[0]) + return handle(n.u.s, (void *)data); + if (unlikely(n.u.n->byte_num == (size_t)-1)) + return handle(n.u.n->child[0].u.s, (void *)data); + + return iterate(n.u.n->child[0], handle, data) + && iterate(n.u.n->child[1], handle, data); +} + +void strset_iterate_(const struct strset *set, + bool (*handle)(const char *, void *), const void *data) +{ + /* Empty set? */ + if (!set->u.n) + return; + + iterate(*set, handle, data); +} + +const struct strset *strset_prefix(const struct strset *set, const char *prefix) +{ + const struct strset *n, *top; + size_t len = strlen(prefix); + const u8 *bytes = (const u8 *)prefix; + + /* Empty set -> return empty set. */ + if (!set->u.n) + return set; + + top = n = set; + + /* We walk to find the top, but keep going to check prefix matches. */ + while (!n->u.s[0]) { + u8 c = 0, direction; + + /* Special node which represents the empty string. */ + if (unlikely(n->u.n->byte_num == (size_t)-1)) { + n = &n->u.n->child[0]; + break; + } + + if (n->u.n->byte_num < len) + c = bytes[n->u.n->byte_num]; + + direction = (c >> n->u.n->bit_num) & 1; + n = &n->u.n->child[direction]; + if (c) + top = n; + } + + if (!strstarts(n->u.s, prefix)) { + /* Convenient return for prefixes which do not appear in set. */ + static const struct strset empty_set; + return &empty_set; + } + + return top; +} + +static void clear(struct strset n) +{ + if (!n.u.s[0]) { + if (likely(n.u.n->byte_num != (size_t)-1)) { + clear(n.u.n->child[0]); + clear(n.u.n->child[1]); + } + free(n.u.n); + } +} + +void strset_clear(struct strset *set) +{ + if (set->u.n) + clear(*set); + set->u.n = NULL; +} diff --git a/ccan/ccan/strset/strset.h b/ccan/ccan/strset/strset.h new file mode 100644 index 0000000..9d6f1ae --- /dev/null +++ b/ccan/ccan/strset/strset.h @@ -0,0 +1,167 @@ +#ifndef CCAN_STRSET_H +#define CCAN_STRSET_H +#include "config.h" +#include <ccan/typesafe_cb/typesafe_cb.h> +#include <stdlib.h> +#include <stdbool.h> + +/** + * struct strset - representation of a string set + * + * It's exposed here to allow you to embed it and so we can inline the + * trivial functions. + */ +struct strset { + union { + struct node *n; + const char *s; + } u; +}; + +/** + * strset_init - initialize a string set (empty) + * + * For completeness; if you've arranged for it to be NULL already you don't + * need this. + * + * Example: + * struct strset set; + * + * strset_init(&set); + */ +static inline void strset_init(struct strset *set) +{ + set->u.n = NULL; +} + +/** + * strset_empty - is this string set empty? + * @set: the set. + * + * Example: + * if (!strset_empty(&set)) + * abort(); + */ +static inline bool strset_empty(const struct strset *set) +{ + return set->u.n == NULL; +} + +/** + * strset_get - is this a member of this string set? + * @set: the set. + * @member: the string to search for. + * + * Returns the member, or NULL if it isn't in the set (and sets errno + * = ENOENT). + * + * Example: + * if (strset_get(&set, "hello")) + * printf("hello is in the set\n"); + */ +char *strset_get(const struct strset *set, const char *member); + +/** + * strset_add - place a member in the string set. + * @set: the set. + * @member: the string to place in the set. + * + * This returns false if we run out of memory (errno = ENOMEM), or + * (more normally) if that string already appears in the set (EEXIST). + * + * Note that the pointer is placed in the set, the string is not copied. If + * you want a copy in the set, use strdup(). + * + * Example: + * if (!strset_add(&set, "goodbye")) + * printf("goodbye was already in the set\n"); + */ +bool strset_add(struct strset *set, const char *member); + +/** + * strset_del - remove a member from the string set. + * @set: the set. + * @member: the string to remove from the set. + * + * This returns the string which was passed to strset_add(), or NULL if + * the string was not in the map (in which case it sets errno = ENOENT). + * + * This means that if you allocated a string (eg. using strdup()), you can + * free it here. + * + * Example: + * if (!strset_del(&set, "goodbye")) + * printf("goodbye was not in the set?\n"); + */ +char *strset_del(struct strset *set, const char *member); + +/** + * strset_clear - remove every member from the set. + * @set: the set. + * + * The set will be empty after this. + * + * Example: + * strset_clear(&set); + */ +void strset_clear(struct strset *set); + +/** + * strset_iterate - ordered iteration over a set + * @set: the set. + * @handle: the function to call. + * @arg: the argument for the function (types should match). + * + * You should not alter the set within the @handle function! If it returns + * false, the iteration will stop. + * + * Example: + * static bool dump_some(const char *member, int *num) + * { + * // Only dump out num nodes. + * if (*(num--) == 0) + * return false; + * printf("%s\n", member); + * return true; + * } + * + * static void dump_set(const struct strset *set) + * { + * int max = 100; + * strset_iterate(set, dump_some, &max); + * if (max < 0) + * printf("... (truncated to 100 entries)\n"); + * } + */ +#define strset_iterate(set, handle, arg) \ + strset_iterate_((set), typesafe_cb_preargs(bool, void *, \ + (handle), (arg), \ + const char *), \ + (arg)) +void strset_iterate_(const struct strset *set, + bool (*handle)(const char *, void *), const void *data); + + +/** + * strset_prefix - return a subset matching a prefix + * @set: the set. + * @prefix: the prefix. + * + * This returns a pointer into @set, so don't alter @set while using + * the return value. You can use strset_iterate(), strset_test() or + * strset_empty() on the returned pointer. + * + * Example: + * static void dump_prefix(const struct strset *set, const char *prefix) + * { + * int max = 100; + * printf("Nodes with prefix %s:\n", prefix); + * strset_iterate(strset_prefix(set, prefix), dump_some, &max); + * if (max < 0) + * printf("... (truncated to 100 entries)\n"); + * } + */ +const struct strset *strset_prefix(const struct strset *set, + const char *prefix); + +#endif /* CCAN_STRSET_H */ diff --git a/ccan/ccan/typesafe_cb/LICENSE b/ccan/ccan/typesafe_cb/LICENSE new file mode 120000 index 0000000..b7951da --- /dev/null +++ b/ccan/ccan/typesafe_cb/LICENSE @@ -0,0 +1 @@ +../../licenses/CC0
\ No newline at end of file diff --git a/ccan/ccan/typesafe_cb/typesafe_cb.h b/ccan/ccan/typesafe_cb/typesafe_cb.h new file mode 100644 index 0000000..126d325 --- /dev/null +++ b/ccan/ccan/typesafe_cb/typesafe_cb.h @@ -0,0 +1,134 @@ +/* CC0 (Public domain) - see LICENSE file for details */ +#ifndef CCAN_TYPESAFE_CB_H +#define CCAN_TYPESAFE_CB_H +#include "config.h" + +#if HAVE_TYPEOF && HAVE_BUILTIN_CHOOSE_EXPR && HAVE_BUILTIN_TYPES_COMPATIBLE_P +/** + * typesafe_cb_cast - only cast an expression if it matches a given type + * @desttype: the type to cast to + * @oktype: the type we allow + * @expr: the expression to cast + * + * This macro is used to create functions which allow multiple types. + * The result of this macro is used somewhere that a @desttype type is + * expected: if @expr is exactly of type @oktype, then it will be + * cast to @desttype type, otherwise left alone. + * + * This macro can be used in static initializers. + * + * This is merely useful for warnings: if the compiler does not + * support the primitives required for typesafe_cb_cast(), it becomes an + * unconditional cast, and the @oktype argument is not used. In + * particular, this means that @oktype can be a type which uses the + * "typeof": it will not be evaluated if typeof is not supported. + * + * Example: + * // We can take either an unsigned long or a void *. + * void _set_some_value(void *val); + * #define set_some_value(e) \ + * _set_some_value(typesafe_cb_cast(void *, unsigned long, (e))) + */ +#define typesafe_cb_cast(desttype, oktype, expr) \ + __builtin_choose_expr( \ + __builtin_types_compatible_p(__typeof__(0?(expr):(expr)), \ + oktype), \ + (desttype)(expr), (expr)) +#else +#define typesafe_cb_cast(desttype, oktype, expr) ((desttype)(expr)) +#endif + +/** + * typesafe_cb_cast3 - only cast an expression if it matches given types + * @desttype: the type to cast to + * @ok1: the first type we allow + * @ok2: the second type we allow + * @ok3: the third type we allow + * @expr: the expression to cast + * + * This is a convenient wrapper for multiple typesafe_cb_cast() calls. + * You can chain them inside each other (ie. use typesafe_cb_cast() + * for expr) if you need more than 3 arguments. + * + * Example: + * // We can take either a long, unsigned long, void * or a const void *. + * void _set_some_value(void *val); + * #define set_some_value(expr) \ + * _set_some_value(typesafe_cb_cast3(void *,, \ + * long, unsigned long, const void *,\ + * (expr))) + */ +#define typesafe_cb_cast3(desttype, ok1, ok2, ok3, expr) \ + typesafe_cb_cast(desttype, ok1, \ + typesafe_cb_cast(desttype, ok2, \ + typesafe_cb_cast(desttype, ok3, \ + (expr)))) + +/** + * typesafe_cb - cast a callback function if it matches the arg + * @rtype: the return type of the callback function + * @atype: the (pointer) type which the callback function expects. + * @fn: the callback function to cast + * @arg: the (pointer) argument to hand to the callback function. + * + * If a callback function takes a single argument, this macro does + * appropriate casts to a function which takes a single atype argument if the + * callback provided matches the @arg. + * + * It is assumed that @arg is of pointer type: usually @arg is passed + * or assigned to a void * elsewhere anyway. + * + * Example: + * void _register_callback(void (*fn)(void *arg), void *arg); + * #define register_callback(fn, arg) \ + * _register_callback(typesafe_cb(void, (fn), void*, (arg)), (arg)) + */ +#define typesafe_cb(rtype, atype, fn, arg) \ + typesafe_cb_cast(rtype (*)(atype), \ + rtype (*)(__typeof__(arg)), \ + (fn)) + +/** + * typesafe_cb_preargs - cast a callback function if it matches the arg + * @rtype: the return type of the callback function + * @atype: the (pointer) type which the callback function expects. + * @fn: the callback function to cast + * @arg: the (pointer) argument to hand to the callback function. + * + * This is a version of typesafe_cb() for callbacks that take other arguments + * before the @arg. + * + * Example: + * void _register_callback(void (*fn)(int, void *arg), void *arg); + * #define register_callback(fn, arg) \ + * _register_callback(typesafe_cb_preargs(void, void *, \ + * (fn), (arg), int), \ + * (arg)) + */ +#define typesafe_cb_preargs(rtype, atype, fn, arg, ...) \ + typesafe_cb_cast(rtype (*)(__VA_ARGS__, atype), \ + rtype (*)(__VA_ARGS__, __typeof__(arg)), \ + (fn)) + +/** + * typesafe_cb_postargs - cast a callback function if it matches the arg + * @rtype: the return type of the callback function + * @atype: the (pointer) type which the callback function expects. + * @fn: the callback function to cast + * @arg: the (pointer) argument to hand to the callback function. + * + * This is a version of typesafe_cb() for callbacks that take other arguments + * after the @arg. + * + * Example: + * void _register_callback(void (*fn)(void *arg, int), void *arg); + * #define register_callback(fn, arg) \ + * _register_callback(typesafe_cb_postargs(void, (fn), void *, \ + * (arg), int), \ + * (arg)) + */ +#define typesafe_cb_postargs(rtype, atype, fn, arg, ...) \ + typesafe_cb_cast(rtype (*)(atype, __VA_ARGS__), \ + rtype (*)(__typeof__(arg), __VA_ARGS__), \ + (fn)) +#endif /* CCAN_CAST_IF_TYPE_H */ diff --git a/ccan/licenses/BSD-MIT b/ccan/licenses/BSD-MIT new file mode 100644 index 0000000..89de354 --- /dev/null +++ b/ccan/licenses/BSD-MIT @@ -0,0 +1,17 @@ +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. diff --git a/ccan/licenses/CC0 b/ccan/licenses/CC0 new file mode 100644 index 0000000..feb9b11 --- /dev/null +++ b/ccan/licenses/CC0 @@ -0,0 +1,28 @@ +Statement of Purpose + +The laws of most jurisdictions throughout the world automatically confer exclusive Copyright and Related Rights (defined below) upon the creator and subsequent owner(s) (each and all, an "owner") of an original work of authorship and/or a database (each, a "Work"). + +Certain owners wish to permanently relinquish those rights to a Work for the purpose of contributing to a commons of creative, cultural and scientific works ("Commons") that the public can reliably and without fear of later claims of infringement build upon, modify, incorporate in other works, reuse and redistribute as freely as possible in any form whatsoever and for any purposes, including without limitation commercial purposes. These owners may contribute to the Commons to promote the ideal of a free culture and the further production of creative, cultural and scientific works, or to gain reputation or greater distribution for their Work in part through the use and efforts of others. + +For these and/or other purposes and motivations, and without any expectation of additional consideration or compensation, the person associating CC0 with a Work (the "Affirmer"), to the extent that he or she is an owner of Copyright and Related Rights in the Work, voluntarily elects to apply CC0 to the Work and publicly distribute the Work under its terms, with knowledge of his or her Copyright and Related Rights in the Work and the meaning and intended legal effect of CC0 on those rights. + +1. Copyright and Related Rights. A Work made available under CC0 may be protected by copyright and related or neighboring rights ("Copyright and Related Rights"). Copyright and Related Rights include, but are not limited to, the following: + + the right to reproduce, adapt, distribute, perform, display, communicate, and translate a Work; + moral rights retained by the original author(s) and/or performer(s); + publicity and privacy rights pertaining to a person's image or likeness depicted in a Work; + rights protecting against unfair competition in regards to a Work, subject to the limitations in paragraph 4(a), below; + rights protecting the extraction, dissemination, use and reuse of data in a Work; + database rights (such as those arising under Directive 96/9/EC of the European Parliament and of the Council of 11 March 1996 on the legal protection of databases, and under any national implementation thereof, including any amended or successor version of such directive); and + other similar, equivalent or corresponding rights throughout the world based on applicable law or treaty, and any national implementations thereof. + +2. Waiver. To the greatest extent permitted by, but not in contravention of, applicable law, Affirmer hereby overtly, fully, permanently, irrevocably and unconditionally waives, abandons, and surrenders all of Affirmer's Copyright and Related Rights and associated claims and causes of action, whether now known or unknown (including existing as well as future claims and causes of action), in the Work (i) in all territories worldwide, (ii) for the maximum duration provided by applicable law or treaty (including future time extensions), (iii) in any current or future medium and for any number of copies, and (iv) for any purpose whatsoever, including without limitation commercial, advertising or promotional purposes (the "Waiver"). Affirmer makes the Waiver for the benefit of each member of the public at large and to the detriment of Affirmer's heirs and successors, fully intending that such Waiver shall not be subject to revocation, rescission, cancellation, termination, or any other legal or equitable action to disrupt the quiet enjoyment of the Work by the public as contemplated by Affirmer's express Statement of Purpose. + +3. Public License Fallback. Should any part of the Waiver for any reason be judged legally invalid or ineffective under applicable law, then the Waiver shall be preserved to the maximum extent permitted taking into account Affirmer's express Statement of Purpose. In addition, to the extent the Waiver is so judged Affirmer hereby grants to each affected person a royalty-free, non transferable, non sublicensable, non exclusive, irrevocable and unconditional license to exercise Affirmer's Copyright and Related Rights in the Work (i) in all territories worldwide, (ii) for the maximum duration provided by applicable law or treaty (including future time extensions), (iii) in any current or future medium and for any number of copies, and (iv) for any purpose whatsoever, including without limitation commercial, advertising or promotional purposes (the "License"). The License shall be deemed effective as of the date CC0 was applied by Affirmer to the Work. Should any part of the License for any reason be judged legally invalid or ineffective under applicable law, such partial invalidity or ineffectiveness shall not invalidate the remainder of the License, and in such case Affirmer hereby affirms that he or she will not (i) exercise any of his or her remaining Copyright and Related Rights in the Work or (ii) assert any associated claims and causes of action with respect to the Work, in either case contrary to Affirmer's express Statement of Purpose. + +4. Limitations and Disclaimers. + + No trademark or patent rights held by Affirmer are waived, abandoned, surrendered, licensed or otherwise affected by this document. + Affirmer offers the Work as-is and makes no representations or warranties of any kind concerning the Work, express, implied, statutory or otherwise, including without limitation warranties of title, merchantability, fitness for a particular purpose, non infringement, or the absence of latent or other defects, accuracy, or the present or absence of errors, whether or not discoverable, all to the greatest extent permissible under applicable law. + Affirmer disclaims responsibility for clearing rights of other persons that may apply to the Work or any use thereof, including without limitation any person's Copyright and Related Rights in the Work. Further, Affirmer disclaims responsibility for obtaining any necessary consents, permissions or other rights required for any use of the Work. + Affirmer understands and acknowledges that Creative Commons is not a party to this document and has no duty or obligation with respect to this CC0 or use of the Work. diff --git a/ccan/licenses/LGPL-2.1 b/ccan/licenses/LGPL-2.1 new file mode 100644 index 0000000..2d2d780 --- /dev/null +++ b/ccan/licenses/LGPL-2.1 @@ -0,0 +1,510 @@ + + GNU LESSER GENERAL PUBLIC LICENSE + Version 2.1, February 1999 + + Copyright (C) 1991, 1999 Free Software Foundation, Inc. + 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + +[This is the first released version of the Lesser GPL. It also counts + as the successor of the GNU Library Public License, version 2, hence + the version number 2.1.] + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +Licenses are intended to guarantee your freedom to share and change +free software--to make sure the software is free for all its users. + + This license, the Lesser General Public License, applies to some +specially designated software packages--typically libraries--of the +Free Software Foundation and other authors who decide to use it. You +can use it too, but we suggest you first think carefully about whether +this license or the ordinary General Public License is the better +strategy to use in any particular case, based on the explanations +below. + + When we speak of free software, we are referring to freedom of use, +not price. Our General Public Licenses are designed to make sure that +you have the freedom to distribute copies of free software (and charge +for this service if you wish); that you receive source code or can get +it if you want it; that you can change the software and use pieces of +it in new free programs; and that you are informed that you can do +these things. + + To protect your rights, we need to make restrictions that forbid +distributors to deny you these rights or to ask you to surrender these +rights. These restrictions translate to certain responsibilities for +you if you distribute copies of the library or if you modify it. + + For example, if you distribute copies of the library, whether gratis +or for a fee, you must give the recipients all the rights that we gave +you. You must make sure that they, too, receive or can get the source +code. If you link other code with the library, you must provide +complete object files to the recipients, so that they can relink them +with the library after making changes to the library and recompiling +it. And you must show them these terms so they know their rights. + + We protect your rights with a two-step method: (1) we copyright the +library, and (2) we offer you this license, which gives you legal +permission to copy, distribute and/or modify the library. + + To protect each distributor, we want to make it very clear that +there is no warranty for the free library. Also, if the library is +modified by someone else and passed on, the recipients should know +that what they have is not the original version, so that the original +author's reputation will not be affected by problems that might be +introduced by others. + + Finally, software patents pose a constant threat to the existence of +any free program. We wish to make sure that a company cannot +effectively restrict the users of a free program by obtaining a +restrictive license from a patent holder. Therefore, we insist that +any patent license obtained for a version of the library must be +consistent with the full freedom of use specified in this license. + + Most GNU software, including some libraries, is covered by the +ordinary GNU General Public License. This license, the GNU Lesser +General Public License, applies to certain designated libraries, and +is quite different from the ordinary General Public License. We use +this license for certain libraries in order to permit linking those +libraries into non-free programs. + + When a program is linked with a library, whether statically or using +a shared library, the combination of the two is legally speaking a +combined work, a derivative of the original library. The ordinary +General Public License therefore permits such linking only if the +entire combination fits its criteria of freedom. The Lesser General +Public License permits more lax criteria for linking other code with +the library. + + We call this license the "Lesser" General Public License because it +does Less to protect the user's freedom than the ordinary General +Public License. It also provides other free software developers Less +of an advantage over competing non-free programs. These disadvantages +are the reason we use the ordinary General Public License for many +libraries. However, the Lesser license provides advantages in certain +special circumstances. + + For example, on rare occasions, there may be a special need to +encourage the widest possible use of a certain library, so that it +becomes a de-facto standard. To achieve this, non-free programs must +be allowed to use the library. A more frequent case is that a free +library does the same job as widely used non-free libraries. In this +case, there is little to gain by limiting the free library to free +software only, so we use the Lesser General Public License. + + In other cases, permission to use a particular library in non-free +programs enables a greater number of people to use a large body of +free software. For example, permission to use the GNU C Library in +non-free programs enables many more people to use the whole GNU +operating system, as well as its variant, the GNU/Linux operating +system. + + Although the Lesser General Public License is Less protective of the +users' freedom, it does ensure that the user of a program that is +linked with the Library has the freedom and the wherewithal to run +that program using a modified version of the Library. + + The precise terms and conditions for copying, distribution and +modification follow. Pay close attention to the difference between a +"work based on the library" and a "work that uses the library". The +former contains code derived from the library, whereas the latter must +be combined with the library in order to run. + + GNU LESSER GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License Agreement applies to any software library or other +program which contains a notice placed by the copyright holder or +other authorized party saying it may be distributed under the terms of +this Lesser General Public License (also called "this License"). +Each licensee is addressed as "you". + + A "library" means a collection of software functions and/or data +prepared so as to be conveniently linked with application programs +(which use some of those functions and data) to form executables. + + The "Library", below, refers to any such software library or work +which has been distributed under these terms. A "work based on the +Library" means either the Library or any derivative work under +copyright law: that is to say, a work containing the Library or a +portion of it, either verbatim or with modifications and/or translated +straightforwardly into another language. (Hereinafter, translation is +included without limitation in the term "modification".) + + "Source code" for a work means the preferred form of the work for +making modifications to it. For a library, complete source code means +all the source code for all modules it contains, plus any associated +interface definition files, plus the scripts used to control +compilation and installation of the library. + + Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running a program using the Library is not restricted, and output from +such a program is covered only if its contents constitute a work based +on the Library (independent of the use of the Library in a tool for +writing it). Whether that is true depends on what the Library does +and what the program that uses the Library does. + + 1. You may copy and distribute verbatim copies of the Library's +complete source code as you receive it, in any medium, provided that +you conspicuously and appropriately publish on each copy an +appropriate copyright notice and disclaimer of warranty; keep intact +all the notices that refer to this License and to the absence of any +warranty; and distribute a copy of this License along with the +Library. + + You may charge a fee for the physical act of transferring a copy, +and you may at your option offer warranty protection in exchange for a +fee. + + 2. You may modify your copy or copies of the Library or any portion +of it, thus forming a work based on the Library, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) The modified work must itself be a software library. + + b) You must cause the files modified to carry prominent notices + stating that you changed the files and the date of any change. + + c) You must cause the whole of the work to be licensed at no + charge to all third parties under the terms of this License. + + d) If a facility in the modified Library refers to a function or a + table of data to be supplied by an application program that uses + the facility, other than as an argument passed when the facility + is invoked, then you must make a good faith effort to ensure that, + in the event an application does not supply such function or + table, the facility still operates, and performs whatever part of + its purpose remains meaningful. + + (For example, a function in a library to compute square roots has + a purpose that is entirely well-defined independent of the + application. Therefore, Subsection 2d requires that any + application-supplied function or table used by this function must + be optional: if the application does not supply it, the square + root function must still compute square roots.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Library, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Library, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote +it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Library. + +In addition, mere aggregation of another work not based on the Library +with the Library (or with a work based on the Library) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may opt to apply the terms of the ordinary GNU General Public +License instead of this License to a given copy of the Library. To do +this, you must alter all the notices that refer to this License, so +that they refer to the ordinary GNU General Public License, version 2, +instead of to this License. (If a newer version than version 2 of the +ordinary GNU General Public License has appeared, then you can specify +that version instead if you wish.) Do not make any other change in +these notices. + + Once this change is made in a given copy, it is irreversible for +that copy, so the ordinary GNU General Public License applies to all +subsequent copies and derivative works made from that copy. + + This option is useful when you wish to copy part of the code of +the Library into a program that is not a library. + + 4. You may copy and distribute the Library (or a portion or +derivative of it, under Section 2) in object code or executable form +under the terms of Sections 1 and 2 above provided that you accompany +it with the complete corresponding machine-readable source code, which +must be distributed under the terms of Sections 1 and 2 above on a +medium customarily used for software interchange. + + If distribution of object code is made by offering access to copy +from a designated place, then offering equivalent access to copy the +source code from the same place satisfies the requirement to +distribute the source code, even though third parties are not +compelled to copy the source along with the object code. + + 5. A program that contains no derivative of any portion of the +Library, but is designed to work with the Library by being compiled or +linked with it, is called a "work that uses the Library". Such a +work, in isolation, is not a derivative work of the Library, and +therefore falls outside the scope of this License. + + However, linking a "work that uses the Library" with the Library +creates an executable that is a derivative of the Library (because it +contains portions of the Library), rather than a "work that uses the +library". The executable is therefore covered by this License. +Section 6 states terms for distribution of such executables. + + When a "work that uses the Library" uses material from a header file +that is part of the Library, the object code for the work may be a +derivative work of the Library even though the source code is not. +Whether this is true is especially significant if the work can be +linked without the Library, or if the work is itself a library. The +threshold for this to be true is not precisely defined by law. + + If such an object file uses only numerical parameters, data +structure layouts and accessors, and small macros and small inline +functions (ten lines or less in length), then the use of the object +file is unrestricted, regardless of whether it is legally a derivative +work. (Executables containing this object code plus portions of the +Library will still fall under Section 6.) + + Otherwise, if the work is a derivative of the Library, you may +distribute the object code for the work under the terms of Section 6. +Any executables containing that work also fall under Section 6, +whether or not they are linked directly with the Library itself. + + 6. As an exception to the Sections above, you may also combine or +link a "work that uses the Library" with the Library to produce a +work containing portions of the Library, and distribute that work +under terms of your choice, provided that the terms permit +modification of the work for the customer's own use and reverse +engineering for debugging such modifications. + + You must give prominent notice with each copy of the work that the +Library is used in it and that the Library and its use are covered by +this License. You must supply a copy of this License. If the work +during execution displays copyright notices, you must include the +copyright notice for the Library among them, as well as a reference +directing the user to the copy of this License. Also, you must do one +of these things: + + a) Accompany the work with the complete corresponding + machine-readable source code for the Library including whatever + changes were used in the work (which must be distributed under + Sections 1 and 2 above); and, if the work is an executable linked + with the Library, with the complete machine-readable "work that + uses the Library", as object code and/or source code, so that the + user can modify the Library and then relink to produce a modified + executable containing the modified Library. (It is understood + that the user who changes the contents of definitions files in the + Library will not necessarily be able to recompile the application + to use the modified definitions.) + + b) Use a suitable shared library mechanism for linking with the + Library. A suitable mechanism is one that (1) uses at run time a + copy of the library already present on the user's computer system, + rather than copying library functions into the executable, and (2) + will operate properly with a modified version of the library, if + the user installs one, as long as the modified version is + interface-compatible with the version that the work was made with. + + c) Accompany the work with a written offer, valid for at least + three years, to give the same user the materials specified in + Subsection 6a, above, for a charge no more than the cost of + performing this distribution. + + d) If distribution of the work is made by offering access to copy + from a designated place, offer equivalent access to copy the above + specified materials from the same place. + + e) Verify that the user has already received a copy of these + materials or that you have already sent this user a copy. + + For an executable, the required form of the "work that uses the +Library" must include any data and utility programs needed for +reproducing the executable from it. However, as a special exception, +the materials to be distributed need not include anything that is +normally distributed (in either source or binary form) with the major +components (compiler, kernel, and so on) of the operating system on +which the executable runs, unless that component itself accompanies +the executable. + + It may happen that this requirement contradicts the license +restrictions of other proprietary libraries that do not normally +accompany the operating system. Such a contradiction means you cannot +use both them and the Library together in an executable that you +distribute. + + 7. You may place library facilities that are a work based on the +Library side-by-side in a single library together with other library +facilities not covered by this License, and distribute such a combined +library, provided that the separate distribution of the work based on +the Library and of the other library facilities is otherwise +permitted, and provided that you do these two things: + + a) Accompany the combined library with a copy of the same work + based on the Library, uncombined with any other library + facilities. This must be distributed under the terms of the + Sections above. + + b) Give prominent notice with the combined library of the fact + that part of it is a work based on the Library, and explaining + where to find the accompanying uncombined form of the same work. + + 8. You may not copy, modify, sublicense, link with, or distribute +the Library except as expressly provided under this License. Any +attempt otherwise to copy, modify, sublicense, link with, or +distribute the Library is void, and will automatically terminate your +rights under this License. However, parties who have received copies, +or rights, from you under this License will not have their licenses +terminated so long as such parties remain in full compliance. + + 9. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Library or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Library (or any work based on the +Library), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Library or works based on it. + + 10. Each time you redistribute the Library (or any work based on the +Library), the recipient automatically receives a license from the +original licensor to copy, distribute, link with or modify the Library +subject to these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties with +this License. + + 11. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Library at all. For example, if a patent +license would not permit royalty-free redistribution of the Library by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Library. + +If any portion of this section is held invalid or unenforceable under +any particular circumstance, the balance of the section is intended to +apply, and the section as a whole is intended to apply in other +circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 12. If the distribution and/or use of the Library is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Library under this License +may add an explicit geographical distribution limitation excluding those +countries, so that distribution is permitted only in or among +countries not thus excluded. In such case, this License incorporates +the limitation as if written in the body of this License. + + 13. The Free Software Foundation may publish revised and/or new +versions of the Lesser General Public License from time to time. +Such new versions will be similar in spirit to the present version, +but may differ in detail to address new problems or concerns. + +Each version is given a distinguishing version number. If the Library +specifies a version number of this License which applies to it and +"any later version", you have the option of following the terms and +conditions either of that version or of any later version published by +the Free Software Foundation. If the Library does not specify a +license version number, you may choose any version ever published by +the Free Software Foundation. + + 14. If you wish to incorporate parts of the Library into other free +programs whose distribution conditions are incompatible with these, +write to the author to ask for permission. For software which is +copyrighted by the Free Software Foundation, write to the Free +Software Foundation; we sometimes make exceptions for this. Our +decision will be guided by the two goals of preserving the free status +of all derivatives of our free software and of promoting the sharing +and reuse of software generally. + + NO WARRANTY + + 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO +WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. +EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR +OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY +KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE +LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME +THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN +WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY +AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU +FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR +CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE +LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING +RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A +FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF +SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH +DAMAGES. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Libraries + + If you develop a new library, and you want it to be of the greatest +possible use to the public, we recommend making it free software that +everyone can redistribute and change. You can do so by permitting +redistribution under these terms (or, alternatively, under the terms +of the ordinary General Public License). + + To apply these terms, attach the following notices to the library. +It is safest to attach them to the start of each source file to most +effectively convey the exclusion of warranty; and each file should +have at least the "copyright" line and a pointer to where the full +notice is found. + + + <one line to give the library's name and a brief idea of what it does.> + Copyright (C) <year> <name of author> + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + +Also add information on how to contact you by electronic and paper mail. + +You should also get your employer (if you work as a programmer) or +your school, if any, to sign a "copyright disclaimer" for the library, +if necessary. Here is a sample; alter the names: + + Yoyodyne, Inc., hereby disclaims all copyright interest in the + library `Frob' (a library for tweaking knobs) written by James + Random Hacker. + + <signature of Ty Coon>, 1 April 1990 + Ty Coon, President of Vice + +That's all there is to it! + + diff --git a/ccan/meson.build b/ccan/meson.build new file mode 100644 index 0000000..35d2b88 --- /dev/null +++ b/ccan/meson.build @@ -0,0 +1,17 @@ +# SPDX-License-Identifier: GPL-2.0-or-later + +sources += files([ + 'ccan/hash/hash.c', + 'ccan/htable/htable.c', + 'ccan/ilog/ilog.c', + 'ccan/likely/likely.c', + 'ccan/list/list.c', + 'ccan/str/debug.c', + 'ccan/str/str.c', + 'ccan/strset/strset.c', +]) + +if get_option('buildtype') == 'debug' + add_project_arguments('-DCCAN_LIST_DEBUG=1', language : ['c']) + add_project_arguments('-DCCAN_STR_DEBUG=1', language : ['c']) +endif |