girepository/gthash.c

   1 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*-
   2  * GObject introspection: Typelib hashing
   3  *
   4  * Copyright (C) 2010 Red Hat, Inc.
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the
  18  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19  * Boston, MA 02111-1307, USA.
  20  */
  21
  22 #include <glib.h>
  23 #include <glib-object.h>
  24 #include <string.h>
  25
  26 #include "cmph/cmph.h"
  27 #include "gitypelib-internal.h"
  28
  29 #define ALIGN_VALUE(this, boundary) \
  30   (( ((unsigned long)(this)) + (((unsigned long)(boundary)) -1)) & (~(((unsigned long)(boundary))-1)))
  31
  32 /*
  33  * String hashing in the typelib.  We have a set of static (fixed) strings,
  34  * and given one, we need to find its index number.  This problem is perfect
  35  * hashing: http://en.wikipedia.org/wiki/Perfect_hashing
  36  *
  37  * I chose CMPH (http://cmph.sourceforge.net/) as it seemed high
  38  * quality, well documented, and easy to embed.
  39  *
  40  * CMPH provides a number of algorithms; I chose BDZ, because while CHD
  41  * appears to be the "best", the simplicitly of BDZ appealed, and really,
  42  * we're only talking about thousands of strings here, not millions, so
  43  * a few microseconds is no big deal.
  44  *
  45  * In memory, the format is:
  46  * INT32 mph_size
  47  * MPH (mph_size bytes)
  48  * (padding for alignment to uint32 if necessary)
  49  * INDEX (array of guint16)
  50  *
  51  * Because BDZ is not order preserving, we need a lookaside table which
  52  * maps the hash value into the directory index.
  53  */
  54
  55 struct _GITypelibHashBuilder {
  56   gboolean prepared;
  57   gboolean buildable;
  58   cmph_t *c;
  59   GHashTable *strings;
  60   guint32 dirmap_offset;
  61   guint32 packed_size;
  62 };
  63
  64 GITypelibHashBuilder *
  65 _gi_typelib_hash_builder_new (void)
  66 {
  67   GITypelibHashBuilder *builder = g_slice_new0 (GITypelibHashBuilder);
  68   builder->c = NULL;
  69   builder->strings = g_hash_table_new_full (g_str_hash, g_str_equal, g_free, NULL);
  70   return builder;
  71 }
  72
  73 void
  74 _gi_typelib_hash_builder_add_string (GITypelibHashBuilder *builder,
  75                                      const char           *str,
  76                                      guint16               value)
  77 {
  78   g_return_if_fail (builder->c == NULL);
  79   g_hash_table_insert (builder->strings, g_strdup (str), GUINT_TO_POINTER ((guint) value));
  80 }
  81
  82 gboolean
  83 _gi_typelib_hash_builder_prepare (GITypelibHashBuilder *builder)
  84 {
  85   char **strs;
  86   GHashTableIter hashiter;
  87   gpointer key, value;
  88   cmph_io_adapter_t *io;
  89   cmph_config_t *config;
  90   guint32 num_elts;
  91   guint32 offset;
  92   guint i;
  93
  94   if (builder->prepared)
  95     return builder->buildable;
  96   g_assert (builder->c == NULL);
  97
  98   num_elts = g_hash_table_size (builder->strings);
  99   g_assert (num_elts <= 65536);
 100
 101   strs = (char**) g_new (char *, num_elts + 1);
 102
 103   i = 0;
 104   g_hash_table_iter_init (&hashiter, builder->strings);
 105   while (g_hash_table_iter_next (&hashiter, &key, &value))
 106     {
 107       const char *str = key;
 108
 109       strs[i++] = g_strdup (str);
 110     }
 111   strs[i++] = NULL;
 112
 113   io = cmph_io_vector_adapter (strs, num_elts);
 114   config = cmph_config_new (io);
 115   cmph_config_set_algo (config, CMPH_BDZ);
 116
 117   builder->c = cmph_new (config);
 118   builder->prepared = TRUE;
 119   if (!builder->c)
 120     {
 121       builder->buildable = FALSE;
 122       goto out;
 123     }
 124   builder->buildable = TRUE;
 125   g_assert (cmph_size (builder->c) == num_elts);
 126
 127   /* Pack a size counter at front */
 128   offset = sizeof(guint32) + cmph_packed_size (builder->c);
 129   builder->dirmap_offset = ALIGN_VALUE (offset, 4);
 130   builder->packed_size = builder->dirmap_offset + (num_elts * sizeof(guint16));
 131  out:
 132   return builder->buildable;
 133 }
 134
 135 guint32
 136 _gi_typelib_hash_builder_get_buffer_size (GITypelibHashBuilder *builder)
 137 {
 138   g_return_val_if_fail (builder != NULL, 0);
 139   g_return_val_if_fail (builder->prepared, 0);
 140   g_return_val_if_fail (builder->buildable, 0 );
 141
 142   return builder->packed_size;
 143 }
 144
 145 void
 146 _gi_typelib_hash_builder_pack (GITypelibHashBuilder *builder, guint8* mem, guint32 len)
 147 {
 148   guint16 *table;
 149   GHashTableIter hashiter;
 150   gpointer key, value;
 151   guint32 num_elts;
 152   guint8 *packed_mem;
 153
 154   g_return_if_fail (builder != NULL);
 155   g_return_if_fail (builder->prepared);
 156   g_return_if_fail (builder->buildable);
 157
 158   g_assert (len >= builder->packed_size);
 159   g_assert ((((unsigned long)mem) & 0x3) == 0);
 160
 161   memset (mem, 0, len);
 162
 163   *((guint32*) mem) = builder->dirmap_offset;
 164   packed_mem = (guint8*)(mem + sizeof(guint32));
 165   cmph_pack (builder->c, packed_mem);
 166
 167   table = (guint16*) (mem + builder->dirmap_offset);
 168
 169   num_elts = g_hash_table_size (builder->strings);
 170   g_hash_table_iter_init (&hashiter, builder->strings);
 171   while (g_hash_table_iter_next (&hashiter, &key, &value))
 172     {
 173       const char *str = key;
 174       guint16 strval = (guint16)GPOINTER_TO_UINT(value);
 175       guint32 hashv;
 176
 177       hashv = cmph_search_packed (packed_mem, str, strlen (str));
 178       g_assert (hashv >= 0 && hashv < num_elts);
 179       table[hashv] = strval;
 180     }
 181 }
 182
 183 void
 184 _gi_typelib_hash_builder_destroy (GITypelibHashBuilder *builder)
 185 {
 186   if (builder->c)
 187     {
 188       cmph_destroy (builder->c);
 189       builder->c = NULL;
 190     }
 191   g_hash_table_destroy (builder->strings);
 192   g_slice_free (GITypelibHashBuilder, builder);
 193 }
 194
 195 guint16
 196 _gi_typelib_hash_search (guint8* memory, const char *str, guint n_entries)
 197 {
 198   guint32 *mph;
 199   guint16 *table;
 200   guint32 dirmap_offset;
 201   guint32 offset;
 202
 203   g_assert ((((unsigned long)memory) & 0x3) == 0);
 204   mph = ((guint32*)memory)+1;
 205
 206   offset = cmph_search_packed (mph, str, strlen (str));
 207
 208   /* Make sure that offset always lies in the entries array.  cmph
 209      cometimes generates offset larger than number of entries (for
 210      'str' argument which is not in the hashed list). In this case,
 211      fake the correct result and depend on caller's final check that
 212      the entry is really the one that the caller wanted. */
 213   if (offset >= n_entries)
 214     offset = 0;
 215
 216   dirmap_offset = *((guint32*)memory);
 217   table = (guint16*) (memory + dirmap_offset);
 218
 219   return table[offset];
 220 }
 221