glib/grel.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the Free
  16  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17  */
  18
  19 /*
  20  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
  21  * file for a list of people on the GLib Team.  See the ChangeLog
  22  * files for a list of changes.  These files are distributed with
  23  * GLib at ftp://ftp.gtk.org/pub/gtk/.
  24  */
  25
  26 /*
  27  * MT safe
  28  */
  29
  30 #include "config.h"
  31
  32 #include <stdarg.h>
  33 #include <string.h>
  34
  35 #include "glib.h"
  36 #include "galias.h"
  37
  38
  39 typedef struct _GRealTuples        GRealTuples;
  40
  41 struct _GRelation
  42 {
  43   gint fields;
  44   gint current_field;
  45
  46   GHashTable   *all_tuples;
  47   GHashTable  **hashed_tuple_tables;
  48
  49   gint count;
  50 };
  51
  52 struct _GRealTuples
  53 {
  54   gint      len;
  55   gint      width;
  56   gpointer *data;
  57 };
  58
  59 static gboolean
  60 tuple_equal_2 (gconstpointer v_a,
  61                gconstpointer v_b)
  62 {
  63   gpointer* a = (gpointer*) v_a;
  64   gpointer* b = (gpointer*) v_b;
  65
  66   return a[0] == b[0] && a[1] == b[1];
  67 }
  68
  69 static guint
  70 tuple_hash_2 (gconstpointer v_a)
  71 {
  72   gpointer* a = (gpointer*) v_a;
  73
  74   return (gulong)a[0] ^ (gulong)a[1];
  75 }
  76
  77 static GHashFunc
  78 tuple_hash (gint fields)
  79 {
  80   switch (fields)
  81     {
  82     case 2:
  83       return tuple_hash_2;
  84     default:
  85       g_error ("no tuple hash for %d", fields);
  86     }
  87
  88   return NULL;
  89 }
  90
  91 static GEqualFunc
  92 tuple_equal (gint fields)
  93 {
  94   switch (fields)
  95     {
  96     case 2:
  97       return tuple_equal_2;
  98     default:
  99       g_error ("no tuple equal for %d", fields);
 100     }
 101
 102   return NULL;
 103 }
 104
 105 GRelation*
 106 g_relation_new (gint fields)
 107 {
 108   GRelation* rel = g_new0 (GRelation, 1);
 109
 110   rel->fields = fields;
 111   rel->all_tuples = g_hash_table_new (tuple_hash (fields), tuple_equal (fields));
 112   rel->hashed_tuple_tables = g_new0 (GHashTable*, fields);
 113
 114   return rel;
 115 }
 116
 117 static void
 118 relation_delete_value_tuple (gpointer tuple_key,
 119                              gpointer tuple_value,
 120                              gpointer user_data)
 121 {
 122   GRelation *relation = user_data;
 123   gpointer *tuple = tuple_value;
 124   g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
 125 }
 126
 127 static void
 128 g_relation_free_array (gpointer key, gpointer value, gpointer user_data)
 129 {
 130   g_hash_table_destroy ((GHashTable*) value);
 131 }
 132
 133 void
 134 g_relation_destroy (GRelation *relation)
 135 {
 136   gint i;
 137
 138   if (relation)
 139     {
 140       for (i = 0; i < relation->fields; i += 1)
 141         {
 142           if (relation->hashed_tuple_tables[i])
 143             {
 144               g_hash_table_foreach (relation->hashed_tuple_tables[i], g_relation_free_array, NULL);
 145               g_hash_table_destroy (relation->hashed_tuple_tables[i]);
 146             }
 147         }
 148
 149       g_hash_table_foreach (relation->all_tuples, relation_delete_value_tuple, relation);
 150       g_hash_table_destroy (relation->all_tuples);
 151
 152       g_free (relation->hashed_tuple_tables);
 153       g_free (relation);
 154     }
 155 }
 156
 157 void
 158 g_relation_index (GRelation   *relation,
 159                   gint         field,
 160                   GHashFunc    hash_func,
 161                   GEqualFunc   key_equal_func)
 162 {
 163   g_return_if_fail (relation != NULL);
 164
 165   g_return_if_fail (relation->count == 0 && relation->hashed_tuple_tables[field] == NULL);
 166
 167   relation->hashed_tuple_tables[field] = g_hash_table_new (hash_func, key_equal_func);
 168 }
 169
 170 void
 171 g_relation_insert (GRelation   *relation,
 172                    ...)
 173 {
 174   gpointer* tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
 175   va_list args;
 176   gint i;
 177
 178   va_start (args, relation);
 179
 180   for (i = 0; i < relation->fields; i += 1)
 181     tuple[i] = va_arg (args, gpointer);
 182
 183   va_end (args);
 184
 185   g_hash_table_insert (relation->all_tuples, tuple, tuple);
 186
 187   relation->count += 1;
 188
 189   for (i = 0; i < relation->fields; i += 1)
 190     {
 191       GHashTable *table;
 192       gpointer    key;
 193       GHashTable *per_key_table;
 194
 195       table = relation->hashed_tuple_tables[i];
 196
 197       if (table == NULL)
 198         continue;
 199
 200       key = tuple[i];
 201       per_key_table = g_hash_table_lookup (table, key);
 202
 203       if (per_key_table == NULL)
 204         {
 205           per_key_table = g_hash_table_new (tuple_hash (relation->fields), tuple_equal (relation->fields));
 206           g_hash_table_insert (table, key, per_key_table);
 207         }
 208
 209       g_hash_table_insert (per_key_table, tuple, tuple);
 210     }
 211 }
 212
 213 static void
 214 g_relation_delete_tuple (gpointer tuple_key,
 215                          gpointer tuple_value,
 216                          gpointer user_data)
 217 {
 218   gpointer      *tuple = (gpointer*) tuple_value;
 219   GRelation     *relation = (GRelation *) user_data;
 220   gint           j;
 221
 222   g_assert (tuple_key == tuple_value);
 223
 224   for (j = 0; j < relation->fields; j += 1)
 225     {
 226       GHashTable *one_table = relation->hashed_tuple_tables[j];
 227       gpointer    one_key;
 228       GHashTable *per_key_table;
 229
 230       if (one_table == NULL)
 231         continue;
 232
 233       if (j == relation->current_field)
 234         /* can't delete from the table we're foreaching in */
 235         continue;
 236
 237       one_key = tuple[j];
 238
 239       per_key_table = g_hash_table_lookup (one_table, one_key);
 240
 241       g_hash_table_remove (per_key_table, tuple);
 242     }
 243
 244   if (g_hash_table_remove (relation->all_tuples, tuple))
 245     g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
 246
 247   relation->count -= 1;
 248 }
 249
 250 gint
 251 g_relation_delete  (GRelation     *relation,
 252                     gconstpointer  key,
 253                     gint           field)
 254 {
 255   GHashTable *table = relation->hashed_tuple_tables[field];
 256   GHashTable *key_table;
 257   gint        count = relation->count;
 258
 259   g_return_val_if_fail (relation != NULL, 0);
 260   g_return_val_if_fail (table != NULL, 0);
 261
 262   key_table = g_hash_table_lookup (table, key);
 263
 264   if (!key_table)
 265     return 0;
 266
 267   relation->current_field = field;
 268
 269   g_hash_table_foreach (key_table, g_relation_delete_tuple, relation);
 270
 271   g_hash_table_remove (table, key);
 272
 273   g_hash_table_destroy (key_table);
 274
 275   /* @@@ FIXME: Remove empty hash tables. */
 276
 277   return count - relation->count;
 278 }
 279
 280 static void
 281 g_relation_select_tuple (gpointer tuple_key,
 282                          gpointer tuple_value,
 283                          gpointer user_data)
 284 {
 285   gpointer    *tuple = (gpointer*) tuple_value;
 286   GRealTuples *tuples = (GRealTuples*) user_data;
 287   gint stride = sizeof (gpointer) * tuples->width;
 288
 289   g_assert (tuple_key == tuple_value);
 290
 291   memcpy (tuples->data + (tuples->len * tuples->width),
 292           tuple,
 293           stride);
 294
 295   tuples->len += 1;
 296 }
 297
 298 GTuples*
 299 g_relation_select (GRelation     *relation,
 300                    gconstpointer  key,
 301                    gint           field)
 302 {
 303   GHashTable  *table = relation->hashed_tuple_tables[field];
 304   GHashTable  *key_table;
 305   GRealTuples *tuples = g_new0 (GRealTuples, 1);
 306   gint count;
 307
 308   g_return_val_if_fail (relation != NULL, NULL);
 309   g_return_val_if_fail (table != NULL, NULL);
 310
 311   key_table = g_hash_table_lookup (table, key);
 312
 313   if (!key_table)
 314     return (GTuples*)tuples;
 315
 316   count = g_relation_count (relation, key, field);
 317
 318   tuples->data = g_malloc (sizeof (gpointer) * relation->fields * count);
 319   tuples->width = relation->fields;
 320
 321   g_hash_table_foreach (key_table, g_relation_select_tuple, tuples);
 322
 323   g_assert (count == tuples->len);
 324
 325   return (GTuples*)tuples;
 326 }
 327
 328 gint
 329 g_relation_count (GRelation     *relation,
 330                   gconstpointer  key,
 331                   gint           field)
 332 {
 333   GHashTable  *table = relation->hashed_tuple_tables[field];
 334   GHashTable  *key_table;
 335
 336   g_return_val_if_fail (relation != NULL, 0);
 337   g_return_val_if_fail (table != NULL, 0);
 338
 339   key_table = g_hash_table_lookup (table, key);
 340
 341   if (!key_table)
 342     return 0;
 343
 344   return g_hash_table_size (key_table);
 345 }
 346
 347 gboolean
 348 g_relation_exists (GRelation   *relation, ...)
 349 {
 350   gpointer *tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
 351   va_list args;
 352   gint i;
 353   gboolean result;
 354
 355   va_start(args, relation);
 356
 357   for (i = 0; i < relation->fields; i += 1)
 358     tuple[i] = va_arg(args, gpointer);
 359
 360   va_end(args);
 361
 362   result = g_hash_table_lookup (relation->all_tuples, tuple) != NULL;
 363
 364   g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
 365
 366   return result;
 367 }
 368
 369 void
 370 g_tuples_destroy (GTuples *tuples0)
 371 {
 372   GRealTuples *tuples = (GRealTuples*) tuples0;
 373
 374   if (tuples)
 375     {
 376       g_free (tuples->data);
 377       g_free (tuples);
 378     }
 379 }
 380
 381 gpointer
 382 g_tuples_index (GTuples     *tuples0,
 383                 gint         index,
 384                 gint         field)
 385 {
 386   GRealTuples *tuples = (GRealTuples*) tuples0;
 387
 388   g_return_val_if_fail (tuples0 != NULL, NULL);
 389   g_return_val_if_fail (field < tuples->width, NULL);
 390
 391   return tuples->data[index * tuples->width + field];
 392 }
 393
 394 /* Print
 395  */
 396
 397 static void
 398 g_relation_print_one (gpointer tuple_key,
 399                       gpointer tuple_value,
 400                       gpointer user_data)
 401 {
 402   gint i;
 403   GString *gstring;
 404   GRelation* rel = (GRelation*) user_data;
 405   gpointer* tuples = (gpointer*) tuple_value;
 406
 407   gstring = g_string_new ("[");
 408
 409   for (i = 0; i < rel->fields; i += 1)
 410     {
 411       g_string_append_printf (gstring, "%p", tuples[i]);
 412
 413       if (i < (rel->fields - 1))
 414         g_string_append (gstring, ",");
 415     }
 416
 417   g_string_append (gstring, "]");
 418   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, gstring->str);
 419   g_string_free (gstring, TRUE);
 420 }
 421
 422 static void
 423 g_relation_print_index (gpointer tuple_key,
 424                         gpointer tuple_value,
 425                         gpointer user_data)
 426 {
 427   GRelation* rel = (GRelation*) user_data;
 428   GHashTable* table = (GHashTable*) tuple_value;
 429
 430   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** key %p", tuple_key);
 431
 432   g_hash_table_foreach (table,
 433                         g_relation_print_one,
 434                         rel);
 435 }
 436
 437 void
 438 g_relation_print (GRelation *relation)
 439 {
 440   gint i;
 441
 442   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** all tuples (%d)", relation->count);
 443
 444   g_hash_table_foreach (relation->all_tuples,
 445                         g_relation_print_one,
 446                         relation);
 447
 448   for (i = 0; i < relation->fields; i += 1)
 449     {
 450       if (relation->hashed_tuple_tables[i] == NULL)
 451         continue;
 452
 453       g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** index %d", i);
 454
 455       g_hash_table_foreach (relation->hashed_tuple_tables[i],
 456                             g_relation_print_index,
 457                             relation);
 458     }
 459
 460 }
 461
 462 #define __G_REL_C__
 463 #include "galiasdef.c"