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 | |
95 | typedef 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 | **/ |
104 | struct _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 | **/ |
124 | struct _GRealTuples |
125 | { |
126 | gint len; |
127 | gint width; |
128 | gpointer *data; |
129 | }; |
130 | |
131 | static gboolean |
132 | tuple_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 | |
141 | static guint |
142 | tuple_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 | |
159 | static GHashFunc |
160 | tuple_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 | |
173 | static GEqualFunc |
174 | tuple_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 | **/ |
198 | GRelation* |
199 | g_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 | |
210 | static void |
211 | relation_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 | |
220 | static void |
221 | g_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 | **/ |
236 | void |
237 | g_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 | **/ |
272 | void |
273 | g_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 | **/ |
296 | void |
297 | g_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 | |
339 | static void |
340 | g_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 | **/ |
389 | gint |
390 | g_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 | |
423 | static void |
424 | g_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 | **/ |
455 | GTuples* |
456 | g_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 | **/ |
502 | gint |
503 | g_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 | **/ |
538 | gboolean |
539 | g_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 | **/ |
571 | void |
572 | g_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 | **/ |
597 | gpointer |
598 | g_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 | |
613 | static void |
614 | g_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 | |
638 | static void |
639 | g_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 | **/ |
662 | void |
663 | g_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 | |