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 #if GLIB_SIZEOF_VOID_P > GLIB_SIZEOF_LONG
  73   /* In practise this snippet has been written for 64-bit Windows
  74    * where ints are 32 bits, pointers 64 bits. More exotic platforms
  75    * need more tweaks.
  76    */
  77   guint* a = (guint*) v_a;
  78
  79   return (a[0] ^ a[1] ^ a[2] ^ a[3]);
  80 #else
  81   gpointer* a = (gpointer*) v_a;
  82
  83   return (gulong)a[0] ^ (gulong)a[1];
  84 #endif
  85 }
  86
  87 static GHashFunc
  88 tuple_hash (gint fields)
  89 {
  90   switch (fields)
  91     {
  92     case 2:
  93       return tuple_hash_2;
  94     default:
  95       g_error ("no tuple hash for %d", fields);
  96     }
  97
  98   return NULL;
  99 }
 100
 101 static GEqualFunc
 102 tuple_equal (gint fields)
 103 {
 104   switch (fields)
 105     {
 106     case 2:
 107       return tuple_equal_2;
 108     default:
 109       g_error ("no tuple equal for %d", fields);
 110     }
 111
 112   return NULL;
 113 }
 114
 115 GRelation*
 116 g_relation_new (gint fields)
 117 {
 118   GRelation* rel = g_new0 (GRelation, 1);
 119
 120   rel->fields = fields;
 121   rel->all_tuples = g_hash_table_new (tuple_hash (fields), tuple_equal (fields));
 122   rel->hashed_tuple_tables = g_new0 (GHashTable*, fields);
 123
 124   return rel;
 125 }
 126
 127 static void
 128 relation_delete_value_tuple (gpointer tuple_key,
 129                              gpointer tuple_value,
 130                              gpointer user_data)
 131 {
 132   GRelation *relation = user_data;
 133   gpointer *tuple = tuple_value;
 134   g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
 135 }
 136
 137 static void
 138 g_relation_free_array (gpointer key, gpointer value, gpointer user_data)
 139 {
 140   g_hash_table_destroy ((GHashTable*) value);
 141 }
 142
 143 void
 144 g_relation_destroy (GRelation *relation)
 145 {
 146   gint i;
 147
 148   if (relation)
 149     {
 150       for (i = 0; i < relation->fields; i += 1)
 151         {
 152           if (relation->hashed_tuple_tables[i])
 153             {
 154               g_hash_table_foreach (relation->hashed_tuple_tables[i], g_relation_free_array, NULL);
 155               g_hash_table_destroy (relation->hashed_tuple_tables[i]);
 156             }
 157         }
 158
 159       g_hash_table_foreach (relation->all_tuples, relation_delete_value_tuple, relation);
 160       g_hash_table_destroy (relation->all_tuples);
 161
 162       g_free (relation->hashed_tuple_tables);
 163       g_free (relation);
 164     }
 165 }
 166
 167 void
 168 g_relation_index (GRelation   *relation,
 169                   gint         field,
 170                   GHashFunc    hash_func,
 171                   GEqualFunc   key_equal_func)
 172 {
 173   g_return_if_fail (relation != NULL);
 174
 175   g_return_if_fail (relation->count == 0 && relation->hashed_tuple_tables[field] == NULL);
 176
 177   relation->hashed_tuple_tables[field] = g_hash_table_new (hash_func, key_equal_func);
 178 }
 179
 180 void
 181 g_relation_insert (GRelation   *relation,
 182                    ...)
 183 {
 184   gpointer* tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
 185   va_list args;
 186   gint i;
 187
 188   va_start (args, relation);
 189
 190   for (i = 0; i < relation->fields; i += 1)
 191     tuple[i] = va_arg (args, gpointer);
 192
 193   va_end (args);
 194
 195   g_hash_table_insert (relation->all_tuples, tuple, tuple);
 196
 197   relation->count += 1;
 198
 199   for (i = 0; i < relation->fields; i += 1)
 200     {
 201       GHashTable *table;
 202       gpointer    key;
 203       GHashTable *per_key_table;
 204
 205       table = relation->hashed_tuple_tables[i];
 206
 207       if (table == NULL)
 208         continue;
 209
 210       key = tuple[i];
 211       per_key_table = g_hash_table_lookup (table, key);
 212
 213       if (per_key_table == NULL)
 214         {
 215           per_key_table = g_hash_table_new (tuple_hash (relation->fields), tuple_equal (relation->fields));
 216           g_hash_table_insert (table, key, per_key_table);
 217         }
 218
 219       g_hash_table_insert (per_key_table, tuple, tuple);
 220     }
 221 }
 222
 223 static void
 224 g_relation_delete_tuple (gpointer tuple_key,
 225                          gpointer tuple_value,
 226                          gpointer user_data)
 227 {
 228   gpointer      *tuple = (gpointer*) tuple_value;
 229   GRelation     *relation = (GRelation *) user_data;
 230   gint           j;
 231
 232   g_assert (tuple_key == tuple_value);
 233
 234   for (j = 0; j < relation->fields; j += 1)
 235     {
 236       GHashTable *one_table = relation->hashed_tuple_tables[j];
 237       gpointer    one_key;
 238       GHashTable *per_key_table;
 239
 240       if (one_table == NULL)
 241         continue;
 242
 243       if (j == relation->current_field)
 244         /* can't delete from the table we're foreaching in */
 245         continue;
 246
 247       one_key = tuple[j];
 248
 249       per_key_table = g_hash_table_lookup (one_table, one_key);
 250
 251       g_hash_table_remove (per_key_table, tuple);
 252     }
 253
 254   if (g_hash_table_remove (relation->all_tuples, tuple))
 255     g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
 256
 257   relation->count -= 1;
 258 }
 259
 260 gint
 261 g_relation_delete  (GRelation     *relation,
 262                     gconstpointer  key,
 263                     gint           field)
 264 {
 265   GHashTable *table;
 266   GHashTable *key_table;
 267   gint        count;
 268
 269   g_return_val_if_fail (relation != NULL, 0);
 270
 271   table = relation->hashed_tuple_tables[field];
 272   count = relation->count;
 273
 274   g_return_val_if_fail (table != NULL, 0);
 275
 276   key_table = g_hash_table_lookup (table, key);
 277
 278   if (!key_table)
 279     return 0;
 280
 281   relation->current_field = field;
 282
 283   g_hash_table_foreach (key_table, g_relation_delete_tuple, relation);
 284
 285   g_hash_table_remove (table, key);
 286
 287   g_hash_table_destroy (key_table);
 288
 289   /* @@@ FIXME: Remove empty hash tables. */
 290
 291   return count - relation->count;
 292 }
 293
 294 static void
 295 g_relation_select_tuple (gpointer tuple_key,
 296                          gpointer tuple_value,
 297                          gpointer user_data)
 298 {
 299   gpointer    *tuple = (gpointer*) tuple_value;
 300   GRealTuples *tuples = (GRealTuples*) user_data;
 301   gint stride = sizeof (gpointer) * tuples->width;
 302
 303   g_assert (tuple_key == tuple_value);
 304
 305   memcpy (tuples->data + (tuples->len * tuples->width),
 306           tuple,
 307           stride);
 308
 309   tuples->len += 1;
 310 }
 311
 312 GTuples*
 313 g_relation_select (GRelation     *relation,
 314                    gconstpointer  key,
 315                    gint           field)
 316 {
 317   GHashTable  *table;
 318   GHashTable  *key_table;
 319   GRealTuples *tuples;
 320   gint count;
 321
 322   g_return_val_if_fail (relation != NULL, NULL);
 323
 324   table = relation->hashed_tuple_tables[field];
 325
 326   g_return_val_if_fail (table != NULL, NULL);
 327
 328   tuples = g_new0 (GRealTuples, 1);
 329   key_table = g_hash_table_lookup (table, key);
 330
 331   if (!key_table)
 332     return (GTuples*)tuples;
 333
 334   count = g_relation_count (relation, key, field);
 335
 336   tuples->data = g_malloc (sizeof (gpointer) * relation->fields * count);
 337   tuples->width = relation->fields;
 338
 339   g_hash_table_foreach (key_table, g_relation_select_tuple, tuples);
 340
 341   g_assert (count == tuples->len);
 342
 343   return (GTuples*)tuples;
 344 }
 345
 346 gint
 347 g_relation_count (GRelation     *relation,
 348                   gconstpointer  key,
 349                   gint           field)
 350 {
 351   GHashTable  *table;
 352   GHashTable  *key_table;
 353
 354   g_return_val_if_fail (relation != NULL, 0);
 355
 356   table = relation->hashed_tuple_tables[field];
 357
 358   g_return_val_if_fail (table != NULL, 0);
 359
 360   key_table = g_hash_table_lookup (table, key);
 361
 362   if (!key_table)
 363     return 0;
 364
 365   return g_hash_table_size (key_table);
 366 }
 367
 368 gboolean
 369 g_relation_exists (GRelation   *relation, ...)
 370 {
 371   gpointer *tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
 372   va_list args;
 373   gint i;
 374   gboolean result;
 375
 376   va_start(args, relation);
 377
 378   for (i = 0; i < relation->fields; i += 1)
 379     tuple[i] = va_arg(args, gpointer);
 380
 381   va_end(args);
 382
 383   result = g_hash_table_lookup (relation->all_tuples, tuple) != NULL;
 384
 385   g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
 386
 387   return result;
 388 }
 389
 390 void
 391 g_tuples_destroy (GTuples *tuples0)
 392 {
 393   GRealTuples *tuples = (GRealTuples*) tuples0;
 394
 395   if (tuples)
 396     {
 397       g_free (tuples->data);
 398       g_free (tuples);
 399     }
 400 }
 401
 402 gpointer
 403 g_tuples_index (GTuples     *tuples0,
 404                 gint         index,
 405                 gint         field)
 406 {
 407   GRealTuples *tuples = (GRealTuples*) tuples0;
 408
 409   g_return_val_if_fail (tuples0 != NULL, NULL);
 410   g_return_val_if_fail (field < tuples->width, NULL);
 411
 412   return tuples->data[index * tuples->width + field];
 413 }
 414
 415 /* Print
 416  */
 417
 418 static void
 419 g_relation_print_one (gpointer tuple_key,
 420                       gpointer tuple_value,
 421                       gpointer user_data)
 422 {
 423   gint i;
 424   GString *gstring;
 425   GRelation* rel = (GRelation*) user_data;
 426   gpointer* tuples = (gpointer*) tuple_value;
 427
 428   gstring = g_string_new ("[");
 429
 430   for (i = 0; i < rel->fields; i += 1)
 431     {
 432       g_string_append_printf (gstring, "%p", tuples[i]);
 433
 434       if (i < (rel->fields - 1))
 435         g_string_append (gstring, ",");
 436     }
 437
 438   g_string_append (gstring, "]");
 439   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "%s", gstring->str);
 440   g_string_free (gstring, TRUE);
 441 }
 442
 443 static void
 444 g_relation_print_index (gpointer tuple_key,
 445                         gpointer tuple_value,
 446                         gpointer user_data)
 447 {
 448   GRelation* rel = (GRelation*) user_data;
 449   GHashTable* table = (GHashTable*) tuple_value;
 450
 451   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** key %p", tuple_key);
 452
 453   g_hash_table_foreach (table,
 454                         g_relation_print_one,
 455                         rel);
 456 }
 457
 458 void
 459 g_relation_print (GRelation *relation)
 460 {
 461   gint i;
 462
 463   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** all tuples (%d)", relation->count);
 464
 465   g_hash_table_foreach (relation->all_tuples,
 466                         g_relation_print_one,
 467                         relation);
 468
 469   for (i = 0; i < relation->fields; i += 1)
 470     {
 471       if (relation->hashed_tuple_tables[i] == NULL)
 472         continue;
 473
 474       g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** index %d", i);
 475
 476       g_hash_table_foreach (relation->hashed_tuple_tables[i],
 477                             g_relation_print_index,
 478                             relation);
 479     }
 480
 481 }
 482
 483 #define __G_REL_C__
 484 #include "galiasdef.c"