1219019Sgabor/* $FreeBSD$ */ 2263986Stijl/* $NetBSD: citrus_db_factory.c,v 1.10 2013/09/14 13:05:51 joerg Exp $ */ 3219019Sgabor 4219019Sgabor/*- 5219019Sgabor * Copyright (c)2003 Citrus Project, 6219019Sgabor * All rights reserved. 7219019Sgabor * 8219019Sgabor * Redistribution and use in source and binary forms, with or without 9219019Sgabor * modification, are permitted provided that the following conditions 10219019Sgabor * are met: 11219019Sgabor * 1. Redistributions of source code must retain the above copyright 12219019Sgabor * notice, this list of conditions and the following disclaimer. 13219019Sgabor * 2. Redistributions in binary form must reproduce the above copyright 14219019Sgabor * notice, this list of conditions and the following disclaimer in the 15219019Sgabor * documentation and/or other materials provided with the distribution. 16219019Sgabor * 17219019Sgabor * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18219019Sgabor * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19219019Sgabor * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20219019Sgabor * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21219019Sgabor * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22219019Sgabor * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23219019Sgabor * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24219019Sgabor * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25219019Sgabor * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26219019Sgabor * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27219019Sgabor * SUCH DAMAGE. 28219019Sgabor */ 29219019Sgabor 30219019Sgabor#include <sys/cdefs.h> 31219019Sgabor#include <sys/types.h> 32219019Sgabor#include <sys/queue.h> 33219019Sgabor 34219019Sgabor#include <arpa/inet.h> 35219019Sgabor#include <assert.h> 36219019Sgabor#include <errno.h> 37219019Sgabor#include <stdio.h> 38219019Sgabor#include <stdlib.h> 39219019Sgabor#include <string.h> 40219019Sgabor 41219019Sgabor#include "citrus_namespace.h" 42219019Sgabor#include "citrus_region.h" 43219019Sgabor#include "citrus_db_file.h" 44219019Sgabor#include "citrus_db_factory.h" 45219019Sgabor 46219019Sgaborstruct _citrus_db_factory_entry { 47219019Sgabor STAILQ_ENTRY(_citrus_db_factory_entry) de_entry; 48219019Sgabor struct _citrus_db_factory_entry *de_next; 49219019Sgabor uint32_t de_hashvalue; 50219019Sgabor struct _region de_key; 51219019Sgabor int de_key_free; 52219019Sgabor struct _region de_data; 53219019Sgabor int de_data_free; 54219019Sgabor int de_idx; 55219019Sgabor}; 56219019Sgabor 57219019Sgaborstruct _citrus_db_factory { 58219019Sgabor size_t df_num_entries; 59219019Sgabor STAILQ_HEAD(, _citrus_db_factory_entry) df_entries; 60219019Sgabor size_t df_total_key_size; 61219019Sgabor size_t df_total_data_size; 62219019Sgabor uint32_t (*df_hashfunc)(struct _citrus_region *); 63219019Sgabor void *df_hashfunc_closure; 64219019Sgabor}; 65219019Sgabor 66219019Sgabor#define DB_ALIGN 16 67219019Sgabor 68219019Sgaborint 69219019Sgabor_citrus_db_factory_create(struct _citrus_db_factory **rdf, 70219019Sgabor _citrus_db_hash_func_t hashfunc, void *hashfunc_closure) 71219019Sgabor{ 72219019Sgabor struct _citrus_db_factory *df; 73219019Sgabor 74219019Sgabor df = malloc(sizeof(*df)); 75219019Sgabor if (df == NULL) 76219019Sgabor return (errno); 77219019Sgabor df->df_num_entries = 0; 78219019Sgabor df->df_total_key_size = df->df_total_data_size = 0; 79219019Sgabor STAILQ_INIT(&df->df_entries); 80219019Sgabor df->df_hashfunc = hashfunc; 81219019Sgabor df->df_hashfunc_closure = hashfunc_closure; 82219019Sgabor 83219019Sgabor *rdf = df; 84219019Sgabor 85219019Sgabor return (0); 86219019Sgabor} 87219019Sgabor 88219019Sgaborvoid 89219019Sgabor_citrus_db_factory_free(struct _citrus_db_factory *df) 90219019Sgabor{ 91219019Sgabor struct _citrus_db_factory_entry *de; 92219019Sgabor 93219019Sgabor while ((de = STAILQ_FIRST(&df->df_entries)) != NULL) { 94219019Sgabor STAILQ_REMOVE_HEAD(&df->df_entries, de_entry); 95219019Sgabor if (de->de_key_free) 96219019Sgabor free(_region_head(&de->de_key)); 97219019Sgabor if (de->de_data_free) 98219019Sgabor free(_region_head(&de->de_data)); 99219019Sgabor free(de); 100219019Sgabor } 101219019Sgabor free(df); 102219019Sgabor} 103219019Sgabor 104219019Sgaborstatic __inline size_t 105219019Sgaborceilto(size_t sz) 106219019Sgabor{ 107219019Sgabor return ((sz + DB_ALIGN - 1) & ~(DB_ALIGN - 1)); 108219019Sgabor} 109219019Sgabor 110219019Sgaborint 111219019Sgabor_citrus_db_factory_add(struct _citrus_db_factory *df, struct _region *key, 112219019Sgabor int keyfree, struct _region *data, int datafree) 113219019Sgabor{ 114219019Sgabor struct _citrus_db_factory_entry *de; 115219019Sgabor 116219019Sgabor de = malloc(sizeof(*de)); 117219019Sgabor if (de == NULL) 118219019Sgabor return (-1); 119219019Sgabor 120219019Sgabor de->de_hashvalue = df->df_hashfunc(key); 121219019Sgabor de->de_key = *key; 122219019Sgabor de->de_key_free = keyfree; 123219019Sgabor de->de_data = *data; 124219019Sgabor de->de_data_free = datafree; 125219019Sgabor de->de_idx = -1; 126219019Sgabor 127219019Sgabor STAILQ_INSERT_TAIL(&df->df_entries, de, de_entry); 128219019Sgabor df->df_total_key_size += _region_size(key); 129219019Sgabor df->df_total_data_size += ceilto(_region_size(data)); 130219019Sgabor df->df_num_entries++; 131219019Sgabor 132219019Sgabor return (0); 133219019Sgabor 134219019Sgabor} 135219019Sgabor 136219019Sgaborint 137219019Sgabor_citrus_db_factory_add_by_string(struct _citrus_db_factory *df, 138219019Sgabor const char *key, struct _citrus_region *data, int datafree) 139219019Sgabor{ 140219019Sgabor struct _region r; 141219019Sgabor char *tmp; 142219019Sgabor 143219019Sgabor tmp = strdup(key); 144219019Sgabor if (tmp == NULL) 145219019Sgabor return (errno); 146219019Sgabor _region_init(&r, tmp, strlen(key)); 147219019Sgabor return _citrus_db_factory_add(df, &r, 1, data, datafree); 148219019Sgabor} 149219019Sgabor 150219019Sgaborint 151219019Sgabor_citrus_db_factory_add8_by_string(struct _citrus_db_factory *df, 152219019Sgabor const char *key, uint8_t val) 153219019Sgabor{ 154219019Sgabor struct _region r; 155219019Sgabor uint8_t *p; 156219019Sgabor 157219019Sgabor p = malloc(sizeof(*p)); 158219019Sgabor if (p == NULL) 159219019Sgabor return (errno); 160219019Sgabor *p = val; 161219019Sgabor _region_init(&r, p, 1); 162219019Sgabor return (_citrus_db_factory_add_by_string(df, key, &r, 1)); 163219019Sgabor} 164219019Sgabor 165219019Sgaborint 166219019Sgabor_citrus_db_factory_add16_by_string(struct _citrus_db_factory *df, 167219019Sgabor const char *key, uint16_t val) 168219019Sgabor{ 169219019Sgabor struct _region r; 170219019Sgabor uint16_t *p; 171219019Sgabor 172219019Sgabor p = malloc(sizeof(*p)); 173219019Sgabor if (p == NULL) 174219019Sgabor return (errno); 175219019Sgabor *p = htons(val); 176219019Sgabor _region_init(&r, p, 2); 177219019Sgabor return (_citrus_db_factory_add_by_string(df, key, &r, 1)); 178219019Sgabor} 179219019Sgabor 180219019Sgaborint 181219019Sgabor_citrus_db_factory_add32_by_string(struct _citrus_db_factory *df, 182219019Sgabor const char *key, uint32_t val) 183219019Sgabor{ 184219019Sgabor struct _region r; 185219019Sgabor uint32_t *p; 186219019Sgabor 187219019Sgabor p = malloc(sizeof(*p)); 188219019Sgabor if (p == NULL) 189219019Sgabor return (errno); 190219019Sgabor *p = htonl(val); 191219019Sgabor _region_init(&r, p, 4); 192219019Sgabor return (_citrus_db_factory_add_by_string(df, key, &r, 1)); 193219019Sgabor} 194219019Sgabor 195219019Sgaborint 196219019Sgabor_citrus_db_factory_add_string_by_string(struct _citrus_db_factory *df, 197219019Sgabor const char *key, const char *data) 198219019Sgabor{ 199219019Sgabor char *p; 200219019Sgabor struct _region r; 201219019Sgabor 202219019Sgabor p = strdup(data); 203219019Sgabor if (p == NULL) 204219019Sgabor return (errno); 205219019Sgabor _region_init(&r, p, strlen(p) + 1); 206219019Sgabor return (_citrus_db_factory_add_by_string(df, key, &r, 1)); 207219019Sgabor} 208219019Sgabor 209219019Sgaborsize_t 210219019Sgabor_citrus_db_factory_calc_size(struct _citrus_db_factory *df) 211219019Sgabor{ 212219019Sgabor size_t sz; 213219019Sgabor 214219019Sgabor sz = ceilto(_CITRUS_DB_HEADER_SIZE); 215219019Sgabor sz += ceilto(_CITRUS_DB_ENTRY_SIZE * df->df_num_entries); 216219019Sgabor sz += ceilto(df->df_total_key_size); 217219019Sgabor sz += df->df_total_data_size; 218219019Sgabor 219219019Sgabor return (sz); 220219019Sgabor} 221219019Sgabor 222219019Sgaborstatic __inline void 223219019Sgaborput8(struct _region *r, size_t *rofs, uint8_t val) 224219019Sgabor{ 225219019Sgabor 226219019Sgabor *(uint8_t *)_region_offset(r, *rofs) = val; 227219019Sgabor *rofs += 1; 228219019Sgabor} 229219019Sgabor 230219019Sgaborstatic __inline void 231219019Sgaborput32(struct _region *r, size_t *rofs, uint32_t val) 232219019Sgabor{ 233219019Sgabor 234219019Sgabor val = htonl(val); 235219019Sgabor memcpy(_region_offset(r, *rofs), &val, 4); 236219019Sgabor *rofs += 4; 237219019Sgabor} 238219019Sgabor 239219019Sgaborstatic __inline void 240219019Sgaborputpad(struct _region *r, size_t *rofs) 241219019Sgabor{ 242219019Sgabor size_t i; 243219019Sgabor 244219019Sgabor for (i = ceilto(*rofs) - *rofs; i > 0; i--) 245219019Sgabor put8(r, rofs, 0); 246219019Sgabor} 247219019Sgabor 248219019Sgaborstatic __inline void 249219019Sgabordump_header(struct _region *r, const char *magic, size_t *rofs, 250219019Sgabor size_t num_entries) 251219019Sgabor{ 252219019Sgabor 253219019Sgabor while (*rofs<_CITRUS_DB_MAGIC_SIZE) 254219019Sgabor put8(r, rofs, *magic++); 255219019Sgabor put32(r, rofs, num_entries); 256219019Sgabor put32(r, rofs, _CITRUS_DB_HEADER_SIZE); 257219019Sgabor} 258219019Sgabor 259219019Sgaborint 260219019Sgabor_citrus_db_factory_serialize(struct _citrus_db_factory *df, const char *magic, 261219019Sgabor struct _region *r) 262219019Sgabor{ 263219019Sgabor struct _citrus_db_factory_entry *de, **depp, *det; 264219019Sgabor size_t dataofs, i, keyofs, nextofs, ofs; 265219019Sgabor 266219019Sgabor ofs = 0; 267219019Sgabor /* check whether more than 0 entries exist */ 268219019Sgabor if (df->df_num_entries == 0) { 269219019Sgabor dump_header(r, magic, &ofs, 0); 270219019Sgabor return (0); 271219019Sgabor } 272219019Sgabor /* allocate hash table */ 273267437Stijl depp = calloc(df->df_num_entries, sizeof(*depp)); 274219019Sgabor if (depp == NULL) 275219019Sgabor return (-1); 276219019Sgabor 277219019Sgabor /* step1: store the entries which are not conflicting */ 278219019Sgabor STAILQ_FOREACH(de, &df->df_entries, de_entry) { 279219019Sgabor de->de_hashvalue %= df->df_num_entries; 280219019Sgabor de->de_idx = -1; 281219019Sgabor de->de_next = NULL; 282219019Sgabor if (depp[de->de_hashvalue] == NULL) { 283219019Sgabor depp[de->de_hashvalue] = de; 284219019Sgabor de->de_idx = (int)de->de_hashvalue; 285219019Sgabor } 286219019Sgabor } 287219019Sgabor 288219019Sgabor /* step2: resolve conflicts */ 289219019Sgabor i = 0; 290219019Sgabor STAILQ_FOREACH(de, &df->df_entries, de_entry) { 291219019Sgabor if (de->de_idx == -1) { 292219019Sgabor det = depp[de->de_hashvalue]; 293219019Sgabor while (det->de_next != NULL) 294219019Sgabor det = det->de_next; 295219019Sgabor det->de_next = de; 296219019Sgabor while (depp[i] != NULL) 297219019Sgabor i++; 298219019Sgabor depp[i] = de; 299219019Sgabor de->de_idx = (int)i; 300219019Sgabor } 301219019Sgabor } 302219019Sgabor 303219019Sgabor keyofs = _CITRUS_DB_HEADER_SIZE + 304219019Sgabor ceilto(df->df_num_entries*_CITRUS_DB_ENTRY_SIZE); 305219019Sgabor dataofs = keyofs + ceilto(df->df_total_key_size); 306219019Sgabor 307219019Sgabor /* dump header */ 308219019Sgabor dump_header(r, magic, &ofs, df->df_num_entries); 309219019Sgabor 310219019Sgabor /* dump entries */ 311219019Sgabor for (i = 0; i < df->df_num_entries; i++) { 312219019Sgabor de = depp[i]; 313219019Sgabor nextofs = 0; 314219019Sgabor if (de->de_next) { 315219019Sgabor nextofs = _CITRUS_DB_HEADER_SIZE + 316219019Sgabor de->de_next->de_idx * _CITRUS_DB_ENTRY_SIZE; 317219019Sgabor } 318219019Sgabor put32(r, &ofs, de->de_hashvalue); 319219019Sgabor put32(r, &ofs, nextofs); 320219019Sgabor put32(r, &ofs, keyofs); 321219019Sgabor put32(r, &ofs, _region_size(&de->de_key)); 322219019Sgabor put32(r, &ofs, dataofs); 323219019Sgabor put32(r, &ofs, _region_size(&de->de_data)); 324219019Sgabor memcpy(_region_offset(r, keyofs), 325219019Sgabor _region_head(&de->de_key), _region_size(&de->de_key)); 326219019Sgabor keyofs += _region_size(&de->de_key); 327219019Sgabor memcpy(_region_offset(r, dataofs), 328219019Sgabor _region_head(&de->de_data), _region_size(&de->de_data)); 329219019Sgabor dataofs += _region_size(&de->de_data); 330219019Sgabor putpad(r, &dataofs); 331219019Sgabor } 332219019Sgabor putpad(r, &ofs); 333219019Sgabor putpad(r, &keyofs); 334219019Sgabor free(depp); 335219019Sgabor 336219019Sgabor return (0); 337219019Sgabor} 338