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