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