1 /* $NetBSD: citrus_db_factory.c,v 1.1 2003/06/25 09:51:29 tshiozak 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 #include <sys/cdefs.h> 30 #if defined(LIBC_SCCS) && !defined(lint) 31 __RCSID("$NetBSD: citrus_db_factory.c,v 1.1 2003/06/25 09:51:29 tshiozak Exp $"); 32 #endif /* LIBC_SCCS and not lint */ 33 34 #include <assert.h> 35 #include <stdio.h> 36 #include <stdlib.h> 37 #include <string.h> 38 #include <errno.h> 39 #include <sys/types.h> 40 #include <sys/queue.h> 41 42 #ifndef __packed 43 #define __packed /* ignored */ 44 #endif 45 #include "citrus_namespace.h" 46 #include "citrus_region.h" 47 #include "citrus_db_file.h" 48 #include "citrus_db_factory.h" 49 50 struct _citrus_db_factory_entry { 51 SIMPLEQ_ENTRY(_citrus_db_factory_entry) de_entry; 52 struct _citrus_db_factory_entry *de_next; 53 u_int32_t de_hashvalue; 54 struct _region de_key; 55 int de_key_free; 56 struct _region de_data; 57 int de_data_free; 58 int de_idx; 59 }; 60 61 struct _citrus_db_factory { 62 size_t df_num_entries; 63 SIMPLEQ_HEAD(, _citrus_db_factory_entry) df_entries; 64 size_t df_total_key_size; 65 size_t df_total_data_size; 66 u_int32_t (*df_hashfunc)(void *, struct _citrus_region *); 67 void *df_hashfunc_closure; 68 }; 69 70 #define DB_ALIGN 16 71 72 int 73 _citrus_db_factory_create(struct _citrus_db_factory **rdf, 74 _citrus_db_hash_func_t hashfunc, 75 void *hashfunc_closure) 76 { 77 struct _citrus_db_factory *df; 78 79 df = malloc(sizeof(*df)); 80 if (df == NULL) 81 return errno; 82 df->df_num_entries = 0; 83 df->df_total_key_size = df->df_total_data_size = 0; 84 SIMPLEQ_INIT(&df->df_entries); 85 df->df_hashfunc = hashfunc; 86 df->df_hashfunc_closure = hashfunc_closure; 87 88 *rdf = df; 89 90 return 0; 91 } 92 93 void 94 _citrus_db_factory_free(struct _citrus_db_factory *df) 95 { 96 struct _citrus_db_factory_entry *de; 97 98 while ((de = SIMPLEQ_FIRST(&df->df_entries)) != NULL) { 99 SIMPLEQ_REMOVE_HEAD(&df->df_entries, de_entry); 100 if (de->de_key_free) 101 free(_region_head(&de->de_key)); 102 if (de->de_data_free) 103 free(_region_head(&de->de_data)); 104 free(de); 105 } 106 free(df); 107 } 108 109 static __inline size_t 110 ceilto(size_t sz) 111 { 112 return (sz+DB_ALIGN-1) & ~(DB_ALIGN-1); 113 } 114 115 int 116 _citrus_db_factory_add(struct _citrus_db_factory *df, 117 struct _region *key, int keyfree, 118 struct _region *data, int datafree) 119 { 120 struct _citrus_db_factory_entry *de; 121 122 de = malloc(sizeof(*de)); 123 if (de == NULL) 124 return -1; 125 126 de->de_hashvalue = df->df_hashfunc(df->df_hashfunc_closure, key); 127 de->de_key = *key; 128 de->de_key_free = keyfree; 129 de->de_data = *data; 130 de->de_data_free = datafree; 131 de->de_idx = -1; 132 133 SIMPLEQ_INSERT_TAIL(&df->df_entries, de, de_entry); 134 df->df_total_key_size += _region_size(key); 135 df->df_total_data_size += ceilto(_region_size(data)); 136 df->df_num_entries++; 137 138 return 0; 139 140 } 141 142 int 143 _citrus_db_factory_add_by_string(struct _citrus_db_factory *df, 144 const char *key, 145 struct _citrus_region *data, int datafree) 146 { 147 struct _region r; 148 char *tmp; 149 tmp = strdup(key); 150 if (tmp == NULL) 151 return errno; 152 _region_init(&r, tmp, strlen(key)); 153 return _citrus_db_factory_add(df, &r, 1, data, datafree); 154 } 155 156 int 157 _citrus_db_factory_add8_by_string(struct _citrus_db_factory *df, 158 const char *key, u_int8_t val) 159 { 160 struct _region r; 161 u_int8_t *p; 162 163 p = malloc(sizeof(*p)); 164 if (p == NULL) 165 return errno; 166 *p = val; 167 _region_init(&r, p, 1); 168 return _citrus_db_factory_add_by_string(df, key, &r, 1); 169 } 170 171 int 172 _citrus_db_factory_add16_by_string(struct _citrus_db_factory *df, 173 const char *key, u_int16_t val) 174 { 175 struct _region r; 176 u_int16_t *p; 177 178 p = malloc(sizeof(*p)); 179 if (p == NULL) 180 return errno; 181 *p = htons(val); 182 _region_init(&r, p, 2); 183 return _citrus_db_factory_add_by_string(df, key, &r, 1); 184 } 185 186 int 187 _citrus_db_factory_add32_by_string(struct _citrus_db_factory *df, 188 const char *key, u_int32_t val) 189 { 190 struct _region r; 191 u_int32_t *p; 192 193 p = malloc(sizeof(*p)); 194 if (p == NULL) 195 return errno; 196 *p = htonl(val); 197 _region_init(&r, p, 4); 198 return _citrus_db_factory_add_by_string(df, key, &r, 1); 199 } 200 201 int 202 _citrus_db_factory_add_string_by_string(struct _citrus_db_factory *df, 203 const char *key, const char *data) 204 { 205 char *p; 206 struct _region r; 207 208 p = strdup(data); 209 if (p == NULL) 210 return errno; 211 _region_init(&r, p, strlen(p)+1); 212 return _citrus_db_factory_add_by_string(df, key, &r, 1); 213 } 214 215 size_t 216 _citrus_db_factory_calc_size(struct _citrus_db_factory *df) 217 { 218 size_t sz; 219 220 sz = ceilto(_CITRUS_DB_HEADER_SIZE); 221 sz += ceilto(_CITRUS_DB_ENTRY_SIZE * df->df_num_entries); 222 sz += ceilto(df->df_total_key_size); 223 sz += df->df_total_data_size; 224 225 return sz; 226 } 227 228 static __inline void 229 put8(struct _region *r, size_t *rofs, u_int8_t val) 230 { 231 *(u_int8_t *)_region_offset(r, *rofs) = val; 232 *rofs += 1; 233 } 234 235 static __inline void 236 put16(struct _region *r, size_t *rofs, u_int16_t val) 237 { 238 val = htons(val); 239 memcpy(_region_offset(r, *rofs), &val, 2); 240 *rofs += 2; 241 } 242 243 static __inline void 244 put32(struct _region *r, size_t *rofs, u_int32_t val) 245 { 246 val = htonl(val); 247 memcpy(_region_offset(r, *rofs), &val, 4); 248 *rofs += 4; 249 } 250 251 static __inline void 252 putpad(struct _region *r, size_t *rofs) 253 { 254 size_t i; 255 for (i=ceilto(*rofs)-*rofs; i>0; i--) 256 put8(r, rofs, 0); 257 } 258 259 static __inline void 260 dump_header(struct _region *r, const char *magic, size_t *rofs, 261 size_t num_entries) 262 { 263 while (*rofs<_CITRUS_DB_MAGIC_SIZE) 264 put8(r, rofs, *magic++); 265 put32(r, rofs, num_entries); 266 put32(r, rofs, _CITRUS_DB_HEADER_SIZE); 267 } 268 269 int 270 _citrus_db_factory_serialize(struct _citrus_db_factory *df, const char *magic, 271 struct _region *r) 272 { 273 size_t i, ofs, keyofs, dataofs, nextofs; 274 struct _citrus_db_factory_entry *de, **depp, *det; 275 276 ofs = 0; 277 /* check whether more than 0 entries exist */ 278 if (df->df_num_entries == 0) { 279 dump_header(r, magic, &ofs, 0); 280 return 0; 281 } 282 /* allocate hash table */ 283 depp = malloc(sizeof(*depp)*df->df_num_entries); 284 if (depp == NULL) 285 return -1; 286 for (i=0; i<df->df_num_entries; i++) 287 *depp = NULL; 288 289 /* step1: store the entries which are not conflicting */ 290 SIMPLEQ_FOREACH(de, &df->df_entries, de_entry) { 291 de->de_hashvalue %= df->df_num_entries; 292 de->de_idx = -1; 293 de->de_next = NULL; 294 if (depp[de->de_hashvalue] == NULL) { 295 depp[de->de_hashvalue] = de; 296 de->de_idx = (int)de->de_hashvalue; 297 } 298 } 299 300 /* step2: resolve conflicts */ 301 i = 0; 302 SIMPLEQ_FOREACH(de, &df->df_entries, de_entry) { 303 if (de->de_idx == -1) { 304 det = depp[de->de_hashvalue]; 305 while (det->de_next != NULL) 306 det = det->de_next; 307 det->de_next = de; 308 while (depp[i] != NULL) 309 i++; 310 depp[i] = de; 311 de->de_idx = (int)i; 312 } 313 } 314 315 keyofs = 316 _CITRUS_DB_HEADER_SIZE + 317 ceilto(df->df_num_entries*_CITRUS_DB_ENTRY_SIZE); 318 dataofs = keyofs + ceilto(df->df_total_key_size); 319 320 /* dump header */ 321 dump_header(r, magic, &ofs, df->df_num_entries); 322 323 /* dump entries */ 324 for (i=0; i<df->df_num_entries; i++) { 325 de = depp[i]; 326 nextofs = 0; 327 if (de->de_next) { 328 nextofs = 329 _CITRUS_DB_HEADER_SIZE + 330 de->de_next->de_idx * _CITRUS_DB_ENTRY_SIZE; 331 } 332 put32(r, &ofs, de->de_hashvalue); 333 put32(r, &ofs, nextofs); 334 put32(r, &ofs, keyofs); 335 put32(r, &ofs, _region_size(&de->de_key)); 336 put32(r, &ofs, dataofs); 337 put32(r, &ofs, _region_size(&de->de_data)); 338 memcpy(_region_offset(r, keyofs), 339 _region_head(&de->de_key), _region_size(&de->de_key)); 340 keyofs += _region_size(&de->de_key); 341 memcpy(_region_offset(r, dataofs), 342 _region_head(&de->de_data), _region_size(&de->de_data)); 343 dataofs += _region_size(&de->de_data); 344 putpad(r, &dataofs); 345 } 346 putpad(r, &ofs); 347 putpad(r, &keyofs); 348 free(depp); 349 350 return 0; 351 } 352