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