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