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