~lattis/muon

ref: 49a50d56c57dfdf470b4bcbffc16bc5ec92dcb4e muon/src/data/bucket_array.c -rw-r--r-- 2.4 KiB
49a50d56Stone Tickle support comma seperated option array 9 months ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include "posix.h"

#include <string.h>
#include <stdint.h>
#include <assert.h>

#include "data/bucket_array.h"
#include "log.h"
#include "platform/mem.h"

struct bucket {
	uint8_t *mem;
	uint32_t len;
};

static void
init_bucket(struct bucket_array *ba, struct bucket *b)
{
	b->mem = z_calloc(ba->item_size, ba->bucket_size);
}

void
bucket_array_init(struct bucket_array *ba,
	uint32_t bucket_size, uint32_t item_size)
{
	assert(item_size > 0);

	*ba = (struct bucket_array) {
		.item_size = item_size,
		.bucket_size = bucket_size,
	};

	darr_init(&ba->buckets, 1, sizeof(struct bucket));

	darr_push(&ba->buckets, &(struct bucket) { 0 });
	init_bucket(ba, darr_get(&ba->buckets, 0));
}

void
bucket_array_clear(struct bucket_array *ba)
{
	uint32_t i;
	struct bucket *b;

	for (i = 0; i < ba->buckets.len; ++i) {
		b = darr_get(&ba->buckets, i);
		b->len = 0;
	}

	ba->buckets.len = 1;
	ba->len = 0;
}

void *
bucket_array_pushn(struct bucket_array *ba, const void *data, uint32_t len, uint32_t reserve)
{
	void *dest;
	struct bucket *b;

	assert(reserve >= len);
	assert(reserve < ba->bucket_size);

	b = darr_get(&ba->buckets, ba->buckets.len - 1);
	if (b->len + reserve > ba->bucket_size) {
		darr_push(&ba->buckets, &(struct bucket) { 0 });
		b = darr_get(&ba->buckets, ba->buckets.len - 1);
		init_bucket(ba, b);
	}

	dest = b->mem + (b->len * ba->item_size);
	memcpy(dest, data, ba->item_size * len);
	b->len += reserve;
	ba->len += reserve;

	return dest;
}

void *
bucket_array_push(struct bucket_array *ba, const void *item)
{
	return bucket_array_pushn(ba, item, 1, 1);
}

void *
bucket_array_get(const struct bucket_array *ba, uint32_t i)
{
	struct bucket *b;
	uint32_t bucket_i = i % ba->bucket_size;

	b = darr_get(&ba->buckets, i / ba->bucket_size);
	assert(bucket_i < b->len);

	return b->mem + (bucket_i * ba->item_size);
}

void
bucket_array_destroy(struct bucket_array *ba)
{
	uint32_t i;

	struct bucket *b;

	for (i = 0; i < ba->buckets.len; ++i) {
		b = darr_get(&ba->buckets, i);

		z_free(b->mem);
	}

	darr_destroy(&ba->buckets);
}

bool
bucket_array_lookup_pointer(struct bucket_array *ba, const uint8_t *p, uint32_t *ret)
{
	uint32_t i;
	for (i = 0; i < ba->buckets.len; ++i) {
		struct bucket *b = b = darr_get(&ba->buckets, i);

		if (b->mem <= p && p < b->mem + (b->len * ba->item_size)) {
			*ret = i * ba->bucket_size + (p - b->mem) / ba->item_size;
			return true;
		}
	}

	return false;
}