2/* $NetBSD: citrus_db_factory.c,v 1.10 2013/09/14 13:05:51 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/cdefs.h> 31#include <sys/types.h> 32#include <sys/queue.h> 33 34#include <arpa/inet.h> 35#include <assert.h> 36#include <errno.h> 37#include <stdio.h> 38#include <stdlib.h> 39#include <string.h> 40 41#include "citrus_namespace.h" 42#include "citrus_region.h" 43#include "citrus_db_file.h" 44#include "citrus_db_factory.h" 45 46struct _citrus_db_factory_entry { 47 STAILQ_ENTRY(_citrus_db_factory_entry) de_entry; 48 struct _citrus_db_factory_entry *de_next; 49 uint32_t de_hashvalue; 50 struct _region de_key; 51 int de_key_free; 52 struct _region de_data; 53 int de_data_free; 54 int de_idx; 55}; 56 57struct _citrus_db_factory { 58 size_t df_num_entries; 59 STAILQ_HEAD(, _citrus_db_factory_entry) df_entries; 60 size_t df_total_key_size; 61 size_t df_total_data_size; 62 uint32_t (*df_hashfunc)(struct _citrus_region *); 63 void *df_hashfunc_closure; 64}; 65 66#define DB_ALIGN 16 67 68int 69_citrus_db_factory_create(struct _citrus_db_factory **rdf, 70 _citrus_db_hash_func_t hashfunc, void *hashfunc_closure) 71{ 72 struct _citrus_db_factory *df; 73 74 df = malloc(sizeof(*df)); 75 if (df == NULL) 76 return (errno); 77 df->df_num_entries = 0; 78 df->df_total_key_size = df->df_total_data_size = 0; 79 STAILQ_INIT(&df->df_entries); 80 df->df_hashfunc = hashfunc; 81 df->df_hashfunc_closure = hashfunc_closure; 82 83 *rdf = df; 84 85 return (0); 86} 87 88void 89_citrus_db_factory_free(struct _citrus_db_factory *df) 90{ 91 struct _citrus_db_factory_entry *de; 92 93 while ((de = STAILQ_FIRST(&df->df_entries)) != NULL) { 94 STAILQ_REMOVE_HEAD(&df->df_entries, de_entry); 95 if (de->de_key_free) 96 free(_region_head(&de->de_key)); 97 if (de->de_data_free) 98 free(_region_head(&de->de_data)); 99 free(de); 100 } 101 free(df); 102} 103 104static __inline size_t 105ceilto(size_t sz) 106{ 107 return ((sz + DB_ALIGN - 1) & ~(DB_ALIGN - 1)); 108} 109 110int 111_citrus_db_factory_add(struct _citrus_db_factory *df, struct _region *key, 112 int keyfree, 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(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 136int 137_citrus_db_factory_add_by_string(struct _citrus_db_factory *df, 138 const char *key, struct _citrus_region *data, int datafree) 139{ 140 struct _region r; 141 char *tmp; 142 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 150int 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 165int 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 180int 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 195int 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 209size_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 222static __inline void 223put8(struct _region *r, size_t *rofs, uint8_t val) 224{ 225 226 *(uint8_t *)_region_offset(r, *rofs) = val; 227 *rofs += 1; 228} 229 230static __inline void 231put32(struct _region *r, size_t *rofs, uint32_t val) 232{ 233 234 val = htonl(val); 235 memcpy(_region_offset(r, *rofs), &val, 4); 236 *rofs += 4; 237} 238 239static __inline void 240putpad(struct _region *r, size_t *rofs) 241{ 242 size_t i; 243 244 for (i = ceilto(*rofs) - *rofs; i > 0; i--) 245 put8(r, rofs, 0); 246} 247 248static __inline void 249dump_header(struct _region *r, const char *magic, size_t *rofs, 250 size_t num_entries) 251{ 252 253 while (*rofs<_CITRUS_DB_MAGIC_SIZE) 254 put8(r, rofs, *magic++); 255 put32(r, rofs, num_entries); 256 put32(r, rofs, _CITRUS_DB_HEADER_SIZE); 257} 258 259int 260_citrus_db_factory_serialize(struct _citrus_db_factory *df, const char *magic, 261 struct _region *r) 262{ 263 struct _citrus_db_factory_entry *de, **depp, *det; 264 size_t dataofs, i, keyofs, nextofs, ofs; 265 266 ofs = 0; 267 /* check whether more than 0 entries exist */ 268 if (df->df_num_entries == 0) { 269 dump_header(r, magic, &ofs, 0); 270 return (0); 271 } 272 /* allocate hash table */
| 2/* $NetBSD: citrus_db_factory.c,v 1.10 2013/09/14 13:05:51 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/cdefs.h> 31#include <sys/types.h> 32#include <sys/queue.h> 33 34#include <arpa/inet.h> 35#include <assert.h> 36#include <errno.h> 37#include <stdio.h> 38#include <stdlib.h> 39#include <string.h> 40 41#include "citrus_namespace.h" 42#include "citrus_region.h" 43#include "citrus_db_file.h" 44#include "citrus_db_factory.h" 45 46struct _citrus_db_factory_entry { 47 STAILQ_ENTRY(_citrus_db_factory_entry) de_entry; 48 struct _citrus_db_factory_entry *de_next; 49 uint32_t de_hashvalue; 50 struct _region de_key; 51 int de_key_free; 52 struct _region de_data; 53 int de_data_free; 54 int de_idx; 55}; 56 57struct _citrus_db_factory { 58 size_t df_num_entries; 59 STAILQ_HEAD(, _citrus_db_factory_entry) df_entries; 60 size_t df_total_key_size; 61 size_t df_total_data_size; 62 uint32_t (*df_hashfunc)(struct _citrus_region *); 63 void *df_hashfunc_closure; 64}; 65 66#define DB_ALIGN 16 67 68int 69_citrus_db_factory_create(struct _citrus_db_factory **rdf, 70 _citrus_db_hash_func_t hashfunc, void *hashfunc_closure) 71{ 72 struct _citrus_db_factory *df; 73 74 df = malloc(sizeof(*df)); 75 if (df == NULL) 76 return (errno); 77 df->df_num_entries = 0; 78 df->df_total_key_size = df->df_total_data_size = 0; 79 STAILQ_INIT(&df->df_entries); 80 df->df_hashfunc = hashfunc; 81 df->df_hashfunc_closure = hashfunc_closure; 82 83 *rdf = df; 84 85 return (0); 86} 87 88void 89_citrus_db_factory_free(struct _citrus_db_factory *df) 90{ 91 struct _citrus_db_factory_entry *de; 92 93 while ((de = STAILQ_FIRST(&df->df_entries)) != NULL) { 94 STAILQ_REMOVE_HEAD(&df->df_entries, de_entry); 95 if (de->de_key_free) 96 free(_region_head(&de->de_key)); 97 if (de->de_data_free) 98 free(_region_head(&de->de_data)); 99 free(de); 100 } 101 free(df); 102} 103 104static __inline size_t 105ceilto(size_t sz) 106{ 107 return ((sz + DB_ALIGN - 1) & ~(DB_ALIGN - 1)); 108} 109 110int 111_citrus_db_factory_add(struct _citrus_db_factory *df, struct _region *key, 112 int keyfree, 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(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 136int 137_citrus_db_factory_add_by_string(struct _citrus_db_factory *df, 138 const char *key, struct _citrus_region *data, int datafree) 139{ 140 struct _region r; 141 char *tmp; 142 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 150int 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 165int 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 180int 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 195int 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 209size_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 222static __inline void 223put8(struct _region *r, size_t *rofs, uint8_t val) 224{ 225 226 *(uint8_t *)_region_offset(r, *rofs) = val; 227 *rofs += 1; 228} 229 230static __inline void 231put32(struct _region *r, size_t *rofs, uint32_t val) 232{ 233 234 val = htonl(val); 235 memcpy(_region_offset(r, *rofs), &val, 4); 236 *rofs += 4; 237} 238 239static __inline void 240putpad(struct _region *r, size_t *rofs) 241{ 242 size_t i; 243 244 for (i = ceilto(*rofs) - *rofs; i > 0; i--) 245 put8(r, rofs, 0); 246} 247 248static __inline void 249dump_header(struct _region *r, const char *magic, size_t *rofs, 250 size_t num_entries) 251{ 252 253 while (*rofs<_CITRUS_DB_MAGIC_SIZE) 254 put8(r, rofs, *magic++); 255 put32(r, rofs, num_entries); 256 put32(r, rofs, _CITRUS_DB_HEADER_SIZE); 257} 258 259int 260_citrus_db_factory_serialize(struct _citrus_db_factory *df, const char *magic, 261 struct _region *r) 262{ 263 struct _citrus_db_factory_entry *de, **depp, *det; 264 size_t dataofs, i, keyofs, nextofs, ofs; 265 266 ofs = 0; 267 /* check whether more than 0 entries exist */ 268 if (df->df_num_entries == 0) { 269 dump_header(r, magic, &ofs, 0); 270 return (0); 271 } 272 /* allocate hash table */
|
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}
| 276 277 /* step1: store the entries which are not conflicting */ 278 STAILQ_FOREACH(de, &df->df_entries, de_entry) { 279 de->de_hashvalue %= df->df_num_entries; 280 de->de_idx = -1; 281 de->de_next = NULL; 282 if (depp[de->de_hashvalue] == NULL) { 283 depp[de->de_hashvalue] = de; 284 de->de_idx = (int)de->de_hashvalue; 285 } 286 } 287 288 /* step2: resolve conflicts */ 289 i = 0; 290 STAILQ_FOREACH(de, &df->df_entries, de_entry) { 291 if (de->de_idx == -1) { 292 det = depp[de->de_hashvalue]; 293 while (det->de_next != NULL) 294 det = det->de_next; 295 det->de_next = de; 296 while (depp[i] != NULL) 297 i++; 298 depp[i] = de; 299 de->de_idx = (int)i; 300 } 301 } 302 303 keyofs = _CITRUS_DB_HEADER_SIZE + 304 ceilto(df->df_num_entries*_CITRUS_DB_ENTRY_SIZE); 305 dataofs = keyofs + ceilto(df->df_total_key_size); 306 307 /* dump header */ 308 dump_header(r, magic, &ofs, df->df_num_entries); 309 310 /* dump entries */ 311 for (i = 0; i < df->df_num_entries; i++) { 312 de = depp[i]; 313 nextofs = 0; 314 if (de->de_next) { 315 nextofs = _CITRUS_DB_HEADER_SIZE + 316 de->de_next->de_idx * _CITRUS_DB_ENTRY_SIZE; 317 } 318 put32(r, &ofs, de->de_hashvalue); 319 put32(r, &ofs, nextofs); 320 put32(r, &ofs, keyofs); 321 put32(r, &ofs, _region_size(&de->de_key)); 322 put32(r, &ofs, dataofs); 323 put32(r, &ofs, _region_size(&de->de_data)); 324 memcpy(_region_offset(r, keyofs), 325 _region_head(&de->de_key), _region_size(&de->de_key)); 326 keyofs += _region_size(&de->de_key); 327 memcpy(_region_offset(r, dataofs), 328 _region_head(&de->de_data), _region_size(&de->de_data)); 329 dataofs += _region_size(&de->de_data); 330 putpad(r, &dataofs); 331 } 332 putpad(r, &ofs); 333 putpad(r, &keyofs); 334 free(depp); 335 336 return (0); 337}
|