Script 'mail_helper' called by obssrc Hello community, here is the log from the commit of package klib for openSUSE:Factory checked in at 2026-06-29 17:32:20 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/klib (Old) and /work/SRC/openSUSE:Factory/.klib.new.11887 (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "klib" Mon Jun 29 17:32:20 2026 rev:2 rq:1362416 version:1.0~git.20251221 Changes: -------- --- /work/SRC/openSUSE:Factory/klib/klib.changes 2023-01-19 16:44:08.641750184 +0100 +++ /work/SRC/openSUSE:Factory/.klib.new.11887/klib.changes 2026-06-29 17:34:06.821753369 +0200 @@ -1,0 +2,5 @@ +Mon Jun 29 12:01:34 UTC 2026 - Paolo Stivanin <[email protected]> + +- Update to 1.0~git.20251221 (no changelog). + +------------------------------------------------------------------- Old: ---- klib-1.0~git.20210716.tar.xz New: ---- klib-1.0~git.20251221.tar.xz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ klib.spec ++++++ --- /var/tmp/diff_new_pack.wK3pdk/_old 2026-06-29 17:34:07.765785667 +0200 +++ /var/tmp/diff_new_pack.wK3pdk/_new 2026-06-29 17:34:07.769785804 +0200 @@ -1,7 +1,7 @@ # # spec file for package klib # -# Copyright (c) 2023 SUSE LLC +# Copyright (c) 2026 SUSE LLC and contributors # # All modifications and additions to the file contributed by third parties # remain the property of their copyright owners, unless otherwise agreed @@ -17,7 +17,7 @@ Name: klib -Version: 1.0~git.20210716 +Version: 1.0~git.20251221 Release: 0 BuildArch: noarch Summary: C library with utility functions ++++++ klib-1.0~git.20210716.tar.xz -> klib-1.0~git.20251221.tar.xz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/.gitignore new/klib-1.0~git.20251221/.gitignore --- old/klib-1.0~git.20210716/.gitignore 2021-07-16 22:45:53.000000000 +0200 +++ new/klib-1.0~git.20251221/.gitignore 1970-01-01 01:00:00.000000000 +0100 @@ -1,40 +0,0 @@ -# General -*.a -*.dSYM/ -*.la -*.lo -*.o -*.opensdf -*.orig -*.sdf -*.suo -*.swp -*.tests -*.vcxproj.filters -*.vcxproj.user -*~ -.git -TAGS - -# Mac/Xcode-specfic -xcuserdata -contents.xcworkspacedata -.DS_Store -._* - -# Test byproducts -test/kbtree_test -test/khash_keith -test/khash_keith2 -test/khash_test -test/klist_test -test/kmin_test -test/kseq_bench -test/kseq_bench2 -test/kseq_test -test/ksort_test -test/ksort_test-stl -test/kstring_bench -test/kstring_bench2 -test/kstring_test -test/kvec_test diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/kalloc.c new/klib-1.0~git.20251221/kalloc.c --- old/klib-1.0~git.20210716/kalloc.c 2021-07-16 22:45:53.000000000 +0200 +++ new/klib-1.0~git.20251221/kalloc.c 2025-12-22 05:35:26.000000000 +0100 @@ -18,15 +18,14 @@ * | | | | * p=p->ptr->ptr->ptr->ptr p->ptr p->ptr->ptr p->ptr->ptr->ptr */ - -#define MIN_CORE_SIZE 0x80000 - typedef struct header_t { size_t size; struct header_t *ptr; } header_t; typedef struct { + void *par; + size_t min_core_size; header_t base, *loop_head, *core_head; /* base is a zero-sized block always kept in the loop */ } kmem_t; @@ -36,31 +35,40 @@ abort(); } -void *km_init(void) +void *km_init2(void *km_par, size_t min_core_size) { - return calloc(1, sizeof(kmem_t)); + kmem_t *km; + km = (kmem_t*)kcalloc(km_par, 1, sizeof(kmem_t)); + km->par = km_par; + if (km_par) km->min_core_size = min_core_size > 0? min_core_size : ((kmem_t*)km_par)->min_core_size - 2; + else km->min_core_size = min_core_size > 0? min_core_size : 0x80000; + return (void*)km; } +void *km_init(void) { return km_init2(0, 0); } + void km_destroy(void *_km) { kmem_t *km = (kmem_t*)_km; + void *km_par; header_t *p, *q; if (km == NULL) return; + km_par = km->par; for (p = km->core_head; p != NULL;) { q = p->ptr; - free(p); + kfree(km_par, p); p = q; } - free(km); + kfree(km_par, km); } static header_t *morecore(kmem_t *km, size_t nu) { header_t *q; size_t bytes, *p; - nu = (nu + 1 + (MIN_CORE_SIZE - 1)) / MIN_CORE_SIZE * MIN_CORE_SIZE; /* the first +1 for core header */ + nu = (nu + 1 + (km->min_core_size - 1)) / km->min_core_size * km->min_core_size; /* the first +1 for core header */ bytes = nu * sizeof(header_t); - q = (header_t*)malloc(bytes); + q = (header_t*)kmalloc(km->par, bytes); if (!q) panic("[morecore] insufficient memory"); q->ptr = km->core_head, q->size = nu, km->core_head = q; p = (size_t*)(q + 1); @@ -125,7 +133,7 @@ if (n_bytes == 0) return 0; if (km == NULL) return malloc(n_bytes); - n_units = (n_bytes + sizeof(size_t) + sizeof(header_t) - 1) / sizeof(header_t) + 1; + n_units = (n_bytes + sizeof(size_t) + sizeof(header_t) - 1) / sizeof(header_t); /* header+n_bytes requires at least this number of units */ if (!(q = km->loop_head)) /* the first time when kmalloc() is called, intialize it */ q = km->loop_head = km->base.ptr = &km->base; @@ -160,22 +168,32 @@ void *krealloc(void *_km, void *ap, size_t n_bytes) // TODO: this can be made more efficient in principle { kmem_t *km = (kmem_t*)_km; - size_t n_units, *p, *q; + size_t cap, *p, *q; if (n_bytes == 0) { kfree(km, ap); return 0; } if (km == NULL) return realloc(ap, n_bytes); if (ap == NULL) return kmalloc(km, n_bytes); - n_units = (n_bytes + sizeof(size_t) + sizeof(header_t) - 1) / sizeof(header_t); p = (size_t*)ap - 1; - if (*p >= n_units) return ap; /* TODO: this prevents shrinking */ + cap = (*p) * sizeof(header_t) - sizeof(size_t); + if (cap >= n_bytes) return ap; /* TODO: this prevents shrinking */ q = (size_t*)kmalloc(km, n_bytes); - memcpy(q, ap, (*p - 1) * sizeof(header_t)); + memcpy(q, ap, cap); kfree(km, ap); return q; } +void *krelocate(void *km, void *ap, size_t n_bytes) +{ + void *p; + if (km == 0 || ap == 0) return ap; + p = kmalloc(km, n_bytes); + memcpy(p, ap, n_bytes); + kfree(km, ap); + return p; +} + void km_stat(const void *_km, km_stat_t *s) { kmem_t *km = (kmem_t*)_km; @@ -196,3 +214,11 @@ s->largest = s->largest > size? s->largest : size; } } + +void km_stat_print(const void *km) +{ + km_stat_t st; + km_stat(km, &st); + fprintf(stderr, "[km_stat] cap=%ld, avail=%ld, largest=%ld, n_core=%ld, n_block=%ld\n", + st.capacity, st.available, st.largest, st.n_blocks, st.n_cores); +} diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/kalloc.h new/klib-1.0~git.20251221/kalloc.h --- old/klib-1.0~git.20210716/kalloc.h 2021-07-16 22:45:53.000000000 +0200 +++ new/klib-1.0~git.20251221/kalloc.h 2025-12-22 05:35:26.000000000 +0100 @@ -13,15 +13,75 @@ void *kmalloc(void *km, size_t size); void *krealloc(void *km, void *ptr, size_t size); +void *krelocate(void *km, void *ap, size_t n_bytes); void *kcalloc(void *km, size_t count, size_t size); void kfree(void *km, void *ptr); void *km_init(void); +void *km_init2(void *km_par, size_t min_core_size); void km_destroy(void *km); void km_stat(const void *_km, km_stat_t *s); +void km_stat_print(const void *km); #ifdef __cplusplus } #endif +#define Kmalloc(km, type, cnt) ((type*)kmalloc((km), (cnt) * sizeof(type))) +#define Kcalloc(km, type, cnt) ((type*)kcalloc((km), (cnt), sizeof(type))) +#define Krealloc(km, type, ptr, cnt) ((type*)krealloc((km), (ptr), (cnt) * sizeof(type))) + +#define Kexpand(km, type, a, m) do { \ + (m) = (m) >= 4? (m) + ((m)>>1) : 16; \ + (a) = Krealloc(km, type, (a), (m)); \ + } while (0) + +#define KMALLOC(km, ptr, len) ((ptr) = (__typeof__(ptr))kmalloc((km), (len) * sizeof(*(ptr)))) +#define KCALLOC(km, ptr, len) ((ptr) = (__typeof__(ptr))kcalloc((km), (len), sizeof(*(ptr)))) +#define KREALLOC(km, ptr, len) ((ptr) = (__typeof__(ptr))krealloc((km), (ptr), (len) * sizeof(*(ptr)))) + +#define KEXPAND(km, a, m) do { \ + (m) = (m) >= 4? (m) + ((m)>>1) : 16; \ + KREALLOC((km), (a), (m)); \ + } while (0) + +#ifndef klib_unused +#if (defined __clang__ && __clang_major__ >= 3) || (defined __GNUC__ && __GNUC__ >= 3) +#define klib_unused __attribute__ ((__unused__)) +#else +#define klib_unused +#endif +#endif /* klib_unused */ + +#define KALLOC_POOL_INIT2(SCOPE, name, kmptype_t) \ + typedef struct { \ + size_t cnt, n, max; \ + kmptype_t **buf; \ + void *km; \ + } kmp_##name##_t; \ + SCOPE kmp_##name##_t *kmp_init_##name(void *km) { \ + kmp_##name##_t *mp; \ + mp = Kcalloc(km, kmp_##name##_t, 1); \ + mp->km = km; \ + return mp; \ + } \ + SCOPE void kmp_destroy_##name(kmp_##name##_t *mp) { \ + size_t k; \ + for (k = 0; k < mp->n; ++k) kfree(mp->km, mp->buf[k]); \ + kfree(mp->km, mp->buf); kfree(mp->km, mp); \ + } \ + SCOPE kmptype_t *kmp_alloc_##name(kmp_##name##_t *mp) { \ + ++mp->cnt; \ + if (mp->n == 0) return (kmptype_t*)kcalloc(mp->km, 1, sizeof(kmptype_t)); \ + return mp->buf[--mp->n]; \ + } \ + SCOPE void kmp_free_##name(kmp_##name##_t *mp, kmptype_t *p) { \ + --mp->cnt; \ + if (mp->n == mp->max) Kexpand(mp->km, kmptype_t*, mp->buf, mp->max); \ + mp->buf[mp->n++] = p; \ + } + +#define KALLOC_POOL_INIT(name, kmptype_t) \ + KALLOC_POOL_INIT2(static inline klib_unused, name, kmptype_t) + #endif diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/kavl.h new/klib-1.0~git.20251221/kavl.h --- old/klib-1.0~git.20210716/kavl.h 2021-07-16 22:45:53.000000000 +0200 +++ new/klib-1.0~git.20251221/kavl.h 2025-12-22 05:35:26.000000000 +0100 @@ -92,6 +92,19 @@ } \ if (cnt_) *cnt_ = cnt; \ return (__type*)p; \ + } \ + __scope __type *kavl_interval_##suf(const __type *root, const __type *x, __type **lower, __type **upper) { \ + const __type *p = root, *l = 0, *u = 0; \ + while (p != 0) { \ + int cmp; \ + cmp = __cmp(x, p); \ + if (cmp < 0) u = p, p = p->__head.p[0]; \ + else if (cmp > 0) l = p, p = p->__head.p[1]; \ + else { l = u = p; break; } \ + } \ + if (lower) *lower = (__type*)l; \ + if (upper) *upper = (__type*)u; \ + return (__type*)p; \ } #define __KAVL_ROTATE(suf, __type, __head) \ @@ -271,43 +284,42 @@ #define __KAVL_ITR(suf, __scope, __type, __head, __cmp) \ struct kavl_itr_##suf { \ - const __type *stack[KAVL_MAX_DEPTH], **top, *right; /* _right_ points to the right child of *top */ \ + const __type *stack[KAVL_MAX_DEPTH], **top; \ }; \ __scope void kavl_itr_first_##suf(const __type *root, struct kavl_itr_##suf *itr) { \ const __type *p; \ for (itr->top = itr->stack - 1, p = root; p; p = p->__head.p[0]) \ *++itr->top = p; \ - itr->right = (*itr->top)->__head.p[1]; \ } \ __scope int kavl_itr_find_##suf(const __type *root, const __type *x, struct kavl_itr_##suf *itr) { \ const __type *p = root; \ itr->top = itr->stack - 1; \ while (p != 0) { \ int cmp; \ + *++itr->top = p; \ cmp = __cmp(x, p); \ - if (cmp < 0) *++itr->top = p, p = p->__head.p[0]; \ + if (cmp < 0) p = p->__head.p[0]; \ else if (cmp > 0) p = p->__head.p[1]; \ else break; \ } \ - if (p) { \ - *++itr->top = p; \ - itr->right = p->__head.p[1]; \ - return 1; \ - } else if (itr->top >= itr->stack) { \ - itr->right = (*itr->top)->__head.p[1]; \ - return 0; \ - } else return 0; \ + return p? 1 : 0; \ } \ - __scope int kavl_itr_next_##suf(struct kavl_itr_##suf *itr) { \ - for (;;) { \ - const __type *p; \ - for (p = itr->right, --itr->top; p; p = p->__head.p[0]) \ + __scope int kavl_itr_next_bidir_##suf(struct kavl_itr_##suf *itr, int dir) { \ + const __type *p; \ + if (itr->top < itr->stack) return 0; \ + dir = !!dir; \ + p = (*itr->top)->__head.p[dir]; \ + if (p) { /* go down */ \ + for (; p; p = p->__head.p[!dir]) \ *++itr->top = p; \ - if (itr->top < itr->stack) return 0; \ - itr->right = (*itr->top)->__head.p[1]; \ return 1; \ + } else { /* go up */ \ + do { \ + p = *itr->top--; \ + } while (itr->top >= itr->stack && p == (*itr->top)->__head.p[dir]); \ + return itr->top < itr->stack? 0 : 1; \ } \ - } + } \ /** * Insert a node to the tree @@ -332,6 +344,7 @@ * @return node equal to _x_ if present, or NULL if absent */ #define kavl_find(suf, root, x, cnt) kavl_find_##suf(root, x, cnt) +#define kavl_interval(suf, root, x, lower, upper) kavl_interval_##suf(root, x, lower, upper) /** * Delete a node from the tree @@ -376,7 +389,8 @@ * * @return 1 if there is a next object; 0 otherwise */ -#define kavl_itr_next(suf, itr) kavl_itr_next_##suf(itr) +#define kavl_itr_next(suf, itr) kavl_itr_next_bidir_##suf(itr, 1) +#define kavl_itr_prev(suf, itr) kavl_itr_next_bidir_##suf(itr, 0) /** * Return the pointer at the iterator diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/kbarena.c new/klib-1.0~git.20251221/kbarena.c --- old/klib-1.0~git.20210716/kbarena.c 1970-01-01 01:00:00.000000000 +0100 +++ new/klib-1.0~git.20251221/kbarena.c 2025-12-22 05:35:26.000000000 +0100 @@ -0,0 +1,104 @@ +#include <stdint.h> +#include <stdlib.h> +#include <string.h> +#include "kbarena.h" + +#define kom_malloc(type, cnt) ((type*)malloc((cnt) * sizeof(type))) +#define kom_calloc(type, cnt) ((type*)calloc((cnt), sizeof(type))) +#define kom_realloc(type, ptr, cnt) ((type*)realloc((ptr), (cnt) * sizeof(type))) + +#define kom_grow(type, ptr, __i, __m, __succ) do { /* make enough room for ptr[__i] */ \ + *(__succ) = 1; \ + if ((__i) >= (__m)) { \ + size_t new_m = (__i) + 16ULL + (((__i) + 1ULL) >> 1); \ + type *new_p; \ + new_p = kom_realloc(type, (ptr), new_m); \ + if (new_p) (__m) = new_m, (ptr) = new_p; \ + else *(__succ) = 0; \ + } \ + } while (0) + +typedef struct { + uint32_t blen, max_blk; // block length and max number of blocks + uint32_t bi, bo; // current block index and block offset + uint8_t **b; // blocks + uint32_t n_stack, m_stack; // stack size and capacity + uint64_t *stack; // saved states (two uint32_t packed together) +} kbarena_t; + +void *kba_init(uint32_t blen) +{ + kbarena_t *ba; + if (blen == 0) return 0; + ba = kom_calloc(kbarena_t, 1); + if (ba == 0) return 0; + ba->blen = (blen + 7) / 8 * 8; // round up to 8 bytes + ba->max_blk = 4; + ba->b = kom_calloc(uint8_t*, ba->max_blk); + ba->b[0] = kom_malloc(uint8_t, ba->blen); // TODO: use aligned alloc + return ba; +} + +void kba_destroy(void *ba_) +{ + kbarena_t *ba = (kbarena_t*)ba_; + uint32_t i; + if (ba == 0) return; + for (i = 0; i < ba->max_blk; ++i) + if (ba->b[i]) free(ba->b[i]); + free(ba->b); free(ba->stack); free(ba); +} + +size_t kba_capacity(const void *ba_) +{ + const kbarena_t *ba = (const kbarena_t*)ba_; + uint32_t i; + size_t cap = 0; + for (i = 0; i < ba->max_blk; ++i) + if (ba->b[i]) cap += ba->blen; + return cap; +} + +void *kba_alloc(void *ba_, uint32_t sz, uint32_t aln) +{ + kbarena_t *ba = (kbarena_t*)ba_; + uint32_t pad = -(int64_t)ba->bo & (aln - 1); + void *p; + if (sz == 0 || sz > ba->blen || (aln & (aln - 1)) != 0) return 0; + if ((uint64_t)ba->bo + sz + pad > ba->blen) { // no room in the current block + uint32_t old_max = ba->max_blk; + int succ; + kom_grow(uint8_t*, ba->b, ba->bi + 1, ba->max_blk, &succ); + if (!succ) return 0; + if (ba->max_blk > old_max) + memset(&ba->b[old_max], 0, (ba->max_blk - old_max) * sizeof(void*)); + if (ba->b[ba->bi + 1] == 0) { + ba->b[ba->bi + 1] = kom_malloc(uint8_t, ba->blen); // TODO: use aligned malloc + if (ba->b[ba->bi + 1] == 0) return 0; + } + ++ba->bi, ba->bo = 0, pad = 0; + } + p = (void*)&ba->b[ba->bi][ba->bo + pad]; + ba->bo += sz + pad; + return p; +} + +int kba_save(void *ba_) +{ + kbarena_t *ba = (kbarena_t*)ba_; + int succ; + kom_grow(uint64_t, ba->stack, ba->n_stack, ba->m_stack, &succ); + if (!succ) return -1; + ba->stack[ba->n_stack++] = (uint64_t)ba->bi << 32 | ba->bo; + return 0; +} + +int kba_restore(void *ba_) +{ + uint64_t x; + kbarena_t *ba = (kbarena_t*)ba_; + if (ba->n_stack == 0) return -1; + x = ba->stack[--ba->n_stack]; + ba->bi = x>>32, ba->bo = (uint32_t)x; + return 0; +} diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/kbarena.h new/klib-1.0~git.20251221/kbarena.h --- old/klib-1.0~git.20210716/kbarena.h 1970-01-01 01:00:00.000000000 +0100 +++ new/klib-1.0~git.20251221/kbarena.h 2025-12-22 05:35:26.000000000 +0100 @@ -0,0 +1,46 @@ +#ifndef AC_KBARENA_H +#define AC_KBARENA_H + +#include <stddef.h> + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * Initialize a blocked arena + * + * @param blen block length in bytes + * + * @return pointer to a blocked arena + */ +void *kba_init(unsigned blen); + +/** Destroy a blocked arena */ +void kba_destroy(void *kba); + +/** + * Allocate memory from a blocked arena + * + * @param len size of the memory to allocate + * @param aln alignment; must be power of 2 + * + * @return pointer to the memory on success; NULL on insufficient memory or + * when len is longer than block length + */ +void *kba_alloc(void *kba, unsigned len, unsigned aln); + +/** Save the state */ +int kba_save(void *kba); + +/** Restore the state (effectively free all memory allocated after the pairing save) */ +int kba_restore(void *kba); + +/** Get the capacity in byte */ +size_t kba_capacity(const void *ba_); + +#ifdef __cplusplus +} +#endif + +#endif diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/kexpr.c new/klib-1.0~git.20251221/kexpr.c --- old/klib-1.0~git.20210716/kexpr.c 2021-07-16 22:45:53.000000000 +0200 +++ new/klib-1.0~git.20251221/kexpr.c 2025-12-22 05:35:26.000000000 +0100 @@ -553,11 +553,11 @@ return 1; } ke = ke_parse(argv[optind], &err); - ke_set_default_func(ke); if (err) { fprintf(stderr, "Parse error: 0x%x\n", err); return 1; } + ke_set_default_func(ke); if (!to_print) { int64_t vi; double vr; diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/khashl.h new/klib-1.0~git.20251221/khashl.h --- old/klib-1.0~git.20210716/khashl.h 2021-07-16 22:45:53.000000000 +0200 +++ new/klib-1.0~git.20251221/khashl.h 2025-12-22 05:35:26.000000000 +0100 @@ -1,6 +1,6 @@ /* The MIT License - Copyright (c) 2019 by Attractive Chaos <[email protected]> + Copyright (c) 2019- by Attractive Chaos <[email protected]> Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the @@ -26,7 +26,7 @@ #ifndef __AC_KHASHL_H #define __AC_KHASHL_H -#define AC_VERSION_KHASHL_H "0.1" +#define AC_VERSION_KHASHL_H "r30" #include <stdlib.h> #include <string.h> @@ -67,22 +67,25 @@ #define KH_LOCAL static kh_inline klib_unused typedef khint32_t khint_t; +typedef const char *kh_cstr_t; -/****************** - * malloc aliases * - ******************/ +/*********************** + * Configurable macros * + ***********************/ -#ifndef kcalloc -#define kcalloc(N,Z) calloc(N,Z) +#ifndef kh_max_count /* set the max load factor */ +#define kh_max_count(cap) (((cap)>>1) + ((cap)>>2)) /* default load factor: 75% */ #endif -#ifndef kmalloc -#define kmalloc(Z) malloc(Z) -#endif -#ifndef krealloc -#define krealloc(P,Z) realloc(P,Z) + +#ifndef kh_packed /* pack the key-value struct */ +#define kh_packed __attribute__ ((__packed__)) #endif -#ifndef kfree -#define kfree(P) free(P) + +#if !defined(Kmalloc) || !defined(Kcalloc) || !defined(Krealloc) || !defined(Kfree) +#define Kmalloc(km, type, cnt) ((type*)malloc((cnt) * sizeof(type))) +#define Kcalloc(km, type, cnt) ((type*)calloc((cnt), sizeof(type))) +#define Krealloc(km, type, ptr, cnt) ((type*)realloc((ptr), (cnt) * sizeof(type))) +#define Kfree(km, ptr) free(ptr) #endif /**************************** @@ -95,7 +98,7 @@ #define __kh_fsize(m) ((m) < 32? 1 : (m)>>5) -static kh_inline khint_t __kh_h2b(khint_t hash, khint_t bits) { return hash * 2654435769U >> (32 - bits); } +static kh_inline khint_t __kh_h2b(khint_t hash, khint_t bits) { return hash * 2654435769U >> (32 - bits); } /* Fibonacci hashing */ /******************* * Hash table base * @@ -103,6 +106,7 @@ #define __KHASHL_TYPE(HType, khkey_t) \ typedef struct HType { \ + void *km; \ khint_t bits, count; \ khint32_t *used; \ khkey_t *keys; \ @@ -110,6 +114,7 @@ #define __KHASHL_PROTOTYPES(HType, prefix, khkey_t) \ extern HType *prefix##_init(void); \ + extern HType *prefix##_init2(void *km); \ extern void prefix##_destroy(HType *h); \ extern void prefix##_clear(HType *h); \ extern khint_t prefix##_getp(const HType *h, const khkey_t *key); \ @@ -118,36 +123,40 @@ extern void prefix##_del(HType *h, khint_t k); #define __KHASHL_IMPL_BASIC(SCOPE, HType, prefix) \ - SCOPE HType *prefix##_init(void) { \ - return (HType*)kcalloc(1, sizeof(HType)); \ + SCOPE HType *prefix##_init2(void *km) { \ + HType *h = Kcalloc(km, HType, 1); \ + h->km = km; \ + return h; \ } \ + SCOPE HType *prefix##_init(void) { return prefix##_init2(0); } \ SCOPE void prefix##_destroy(HType *h) { \ if (!h) return; \ - kfree((void *)h->keys); kfree(h->used); \ - kfree(h); \ + Kfree(h->km, (void*)h->keys); Kfree(h->km, h->used); \ + Kfree(h->km, h); \ } \ SCOPE void prefix##_clear(HType *h) { \ if (h && h->used) { \ - uint32_t n_buckets = 1U << h->bits; \ + khint_t n_buckets = (khint_t)1U << h->bits; \ memset(h->used, 0, __kh_fsize(n_buckets) * sizeof(khint32_t)); \ h->count = 0; \ } \ } #define __KHASHL_IMPL_GET(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ - SCOPE khint_t prefix##_getp(const HType *h, const khkey_t *key) { \ + SCOPE khint_t prefix##_getp_core(const HType *h, const khkey_t *key, khint_t hash) { \ khint_t i, last, n_buckets, mask; \ if (h->keys == 0) return 0; \ - n_buckets = 1U << h->bits; \ + n_buckets = (khint_t)1U << h->bits; \ mask = n_buckets - 1U; \ - i = last = __kh_h2b(__hash_fn(*key), h->bits); \ + i = last = __kh_h2b(hash, h->bits); \ while (__kh_used(h->used, i) && !__hash_eq(h->keys[i], *key)) { \ i = (i + 1U) & mask; \ if (i == last) return n_buckets; \ } \ return !__kh_used(h->used, i)? n_buckets : i; \ } \ - SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { return prefix##_getp(h, &key); } + SCOPE khint_t prefix##_getp(const HType *h, const khkey_t *key) { return prefix##_getp_core(h, key, __hash_fn(*key)); } \ + SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { return prefix##_getp_core(h, &key, __hash_fn(key)); } #define __KHASHL_IMPL_RESIZE(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ SCOPE int prefix##_resize(HType *h, khint_t new_n_buckets) { \ @@ -156,15 +165,15 @@ while ((x >>= 1) != 0) ++j; \ if (new_n_buckets & (new_n_buckets - 1)) ++j; \ new_bits = j > 2? j : 2; \ - new_n_buckets = 1U << new_bits; \ - if (h->count > (new_n_buckets>>1) + (new_n_buckets>>2)) return 0; /* requested size is too small */ \ - new_used = (khint32_t*)kmalloc(__kh_fsize(new_n_buckets) * sizeof(khint32_t)); \ + new_n_buckets = (khint_t)1U << new_bits; \ + if (h->count > kh_max_count(new_n_buckets)) return 0; /* requested size is too small */ \ + new_used = Kmalloc(h->km, khint32_t, __kh_fsize(new_n_buckets)); \ memset(new_used, 0, __kh_fsize(new_n_buckets) * sizeof(khint32_t)); \ if (!new_used) return -1; /* not enough memory */ \ - n_buckets = h->keys? 1U<<h->bits : 0U; \ + n_buckets = h->keys? (khint_t)1U<<h->bits : 0U; \ if (n_buckets < new_n_buckets) { /* expand */ \ - khkey_t *new_keys = (khkey_t*)krealloc((void*)h->keys, new_n_buckets * sizeof(khkey_t)); \ - if (!new_keys) { kfree(new_used); return -1; } \ + khkey_t *new_keys = Krealloc(h->km, khkey_t, h->keys, new_n_buckets); \ + if (!new_keys) { Kfree(h->km, new_used); return -1; } \ h->keys = new_keys; \ } /* otherwise shrink */ \ new_mask = new_n_buckets - 1; \ @@ -188,24 +197,24 @@ } \ } \ if (n_buckets > new_n_buckets) /* shrink the hash table */ \ - h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \ - kfree(h->used); /* free the working space */ \ + h->keys = Krealloc(h->km, khkey_t, (void*)h->keys, new_n_buckets); \ + Kfree(h->km, h->used); /* free the working space */ \ h->used = new_used, h->bits = new_bits; \ return 0; \ } #define __KHASHL_IMPL_PUT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ - SCOPE khint_t prefix##_putp(HType *h, const khkey_t *key, int *absent) { \ + SCOPE khint_t prefix##_putp_core(HType *h, const khkey_t *key, khint_t hash, int *absent) { \ khint_t n_buckets, i, last, mask; \ - n_buckets = h->keys? 1U<<h->bits : 0U; \ + n_buckets = h->keys? (khint_t)1U<<h->bits : 0U; \ *absent = -1; \ - if (h->count >= (n_buckets>>1) + (n_buckets>>2)) { /* rehashing */ \ + if (h->count >= kh_max_count(n_buckets)) { /* rehashing */ \ if (prefix##_resize(h, n_buckets + 1U) < 0) \ return n_buckets; \ - n_buckets = 1U<<h->bits; \ + n_buckets = (khint_t)1U<<h->bits; \ } /* TODO: to implement automatically shrinking; resize() already support shrinking */ \ mask = n_buckets - 1; \ - i = last = __kh_h2b(__hash_fn(*key), h->bits); \ + i = last = __kh_h2b(hash, h->bits); \ while (__kh_used(h->used, i) && !__hash_eq(h->keys[i], *key)) { \ i = (i + 1U) & mask; \ if (i == last) break; \ @@ -218,13 +227,14 @@ } else *absent = 0; /* Don't touch h->keys[i] if present */ \ return i; \ } \ - SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { return prefix##_putp(h, &key, absent); } + SCOPE khint_t prefix##_putp(HType *h, const khkey_t *key, int *absent) { return prefix##_putp_core(h, key, __hash_fn(*key), absent); } \ + SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { return prefix##_putp_core(h, &key, __hash_fn(key), absent); } #define __KHASHL_IMPL_DEL(SCOPE, HType, prefix, khkey_t, __hash_fn) \ SCOPE int prefix##_del(HType *h, khint_t i) { \ khint_t j = i, k, mask, n_buckets; \ if (h->keys == 0) return 0; \ - n_buckets = 1U<<h->bits; \ + n_buckets = (khint_t)1U<<h->bits; \ mask = n_buckets - 1U; \ while (1) { \ j = (j + 1U) & mask; \ @@ -250,55 +260,159 @@ __KHASHL_IMPL_PUT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ __KHASHL_IMPL_DEL(SCOPE, HType, prefix, khkey_t, __hash_fn) +/*************************** + * Ensemble of hash tables * + ***************************/ + +typedef struct { + khint_t sub, pos; +} kh_ensitr_t; + +#define KHASHE_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + KHASHL_INIT(KH_LOCAL, HType##_sub, prefix##_sub, khkey_t, __hash_fn, __hash_eq) \ + typedef struct HType { \ + void *km; \ + khint64_t count:54, bits:8; \ + HType##_sub *sub; \ + } HType; \ + SCOPE HType *prefix##_init2(void *km, int bits) { \ + HType *g; \ + g = Kcalloc(km, HType, 1); \ + g->bits = bits, g->km = km; \ + g->sub = Kcalloc(km, HType##_sub, 1U<<bits); \ + return g; \ + } \ + SCOPE HType *prefix##_init(int bits) { return prefix##_init2(0, bits); } \ + SCOPE void prefix##_destroy(HType *g) { \ + int t; \ + if (!g) return; \ + for (t = 0; t < 1<<g->bits; ++t) { Kfree(g->km, (void*)g->sub[t].keys); Kfree(g->km, g->sub[t].used); } \ + Kfree(g->km, g->sub); Kfree(g->km, g); \ + } \ + SCOPE kh_ensitr_t prefix##_getp(const HType *g, const khkey_t *key) { \ + khint_t hash, low, ret; \ + kh_ensitr_t r; \ + HType##_sub *h; \ + hash = __hash_fn(*key); \ + low = hash & ((1U<<g->bits) - 1); \ + h = &g->sub[low]; \ + ret = prefix##_sub_getp_core(h, key, hash); \ + if (ret == kh_end(h)) r.sub = low, r.pos = (khint_t)-1; \ + else r.sub = low, r.pos = ret; \ + return r; \ + } \ + SCOPE kh_ensitr_t prefix##_get(const HType *g, const khkey_t key) { return prefix##_getp(g, &key); } \ + SCOPE kh_ensitr_t prefix##_putp(HType *g, const khkey_t *key, int *absent) { \ + khint_t hash, low, ret; \ + kh_ensitr_t r; \ + HType##_sub *h; \ + hash = __hash_fn(*key); \ + low = hash & ((1U<<g->bits) - 1); \ + h = &g->sub[low]; \ + ret = prefix##_sub_putp_core(h, key, hash, absent); \ + if (*absent) ++g->count; \ + r.sub = low, r.pos = ret; \ + return r; \ + } \ + SCOPE kh_ensitr_t prefix##_put(HType *g, const khkey_t key, int *absent) { return prefix##_putp(g, &key, absent); } \ + SCOPE int prefix##_del(HType *g, kh_ensitr_t itr) { \ + HType##_sub *h = &g->sub[itr.sub]; \ + int ret; \ + ret = prefix##_sub_del(h, itr.pos); \ + if (ret) --g->count; \ + return ret; \ + } \ + SCOPE void prefix##_clear(HType *g) { \ + int i; \ + for (i = 0; i < 1U<<g->bits; ++i) prefix##_sub_clear(&g->sub[i]); \ + g->count = 0; \ + } + /***************************** * More convenient interface * *****************************/ -#define __kh_packed __attribute__ ((__packed__)) -#define __kh_cached_hash(x) ((x).hash) +/* common */ #define KHASHL_SET_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ - typedef struct { khkey_t key; } __kh_packed HType##_s_bucket_t; \ + typedef struct { khkey_t key; } kh_packed HType##_s_bucket_t; \ static kh_inline khint_t prefix##_s_hash(HType##_s_bucket_t x) { return __hash_fn(x.key); } \ static kh_inline int prefix##_s_eq(HType##_s_bucket_t x, HType##_s_bucket_t y) { return __hash_eq(x.key, y.key); } \ KHASHL_INIT(KH_LOCAL, HType, prefix##_s, HType##_s_bucket_t, prefix##_s_hash, prefix##_s_eq) \ SCOPE HType *prefix##_init(void) { return prefix##_s_init(); } \ + SCOPE HType *prefix##_init2(void *km) { return prefix##_s_init2(km); } \ SCOPE void prefix##_destroy(HType *h) { prefix##_s_destroy(h); } \ SCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { prefix##_s_resize(h, new_n_buckets); } \ SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_s_bucket_t t; t.key = key; return prefix##_s_getp(h, &t); } \ SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_s_del(h, k); } \ - SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_s_bucket_t t; t.key = key; return prefix##_s_putp(h, &t, absent); } + SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_s_bucket_t t; t.key = key; return prefix##_s_putp(h, &t, absent); } \ + SCOPE void prefix##_clear(HType *h) { prefix##_s_clear(h); } #define KHASHL_MAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \ - typedef struct { khkey_t key; kh_val_t val; } __kh_packed HType##_m_bucket_t; \ + typedef struct { khkey_t key; kh_val_t val; } kh_packed HType##_m_bucket_t; \ static kh_inline khint_t prefix##_m_hash(HType##_m_bucket_t x) { return __hash_fn(x.key); } \ static kh_inline int prefix##_m_eq(HType##_m_bucket_t x, HType##_m_bucket_t y) { return __hash_eq(x.key, y.key); } \ KHASHL_INIT(KH_LOCAL, HType, prefix##_m, HType##_m_bucket_t, prefix##_m_hash, prefix##_m_eq) \ SCOPE HType *prefix##_init(void) { return prefix##_m_init(); } \ + SCOPE HType *prefix##_init2(void *km) { return prefix##_m_init2(km); } \ SCOPE void prefix##_destroy(HType *h) { prefix##_m_destroy(h); } \ + SCOPE void prefix##_resize(HType *h, khint_t new_n_buckets) { prefix##_m_resize(h, new_n_buckets); } \ SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_m_bucket_t t; t.key = key; return prefix##_m_getp(h, &t); } \ SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_m_del(h, k); } \ - SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_m_bucket_t t; t.key = key; return prefix##_m_putp(h, &t, absent); } + SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_m_bucket_t t; t.key = key; return prefix##_m_putp(h, &t, absent); } \ + SCOPE void prefix##_clear(HType *h) { prefix##_m_clear(h); } + +/* cached hashes to trade memory for performance when hashing and comparison are expensive */ + +#define __kh_cached_hash(x) ((x).hash) #define KHASHL_CSET_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ - typedef struct { khkey_t key; khint_t hash; } __kh_packed HType##_cs_bucket_t; \ + typedef struct { khkey_t key; khint_t hash; } kh_packed HType##_cs_bucket_t; \ static kh_inline int prefix##_cs_eq(HType##_cs_bucket_t x, HType##_cs_bucket_t y) { return x.hash == y.hash && __hash_eq(x.key, y.key); } \ KHASHL_INIT(KH_LOCAL, HType, prefix##_cs, HType##_cs_bucket_t, __kh_cached_hash, prefix##_cs_eq) \ SCOPE HType *prefix##_init(void) { return prefix##_cs_init(); } \ SCOPE void prefix##_destroy(HType *h) { prefix##_cs_destroy(h); } \ SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_cs_bucket_t t; t.key = key; t.hash = __hash_fn(key); return prefix##_cs_getp(h, &t); } \ SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_cs_del(h, k); } \ - SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_cs_bucket_t t; t.key = key, t.hash = __hash_fn(key); return prefix##_cs_putp(h, &t, absent); } + SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_cs_bucket_t t; t.key = key, t.hash = __hash_fn(key); return prefix##_cs_putp(h, &t, absent); } \ + SCOPE void prefix##_clear(HType *h) { prefix##_cs_clear(h); } #define KHASHL_CMAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \ - typedef struct { khkey_t key; kh_val_t val; khint_t hash; } __kh_packed HType##_cm_bucket_t; \ + typedef struct { khkey_t key; kh_val_t val; khint_t hash; } kh_packed HType##_cm_bucket_t; \ static kh_inline int prefix##_cm_eq(HType##_cm_bucket_t x, HType##_cm_bucket_t y) { return x.hash == y.hash && __hash_eq(x.key, y.key); } \ KHASHL_INIT(KH_LOCAL, HType, prefix##_cm, HType##_cm_bucket_t, __kh_cached_hash, prefix##_cm_eq) \ SCOPE HType *prefix##_init(void) { return prefix##_cm_init(); } \ SCOPE void prefix##_destroy(HType *h) { prefix##_cm_destroy(h); } \ SCOPE khint_t prefix##_get(const HType *h, khkey_t key) { HType##_cm_bucket_t t; t.key = key; t.hash = __hash_fn(key); return prefix##_cm_getp(h, &t); } \ SCOPE int prefix##_del(HType *h, khint_t k) { return prefix##_cm_del(h, k); } \ - SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_cm_bucket_t t; t.key = key, t.hash = __hash_fn(key); return prefix##_cm_putp(h, &t, absent); } + SCOPE khint_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_cm_bucket_t t; t.key = key, t.hash = __hash_fn(key); return prefix##_cm_putp(h, &t, absent); } \ + SCOPE void prefix##_clear(HType *h) { prefix##_cm_clear(h); } + +/* ensemble for huge hash tables */ + +#define KHASHE_SET_INIT(SCOPE, HType, prefix, khkey_t, __hash_fn, __hash_eq) \ + typedef struct { khkey_t key; } kh_packed HType##_es_bucket_t; \ + static kh_inline khint_t prefix##_es_hash(HType##_es_bucket_t x) { return __hash_fn(x.key); } \ + static kh_inline int prefix##_es_eq(HType##_es_bucket_t x, HType##_es_bucket_t y) { return __hash_eq(x.key, y.key); } \ + KHASHE_INIT(KH_LOCAL, HType, prefix##_es, HType##_es_bucket_t, prefix##_es_hash, prefix##_es_eq) \ + SCOPE HType *prefix##_init(int bits) { return prefix##_es_init(bits); } \ + SCOPE void prefix##_destroy(HType *h) { prefix##_es_destroy(h); } \ + SCOPE kh_ensitr_t prefix##_get(const HType *h, khkey_t key) { HType##_es_bucket_t t; t.key = key; return prefix##_es_getp(h, &t); } \ + SCOPE int prefix##_del(HType *h, kh_ensitr_t k) { return prefix##_es_del(h, k); } \ + SCOPE kh_ensitr_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_es_bucket_t t; t.key = key; return prefix##_es_putp(h, &t, absent); } \ + SCOPE void prefix##_clear(HType *h) { prefix##_es_clear(h); } + +#define KHASHE_MAP_INIT(SCOPE, HType, prefix, khkey_t, kh_val_t, __hash_fn, __hash_eq) \ + typedef struct { khkey_t key; kh_val_t val; } kh_packed HType##_em_bucket_t; \ + static kh_inline khint_t prefix##_em_hash(HType##_em_bucket_t x) { return __hash_fn(x.key); } \ + static kh_inline int prefix##_em_eq(HType##_em_bucket_t x, HType##_em_bucket_t y) { return __hash_eq(x.key, y.key); } \ + KHASHE_INIT(KH_LOCAL, HType, prefix##_em, HType##_em_bucket_t, prefix##_em_hash, prefix##_em_eq) \ + SCOPE HType *prefix##_init(int bits) { return prefix##_em_init(bits); } \ + SCOPE void prefix##_destroy(HType *h) { prefix##_em_destroy(h); } \ + SCOPE kh_ensitr_t prefix##_get(const HType *h, khkey_t key) { HType##_em_bucket_t t; t.key = key; return prefix##_em_getp(h, &t); } \ + SCOPE int prefix##_del(HType *h, kh_ensitr_t k) { return prefix##_em_del(h, k); } \ + SCOPE kh_ensitr_t prefix##_put(HType *h, khkey_t key, int *absent) { HType##_em_bucket_t t; t.key = key; return prefix##_em_putp(h, &t, absent); } \ + SCOPE void prefix##_clear(HType *h) { prefix##_em_clear(h); } /************************** * Public macro functions * @@ -313,6 +427,16 @@ #define kh_val(h, x) ((h)->keys[x].val) #define kh_exist(h, x) __kh_used((h)->used, (x)) +#define kh_foreach(h, x) for ((x) = 0; (x) != kh_end(h); ++(x)) if (kh_exist((h), (x))) + +#define kh_ens_key(g, x) kh_key(&(g)->sub[(x).sub], (x).pos) +#define kh_ens_val(g, x) kh_val(&(g)->sub[(x).sub], (x).pos) +#define kh_ens_exist(g, x) kh_exist(&(g)->sub[(x).sub], (x).pos) +#define kh_ens_is_end(x) ((x).pos == (khint_t)-1) +#define kh_ens_size(g) ((g)->count) + +#define kh_ens_foreach(g, x) for ((x).sub = 0; (x).sub != 1<<(g)->bits; ++(x).sub) for ((x).pos = 0; (x).pos != kh_end(&(g)->sub[(x).sub]); ++(x).pos) if (kh_ens_exist((g), (x))) + /************************************** * Common hash and equality functions * **************************************/ @@ -321,30 +445,37 @@ #define kh_eq_str(a, b) (strcmp((a), (b)) == 0) #define kh_hash_dummy(x) ((khint_t)(x)) -static kh_inline khint_t kh_hash_uint32(khint_t key) { - key += ~(key << 15); - key ^= (key >> 10); - key += (key << 3); - key ^= (key >> 6); - key += ~(key << 11); - key ^= (key >> 16); - return key; +static kh_inline khint_t kh_hash_uint32(khint_t x) { /* murmur finishing */ + x ^= x >> 16; + x *= 0x85ebca6bU; + x ^= x >> 13; + x *= 0xc2b2ae35U; + x ^= x >> 16; + return x; } -static kh_inline khint_t kh_hash_uint64(khint64_t key) { - key = ~key + (key << 21); - key = key ^ key >> 24; - key = (key + (key << 3)) + (key << 8); - key = key ^ key >> 14; - key = (key + (key << 2)) + (key << 4); - key = key ^ key >> 28; - key = key + (key << 31); - return (khint_t)key; +static kh_inline khint_t kh_hash_uint64(khint64_t x) { /* splitmix64; see https://nullprogram.com/blog/2018/07/31/ for inversion */ + x ^= x >> 30; + x *= 0xbf58476d1ce4e5b9ULL; + x ^= x >> 27; + x *= 0x94d049bb133111ebULL; + x ^= x >> 31; + return (khint_t)x; +} + +static kh_inline khint_t kh_hash_str(kh_cstr_t s) { /* FNV1a */ + khint_t h = 2166136261U; + const unsigned char *t = (const unsigned char*)s; + for (; *t; ++t) + h ^= *t, h *= 16777619; + return h; } -static kh_inline khint_t kh_hash_str(const char *s) { - khint_t h = (khint_t)*s; - if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s; +static kh_inline khint_t kh_hash_bytes(int len, const unsigned char *s) { + khint_t h = 2166136261U; + int i; + for (i = 0; i < len; ++i) + h ^= s[i], h *= 16777619; return h; } diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/kmempool.c new/klib-1.0~git.20251221/kmempool.c --- old/klib-1.0~git.20210716/kmempool.c 1970-01-01 01:00:00.000000000 +0100 +++ new/klib-1.0~git.20251221/kmempool.c 2025-12-22 05:35:26.000000000 +0100 @@ -0,0 +1,73 @@ +#include <stdint.h> +#include <stdlib.h> +#include "kmempool.h" + +#define Malloc(type, cnt) ((type*)malloc((cnt) * sizeof(type))) +#define Calloc(type, cnt) ((type*)calloc((cnt), sizeof(type))) +#define Realloc(type, ptr, cnt) ((type*)realloc((ptr), (cnt) * sizeof(type))) + +typedef struct { + uint32_t sz; // size of an entry + uint32_t chunk_size; // number of entries in a chunk + uint32_t n_chunk; // number of chunks + uint8_t *p; // pointing to an entry that can be allocated from a chunk + uint8_t *p_end; // end of the current chunk + uint8_t **chunk; // list of chunks + uint32_t n_buf, m_buf; // number/max number of buffered free entries + void **buf; // list of pointers to free entries +} kmempool_t; + +static void kmp_add_chunk(kmempool_t *mp) // add a new chunk +{ + uint64_t x = (uint64_t)mp->sz * mp->chunk_size; + mp->chunk = Realloc(uint8_t*, mp->chunk, mp->n_chunk + 1); + mp->p = mp->chunk[mp->n_chunk++] = Calloc(uint8_t, x); + mp->p_end = mp->p + x; +} + +void *kmp_init2(unsigned sz, unsigned chunk_size) +{ + kmempool_t *mp; + mp = Calloc(kmempool_t, 1); + mp->sz = sz, mp->chunk_size = chunk_size; + kmp_add_chunk(mp); + return mp; +} + +void *kmp_init(unsigned sz) // fixed chunk size +{ + return kmp_init2(sz, 0x10000); +} + +void kmp_destroy(void *mp_) +{ + kmempool_t *mp = (kmempool_t*)mp_; + uint32_t i; + for (i = 0; i < mp->n_chunk; ++i) // free all chunks + free(mp->chunk[i]); + free(mp->chunk); free(mp->buf); free(mp); +} + +void *kmp_alloc(void *mp_) +{ + kmempool_t *mp = (kmempool_t*)mp_; + void *ret; + if (mp->n_buf > 0) { // there are buffered free entries + ret = mp->buf[--mp->n_buf]; + } else { // need to "allocate" from chunks + if (mp->p == mp->p_end) kmp_add_chunk(mp); // chunk full; add a new one + ret = (void*)mp->p; + mp->p += mp->sz; + } + return ret; +} + +void kmp_free(void *mp_, void *p) +{ + kmempool_t *mp = (kmempool_t*)mp_; + if (mp->n_buf == mp->m_buf) { // then enlarge the buffer + mp->m_buf += (mp->m_buf>>1) + 16; + mp->buf = Realloc(void*, mp->buf, mp->m_buf); + } + mp->buf[mp->n_buf++] = p; +} diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/kmempool.h new/klib-1.0~git.20251221/kmempool.h --- old/klib-1.0~git.20210716/kmempool.h 1970-01-01 01:00:00.000000000 +0100 +++ new/klib-1.0~git.20251221/kmempool.h 2025-12-22 05:35:26.000000000 +0100 @@ -0,0 +1,17 @@ +#ifndef AC_KMEMPOOL_H +#define AC_KMEMPOOL_H + +#ifdef __cplusplus +extern "C" { +#endif + +void *kmp_init(unsigned sz); +void kmp_destroy(void *mp); +void *kmp_alloc(void *mp); +void kmp_free(void *mp, void *p); + +#ifdef __cplusplus +} +#endif + +#endif diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/kseq.h new/klib-1.0~git.20251221/kseq.h --- old/klib-1.0~git.20210716/kseq.h 2021-07-16 22:45:53.000000000 +0200 +++ new/klib-1.0~git.20251221/kseq.h 2025-12-22 05:35:26.000000000 +0100 @@ -107,12 +107,12 @@ if (ks->end == -1) { ks->is_eof = 1; return -3; } \ } else break; \ } \ - if (delimiter == KS_SEP_LINE) { \ - for (i = ks->begin; i < ks->end; ++i) \ - if (ks->buf[i] == '\n') break; \ + if (delimiter == KS_SEP_LINE) { \ + unsigned char *sep = memchr(ks->buf + ks->begin, '\n', ks->end - ks->begin); \ + i = sep != NULL ? sep - ks->buf : ks->end; \ } else if (delimiter > KS_SEP_MAX) { \ - for (i = ks->begin; i < ks->end; ++i) \ - if (ks->buf[i] == delimiter) break; \ + unsigned char *sep = memchr(ks->buf + ks->begin, delimiter, ks->end - ks->begin); \ + i = sep != NULL ? sep - ks->buf : ks->end; \ } else if (delimiter == KS_SEP_SPACE) { \ for (i = ks->begin; i < ks->end; ++i) \ if (isspace(ks->buf[i])) break; \ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/test/Makefile new/klib-1.0~git.20251221/test/Makefile --- old/klib-1.0~git.20210716/test/Makefile 2021-07-16 22:45:53.000000000 +0200 +++ new/klib-1.0~git.20251221/test/Makefile 2025-12-22 05:35:26.000000000 +0100 @@ -70,3 +70,6 @@ ketopt_test:ketopt_test.c ../ketopt.h $(CC) $(CFLAGS) -o $@ ketopt_test.c + +kbarena_test:kbarena_test.c ../kbarena.h ../kbarena.c + $(CC) $(CFLAGS) -o $@ $< ../kbarena.c diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/test/kbarena_test.c new/klib-1.0~git.20251221/test/kbarena_test.c --- old/klib-1.0~git.20210716/test/kbarena_test.c 1970-01-01 01:00:00.000000000 +0100 +++ new/klib-1.0~git.20251221/test/kbarena_test.c 2025-12-22 05:35:26.000000000 +0100 @@ -0,0 +1,19 @@ +#include <stdio.h> +#include "kbarena.h" + +int main(void) +{ + int i; + void *ba; + ba = kba_init(1000); + for (i = 0; i < 100; ++i) + kba_alloc(ba, 23, 1); + kba_save(ba); + for (i = 0; i < 100; ++i) + kba_alloc(ba, 29, 1); + kba_restore(ba); + for (i = 0; i < 100; ++i) + kba_alloc(ba, 29, 1); + kba_destroy(ba); + return 0; +} diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/klib-1.0~git.20210716/test/kseq_bench2.c new/klib-1.0~git.20251221/test/kseq_bench2.c --- old/klib-1.0~git.20210716/test/kseq_bench2.c 2021-07-16 22:45:53.000000000 +0200 +++ new/klib-1.0~git.20251221/test/kseq_bench2.c 2025-12-22 05:35:26.000000000 +0100 @@ -3,6 +3,7 @@ #include <stdint.h> #include <stdlib.h> #include <fcntl.h> +#include <unistd.h> #include "kseq.h" KSTREAM_INIT(int, read, 4096)
