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