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