1 /* GLIB - Library of useful routines for C programming
2 * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald
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.
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.
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.
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/.
40 * @title: Relations and Tuples
41 * @short_description: tables of data which can be indexed on any
44 * A #GRelation is a table of data which can be indexed on any number
45 * of fields, rather like simple database tables. A #GRelation contains
46 * a number of records, called tuples. Each record contains a number of
47 * fields. Records are not ordered, so it is not possible to find the
48 * record at a particular index.
50 * Note that #GRelation tables are currently limited to 2 fields.
52 * To create a GRelation, use g_relation_new().
54 * To specify which fields should be indexed, use g_relation_index().
55 * Note that this must be called before any tuples are added to the
58 * To add records to a #GRelation use g_relation_insert().
60 * To determine if a given record appears in a #GRelation, use
61 * g_relation_exists(). Note that fields are compared directly, so
62 * pointers must point to the exact same position (i.e. different
63 * copies of the same string will not match.)
65 * To count the number of records which have a particular value in a
66 * given field, use g_relation_count().
68 * To get all the records which have a particular value in a given
69 * field, use g_relation_select(). To access fields of the resulting
70 * records, use g_tuples_index(). To free the resulting records use
73 * To delete all records which have a particular value in a given
74 * field, use g_relation_delete().
76 * To destroy the #GRelation, use g_relation_destroy().
78 * To help debug #GRelation objects, use g_relation_print().
81 typedef struct _GRealTuples GRealTuples
;
86 * The #GRelation struct is an opaque data structure to represent a
87 * <link linkend="glib-Relations-and-Tuples">Relation</link>. It should
88 * only be accessed via the following functions.
95 GHashTable
*all_tuples
;
96 GHashTable
**hashed_tuple_tables
;
103 * @len: the number of records that matched.
105 * The #GTuples struct is used to return records (or tuples) from the
106 * #GRelation by g_relation_select(). It only contains one public
107 * member - the number of records that matched. To access the matched
108 * records, you must use g_tuples_index().
118 tuple_equal_2 (gconstpointer v_a
,
121 gpointer
* a
= (gpointer
*) v_a
;
122 gpointer
* b
= (gpointer
*) v_b
;
124 return a
[0] == b
[0] && a
[1] == b
[1];
128 tuple_hash_2 (gconstpointer v_a
)
130 #if GLIB_SIZEOF_VOID_P > GLIB_SIZEOF_LONG
131 /* In practise this snippet has been written for 64-bit Windows
132 * where ints are 32 bits, pointers 64 bits. More exotic platforms
135 guint
* a
= (guint
*) v_a
;
137 return (a
[0] ^ a
[1] ^ a
[2] ^ a
[3]);
139 gpointer
* a
= (gpointer
*) v_a
;
141 return (gulong
)a
[0] ^ (gulong
)a
[1];
146 tuple_hash (gint fields
)
153 g_error ("no tuple hash for %d", fields
);
160 tuple_equal (gint fields
)
165 return tuple_equal_2
;
167 g_error ("no tuple equal for %d", fields
);
175 * @fields: the number of fields.
176 * @Returns: a new #GRelation.
178 * Creates a new #GRelation with the given number of fields. Note that
179 * currently the number of fields must be 2.
182 g_relation_new (gint fields
)
184 GRelation
* rel
= g_new0 (GRelation
, 1);
186 rel
->fields
= fields
;
187 rel
->all_tuples
= g_hash_table_new (tuple_hash (fields
), tuple_equal (fields
));
188 rel
->hashed_tuple_tables
= g_new0 (GHashTable
*, fields
);
194 relation_delete_value_tuple (gpointer tuple_key
,
195 gpointer tuple_value
,
198 GRelation
*relation
= user_data
;
199 gpointer
*tuple
= tuple_value
;
200 g_slice_free1 (relation
->fields
* sizeof (gpointer
), tuple
);
204 g_relation_free_array (gpointer key
, gpointer value
, gpointer user_data
)
206 g_hash_table_destroy ((GHashTable
*) value
);
210 * g_relation_destroy:
211 * @relation: a #GRelation.
213 * Destroys the #GRelation, freeing all memory allocated. However, it
214 * does not free memory allocated for the tuple data, so you should
215 * free that first if appropriate.
218 g_relation_destroy (GRelation
*relation
)
224 for (i
= 0; i
< relation
->fields
; i
+= 1)
226 if (relation
->hashed_tuple_tables
[i
])
228 g_hash_table_foreach (relation
->hashed_tuple_tables
[i
], g_relation_free_array
, NULL
);
229 g_hash_table_destroy (relation
->hashed_tuple_tables
[i
]);
233 g_hash_table_foreach (relation
->all_tuples
, relation_delete_value_tuple
, relation
);
234 g_hash_table_destroy (relation
->all_tuples
);
236 g_free (relation
->hashed_tuple_tables
);
243 * @relation: a #GRelation.
244 * @field: the field to index, counting from 0.
245 * @hash_func: a function to produce a hash value from the field data.
246 * @key_equal_func: a function to compare two values of the given field.
248 * Creates an index on the given field. Note that this must be called
249 * before any records are added to the #GRelation.
252 g_relation_index (GRelation
*relation
,
255 GEqualFunc key_equal_func
)
257 g_return_if_fail (relation
!= NULL
);
259 g_return_if_fail (relation
->count
== 0 && relation
->hashed_tuple_tables
[field
] == NULL
);
261 relation
->hashed_tuple_tables
[field
] = g_hash_table_new (hash_func
, key_equal_func
);
266 * @relation: a #GRelation.
267 * @Varargs: the fields of the record to add. These must match the
268 * number of fields in the #GRelation, and of type #gpointer
271 * Inserts a record into a #GRelation.
274 g_relation_insert (GRelation
*relation
,
277 gpointer
* tuple
= g_slice_alloc (relation
->fields
* sizeof (gpointer
));
281 va_start (args
, relation
);
283 for (i
= 0; i
< relation
->fields
; i
+= 1)
284 tuple
[i
] = va_arg (args
, gpointer
);
288 g_hash_table_insert (relation
->all_tuples
, tuple
, tuple
);
290 relation
->count
+= 1;
292 for (i
= 0; i
< relation
->fields
; i
+= 1)
296 GHashTable
*per_key_table
;
298 table
= relation
->hashed_tuple_tables
[i
];
304 per_key_table
= g_hash_table_lookup (table
, key
);
306 if (per_key_table
== NULL
)
308 per_key_table
= g_hash_table_new (tuple_hash (relation
->fields
), tuple_equal (relation
->fields
));
309 g_hash_table_insert (table
, key
, per_key_table
);
312 g_hash_table_insert (per_key_table
, tuple
, tuple
);
317 g_relation_delete_tuple (gpointer tuple_key
,
318 gpointer tuple_value
,
321 gpointer
*tuple
= (gpointer
*) tuple_value
;
322 GRelation
*relation
= (GRelation
*) user_data
;
325 g_assert (tuple_key
== tuple_value
);
327 for (j
= 0; j
< relation
->fields
; j
+= 1)
329 GHashTable
*one_table
= relation
->hashed_tuple_tables
[j
];
331 GHashTable
*per_key_table
;
333 if (one_table
== NULL
)
336 if (j
== relation
->current_field
)
337 /* can't delete from the table we're foreaching in */
342 per_key_table
= g_hash_table_lookup (one_table
, one_key
);
344 g_hash_table_remove (per_key_table
, tuple
);
347 if (g_hash_table_remove (relation
->all_tuples
, tuple
))
348 g_slice_free1 (relation
->fields
* sizeof (gpointer
), tuple
);
350 relation
->count
-= 1;
355 * @relation: a #GRelation.
356 * @key: the value to compare with.
357 * @field: the field of each record to match.
358 * @Returns: the number of records deleted.
360 * Deletes any records from a #GRelation that have the given key value
361 * in the given field.
364 g_relation_delete (GRelation
*relation
,
369 GHashTable
*key_table
;
372 g_return_val_if_fail (relation
!= NULL
, 0);
374 table
= relation
->hashed_tuple_tables
[field
];
375 count
= relation
->count
;
377 g_return_val_if_fail (table
!= NULL
, 0);
379 key_table
= g_hash_table_lookup (table
, key
);
384 relation
->current_field
= field
;
386 g_hash_table_foreach (key_table
, g_relation_delete_tuple
, relation
);
388 g_hash_table_remove (table
, key
);
390 g_hash_table_destroy (key_table
);
392 /* @@@ FIXME: Remove empty hash tables. */
394 return count
- relation
->count
;
398 g_relation_select_tuple (gpointer tuple_key
,
399 gpointer tuple_value
,
402 gpointer
*tuple
= (gpointer
*) tuple_value
;
403 GRealTuples
*tuples
= (GRealTuples
*) user_data
;
404 gint stride
= sizeof (gpointer
) * tuples
->width
;
406 g_assert (tuple_key
== tuple_value
);
408 memcpy (tuples
->data
+ (tuples
->len
* tuples
->width
),
417 * @relation: a #GRelation.
418 * @key: the value to compare with.
419 * @field: the field of each record to match.
420 * @Returns: the records (tuples) that matched.
422 * Returns all of the tuples which have the given key in the given
423 * field. Use g_tuples_index() to access the returned records. The
424 * returned records should be freed with g_tuples_destroy().
427 g_relation_select (GRelation
*relation
,
432 GHashTable
*key_table
;
436 g_return_val_if_fail (relation
!= NULL
, NULL
);
438 table
= relation
->hashed_tuple_tables
[field
];
440 g_return_val_if_fail (table
!= NULL
, NULL
);
442 tuples
= g_new0 (GRealTuples
, 1);
443 key_table
= g_hash_table_lookup (table
, key
);
446 return (GTuples
*)tuples
;
448 count
= g_relation_count (relation
, key
, field
);
450 tuples
->data
= g_malloc (sizeof (gpointer
) * relation
->fields
* count
);
451 tuples
->width
= relation
->fields
;
453 g_hash_table_foreach (key_table
, g_relation_select_tuple
, tuples
);
455 g_assert (count
== tuples
->len
);
457 return (GTuples
*)tuples
;
462 * @relation: a #GRelation.
463 * @key: the value to compare with.
464 * @field: the field of each record to match.
465 * @Returns: the number of matches.
467 * Returns the number of tuples in a #GRelation that have the given
468 * value in the given field.
471 g_relation_count (GRelation
*relation
,
476 GHashTable
*key_table
;
478 g_return_val_if_fail (relation
!= NULL
, 0);
480 table
= relation
->hashed_tuple_tables
[field
];
482 g_return_val_if_fail (table
!= NULL
, 0);
484 key_table
= g_hash_table_lookup (table
, key
);
489 return g_hash_table_size (key_table
);
494 * @relation: a #GRelation.
495 * @Varargs: the fields of the record to compare. The number must match
496 * the number of fields in the #GRelation.
497 * @Returns: %TRUE if a record matches.
499 * Returns %TRUE if a record with the given values exists in a
500 * #GRelation. Note that the values are compared directly, so that, for
501 * example, two copies of the same string will not match.
504 g_relation_exists (GRelation
*relation
, ...)
506 gpointer
*tuple
= g_slice_alloc (relation
->fields
* sizeof (gpointer
));
511 va_start(args
, relation
);
513 for (i
= 0; i
< relation
->fields
; i
+= 1)
514 tuple
[i
] = va_arg(args
, gpointer
);
518 result
= g_hash_table_lookup (relation
->all_tuples
, tuple
) != NULL
;
520 g_slice_free1 (relation
->fields
* sizeof (gpointer
), tuple
);
527 * @tuples: the tuple data to free.
529 * Frees the records which were returned by g_relation_select(). This
530 * should always be called after g_relation_select() when you are
531 * finished with the records. The records are not removed from the
535 g_tuples_destroy (GTuples
*tuples0
)
537 GRealTuples
*tuples
= (GRealTuples
*) tuples0
;
541 g_free (tuples
->data
);
548 * @tuples: the tuple data, returned by g_relation_select().
549 * @index_: the index of the record.
550 * @field: the field to return.
551 * @Returns: the field of the record.
553 * Gets a field from the records returned by g_relation_select(). It
554 * returns the given field of the record at the given index. The
555 * returned value should not be changed.
558 g_tuples_index (GTuples
*tuples0
,
562 GRealTuples
*tuples
= (GRealTuples
*) tuples0
;
564 g_return_val_if_fail (tuples0
!= NULL
, NULL
);
565 g_return_val_if_fail (field
< tuples
->width
, NULL
);
567 return tuples
->data
[index
* tuples
->width
+ field
];
574 g_relation_print_one (gpointer tuple_key
,
575 gpointer tuple_value
,
580 GRelation
* rel
= (GRelation
*) user_data
;
581 gpointer
* tuples
= (gpointer
*) tuple_value
;
583 gstring
= g_string_new ("[");
585 for (i
= 0; i
< rel
->fields
; i
+= 1)
587 g_string_append_printf (gstring
, "%p", tuples
[i
]);
589 if (i
< (rel
->fields
- 1))
590 g_string_append (gstring
, ",");
593 g_string_append (gstring
, "]");
594 g_log (G_LOG_DOMAIN
, G_LOG_LEVEL_INFO
, "%s", gstring
->str
);
595 g_string_free (gstring
, TRUE
);
599 g_relation_print_index (gpointer tuple_key
,
600 gpointer tuple_value
,
603 GRelation
* rel
= (GRelation
*) user_data
;
604 GHashTable
* table
= (GHashTable
*) tuple_value
;
606 g_log (G_LOG_DOMAIN
, G_LOG_LEVEL_INFO
, "*** key %p", tuple_key
);
608 g_hash_table_foreach (table
,
609 g_relation_print_one
,
615 * @relation: a #GRelation.
617 * Outputs information about all records in a #GRelation, as well as
618 * the indexes. It is for debugging.
621 g_relation_print (GRelation
*relation
)
625 g_log (G_LOG_DOMAIN
, G_LOG_LEVEL_INFO
, "*** all tuples (%d)", relation
->count
);
627 g_hash_table_foreach (relation
->all_tuples
,
628 g_relation_print_one
,
631 for (i
= 0; i
< relation
->fields
; i
+= 1)
633 if (relation
->hashed_tuple_tables
[i
] == NULL
)
636 g_log (G_LOG_DOMAIN
, G_LOG_LEVEL_INFO
, "*** index %d", i
);
638 g_hash_table_foreach (relation
->hashed_tuple_tables
[i
],
639 g_relation_print_index
,
646 #include "galiasdef.c"