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

source code of gtk/subprojects/glib/glib/deprecated/grel.c