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