1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
3 *
4 * SPDX-License-Identifier: LGPL-2.1-or-later
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free
18 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 */
20
21 /*
22 * Modified by the GLib Team and others 1997-2000. See the AUTHORS
23 * file for a list of people on the GLib Team. See the ChangeLog
24 * files for a list of changes. These files are distributed with
25 * GLib at ftp://ftp.gtk.org/pub/gtk/.
26 */
27
28 /*
29 * MT safe
30 */
31
32 #include "config.h"
33
34 /* we know we are deprecated here, no need for warnings */
35 #ifndef GLIB_DISABLE_DEPRECATION_WARNINGS
36 #define GLIB_DISABLE_DEPRECATION_WARNINGS
37 #endif
38
39 #include "grel.h"
40
41 #include <glib/gmessages.h>
42 #include <glib/gtestutils.h>
43 #include <glib/gstring.h>
44 #include <glib/gslice.h>
45 #include <glib/ghash.h>
46
47 #include <stdarg.h>
48 #include <string.h>
49
50 /**
51 * GRelation:
52 *
53 * A `GRelation` is a table of data which can be indexed on any number
54 * of fields, rather like simple database tables. A `GRelation` contains
55 * a number of records, called tuples. Each record contains a number of
56 * fields. Records are not ordered, so it is not possible to find the
57 * record at a particular index.
58 *
59 * Note that `GRelation` tables are currently limited to 2 fields.
60 *
61 * To create a `GRelation`, use [func@GLib.Relation.new].
62 *
63 * To specify which fields should be indexed, use [method@GLib.Relation.index].
64 * Note that this must be called before any tuples are added to the
65 * `GRelation`.
66 *
67 * To add records to a `GRelation` use [method@GLib.Relation.insert].
68 *
69 * To determine if a given record appears in a `GRelation`, use
70 * [method@GLib.Relation.exists]. Note that fields are compared directly, so
71 * pointers must point to the exact same position (i.e. different
72 * copies of the same string will not match.)
73 *
74 * To count the number of records which have a particular value in a
75 * given field, use [method@GLib.Relation.count].
76 *
77 * To get all the records which have a particular value in a given
78 * field, use [method@GLib.Relation.select]. To access fields of the resulting
79 * records, use [method@GLib.Tuples.index]. To free the resulting records use
80 * [method@GLib.Tuples.destroy].
81 *
82 * To delete all records which have a particular value in a given
83 * field, use [method@GLib.Relation.delete].
84 *
85 * To destroy the `GRelation`, use [method@GLib.Relation.destroy].
86 *
87 * To help debug `GRelation` objects, use [method@GLib.Relation.print].
88 *
89 * `GRelation` has been marked as deprecated, since this API has never
90 * been fully implemented, is not very actively maintained and rarely
91 * used.
92 *
93 * Deprecated: 2.26: Rarely used API
94 **/
95
96 typedef struct _GRealTuples GRealTuples;
97
98 struct _GRelation
99 {
100 gint fields;
101 gint current_field;
102
103 GHashTable *all_tuples;
104 GHashTable **hashed_tuple_tables;
105
106 gint count;
107 };
108
109 /**
110 * GTuples:
111 * @len: the number of records that matched.
112 *
113 * The #GTuples struct is used to return records (or tuples) from the
114 * #GRelation by g_relation_select(). It only contains one public
115 * member - the number of records that matched. To access the matched
116 * records, you must use g_tuples_index().
117 *
118 * Deprecated: 2.26: Rarely used API
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 *
187 * Creates a new #GRelation with the given number of fields. Note that
188 * currently the number of fields must be 2.
189 *
190 * Returns: a new #GRelation.
191 *
192 * Deprecated: 2.26: Rarely used API
193 **/
194 GRelation*
195 g_relation_new (gint fields)
196 {
197 GRelation* rel = g_new0 (GRelation, 1);
198
199 rel->fields = fields;
200 rel->all_tuples = g_hash_table_new (tuple_hash (fields), tuple_equal (fields));
201 rel->hashed_tuple_tables = g_new0 (GHashTable*, fields);
202
203 return rel;
204 }
205
206 static void
207 relation_delete_value_tuple (gpointer tuple_key,
208 gpointer tuple_value,
209 gpointer user_data)
210 {
211 GRelation *relation = user_data;
212 gpointer *tuple = tuple_value;
213 g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
214 }
215
216 static void
217 g_relation_free_array (gpointer key, gpointer value, gpointer user_data)
218 {
219 g_hash_table_destroy ((GHashTable*) value);
220 }
221
222 /**
223 * g_relation_destroy:
224 * @relation: a #GRelation.
225 *
226 * Destroys the #GRelation, freeing all memory allocated. However, it
227 * does not free memory allocated for the tuple data, so you should
228 * free that first if appropriate.
229 *
230 * Deprecated: 2.26: Rarely used API
231 **/
232 void
233 g_relation_destroy (GRelation *relation)
234 {
235 gint i;
236
237 if (relation)
238 {
239 for (i = 0; i < relation->fields; i += 1)
240 {
241 if (relation->hashed_tuple_tables[i])
242 {
243 g_hash_table_foreach (relation->hashed_tuple_tables[i], g_relation_free_array, NULL);
244 g_hash_table_destroy (relation->hashed_tuple_tables[i]);
245 }
246 }
247
248 g_hash_table_foreach (relation->all_tuples, relation_delete_value_tuple, relation);
249 g_hash_table_destroy (relation->all_tuples);
250
251 g_free (relation->hashed_tuple_tables);
252 g_free (relation);
253 }
254 }
255
256 /**
257 * g_relation_index:
258 * @relation: a #GRelation.
259 * @field: the field to index, counting from 0.
260 * @hash_func: a function to produce a hash value from the field data.
261 * @key_equal_func: a function to compare two values of the given field.
262 *
263 * Creates an index on the given field. Note that this must be called
264 * before any records are added to the #GRelation.
265 *
266 * Deprecated: 2.26: Rarely used API
267 **/
268 void
269 g_relation_index (GRelation *relation,
270 gint field,
271 GHashFunc hash_func,
272 GEqualFunc key_equal_func)
273 {
274 g_return_if_fail (relation != NULL);
275
276 g_return_if_fail (relation->count == 0 && relation->hashed_tuple_tables[field] == NULL);
277
278 relation->hashed_tuple_tables[field] = g_hash_table_new (hash_func, key_equal_func);
279 }
280
281 /**
282 * g_relation_insert:
283 * @relation: a #GRelation.
284 * @...: the fields of the record to add. These must match the
285 * number of fields in the #GRelation, and of type #gpointer
286 * or #gconstpointer.
287 *
288 * Inserts a record into a #GRelation.
289 *
290 * Deprecated: 2.26: Rarely used API
291 **/
292 void
293 g_relation_insert (GRelation *relation,
294 ...)
295 {
296 gpointer* tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
297 va_list args;
298 gint i;
299
300 va_start (args, relation);
301
302 for (i = 0; i < relation->fields; i += 1)
303 tuple[i] = va_arg (args, gpointer);
304
305 va_end (args);
306
307 g_hash_table_insert (relation->all_tuples, tuple, tuple);
308
309 relation->count += 1;
310
311 for (i = 0; i < relation->fields; i += 1)
312 {
313 GHashTable *table;
314 gpointer key;
315 GHashTable *per_key_table;
316
317 table = relation->hashed_tuple_tables[i];
318
319 if (table == NULL)
320 continue;
321
322 key = tuple[i];
323 per_key_table = g_hash_table_lookup (table, key);
324
325 if (per_key_table == NULL)
326 {
327 per_key_table = g_hash_table_new (tuple_hash (relation->fields), tuple_equal (relation->fields));
328 g_hash_table_insert (table, key, per_key_table);
329 }
330
331 g_hash_table_insert (per_key_table, tuple, tuple);
332 }
333 }
334
335 static void
336 g_relation_delete_tuple (gpointer tuple_key,
337 gpointer tuple_value,
338 gpointer user_data)
339 {
340 gpointer *tuple = (gpointer*) tuple_value;
341 GRelation *relation = (GRelation *) user_data;
342 gint j;
343
344 g_assert (tuple_key == tuple_value);
345
346 for (j = 0; j < relation->fields; j += 1)
347 {
348 GHashTable *one_table = relation->hashed_tuple_tables[j];
349 gpointer one_key;
350 GHashTable *per_key_table;
351
352 if (one_table == NULL)
353 continue;
354
355 if (j == relation->current_field)
356 /* can't delete from the table we're foreaching in */
357 continue;
358
359 one_key = tuple[j];
360
361 per_key_table = g_hash_table_lookup (one_table, one_key);
362
363 g_hash_table_remove (per_key_table, tuple);
364 }
365
366 if (g_hash_table_remove (relation->all_tuples, tuple))
367 g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
368
369 relation->count -= 1;
370 }
371
372 /**
373 * g_relation_delete:
374 * @relation: a #GRelation.
375 * @key: the value to compare with.
376 * @field: the field of each record to match.
377 *
378 * Deletes any records from a #GRelation that have the given key value
379 * in the given field.
380 *
381 * Returns: the number of records deleted.
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 *
443 * Returns all of the tuples which have the given key in the given
444 * field. Use g_tuples_index() to access the returned records. The
445 * returned records should be freed with g_tuples_destroy().
446 *
447 * Returns: the records (tuples) that matched.
448 *
449 * Deprecated: 2.26: Rarely used API
450 **/
451 GTuples*
452 g_relation_select (GRelation *relation,
453 gconstpointer key,
454 gint field)
455 {
456 GHashTable *table;
457 GHashTable *key_table;
458 GRealTuples *tuples;
459 gint count;
460
461 g_return_val_if_fail (relation != NULL, NULL);
462
463 table = relation->hashed_tuple_tables[field];
464
465 g_return_val_if_fail (table != NULL, NULL);
466
467 tuples = g_new0 (GRealTuples, 1);
468 key_table = g_hash_table_lookup (table, key);
469
470 if (!key_table)
471 return (GTuples*)tuples;
472
473 count = g_relation_count (relation, key, field);
474
475 tuples->data = g_malloc (sizeof (gpointer) * relation->fields * count);
476 tuples->width = relation->fields;
477
478 g_hash_table_foreach (key_table, g_relation_select_tuple, tuples);
479
480 g_assert (count == tuples->len);
481
482 return (GTuples*)tuples;
483 }
484
485 /**
486 * g_relation_count:
487 * @relation: a #GRelation.
488 * @key: the value to compare with.
489 * @field: the field of each record to match.
490 *
491 * Returns the number of tuples in a #GRelation that have the given
492 * value in the given field.
493 *
494 * Returns: the number of matches.
495 *
496 * Deprecated: 2.26: Rarely used API
497 **/
498 gint
499 g_relation_count (GRelation *relation,
500 gconstpointer key,
501 gint field)
502 {
503 GHashTable *table;
504 GHashTable *key_table;
505
506 g_return_val_if_fail (relation != NULL, 0);
507
508 table = relation->hashed_tuple_tables[field];
509
510 g_return_val_if_fail (table != NULL, 0);
511
512 key_table = g_hash_table_lookup (table, key);
513
514 if (!key_table)
515 return 0;
516
517 return g_hash_table_size (key_table);
518 }
519
520 /**
521 * g_relation_exists:
522 * @relation: a #GRelation.
523 * @...: the fields of the record to compare. The number must match
524 * the number of fields in the #GRelation.
525 *
526 * Returns %TRUE if a record with the given values exists in a
527 * #GRelation. Note that the values are compared directly, so that, for
528 * example, two copies of the same string will not match.
529 *
530 * Returns: %TRUE if a record matches.
531 *
532 * Deprecated: 2.26: Rarely used API
533 **/
534 gboolean
535 g_relation_exists (GRelation *relation, ...)
536 {
537 gpointer *tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
538 va_list args;
539 gint i;
540 gboolean result;
541
542 va_start(args, relation);
543
544 for (i = 0; i < relation->fields; i += 1)
545 tuple[i] = va_arg(args, gpointer);
546
547 va_end(args);
548
549 result = g_hash_table_lookup (relation->all_tuples, tuple) != NULL;
550
551 g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
552
553 return result;
554 }
555
556 /**
557 * g_tuples_destroy:
558 * @tuples: the tuple data to free.
559 *
560 * Frees the records which were returned by g_relation_select(). This
561 * should always be called after g_relation_select() when you are
562 * finished with the records. The records are not removed from the
563 * #GRelation.
564 *
565 * Deprecated: 2.26: Rarely used API
566 **/
567 void
568 g_tuples_destroy (GTuples *tuples0)
569 {
570 GRealTuples *tuples = (GRealTuples*) tuples0;
571
572 if (tuples)
573 {
574 g_free (tuples->data);
575 g_free (tuples);
576 }
577 }
578
579 /**
580 * g_tuples_index:
581 * @tuples: the tuple data, returned by g_relation_select().
582 * @index_: the index of the record.
583 * @field: the field to return.
584 *
585 * Gets a field from the records returned by g_relation_select(). It
586 * returns the given field of the record at the given index. The
587 * returned value should not be changed.
588 *
589 * Returns: the field of the record.
590 *
591 * Deprecated: 2.26: Rarely used API
592 **/
593 gpointer
594 g_tuples_index (GTuples *tuples0,
595 gint index,
596 gint field)
597 {
598 GRealTuples *tuples = (GRealTuples*) tuples0;
599
600 g_return_val_if_fail (tuples0 != NULL, NULL);
601 g_return_val_if_fail (field < tuples->width, NULL);
602
603 return tuples->data[index * tuples->width + field];
604 }
605
606 /* Print
607 */
608
609 static void
610 g_relation_print_one (gpointer tuple_key,
611 gpointer tuple_value,
612 gpointer user_data)
613 {
614 gint i;
615 GString *gstring;
616 GRelation* rel = (GRelation*) user_data;
617 gpointer* tuples = (gpointer*) tuple_value;
618
619 gstring = g_string_new ("[");
620
621 for (i = 0; i < rel->fields; i += 1)
622 {
623 g_string_append_printf (gstring, "%p", tuples[i]);
624
625 if (i < (rel->fields - 1))
626 g_string_append (gstring, ",");
627 }
628
629 g_string_append (gstring, "]");
630 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "%s", gstring->str);
631 g_string_free (gstring, TRUE);
632 }
633
634 static void
635 g_relation_print_index (gpointer tuple_key,
636 gpointer tuple_value,
637 gpointer user_data)
638 {
639 GRelation* rel = (GRelation*) user_data;
640 GHashTable* table = (GHashTable*) tuple_value;
641
642 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** key %p", tuple_key);
643
644 g_hash_table_foreach (table,
645 g_relation_print_one,
646 rel);
647 }
648
649 /**
650 * g_relation_print:
651 * @relation: a #GRelation.
652 *
653 * Outputs information about all records in a #GRelation, as well as
654 * the indexes. It is for debugging.
655 *
656 * Deprecated: 2.26: Rarely used API
657 **/
658 void
659 g_relation_print (GRelation *relation)
660 {
661 gint i;
662
663 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** all tuples (%d)", relation->count);
664
665 g_hash_table_foreach (relation->all_tuples,
666 g_relation_print_one,
667 relation);
668
669 for (i = 0; i < relation->fields; i += 1)
670 {
671 if (relation->hashed_tuple_tables[i] == NULL)
672 continue;
673
674 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** index %d", i);
675
676 g_hash_table_foreach (relation->hashed_tuple_tables[i],
677 g_relation_print_index,
678 relation);
679 }
680
681 }