Ydb stable 23-1-2623.1.26

x-stable-origin-commit: 22184a7e157553d447f17a2dffc4ea2d32dfd74d

1 files changed, 416 insertions, 0 deletions

diff --git a/contrib/libs/libfyaml/src/lib/fy-accel.c b/contrib/libs/libfyaml/src/lib/fy-accel.c
new file mode 100644
index 0000000000..1b1ac99f32
--- /dev/null
+++ b/contrib/libs/libfyaml/src/lib/fy-accel.c
@@ -0,0 +1,416 @@
+/*
+ * fy-accel.c - YAML accelerated access methods
+ *
+ * Copyright (c) 2019 Pantelis Antoniou <pantelis.antoniou@konsulko.com>
+ *
+ * SPDX-License-Identifier: MIT
+ */
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <limits.h>
+#include <string.h>
+
+#include <libfyaml.h>
+
+#include "fy-parse.h"
+#include "fy-doc.h"
+
+#include "fy-accel.h"
+
+#define XXH_STATIC_LINKING_ONLY
+#include "xxhash.h"
+
+/* powers of two and the closest primes before
+ *
+ * pow2:  1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536
+ * prime: 1 2 3 7 13 31 61 127 251 509 1021 2039 4093 8191 16381 32749 65521
+ *
+ * pow2:  131072 262144 524288
+ * prime: 130657 262051 524201
+ */
+
+/* 64K bucket should be enough for everybody */
+static const uint32_t prime_lt_pow2[] = {
+	1, 2, 3, 7, 13, 31, 61, 127, 251, 509, 1021,
+	2039, 4093, 8191, 16381, 32749, 65521,
+	130657, 262051, 524201
+};
+
+static inline unsigned int
+fy_accel_hash_to_pos(struct fy_accel *xl, const void *hash, unsigned int nbuckets)
+{
+	uint64_t pos;
+
+	switch (xl->hd->size) {
+	case 1:
+		pos = *(const uint8_t *)hash;
+		break;
+	case 2:
+		assert(!((uintptr_t)hash & 1));
+		pos = *(const uint16_t *)hash;
+		break;
+	case 4:
+		assert(!((uintptr_t)hash & 3));
+		pos = *(const uint32_t *)hash;
+		break;
+	case 8:
+		assert(!((uintptr_t)hash & 7));
+		pos = *(const uint64_t *)hash;
+		break;
+	default:
+		/* sigh, what ever */
+		pos = XXH32(hash, xl->hd->size, 0);
+		break;
+	}
+
+	return (unsigned int)(pos % nbuckets);
+}
+
+static inline bool
+fy_accel_hash_eq(struct fy_accel *xl, const void *hash1, const void *hash2)
+{
+	switch (xl->hd->size) {
+	case 1:
+		return *(const uint8_t *)hash1 == *(const uint8_t *)hash2;
+	case 2:
+		assert(!((uintptr_t)hash1 & 1));
+		assert(!((uintptr_t)hash2 & 1));
+		return *(const uint16_t *)hash1 == *(const uint16_t *)hash2;
+	case 4:
+		assert(!((uintptr_t)hash1 & 3));
+		assert(!((uintptr_t)hash2 & 3));
+		return *(const uint32_t *)hash1 == *(const uint32_t *)hash2;
+	case 8:
+		assert(!((uintptr_t)hash1 & 7));
+		assert(!((uintptr_t)hash2 & 7));
+		return *(const uint64_t *)hash1 == *(const uint64_t *)hash2;
+	default:
+		break;
+	}
+
+	return !memcmp(hash1, hash2, xl->hd->size);
+}
+
+int fy_accel_resize(struct fy_accel *xl, unsigned int min_buckets)
+{
+	unsigned int next_pow2, exp, i, nbuckets, pos;
+	struct fy_accel_entry_list *xlel;
+	struct fy_accel_entry *xle;
+	struct fy_accel_entry_list *buckets_new;
+
+	/* get the next power of two larger or equal */
+	next_pow2 = 1;
+	exp = 0;
+	while (next_pow2 < min_buckets &&
+	       exp < sizeof(prime_lt_pow2)/sizeof(prime_lt_pow2[0])) {
+		next_pow2 <<= 1;
+		exp++;
+	}
+
+	nbuckets = prime_lt_pow2[exp];
+	if (nbuckets == xl->nbuckets)
+		return 0;
+
+	buckets_new = malloc(sizeof(*buckets_new) * nbuckets);
+	if (!buckets_new)
+		return -1;
+
+	for (i = 0, xlel = buckets_new; i < nbuckets; i++, xlel++)
+		fy_accel_entry_list_init(xlel);
+
+	if (xl->buckets) {
+		for (i = 0, xlel = xl->buckets; i < xl->nbuckets; i++, xlel++) {
+			while ((xle = fy_accel_entry_list_pop(xlel)) != NULL) {
+				pos = fy_accel_hash_to_pos(xl, xle->hash, nbuckets);
+				fy_accel_entry_list_add_tail(&buckets_new[pos], xle);
+			}
+		}
+		free(xl->buckets);
+	}
+	xl->buckets = buckets_new;
+	xl->nbuckets = nbuckets;
+	xl->next_exp2 = exp;
+
+	return 0;
+}
+
+int fy_accel_grow(struct fy_accel *xl)
+{
+	if (!xl)
+		return -1;
+
+	/* should not grow indefinetely */
+	if (xl->next_exp2 >= sizeof(prime_lt_pow2)/sizeof(prime_lt_pow2[0]))
+		return -1;
+
+	return fy_accel_resize(xl, prime_lt_pow2[xl->next_exp2 + 1]);
+}
+
+int fy_accel_shrink(struct fy_accel *xl)
+{
+	if (!xl)
+		return -1;
+
+	/* should not shrink indefinetely */
+	if (xl->next_exp2 <= 0)
+		return -1;
+
+	return fy_accel_resize(xl, prime_lt_pow2[xl->next_exp2 - 1]);
+}
+
+int
+fy_accel_setup(struct fy_accel *xl,
+	       const struct fy_hash_desc *hd,
+	       void *userdata,
+	       unsigned int min_buckets)
+{
+	if (!xl || !hd || !hd->size || !hd->hash)
+		return -1;
+
+	memset(xl, 0, sizeof(*xl));
+	xl->hd = hd;
+	xl->userdata = userdata;
+	xl->count = 0;
+
+	return fy_accel_resize(xl, min_buckets);
+}
+
+void fy_accel_cleanup(struct fy_accel *xl)
+{
+	unsigned int i;
+	struct fy_accel_entry_list *xlel;
+	struct fy_accel_entry *xle;
+
+	if (!xl)
+		return;
+
+	for (i = 0, xlel = xl->buckets; i < xl->nbuckets; i++, xlel++) {
+		while ((xle = fy_accel_entry_list_pop(xlel)) != NULL) {
+			free(xle);
+			assert(xl->count > 0);
+			xl->count--;
+		}
+	}
+
+	free(xl->buckets);
+}
+
+struct fy_accel_entry *
+fy_accel_entry_insert(struct fy_accel *xl, const void *key, const void *value)
+{
+	struct fy_accel_entry *xle, *xlet;
+	struct fy_accel_entry_list *xlel;
+	unsigned int pos, bucket_size;
+	int rc;
+
+	if (!xl)
+		return NULL;
+
+	xle = malloc(sizeof(*xle) + xl->hd->size);
+	if (!xle)
+		goto err_out;
+
+	rc = xl->hd->hash(xl, key, xl->userdata, xle->hash);
+	if (rc)
+		goto err_out;
+	xle->key = key;
+	xle->value = value;
+
+	pos = fy_accel_hash_to_pos(xl, xle->hash, xl->nbuckets);
+	xlel = &xl->buckets[pos];
+
+	fy_accel_entry_list_add_tail(xlel, xle);
+
+	assert(xl->count < UINT_MAX);
+	xl->count++;
+
+	/* if we don't auto-resize, return */
+	if (xl->hd->max_bucket_grow_limit) {
+		bucket_size = 0;
+		for (xlet = fy_accel_entry_list_first(xlel); xlet; xlet = fy_accel_entry_next(xlel, xlet)) {
+			bucket_size++;
+			if (bucket_size >= xl->hd->max_bucket_grow_limit)
+				break;
+		}
+
+		/* we don't really care whether the grow up succeeds or not */
+		if (bucket_size >= xl->hd->max_bucket_grow_limit)
+			(void)fy_accel_grow(xl);
+	}
+
+	return xle;
+err_out:
+	if (xle)
+		free(xle);
+	return NULL;
+}
+
+struct fy_accel_entry *
+fy_accel_entry_lookup(struct fy_accel *xl, const void *key)
+{
+	struct fy_accel_entry_iter xli;
+	struct fy_accel_entry *xle;
+
+	xle = fy_accel_entry_iter_start(&xli, xl, key);
+	fy_accel_entry_iter_finish(&xli);
+
+	return xle;
+}
+
+struct fy_accel_entry *
+fy_accel_entry_lookup_key_value(struct fy_accel *xl, const void *key, const void *value)
+{
+	struct fy_accel_entry_iter xli;
+	struct fy_accel_entry *xle;
+
+	for (xle = fy_accel_entry_iter_start(&xli, xl, key); xle;
+	     xle = fy_accel_entry_iter_next(&xli)) {
+
+		if (xle->value == value)
+			break;
+	}
+	fy_accel_entry_iter_finish(&xli);
+
+	return xle;
+}
+
+void
+fy_accel_entry_remove(struct fy_accel *xl, struct fy_accel_entry *xle)
+{
+	unsigned int pos;
+
+	if (!xl || !xle)
+		return;
+
+	pos = fy_accel_hash_to_pos(xl, xle->hash, xl->nbuckets);
+
+	fy_accel_entry_list_del(&xl->buckets[pos], xle);
+
+	assert(xl->count > 0);
+	xl->count--;
+
+	free(xle);
+}
+
+int
+fy_accel_insert(struct fy_accel *xl, const void *key, const void *value)
+{
+	struct fy_accel_entry *xle;
+
+	xle = fy_accel_entry_lookup(xl, key);
+	if (xle)
+		return -1;	/* exists */
+
+	xle = fy_accel_entry_insert(xl, key, value);
+	if (!xle)
+		return -1;	/* failure to insert */
+
+	return 0;
+}
+
+const void *
+fy_accel_lookup(struct fy_accel *xl, const void *key)
+{
+	struct fy_accel_entry *xle;
+
+	xle = fy_accel_entry_lookup(xl, key);
+	return xle ? xle->value : NULL;
+}
+
+int
+fy_accel_remove(struct fy_accel *xl, const void *data)
+{
+	struct fy_accel_entry *xle;
+
+	xle = fy_accel_entry_lookup(xl, data);
+	if (!xle)
+		return -1;
+
+	fy_accel_entry_remove(xl, xle);
+
+	return 0;
+}
+
+struct fy_accel_entry *
+fy_accel_entry_iter_next_internal(struct fy_accel_entry_iter *xli)
+{
+	struct fy_accel *xl;
+	struct fy_accel_entry *xle;
+	struct fy_accel_entry_list *xlel;
+	const void *key;
+	void *hash;
+
+	if (!xli)
+		return NULL;
+
+	xl = xli->xl;
+	hash = xli->hash;
+	xlel = xli->xlel;
+	if (!xl || !hash || !xlel)
+		return NULL;
+	key = xli->key;
+
+	xle = !xli->xle ? fy_accel_entry_list_first(xlel) :
+			  fy_accel_entry_next(xlel, xli->xle);
+	for (; xle; xle = fy_accel_entry_next(xlel, xle)) {
+		if (fy_accel_hash_eq(xl, hash, xle->hash) &&
+		    xl->hd->eq(xl, hash, xle->key, key, xl->userdata))
+			break;
+	}
+	return xli->xle = xle;
+}
+
+struct fy_accel_entry *
+fy_accel_entry_iter_start(struct fy_accel_entry_iter *xli, struct fy_accel *xl, const void *key)
+{
+	unsigned int pos;
+	int rc;
+
+	if (!xli || !xl)
+		return NULL;
+	xli->xl = xl;
+	xli->key = key;
+	if (xl->hd->size <= sizeof(xli->hash_inline))
+		xli->hash = xli->hash_inline;
+	else
+		xli->hash = malloc(xl->hd->size);
+	xli->xlel = NULL;
+
+	if (!xli->hash)
+		goto err_out;
+
+	rc = xl->hd->hash(xl, key, xl->userdata, xli->hash);
+	if (rc)
+		goto err_out;
+
+	pos = fy_accel_hash_to_pos(xl, xli->hash, xl->nbuckets);
+	xli->xlel = &xl->buckets[pos];
+
+	xli->xle = NULL;
+
+	return fy_accel_entry_iter_next_internal(xli);
+
+err_out:
+	fy_accel_entry_iter_finish(xli);
+	return NULL;
+}
+
+void fy_accel_entry_iter_finish(struct fy_accel_entry_iter *xli)
+{
+	if (!xli)
+		return;
+
+	if (xli->hash && xli->hash != xli->hash_inline)
+		free(xli->hash);
+}
+
+struct fy_accel_entry *
+fy_accel_entry_iter_next(struct fy_accel_entry_iter *xli)
+{
+	if (!xli || !xli->xle)
+		return NULL;
+
+	return fy_accel_entry_iter_next_internal(xli);
+}