1/*	$NetBSD: citrus_db_factory.c,v 1.11 2021/10/29 10:54:56 nia Exp $	*/
2
3/*-
4 * Copyright (c)2003 Citrus Project,
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 *    notice, this list of conditions and the following disclaimer in the
14 *    documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28
29#if HAVE_NBTOOL_CONFIG_H
30#include "nbtool_config.h"
31#endif
32
33#include <sys/cdefs.h>
34#if defined(LIBC_SCCS) && !defined(lint)
35__RCSID("$NetBSD: citrus_db_factory.c,v 1.11 2021/10/29 10:54:56 nia Exp $");
36#endif /* LIBC_SCCS and not lint */
37
38#include <assert.h>
39#include <stdio.h>
40#include <stdlib.h>
41#include <string.h>
42#include <errno.h>
43#include <arpa/inet.h>
44#include <sys/types.h>
45#include <sys/queue.h>
46
47#include "citrus_namespace.h"
48#include "citrus_region.h"
49#include "citrus_db_file.h"
50#include "citrus_db_factory.h"
51
52struct _citrus_db_factory_entry {
53	SIMPLEQ_ENTRY(_citrus_db_factory_entry)	de_entry;
54	struct _citrus_db_factory_entry *de_next;
55	uint32_t de_hashvalue;
56	struct _region de_key;
57	int de_key_free;
58	struct _region de_data;
59	int de_data_free;
60	int de_idx;
61};
62
63struct _citrus_db_factory {
64	size_t df_num_entries;
65	SIMPLEQ_HEAD(, _citrus_db_factory_entry) df_entries;
66	size_t df_total_key_size;
67	size_t df_total_data_size;
68	uint32_t (*df_hashfunc)(void *, struct _citrus_region *);
69	void *df_hashfunc_closure;
70};
71
72#define DB_ALIGN 16
73
74int
75_citrus_db_factory_create(struct _citrus_db_factory **rdf,
76			  _citrus_db_hash_func_t hashfunc,
77			  void *hashfunc_closure)
78{
79	struct _citrus_db_factory *df;
80
81	df = malloc(sizeof(*df));
82	if (df == NULL)
83		return errno;
84	df->df_num_entries = 0;
85	df->df_total_key_size = df->df_total_data_size = 0;
86	SIMPLEQ_INIT(&df->df_entries);
87	df->df_hashfunc = hashfunc;
88	df->df_hashfunc_closure = hashfunc_closure;
89
90	*rdf = df;
91
92	return 0;
93}
94
95void
96_citrus_db_factory_free(struct _citrus_db_factory *df)
97{
98	struct _citrus_db_factory_entry *de;
99
100	while ((de = SIMPLEQ_FIRST(&df->df_entries)) != NULL) {
101		SIMPLEQ_REMOVE_HEAD(&df->df_entries, de_entry);
102		if (de->de_key_free)
103			free(_region_head(&de->de_key));
104		if (de->de_data_free)
105			free(_region_head(&de->de_data));
106		free(de);
107	}
108	free(df);
109}
110
111static __inline size_t
112ceilto(size_t sz)
113{
114	return (sz+DB_ALIGN-1) & ~(DB_ALIGN-1);
115}
116
117int
118_citrus_db_factory_add(struct _citrus_db_factory *df,
119		       struct _region *key, int keyfree,
120		       struct _region *data, int datafree)
121{
122	struct _citrus_db_factory_entry *de;
123
124	de = malloc(sizeof(*de));
125	if (de == NULL)
126		return -1;
127
128	de->de_hashvalue = df->df_hashfunc(df->df_hashfunc_closure, key);
129	de->de_key = *key;
130	de->de_key_free = keyfree;
131	de->de_data = *data;
132	de->de_data_free = datafree;
133	de->de_idx = -1;
134
135	SIMPLEQ_INSERT_TAIL(&df->df_entries, de, de_entry);
136	df->df_total_key_size += _region_size(key);
137	df->df_total_data_size += ceilto(_region_size(data));
138	df->df_num_entries++;
139
140	return 0;
141
142}
143
144int
145_citrus_db_factory_add_by_string(struct _citrus_db_factory *df,
146				 const char *key,
147				 struct _citrus_region *data, int datafree)
148{
149	struct _region r;
150	char *tmp;
151	tmp = strdup(key);
152	if (tmp == NULL)
153		return errno;
154	_region_init(&r, tmp, strlen(key));
155	return _citrus_db_factory_add(df, &r, 1, data, datafree);
156}
157
158int
159_citrus_db_factory_add8_by_string(struct _citrus_db_factory *df,
160				  const char *key, uint8_t val)
161{
162	struct _region r;
163	uint8_t *p;
164
165	p = malloc(sizeof(*p));
166	if (p == NULL)
167		return errno;
168	*p = val;
169	_region_init(&r, p, 1);
170	return _citrus_db_factory_add_by_string(df, key, &r, 1);
171}
172
173int
174_citrus_db_factory_add16_by_string(struct _citrus_db_factory *df,
175				   const char *key, uint16_t val)
176{
177	struct _region r;
178	uint16_t *p;
179
180	p = malloc(sizeof(*p));
181	if (p == NULL)
182		return errno;
183	*p = htons(val);
184	_region_init(&r, p, 2);
185	return _citrus_db_factory_add_by_string(df, key, &r, 1);
186}
187
188int
189_citrus_db_factory_add32_by_string(struct _citrus_db_factory *df,
190				   const char *key, uint32_t val)
191{
192	struct _region r;
193	uint32_t *p;
194
195	p = malloc(sizeof(*p));
196	if (p == NULL)
197		return errno;
198	*p = htonl(val);
199	_region_init(&r, p, 4);
200	return _citrus_db_factory_add_by_string(df, key, &r, 1);
201}
202
203int
204_citrus_db_factory_add_string_by_string(struct _citrus_db_factory *df,
205					const char *key, const char *data)
206{
207	char *p;
208	struct _region r;
209
210	p = strdup(data);
211	if (p == NULL)
212		return errno;
213	_region_init(&r, p, strlen(p)+1);
214	return _citrus_db_factory_add_by_string(df, key, &r, 1);
215}
216
217size_t
218_citrus_db_factory_calc_size(struct _citrus_db_factory *df)
219{
220	size_t sz;
221
222	sz = ceilto(_CITRUS_DB_HEADER_SIZE);
223	sz += ceilto(_CITRUS_DB_ENTRY_SIZE * df->df_num_entries);
224	sz += ceilto(df->df_total_key_size);
225	sz += df->df_total_data_size;
226
227	return sz;
228}
229
230static __inline void
231put8(struct _region *r, size_t *rofs, uint8_t val)
232{
233	*(uint8_t *)_region_offset(r, *rofs) = val;
234	*rofs += 1;
235}
236
237static __inline void
238put32(struct _region *r, size_t *rofs, uint32_t val)
239{
240	val = htonl(val);
241	memcpy(_region_offset(r, *rofs), &val, 4);
242	*rofs += 4;
243}
244
245static __inline void
246putpad(struct _region *r, size_t *rofs)
247{
248	size_t i;
249	for (i = ceilto(*rofs) - *rofs; i > 0; i--)
250		put8(r, rofs, 0);
251}
252
253static __inline void
254dump_header(struct _region *r, const char *magic, size_t *rofs,
255	    size_t num_entries)
256{
257	while (*rofs<_CITRUS_DB_MAGIC_SIZE)
258		put8(r, rofs, *magic++);
259	put32(r, rofs, num_entries);
260	put32(r, rofs, _CITRUS_DB_HEADER_SIZE);
261}
262
263int
264_citrus_db_factory_serialize(struct _citrus_db_factory *df, const char *magic,
265			     struct _region *r)
266{
267	size_t i, ofs, keyofs, dataofs, nextofs;
268	struct _citrus_db_factory_entry *de, **depp, *det;
269
270	ofs = 0;
271	/* check whether more than 0 entries exist */
272	if (df->df_num_entries == 0) {
273		dump_header(r, magic, &ofs, 0);
274		return 0;
275	}
276	/* allocate hash table */
277	depp = calloc(df->df_num_entries, sizeof(*depp));
278	if (depp == NULL)
279		return -1;
280
281	/* step1: store the entries which are not conflicting */
282	SIMPLEQ_FOREACH(de, &df->df_entries, de_entry) {
283		de->de_hashvalue %= df->df_num_entries;
284		de->de_idx = -1;
285		de->de_next = NULL;
286		if (depp[de->de_hashvalue] == NULL) {
287			depp[de->de_hashvalue] = de;
288			de->de_idx = (int)de->de_hashvalue;
289		}
290	}
291
292	/* step2: resolve conflicts */
293	i = 0;
294	SIMPLEQ_FOREACH(de, &df->df_entries, de_entry) {
295		if (de->de_idx == -1) {
296			det = depp[de->de_hashvalue];
297			while (det->de_next != NULL)
298				det = det->de_next;
299			det->de_next = de;
300			while (depp[i] != NULL)
301				i++;
302			depp[i] = de;
303			de->de_idx = (int)i;
304		}
305	}
306
307	keyofs =
308	    _CITRUS_DB_HEADER_SIZE +
309	    ceilto(df->df_num_entries*_CITRUS_DB_ENTRY_SIZE);
310	dataofs = keyofs + ceilto(df->df_total_key_size);
311
312	/* dump header */
313	dump_header(r, magic, &ofs, df->df_num_entries);
314
315	/* dump entries */
316	for (i = 0; i < df->df_num_entries; i++) {
317		de = depp[i];
318		nextofs = 0;
319		if (de->de_next) {
320			nextofs =
321			    _CITRUS_DB_HEADER_SIZE +
322			    de->de_next->de_idx * _CITRUS_DB_ENTRY_SIZE;
323		}
324		put32(r, &ofs, de->de_hashvalue);
325		put32(r, &ofs, nextofs);
326		put32(r, &ofs, keyofs);
327		put32(r, &ofs, _region_size(&de->de_key));
328		put32(r, &ofs, dataofs);
329		put32(r, &ofs, _region_size(&de->de_data));
330		memcpy(_region_offset(r, keyofs),
331		       _region_head(&de->de_key), _region_size(&de->de_key));
332		keyofs += _region_size(&de->de_key);
333		memcpy(_region_offset(r, dataofs),
334		       _region_head(&de->de_data), _region_size(&de->de_data));
335		dataofs += _region_size(&de->de_data);
336		putpad(r, &dataofs);
337	}
338	putpad(r, &ofs);
339	putpad(r, &keyofs);
340	free(depp);
341
342	return 0;
343}
344