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  * <link linkend="glib-Relations-and-Tuples">Relation</link>. 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  * @Returns: a new #GRelation.
 189  *
 190  * Creates a new #GRelation with the given number of fields. Note that
 191  * currently the number of fields must be 2.
 192  *
 193  * Deprecated: 2.26: Rarely used API
 194  **/
 195 GRelation*
 196 g_relation_new (gint fields)
 197 {
 198   GRelation* rel = g_new0 (GRelation, 1);
 199
 200   rel->fields = fields;
 201   rel->all_tuples = g_hash_table_new (tuple_hash (fields), tuple_equal (fields));
 202   rel->hashed_tuple_tables = g_new0 (GHashTable*, fields);
 203
 204   return rel;
 205 }
 206
 207 static void
 208 relation_delete_value_tuple (gpointer tuple_key,
 209                              gpointer tuple_value,
 210                              gpointer user_data)
 211 {
 212   GRelation *relation = user_data;
 213   gpointer *tuple = tuple_value;
 214   g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
 215 }
 216
 217 static void
 218 g_relation_free_array (gpointer key, gpointer value, gpointer user_data)
 219 {
 220   g_hash_table_destroy ((GHashTable*) value);
 221 }
 222
 223 /**
 224  * g_relation_destroy:
 225  * @relation: a #GRelation.
 226  *
 227  * Destroys the #GRelation, freeing all memory allocated. However, it
 228  * does not free memory allocated for the tuple data, so you should
 229  * free that first if appropriate.
 230  *
 231  * Deprecated: 2.26: Rarely used API
 232  **/
 233 void
 234 g_relation_destroy (GRelation *relation)
 235 {
 236   gint i;
 237
 238   if (relation)
 239     {
 240       for (i = 0; i < relation->fields; i += 1)
 241         {
 242           if (relation->hashed_tuple_tables[i])
 243             {
 244               g_hash_table_foreach (relation->hashed_tuple_tables[i], g_relation_free_array, NULL);
 245               g_hash_table_destroy (relation->hashed_tuple_tables[i]);
 246             }
 247         }
 248
 249       g_hash_table_foreach (relation->all_tuples, relation_delete_value_tuple, relation);
 250       g_hash_table_destroy (relation->all_tuples);
 251
 252       g_free (relation->hashed_tuple_tables);
 253       g_free (relation);
 254     }
 255 }
 256
 257 /**
 258  * g_relation_index:
 259  * @relation: a #GRelation.
 260  * @field: the field to index, counting from 0.
 261  * @hash_func: a function to produce a hash value from the field data.
 262  * @key_equal_func: a function to compare two values of the given field.
 263  *
 264  * Creates an index on the given field. Note that this must be called
 265  * before any records are added to the #GRelation.
 266  *
 267  * Deprecated: 2.26: Rarely used API
 268  **/
 269 void
 270 g_relation_index (GRelation   *relation,
 271                   gint         field,
 272                   GHashFunc    hash_func,
 273                   GEqualFunc   key_equal_func)
 274 {
 275   g_return_if_fail (relation != NULL);
 276
 277   g_return_if_fail (relation->count == 0 && relation->hashed_tuple_tables[field] == NULL);
 278
 279   relation->hashed_tuple_tables[field] = g_hash_table_new (hash_func, key_equal_func);
 280 }
 281
 282 /**
 283  * g_relation_insert:
 284  * @relation: a #GRelation.
 285  * @...: the fields of the record to add. These must match the
 286  *       number of fields in the #GRelation, and of type #gpointer
 287  *       or #gconstpointer.
 288  *
 289  * Inserts a record into a #GRelation.
 290  *
 291  * Deprecated: 2.26: Rarely used API
 292  **/
 293 void
 294 g_relation_insert (GRelation   *relation,
 295                    ...)
 296 {
 297   gpointer* tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
 298   va_list args;
 299   gint i;
 300
 301   va_start (args, relation);
 302
 303   for (i = 0; i < relation->fields; i += 1)
 304     tuple[i] = va_arg (args, gpointer);
 305
 306   va_end (args);
 307
 308   g_hash_table_insert (relation->all_tuples, tuple, tuple);
 309
 310   relation->count += 1;
 311
 312   for (i = 0; i < relation->fields; i += 1)
 313     {
 314       GHashTable *table;
 315       gpointer    key;
 316       GHashTable *per_key_table;
 317
 318       table = relation->hashed_tuple_tables[i];
 319
 320       if (table == NULL)
 321         continue;
 322
 323       key = tuple[i];
 324       per_key_table = g_hash_table_lookup (table, key);
 325
 326       if (per_key_table == NULL)
 327         {
 328           per_key_table = g_hash_table_new (tuple_hash (relation->fields), tuple_equal (relation->fields));
 329           g_hash_table_insert (table, key, per_key_table);
 330         }
 331
 332       g_hash_table_insert (per_key_table, tuple, tuple);
 333     }
 334 }
 335
 336 static void
 337 g_relation_delete_tuple (gpointer tuple_key,
 338                          gpointer tuple_value,
 339                          gpointer user_data)
 340 {
 341   gpointer      *tuple = (gpointer*) tuple_value;
 342   GRelation     *relation = (GRelation *) user_data;
 343   gint           j;
 344
 345   g_assert (tuple_key == tuple_value);
 346
 347   for (j = 0; j < relation->fields; j += 1)
 348     {
 349       GHashTable *one_table = relation->hashed_tuple_tables[j];
 350       gpointer    one_key;
 351       GHashTable *per_key_table;
 352
 353       if (one_table == NULL)
 354         continue;
 355
 356       if (j == relation->current_field)
 357         /* can't delete from the table we're foreaching in */
 358         continue;
 359
 360       one_key = tuple[j];
 361
 362       per_key_table = g_hash_table_lookup (one_table, one_key);
 363
 364       g_hash_table_remove (per_key_table, tuple);
 365     }
 366
 367   if (g_hash_table_remove (relation->all_tuples, tuple))
 368     g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
 369
 370   relation->count -= 1;
 371 }
 372
 373 /**
 374  * g_relation_delete:
 375  * @relation: a #GRelation.
 376  * @key: the value to compare with.
 377  * @field: the field of each record to match.
 378  * @Returns: the number of records deleted.
 379  *
 380  * Deletes any records from a #GRelation that have the given key value
 381  * in the given field.
 382  *
 383  * Deprecated: 2.26: Rarely used API
 384  **/
 385 gint
 386 g_relation_delete  (GRelation     *relation,
 387                     gconstpointer  key,
 388                     gint           field)
 389 {
 390   GHashTable *table;
 391   GHashTable *key_table;
 392   gint        count;
 393
 394   g_return_val_if_fail (relation != NULL, 0);
 395
 396   table = relation->hashed_tuple_tables[field];
 397   count = relation->count;
 398
 399   g_return_val_if_fail (table != NULL, 0);
 400
 401   key_table = g_hash_table_lookup (table, key);
 402
 403   if (!key_table)
 404     return 0;
 405
 406   relation->current_field = field;
 407
 408   g_hash_table_foreach (key_table, g_relation_delete_tuple, relation);
 409
 410   g_hash_table_remove (table, key);
 411
 412   g_hash_table_destroy (key_table);
 413
 414   /* @@@ FIXME: Remove empty hash tables. */
 415
 416   return count - relation->count;
 417 }
 418
 419 static void
 420 g_relation_select_tuple (gpointer tuple_key,
 421                          gpointer tuple_value,
 422                          gpointer user_data)
 423 {
 424   gpointer    *tuple = (gpointer*) tuple_value;
 425   GRealTuples *tuples = (GRealTuples*) user_data;
 426   gint stride = sizeof (gpointer) * tuples->width;
 427
 428   g_assert (tuple_key == tuple_value);
 429
 430   memcpy (tuples->data + (tuples->len * tuples->width),
 431           tuple,
 432           stride);
 433
 434   tuples->len += 1;
 435 }
 436
 437 /**
 438  * g_relation_select:
 439  * @relation: a #GRelation.
 440  * @key: the value to compare with.
 441  * @field: the field of each record to match.
 442  * @Returns: the records (tuples) that matched.
 443  *
 444  * Returns all of the tuples which have the given key in the given
 445  * field. Use g_tuples_index() to access the returned records. The
 446  * returned records should be freed with g_tuples_destroy().
 447  *
 448  * Deprecated: 2.26: Rarely used API
 449  **/
 450 GTuples*
 451 g_relation_select (GRelation     *relation,
 452                    gconstpointer  key,
 453                    gint           field)
 454 {
 455   GHashTable  *table;
 456   GHashTable  *key_table;
 457   GRealTuples *tuples;
 458   gint count;
 459
 460   g_return_val_if_fail (relation != NULL, NULL);
 461
 462   table = relation->hashed_tuple_tables[field];
 463
 464   g_return_val_if_fail (table != NULL, NULL);
 465
 466   tuples = g_new0 (GRealTuples, 1);
 467   key_table = g_hash_table_lookup (table, key);
 468
 469   if (!key_table)
 470     return (GTuples*)tuples;
 471
 472   count = g_relation_count (relation, key, field);
 473
 474   tuples->data = g_malloc (sizeof (gpointer) * relation->fields * count);
 475   tuples->width = relation->fields;
 476
 477   g_hash_table_foreach (key_table, g_relation_select_tuple, tuples);
 478
 479   g_assert (count == tuples->len);
 480
 481   return (GTuples*)tuples;
 482 }
 483
 484 /**
 485  * g_relation_count:
 486  * @relation: a #GRelation.
 487  * @key: the value to compare with.
 488  * @field: the field of each record to match.
 489  * @Returns: the number of matches.
 490  *
 491  * Returns the number of tuples in a #GRelation that have the given
 492  * value in the given field.
 493  *
 494  * Deprecated: 2.26: Rarely used API
 495  **/
 496 gint
 497 g_relation_count (GRelation     *relation,
 498                   gconstpointer  key,
 499                   gint           field)
 500 {
 501   GHashTable  *table;
 502   GHashTable  *key_table;
 503
 504   g_return_val_if_fail (relation != NULL, 0);
 505
 506   table = relation->hashed_tuple_tables[field];
 507
 508   g_return_val_if_fail (table != NULL, 0);
 509
 510   key_table = g_hash_table_lookup (table, key);
 511
 512   if (!key_table)
 513     return 0;
 514
 515   return g_hash_table_size (key_table);
 516 }
 517
 518 /**
 519  * g_relation_exists:
 520  * @relation: a #GRelation.
 521  * @...: the fields of the record to compare. The number must match
 522  *       the number of fields in the #GRelation.
 523  * @Returns: %TRUE if a record matches.
 524  *
 525  * Returns %TRUE if a record with the given values exists in a
 526  * #GRelation. Note that the values are compared directly, so that, for
 527  * example, two copies of the same string will not match.
 528  *
 529  * Deprecated: 2.26: Rarely used API
 530  **/
 531 gboolean
 532 g_relation_exists (GRelation   *relation, ...)
 533 {
 534   gpointer *tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
 535   va_list args;
 536   gint i;
 537   gboolean result;
 538
 539   va_start(args, relation);
 540
 541   for (i = 0; i < relation->fields; i += 1)
 542     tuple[i] = va_arg(args, gpointer);
 543
 544   va_end(args);
 545
 546   result = g_hash_table_lookup (relation->all_tuples, tuple) != NULL;
 547
 548   g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
 549
 550   return result;
 551 }
 552
 553 /**
 554  * g_tuples_destroy:
 555  * @tuples: the tuple data to free.
 556  *
 557  * Frees the records which were returned by g_relation_select(). This
 558  * should always be called after g_relation_select() when you are
 559  * finished with the records. The records are not removed from the
 560  * #GRelation.
 561  *
 562  * Deprecated: 2.26: Rarely used API
 563  **/
 564 void
 565 g_tuples_destroy (GTuples *tuples0)
 566 {
 567   GRealTuples *tuples = (GRealTuples*) tuples0;
 568
 569   if (tuples)
 570     {
 571       g_free (tuples->data);
 572       g_free (tuples);
 573     }
 574 }
 575
 576 /**
 577  * g_tuples_index:
 578  * @tuples: the tuple data, returned by g_relation_select().
 579  * @index_: the index of the record.
 580  * @field: the field to return.
 581  * @Returns: the field of the record.
 582  *
 583  * Gets a field from the records returned by g_relation_select(). It
 584  * returns the given field of the record at the given index. The
 585  * returned value should not be changed.
 586  *
 587  * Deprecated: 2.26: Rarely used API
 588  **/
 589 gpointer
 590 g_tuples_index (GTuples     *tuples0,
 591                 gint         index,
 592                 gint         field)
 593 {
 594   GRealTuples *tuples = (GRealTuples*) tuples0;
 595
 596   g_return_val_if_fail (tuples0 != NULL, NULL);
 597   g_return_val_if_fail (field < tuples->width, NULL);
 598
 599   return tuples->data[index * tuples->width + field];
 600 }
 601
 602 /* Print
 603  */
 604
 605 static void
 606 g_relation_print_one (gpointer tuple_key,
 607                       gpointer tuple_value,
 608                       gpointer user_data)
 609 {
 610   gint i;
 611   GString *gstring;
 612   GRelation* rel = (GRelation*) user_data;
 613   gpointer* tuples = (gpointer*) tuple_value;
 614
 615   gstring = g_string_new ("[");
 616
 617   for (i = 0; i < rel->fields; i += 1)
 618     {
 619       g_string_append_printf (gstring, "%p", tuples[i]);
 620
 621       if (i < (rel->fields - 1))
 622         g_string_append (gstring, ",");
 623     }
 624
 625   g_string_append (gstring, "]");
 626   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "%s", gstring->str);
 627   g_string_free (gstring, TRUE);
 628 }
 629
 630 static void
 631 g_relation_print_index (gpointer tuple_key,
 632                         gpointer tuple_value,
 633                         gpointer user_data)
 634 {
 635   GRelation* rel = (GRelation*) user_data;
 636   GHashTable* table = (GHashTable*) tuple_value;
 637
 638   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** key %p", tuple_key);
 639
 640   g_hash_table_foreach (table,
 641                         g_relation_print_one,
 642                         rel);
 643 }
 644
 645 /**
 646  * g_relation_print:
 647  * @relation: a #GRelation.
 648  *
 649  * Outputs information about all records in a #GRelation, as well as
 650  * the indexes. It is for debugging.
 651  *
 652  * Deprecated: 2.26: Rarely used API
 653  **/
 654 void
 655 g_relation_print (GRelation *relation)
 656 {
 657   gint i;
 658
 659   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** all tuples (%d)", relation->count);
 660
 661   g_hash_table_foreach (relation->all_tuples,
 662                         g_relation_print_one,
 663                         relation);
 664
 665   for (i = 0; i < relation->fields; i += 1)
 666     {
 667       if (relation->hashed_tuple_tables[i] == NULL)
 668         continue;
 669
 670       g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** index %d", i);
 671
 672       g_hash_table_foreach (relation->hashed_tuple_tables[i],
 673                             g_relation_print_index,
 674                             relation);
 675     }
 676
 677 }