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