lib/libc/citrus/citrus_db_factory.c

   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 }