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