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