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