lib/libc/iconv/citrus_db_factory.c

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