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