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   *((guint32*) mem) = builder->dirmap_offset;
 162   packed_mem = (guint8*)(mem + sizeof(guint32));
 163   cmph_pack (builder->c, packed_mem);
 164
 165   table = (guint16*) (mem + builder->dirmap_offset);
 166
 167   num_elts = g_hash_table_size (builder->strings);
 168   g_hash_table_iter_init (&hashiter, builder->strings);
 169   while (g_hash_table_iter_next (&hashiter, &key, &value))
 170     {
 171       const char *str = key;
 172       guint16 strval = (guint16)GPOINTER_TO_UINT(value);
 173       guint32 hashv;
 174
 175       hashv = cmph_search_packed (packed_mem, str, strlen (str));
 176       g_assert (hashv >= 0 && hashv < num_elts);
 177       table[hashv] = strval;
 178     }
 179 }
 180
 181 void
 182 _gi_typelib_hash_builder_destroy (GITypelibHashBuilder *builder)
 183 {
 184   if (builder->c)
 185     {
 186       cmph_destroy (builder->c);
 187       builder->c = NULL;
 188     }
 189   g_hash_table_destroy (builder->strings);
 190   g_slice_free (GITypelibHashBuilder, builder);
 191 }
 192
 193 guint16
 194 _gi_typelib_hash_search (guint8* memory, const char *str)
 195 {
 196   guint32 *mph;
 197   guint16 *table;
 198   guint32 dirmap_offset;
 199   guint32 offset;
 200
 201   g_assert ((((unsigned long)memory) & 0x3) == 0);
 202   mph = ((guint32*)memory)+1;
 203
 204   offset = cmph_search_packed (mph, str, strlen (str));
 205
 206   dirmap_offset = *((guint32*)memory);
 207   table = (guint16*) (memory + dirmap_offset);
 208
 209   return table[offset];
 210 }
 211