lib/libc/citrus/citrus_db_factory.c

   1 /* $FreeBSD: head/lib/libc/iconv/citrus_db_factory.c 267437 2014-06-13 08:28:51Z tijl $ */
   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
  46 struct _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
  57 struct _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
  68 int
  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
  88 void
  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
 104 static __inline size_t
 105 ceilto(size_t sz)
 106 {
 107         return ((sz + DB_ALIGN - 1) & ~(DB_ALIGN - 1));
 108 }
 109
 110 int
 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
 136 int
 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
 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
 226         *(uint8_t *)_region_offset(r, *rofs) = val;
 227         *rofs += 1;
 228 }
 229
 230 static __inline void
 231 put32(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
 239 static __inline void
 240 putpad(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
 248 static __inline void
 249 dump_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
 259 int
 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 */
 273         depp = malloc(sizeof(*depp) * df->df_num_entries);
 274         if (depp == NULL)
 275                 return (-1);
 276         for (i = 0; i < df->df_num_entries; i++)
 277                 depp[i] = NULL;
 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 }