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  * SECTION: relations
  40  * @title: Relations and Tuples
  41  * @short_description: tables of data which can be indexed on any
  42  *                     number of fields
  43  *
  44  * A #GRelation is a table of data which can be indexed on any number
  45  * of fields, rather like simple database tables. A #GRelation contains
  46  * a number of records, called tuples. Each record contains a number of
  47  * fields. Records are not ordered, so it is not possible to find the
  48  * record at a particular index.
  49  *
  50  * Note that #GRelation tables are currently limited to 2 fields.
  51  *
  52  * To create a GRelation, use g_relation_new().
  53  *
  54  * To specify which fields should be indexed, use g_relation_index().
  55  * Note that this must be called before any tuples are added to the
  56  * #GRelation.
  57  *
  58  * To add records to a #GRelation use g_relation_insert().
  59  *
  60  * To determine if a given record appears in a #GRelation, use
  61  * g_relation_exists(). Note that fields are compared directly, so
  62  * pointers must point to the exact same position (i.e. different
  63  * copies of the same string will not match.)
  64  *
  65  * To count the number of records which have a particular value in a
  66  * given field, use g_relation_count().
  67  *
  68  * To get all the records which have a particular value in a given
  69  * field, use g_relation_select(). To access fields of the resulting
  70  * records, use g_tuples_index(). To free the resulting records use
  71  * g_tuples_destroy().
  72  *
  73  * To delete all records which have a particular value in a given
  74  * field, use g_relation_delete().
  75  *
  76  * To destroy the #GRelation, use g_relation_destroy().
  77  *
  78  * To help debug #GRelation objects, use g_relation_print().
  79  **/
  80
  81 typedef struct _GRealTuples        GRealTuples;
  82
  83 /**
  84  * GRelation:
  85  *
  86  * The #GRelation struct is an opaque data structure to represent a
  87  * <link linkend="glib-Relations-and-Tuples">Relation</link>. It should
  88  * only be accessed via the following functions.
  89  **/
  90 struct _GRelation
  91 {
  92   gint fields;
  93   gint current_field;
  94
  95   GHashTable   *all_tuples;
  96   GHashTable  **hashed_tuple_tables;
  97
  98   gint count;
  99 };
 100
 101 /**
 102  * GTuples:
 103  * @len: the number of records that matched.
 104  *
 105  * The #GTuples struct is used to return records (or tuples) from the
 106  * #GRelation by g_relation_select(). It only contains one public
 107  * member - the number of records that matched. To access the matched
 108  * records, you must use g_tuples_index().
 109  **/
 110 struct _GRealTuples
 111 {
 112   gint      len;
 113   gint      width;
 114   gpointer *data;
 115 };
 116
 117 static gboolean
 118 tuple_equal_2 (gconstpointer v_a,
 119                gconstpointer v_b)
 120 {
 121   gpointer* a = (gpointer*) v_a;
 122   gpointer* b = (gpointer*) v_b;
 123
 124   return a[0] == b[0] && a[1] == b[1];
 125 }
 126
 127 static guint
 128 tuple_hash_2 (gconstpointer v_a)
 129 {
 130 #if GLIB_SIZEOF_VOID_P > GLIB_SIZEOF_LONG
 131   /* In practise this snippet has been written for 64-bit Windows
 132    * where ints are 32 bits, pointers 64 bits. More exotic platforms
 133    * need more tweaks.
 134    */
 135   guint* a = (guint*) v_a;
 136
 137   return (a[0] ^ a[1] ^ a[2] ^ a[3]);
 138 #else
 139   gpointer* a = (gpointer*) v_a;
 140
 141   return (gulong)a[0] ^ (gulong)a[1];
 142 #endif
 143 }
 144
 145 static GHashFunc
 146 tuple_hash (gint fields)
 147 {
 148   switch (fields)
 149     {
 150     case 2:
 151       return tuple_hash_2;
 152     default:
 153       g_error ("no tuple hash for %d", fields);
 154     }
 155
 156   return NULL;
 157 }
 158
 159 static GEqualFunc
 160 tuple_equal (gint fields)
 161 {
 162   switch (fields)
 163     {
 164     case 2:
 165       return tuple_equal_2;
 166     default:
 167       g_error ("no tuple equal for %d", fields);
 168     }
 169
 170   return NULL;
 171 }
 172
 173 /**
 174  * g_relation_new:
 175  * @fields: the number of fields.
 176  * @Returns: a new #GRelation.
 177  *
 178  * Creates a new #GRelation with the given number of fields. Note that
 179  * currently the number of fields must be 2.
 180  **/
 181 GRelation*
 182 g_relation_new (gint fields)
 183 {
 184   GRelation* rel = g_new0 (GRelation, 1);
 185
 186   rel->fields = fields;
 187   rel->all_tuples = g_hash_table_new (tuple_hash (fields), tuple_equal (fields));
 188   rel->hashed_tuple_tables = g_new0 (GHashTable*, fields);
 189
 190   return rel;
 191 }
 192
 193 static void
 194 relation_delete_value_tuple (gpointer tuple_key,
 195                              gpointer tuple_value,
 196                              gpointer user_data)
 197 {
 198   GRelation *relation = user_data;
 199   gpointer *tuple = tuple_value;
 200   g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
 201 }
 202
 203 static void
 204 g_relation_free_array (gpointer key, gpointer value, gpointer user_data)
 205 {
 206   g_hash_table_destroy ((GHashTable*) value);
 207 }
 208
 209 /**
 210  * g_relation_destroy:
 211  * @relation: a #GRelation.
 212  *
 213  * Destroys the #GRelation, freeing all memory allocated. However, it
 214  * does not free memory allocated for the tuple data, so you should
 215  * free that first if appropriate.
 216  **/
 217 void
 218 g_relation_destroy (GRelation *relation)
 219 {
 220   gint i;
 221
 222   if (relation)
 223     {
 224       for (i = 0; i < relation->fields; i += 1)
 225         {
 226           if (relation->hashed_tuple_tables[i])
 227             {
 228               g_hash_table_foreach (relation->hashed_tuple_tables[i], g_relation_free_array, NULL);
 229               g_hash_table_destroy (relation->hashed_tuple_tables[i]);
 230             }
 231         }
 232
 233       g_hash_table_foreach (relation->all_tuples, relation_delete_value_tuple, relation);
 234       g_hash_table_destroy (relation->all_tuples);
 235
 236       g_free (relation->hashed_tuple_tables);
 237       g_free (relation);
 238     }
 239 }
 240
 241 /**
 242  * g_relation_index:
 243  * @relation: a #GRelation.
 244  * @field: the field to index, counting from 0.
 245  * @hash_func: a function to produce a hash value from the field data.
 246  * @key_equal_func: a function to compare two values of the given field.
 247  *
 248  * Creates an index on the given field. Note that this must be called
 249  * before any records are added to the #GRelation.
 250  **/
 251 void
 252 g_relation_index (GRelation   *relation,
 253                   gint         field,
 254                   GHashFunc    hash_func,
 255                   GEqualFunc   key_equal_func)
 256 {
 257   g_return_if_fail (relation != NULL);
 258
 259   g_return_if_fail (relation->count == 0 && relation->hashed_tuple_tables[field] == NULL);
 260
 261   relation->hashed_tuple_tables[field] = g_hash_table_new (hash_func, key_equal_func);
 262 }
 263
 264 /**
 265  * g_relation_insert:
 266  * @relation: a #GRelation.
 267  * @Varargs: the fields of the record to add. These must match the
 268  *           number of fields in the #GRelation, and of type #gpointer
 269  *           or #gconstpointer.
 270  *
 271  * Inserts a record into a #GRelation.
 272  **/
 273 void
 274 g_relation_insert (GRelation   *relation,
 275                    ...)
 276 {
 277   gpointer* tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
 278   va_list args;
 279   gint i;
 280
 281   va_start (args, relation);
 282
 283   for (i = 0; i < relation->fields; i += 1)
 284     tuple[i] = va_arg (args, gpointer);
 285
 286   va_end (args);
 287
 288   g_hash_table_insert (relation->all_tuples, tuple, tuple);
 289
 290   relation->count += 1;
 291
 292   for (i = 0; i < relation->fields; i += 1)
 293     {
 294       GHashTable *table;
 295       gpointer    key;
 296       GHashTable *per_key_table;
 297
 298       table = relation->hashed_tuple_tables[i];
 299
 300       if (table == NULL)
 301         continue;
 302
 303       key = tuple[i];
 304       per_key_table = g_hash_table_lookup (table, key);
 305
 306       if (per_key_table == NULL)
 307         {
 308           per_key_table = g_hash_table_new (tuple_hash (relation->fields), tuple_equal (relation->fields));
 309           g_hash_table_insert (table, key, per_key_table);
 310         }
 311
 312       g_hash_table_insert (per_key_table, tuple, tuple);
 313     }
 314 }
 315
 316 static void
 317 g_relation_delete_tuple (gpointer tuple_key,
 318                          gpointer tuple_value,
 319                          gpointer user_data)
 320 {
 321   gpointer      *tuple = (gpointer*) tuple_value;
 322   GRelation     *relation = (GRelation *) user_data;
 323   gint           j;
 324
 325   g_assert (tuple_key == tuple_value);
 326
 327   for (j = 0; j < relation->fields; j += 1)
 328     {
 329       GHashTable *one_table = relation->hashed_tuple_tables[j];
 330       gpointer    one_key;
 331       GHashTable *per_key_table;
 332
 333       if (one_table == NULL)
 334         continue;
 335
 336       if (j == relation->current_field)
 337         /* can't delete from the table we're foreaching in */
 338         continue;
 339
 340       one_key = tuple[j];
 341
 342       per_key_table = g_hash_table_lookup (one_table, one_key);
 343
 344       g_hash_table_remove (per_key_table, tuple);
 345     }
 346
 347   if (g_hash_table_remove (relation->all_tuples, tuple))
 348     g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
 349
 350   relation->count -= 1;
 351 }
 352
 353 /**
 354  * g_relation_delete:
 355  * @relation: a #GRelation.
 356  * @key: the value to compare with.
 357  * @field: the field of each record to match.
 358  * @Returns: the number of records deleted.
 359  *
 360  * Deletes any records from a #GRelation that have the given key value
 361  * in the given field.
 362  **/
 363 gint
 364 g_relation_delete  (GRelation     *relation,
 365                     gconstpointer  key,
 366                     gint           field)
 367 {
 368   GHashTable *table;
 369   GHashTable *key_table;
 370   gint        count;
 371
 372   g_return_val_if_fail (relation != NULL, 0);
 373
 374   table = relation->hashed_tuple_tables[field];
 375   count = relation->count;
 376
 377   g_return_val_if_fail (table != NULL, 0);
 378
 379   key_table = g_hash_table_lookup (table, key);
 380
 381   if (!key_table)
 382     return 0;
 383
 384   relation->current_field = field;
 385
 386   g_hash_table_foreach (key_table, g_relation_delete_tuple, relation);
 387
 388   g_hash_table_remove (table, key);
 389
 390   g_hash_table_destroy (key_table);
 391
 392   /* @@@ FIXME: Remove empty hash tables. */
 393
 394   return count - relation->count;
 395 }
 396
 397 static void
 398 g_relation_select_tuple (gpointer tuple_key,
 399                          gpointer tuple_value,
 400                          gpointer user_data)
 401 {
 402   gpointer    *tuple = (gpointer*) tuple_value;
 403   GRealTuples *tuples = (GRealTuples*) user_data;
 404   gint stride = sizeof (gpointer) * tuples->width;
 405
 406   g_assert (tuple_key == tuple_value);
 407
 408   memcpy (tuples->data + (tuples->len * tuples->width),
 409           tuple,
 410           stride);
 411
 412   tuples->len += 1;
 413 }
 414
 415 /**
 416  * g_relation_select:
 417  * @relation: a #GRelation.
 418  * @key: the value to compare with.
 419  * @field: the field of each record to match.
 420  * @Returns: the records (tuples) that matched.
 421  *
 422  * Returns all of the tuples which have the given key in the given
 423  * field. Use g_tuples_index() to access the returned records. The
 424  * returned records should be freed with g_tuples_destroy().
 425  **/
 426 GTuples*
 427 g_relation_select (GRelation     *relation,
 428                    gconstpointer  key,
 429                    gint           field)
 430 {
 431   GHashTable  *table;
 432   GHashTable  *key_table;
 433   GRealTuples *tuples;
 434   gint count;
 435
 436   g_return_val_if_fail (relation != NULL, NULL);
 437
 438   table = relation->hashed_tuple_tables[field];
 439
 440   g_return_val_if_fail (table != NULL, NULL);
 441
 442   tuples = g_new0 (GRealTuples, 1);
 443   key_table = g_hash_table_lookup (table, key);
 444
 445   if (!key_table)
 446     return (GTuples*)tuples;
 447
 448   count = g_relation_count (relation, key, field);
 449
 450   tuples->data = g_malloc (sizeof (gpointer) * relation->fields * count);
 451   tuples->width = relation->fields;
 452
 453   g_hash_table_foreach (key_table, g_relation_select_tuple, tuples);
 454
 455   g_assert (count == tuples->len);
 456
 457   return (GTuples*)tuples;
 458 }
 459
 460 /**
 461  * g_relation_count:
 462  * @relation: a #GRelation.
 463  * @key: the value to compare with.
 464  * @field: the field of each record to match.
 465  * @Returns: the number of matches.
 466  *
 467  * Returns the number of tuples in a #GRelation that have the given
 468  * value in the given field.
 469  **/
 470 gint
 471 g_relation_count (GRelation     *relation,
 472                   gconstpointer  key,
 473                   gint           field)
 474 {
 475   GHashTable  *table;
 476   GHashTable  *key_table;
 477
 478   g_return_val_if_fail (relation != NULL, 0);
 479
 480   table = relation->hashed_tuple_tables[field];
 481
 482   g_return_val_if_fail (table != NULL, 0);
 483
 484   key_table = g_hash_table_lookup (table, key);
 485
 486   if (!key_table)
 487     return 0;
 488
 489   return g_hash_table_size (key_table);
 490 }
 491
 492 /**
 493  * g_relation_exists:
 494  * @relation: a #GRelation.
 495  * @Varargs: the fields of the record to compare. The number must match
 496  *           the number of fields in the #GRelation.
 497  * @Returns: %TRUE if a record matches.
 498  *
 499  * Returns %TRUE if a record with the given values exists in a
 500  * #GRelation. Note that the values are compared directly, so that, for
 501  * example, two copies of the same string will not match.
 502  **/
 503 gboolean
 504 g_relation_exists (GRelation   *relation, ...)
 505 {
 506   gpointer *tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
 507   va_list args;
 508   gint i;
 509   gboolean result;
 510
 511   va_start(args, relation);
 512
 513   for (i = 0; i < relation->fields; i += 1)
 514     tuple[i] = va_arg(args, gpointer);
 515
 516   va_end(args);
 517
 518   result = g_hash_table_lookup (relation->all_tuples, tuple) != NULL;
 519
 520   g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
 521
 522   return result;
 523 }
 524
 525 /**
 526  * g_tuples_destroy:
 527  * @tuples: the tuple data to free.
 528  *
 529  * Frees the records which were returned by g_relation_select(). This
 530  * should always be called after g_relation_select() when you are
 531  * finished with the records. The records are not removed from the
 532  * #GRelation.
 533  **/
 534 void
 535 g_tuples_destroy (GTuples *tuples0)
 536 {
 537   GRealTuples *tuples = (GRealTuples*) tuples0;
 538
 539   if (tuples)
 540     {
 541       g_free (tuples->data);
 542       g_free (tuples);
 543     }
 544 }
 545
 546 /**
 547  * g_tuples_index:
 548  * @tuples: the tuple data, returned by g_relation_select().
 549  * @index_: the index of the record.
 550  * @field: the field to return.
 551  * @Returns: the field of the record.
 552  *
 553  * Gets a field from the records returned by g_relation_select(). It
 554  * returns the given field of the record at the given index. The
 555  * returned value should not be changed.
 556  **/
 557 gpointer
 558 g_tuples_index (GTuples     *tuples0,
 559                 gint         index,
 560                 gint         field)
 561 {
 562   GRealTuples *tuples = (GRealTuples*) tuples0;
 563
 564   g_return_val_if_fail (tuples0 != NULL, NULL);
 565   g_return_val_if_fail (field < tuples->width, NULL);
 566
 567   return tuples->data[index * tuples->width + field];
 568 }
 569
 570 /* Print
 571  */
 572
 573 static void
 574 g_relation_print_one (gpointer tuple_key,
 575                       gpointer tuple_value,
 576                       gpointer user_data)
 577 {
 578   gint i;
 579   GString *gstring;
 580   GRelation* rel = (GRelation*) user_data;
 581   gpointer* tuples = (gpointer*) tuple_value;
 582
 583   gstring = g_string_new ("[");
 584
 585   for (i = 0; i < rel->fields; i += 1)
 586     {
 587       g_string_append_printf (gstring, "%p", tuples[i]);
 588
 589       if (i < (rel->fields - 1))
 590         g_string_append (gstring, ",");
 591     }
 592
 593   g_string_append (gstring, "]");
 594   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "%s", gstring->str);
 595   g_string_free (gstring, TRUE);
 596 }
 597
 598 static void
 599 g_relation_print_index (gpointer tuple_key,
 600                         gpointer tuple_value,
 601                         gpointer user_data)
 602 {
 603   GRelation* rel = (GRelation*) user_data;
 604   GHashTable* table = (GHashTable*) tuple_value;
 605
 606   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** key %p", tuple_key);
 607
 608   g_hash_table_foreach (table,
 609                         g_relation_print_one,
 610                         rel);
 611 }
 612
 613 /**
 614  * g_relation_print:
 615  * @relation: a #GRelation.
 616  *
 617  * Outputs information about all records in a #GRelation, as well as
 618  * the indexes. It is for debugging.
 619  **/
 620 void
 621 g_relation_print (GRelation *relation)
 622 {
 623   gint i;
 624
 625   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** all tuples (%d)", relation->count);
 626
 627   g_hash_table_foreach (relation->all_tuples,
 628                         g_relation_print_one,
 629                         relation);
 630
 631   for (i = 0; i < relation->fields; i += 1)
 632     {
 633       if (relation->hashed_tuple_tables[i] == NULL)
 634         continue;
 635
 636       g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** index %d", i);
 637
 638       g_hash_table_foreach (relation->hashed_tuple_tables[i],
 639                             g_relation_print_index,
 640                             relation);
 641     }
 642
 643 }
 644
 645 #define __G_REL_C__
 646 #include "galiasdef.c"