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