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 /* $DragonFly: src/lib/libc/citrus/citrus_db_factory.c,v 1.2 2008/04/10 10:21:01 hasso 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 }