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  * Modified by the GLib Team and others 1997-1999.  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_assert (rel->count == 0 && rel->hashed_tuple_tables[field] == NULL);
 158
 159   rel->hashed_tuple_tables[field] = g_hash_table_new (hash_func, key_compare_func);
 160 }
 161
 162 void
 163 g_relation_insert (GRelation   *relation,
 164                    ...)
 165 {
 166   GRealRelation *rel = (GRealRelation *) relation;
 167   gpointer* tuple = g_chunk_new (gpointer, rel->tuple_chunk);
 168   va_list args;
 169   gint i;
 170
 171   va_start(args, relation);
 172
 173   for (i = 0; i < rel->fields; i += 1)
 174     tuple[i] = va_arg(args, gpointer);
 175
 176   va_end(args);
 177
 178   g_hash_table_insert (rel->all_tuples, tuple, tuple);
 179
 180   rel->count += 1;
 181
 182   for (i = 0; i < rel->fields; i += 1)
 183     {
 184       GHashTable *table;
 185       gpointer    key;
 186       GHashTable *per_key_table;
 187
 188       table = rel->hashed_tuple_tables[i];
 189
 190       if (table == NULL)
 191         continue;
 192
 193       key = tuple[i];
 194       per_key_table = g_hash_table_lookup (table, key);
 195
 196       if (per_key_table == NULL)
 197         {
 198           per_key_table = g_hash_table_new (tuple_hash (rel->fields), tuple_equal (rel->fields));
 199           g_hash_table_insert (table, key, per_key_table);
 200         }
 201
 202       g_hash_table_insert (per_key_table, tuple, tuple);
 203     }
 204 }
 205
 206 static void
 207 g_relation_delete_tuple (gpointer tuple_key, gpointer tuple_value, gpointer user_data)
 208 {
 209   gpointer      *tuple = (gpointer*) tuple_value;
 210   GRealRelation *rel = (GRealRelation *) user_data;
 211   gint           j;
 212
 213   g_assert (tuple_key == tuple_value);
 214
 215   for (j = 0; j < rel->fields; j += 1)
 216     {
 217       GHashTable *one_table = rel->hashed_tuple_tables[j];
 218       gpointer    one_key;
 219       GHashTable *per_key_table;
 220
 221       if (one_table == NULL)
 222         continue;
 223
 224       if (j == rel->current_field)
 225         /* can't delete from the table we're foreaching in */
 226         continue;
 227
 228       one_key = tuple[j];
 229
 230       per_key_table = g_hash_table_lookup (one_table, one_key);
 231
 232       g_hash_table_remove (per_key_table, tuple);
 233     }
 234
 235   g_hash_table_remove (rel->all_tuples, tuple);
 236
 237   rel->count -= 1;
 238 }
 239
 240 gint
 241 g_relation_delete  (GRelation   *relation,
 242                     gconstpointer  key,
 243                     gint         field)
 244 {
 245   GRealRelation *rel = (GRealRelation *) relation;
 246   GHashTable *table = rel->hashed_tuple_tables[field];
 247   GHashTable *key_table;
 248   gint        count = rel->count;
 249
 250   g_assert (table);
 251
 252   key_table = g_hash_table_lookup (table, key);
 253
 254   if (!key_table)
 255     return 0;
 256
 257   rel->current_field = field;
 258
 259   g_hash_table_foreach (key_table, g_relation_delete_tuple, rel);
 260
 261   g_hash_table_remove (table, key);
 262
 263   g_hash_table_destroy (key_table);
 264
 265   /* @@@ FIXME: Remove empty hash tables. */
 266
 267   return count - rel->count;
 268 }
 269
 270 static void
 271 g_relation_select_tuple (gpointer tuple_key, gpointer tuple_value, gpointer user_data)
 272 {
 273   gpointer    *tuple = (gpointer*) tuple_value;
 274   GRealTuples *tuples = (GRealTuples*) user_data;
 275   gint stride = sizeof (gpointer) * tuples->width;
 276
 277   g_assert (tuple_key == tuple_value);
 278
 279   memcpy (tuples->data + (tuples->len * tuples->width),
 280           tuple,
 281           stride);
 282
 283   tuples->len += 1;
 284 }
 285
 286 GTuples*
 287 g_relation_select (GRelation   *relation,
 288                    gconstpointer  key,
 289                    gint         field)
 290 {
 291   GRealRelation *rel = (GRealRelation *) relation;
 292   GHashTable  *table = rel->hashed_tuple_tables[field];
 293   GHashTable  *key_table;
 294   GRealTuples *tuples = g_new0 (GRealTuples, 1);
 295   gint count;
 296
 297   g_assert (table);
 298
 299   key_table = g_hash_table_lookup (table, key);
 300
 301   if (!key_table)
 302     return (GTuples*)tuples;
 303
 304   count = g_relation_count (relation, key, field);
 305
 306   tuples->data = g_malloc (sizeof (gpointer) * rel->fields * count);
 307   tuples->width = rel->fields;
 308
 309   g_hash_table_foreach (key_table, g_relation_select_tuple, tuples);
 310
 311   g_assert (count == tuples->len);
 312
 313   return (GTuples*)tuples;
 314 }
 315
 316 gint
 317 g_relation_count (GRelation   *relation,
 318                   gconstpointer  key,
 319                   gint         field)
 320 {
 321   GRealRelation *rel = (GRealRelation *) relation;
 322   GHashTable  *table = rel->hashed_tuple_tables[field];
 323   GHashTable  *key_table;
 324
 325   g_assert (table);
 326
 327   key_table = g_hash_table_lookup (table, key);
 328
 329   if (!key_table)
 330     return 0;
 331
 332   return g_hash_table_size (key_table);
 333 }
 334
 335 gboolean
 336 g_relation_exists (GRelation   *relation, ...)
 337 {
 338   GRealRelation *rel = (GRealRelation *) relation;
 339   gpointer* tuple = g_chunk_new (gpointer, rel->tuple_chunk);
 340   va_list args;
 341   gint i;
 342   gboolean result;
 343
 344   va_start(args, relation);
 345
 346   for (i = 0; i < rel->fields; i += 1)
 347     tuple[i] = va_arg(args, gpointer);
 348
 349   va_end(args);
 350
 351   result = g_hash_table_lookup (rel->all_tuples, tuple) != NULL;
 352
 353   g_mem_chunk_free (rel->tuple_chunk, tuple);
 354
 355   return result;
 356 }
 357
 358 void
 359 g_tuples_destroy (GTuples *tuples0)
 360 {
 361   GRealTuples *tuples = (GRealTuples*) tuples0;
 362
 363   if (tuples)
 364     {
 365       g_free (tuples->data);
 366       g_free (tuples);
 367     }
 368 }
 369
 370 gpointer
 371 g_tuples_index (GTuples     *tuples0,
 372                 gint         index,
 373                 gint         field)
 374 {
 375   GRealTuples *tuples = (GRealTuples*) tuples0;
 376
 377   g_assert (field < tuples->width);
 378
 379   return tuples->data[index * tuples->width + field];
 380 }
 381
 382 /* Print
 383  */
 384
 385 static void
 386 g_relation_print_one (gpointer tuple_key,
 387                       gpointer tuple_value,
 388                       gpointer user_data)
 389 {
 390   gint i;
 391   GString *gstring;
 392   GRealRelation* rel = (GRealRelation*) user_data;
 393   gpointer* tuples = (gpointer*) tuple_value;
 394
 395   gstring = g_string_new ("[");
 396
 397   for (i = 0; i < rel->fields; i += 1)
 398     {
 399       g_string_sprintfa (gstring, "%p", tuples[i]);
 400
 401       if (i < (rel->fields - 1))
 402         g_string_append (gstring, ",");
 403     }
 404
 405   g_string_append (gstring, "]");
 406   g_log (g_log_domain_glib, G_LOG_LEVEL_INFO, gstring->str);
 407   g_string_free (gstring, TRUE);
 408 }
 409
 410 static void
 411 g_relation_print_index (gpointer tuple_key,
 412                         gpointer tuple_value,
 413                         gpointer user_data)
 414 {
 415   GRealRelation* rel = (GRealRelation*) user_data;
 416   GHashTable* table = (GHashTable*) tuple_value;
 417
 418   g_log (g_log_domain_glib, G_LOG_LEVEL_INFO, "*** key %p", tuple_key);
 419
 420   g_hash_table_foreach (table,
 421                         g_relation_print_one,
 422                         rel);
 423 }
 424
 425 void
 426 g_relation_print (GRelation *relation)
 427 {
 428   gint i;
 429   GRealRelation* rel = (GRealRelation*) relation;
 430
 431   g_log (g_log_domain_glib, G_LOG_LEVEL_INFO, "*** all tuples (%d)", rel->count);
 432
 433   g_hash_table_foreach (rel->all_tuples,
 434                         g_relation_print_one,
 435                         rel);
 436
 437   for (i = 0; i < rel->fields; i += 1)
 438     {
 439       if (rel->hashed_tuple_tables[i] == NULL)
 440         continue;
 441
 442       g_log (g_log_domain_glib, G_LOG_LEVEL_INFO, "*** index %d", i);
 443
 444       g_hash_table_foreach (rel->hashed_tuple_tables[i],
 445                             g_relation_print_index,
 446                             rel);
 447     }
 448
 449 }