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