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