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 48 struct _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 59 struct _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 70 int 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 90 void 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 106 static __inline size_t 107 ceilto(size_t sz) 108 { 109 return ((sz + DB_ALIGN - 1) & ~(DB_ALIGN - 1)); 110 } 111 112 int 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 138 int 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 152 int 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 167 int 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 182 int 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 197 int 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 211 size_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 224 static __inline void 225 put8(struct _region *r, size_t *rofs, uint8_t val) 226 { 227 228 *(uint8_t *)_region_offset(r, *rofs) = val; 229 *rofs += 1; 230 } 231 232 static __inline void 233 put32(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 241 static __inline void 242 putpad(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 250 static __inline void 251 dump_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 261 int 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