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/.
39 typedef struct _GRealTuples GRealTuples;
46 GHashTable *all_tuples;
47 GHashTable **hashed_tuple_tables;
60 tuple_equal_2 (gconstpointer v_a,
63 gpointer* a = (gpointer*) v_a;
64 gpointer* b = (gpointer*) v_b;
66 return a[0] == b[0] && a[1] == b[1];
70 tuple_hash_2 (gconstpointer v_a)
72 gpointer* a = (gpointer*) v_a;
74 return (gulong)a[0] ^ (gulong)a[1];
78 tuple_hash (gint fields)
85 g_error ("no tuple hash for %d", fields);
92 tuple_equal (gint fields)
99 g_error ("no tuple equal for %d", fields);
106 g_relation_new (gint fields)
108 GRelation* rel = g_new0 (GRelation, 1);
110 rel->fields = fields;
111 rel->all_tuples = g_hash_table_new (tuple_hash (fields), tuple_equal (fields));
112 rel->hashed_tuple_tables = g_new0 (GHashTable*, fields);
118 relation_delete_value_tuple (gpointer tuple_key,
119 gpointer tuple_value,
122 GRelation *relation = user_data;
123 gpointer *tuple = tuple_value;
124 g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
128 g_relation_free_array (gpointer key, gpointer value, gpointer user_data)
130 g_hash_table_destroy ((GHashTable*) value);
134 g_relation_destroy (GRelation *relation)
140 for (i = 0; i < relation->fields; i += 1)
142 if (relation->hashed_tuple_tables[i])
144 g_hash_table_foreach (relation->hashed_tuple_tables[i], g_relation_free_array, NULL);
145 g_hash_table_destroy (relation->hashed_tuple_tables[i]);
149 g_hash_table_foreach (relation->all_tuples, relation_delete_value_tuple, relation);
150 g_hash_table_destroy (relation->all_tuples);
152 g_free (relation->hashed_tuple_tables);
158 g_relation_index (GRelation *relation,
161 GEqualFunc key_equal_func)
163 g_return_if_fail (relation != NULL);
165 g_return_if_fail (relation->count == 0 && relation->hashed_tuple_tables[field] == NULL);
167 relation->hashed_tuple_tables[field] = g_hash_table_new (hash_func, key_equal_func);
171 g_relation_insert (GRelation *relation,
174 gpointer* tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
178 va_start (args, relation);
180 for (i = 0; i < relation->fields; i += 1)
181 tuple[i] = va_arg (args, gpointer);
185 g_hash_table_insert (relation->all_tuples, tuple, tuple);
187 relation->count += 1;
189 for (i = 0; i < relation->fields; i += 1)
193 GHashTable *per_key_table;
195 table = relation->hashed_tuple_tables[i];
201 per_key_table = g_hash_table_lookup (table, key);
203 if (per_key_table == NULL)
205 per_key_table = g_hash_table_new (tuple_hash (relation->fields), tuple_equal (relation->fields));
206 g_hash_table_insert (table, key, per_key_table);
209 g_hash_table_insert (per_key_table, tuple, tuple);
214 g_relation_delete_tuple (gpointer tuple_key,
215 gpointer tuple_value,
218 gpointer *tuple = (gpointer*) tuple_value;
219 GRelation *relation = (GRelation *) user_data;
222 g_assert (tuple_key == tuple_value);
224 for (j = 0; j < relation->fields; j += 1)
226 GHashTable *one_table = relation->hashed_tuple_tables[j];
228 GHashTable *per_key_table;
230 if (one_table == NULL)
233 if (j == relation->current_field)
234 /* can't delete from the table we're foreaching in */
239 per_key_table = g_hash_table_lookup (one_table, one_key);
241 g_hash_table_remove (per_key_table, tuple);
244 if (g_hash_table_remove (relation->all_tuples, tuple))
245 g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
247 relation->count -= 1;
251 g_relation_delete (GRelation *relation,
255 GHashTable *table = relation->hashed_tuple_tables[field];
256 GHashTable *key_table;
257 gint count = relation->count;
259 g_return_val_if_fail (relation != NULL, 0);
260 g_return_val_if_fail (table != NULL, 0);
262 key_table = g_hash_table_lookup (table, key);
267 relation->current_field = field;
269 g_hash_table_foreach (key_table, g_relation_delete_tuple, relation);
271 g_hash_table_remove (table, key);
273 g_hash_table_destroy (key_table);
275 /* @@@ FIXME: Remove empty hash tables. */
277 return count - relation->count;
281 g_relation_select_tuple (gpointer tuple_key,
282 gpointer tuple_value,
285 gpointer *tuple = (gpointer*) tuple_value;
286 GRealTuples *tuples = (GRealTuples*) user_data;
287 gint stride = sizeof (gpointer) * tuples->width;
289 g_assert (tuple_key == tuple_value);
291 memcpy (tuples->data + (tuples->len * tuples->width),
299 g_relation_select (GRelation *relation,
303 GHashTable *table = relation->hashed_tuple_tables[field];
304 GHashTable *key_table;
305 GRealTuples *tuples = g_new0 (GRealTuples, 1);
308 g_return_val_if_fail (relation != NULL, NULL);
309 g_return_val_if_fail (table != NULL, NULL);
311 key_table = g_hash_table_lookup (table, key);
314 return (GTuples*)tuples;
316 count = g_relation_count (relation, key, field);
318 tuples->data = g_malloc (sizeof (gpointer) * relation->fields * count);
319 tuples->width = relation->fields;
321 g_hash_table_foreach (key_table, g_relation_select_tuple, tuples);
323 g_assert (count == tuples->len);
325 return (GTuples*)tuples;
329 g_relation_count (GRelation *relation,
333 GHashTable *table = relation->hashed_tuple_tables[field];
334 GHashTable *key_table;
336 g_return_val_if_fail (relation != NULL, 0);
337 g_return_val_if_fail (table != NULL, 0);
339 key_table = g_hash_table_lookup (table, key);
344 return g_hash_table_size (key_table);
348 g_relation_exists (GRelation *relation, ...)
350 gpointer *tuple = g_slice_alloc (relation->fields * sizeof (gpointer));
355 va_start(args, relation);
357 for (i = 0; i < relation->fields; i += 1)
358 tuple[i] = va_arg(args, gpointer);
362 result = g_hash_table_lookup (relation->all_tuples, tuple) != NULL;
364 g_slice_free1 (relation->fields * sizeof (gpointer), tuple);
370 g_tuples_destroy (GTuples *tuples0)
372 GRealTuples *tuples = (GRealTuples*) tuples0;
376 g_free (tuples->data);
382 g_tuples_index (GTuples *tuples0,
386 GRealTuples *tuples = (GRealTuples*) tuples0;
388 g_return_val_if_fail (tuples0 != NULL, NULL);
389 g_return_val_if_fail (field < tuples->width, NULL);
391 return tuples->data[index * tuples->width + field];
398 g_relation_print_one (gpointer tuple_key,
399 gpointer tuple_value,
404 GRelation* rel = (GRelation*) user_data;
405 gpointer* tuples = (gpointer*) tuple_value;
407 gstring = g_string_new ("[");
409 for (i = 0; i < rel->fields; i += 1)
411 g_string_append_printf (gstring, "%p", tuples[i]);
413 if (i < (rel->fields - 1))
414 g_string_append (gstring, ",");
417 g_string_append (gstring, "]");
418 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, gstring->str);
419 g_string_free (gstring, TRUE);
423 g_relation_print_index (gpointer tuple_key,
424 gpointer tuple_value,
427 GRelation* rel = (GRelation*) user_data;
428 GHashTable* table = (GHashTable*) tuple_value;
430 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** key %p", tuple_key);
432 g_hash_table_foreach (table,
433 g_relation_print_one,
438 g_relation_print (GRelation *relation)
442 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** all tuples (%d)", relation->count);
444 g_hash_table_foreach (relation->all_tuples,
445 g_relation_print_one,
448 for (i = 0; i < relation->fields; i += 1)
450 if (relation->hashed_tuple_tables[i] == NULL)
453 g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** index %d", i);
455 g_hash_table_foreach (relation->hashed_tuple_tables[i],
456 g_relation_print_index,
463 #include "galiasdef.c"