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