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 Library 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 * Library General Public License for more details.
14 * You should have received a copy of the GNU Library 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-1999. 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/.
34 typedef struct _GRealRelation GRealRelation;
35 typedef struct _GRealTuples GRealTuples;
42 GHashTable *all_tuples;
43 GHashTable **hashed_tuple_tables;
44 GMemChunk *tuple_chunk;
57 tuple_equal_2 (gconstpointer v_a,
60 gpointer* a = (gpointer*) v_a;
61 gpointer* b = (gpointer*) v_b;
63 return a[0] == b[0] && a[1] == b[1];
67 tuple_hash_2 (gconstpointer v_a)
69 gpointer* a = (gpointer*) v_a;
71 return (gulong)a[0] ^ (gulong)a[1];
75 tuple_hash (gint fields)
82 g_error ("no tuple hash for %d", fields);
89 tuple_equal (gint fields)
96 g_error ("no tuple equal for %d", fields);
103 g_relation_new (gint fields)
105 GRealRelation* rel = g_new0 (GRealRelation, 1);
107 rel->fields = fields;
108 rel->tuple_chunk = g_mem_chunk_new ("Relation Chunk",
109 fields * sizeof (gpointer),
110 fields * sizeof (gpointer) * 128,
112 rel->all_tuples = g_hash_table_new (tuple_hash (fields), tuple_equal (fields));
113 rel->hashed_tuple_tables = g_new0 (GHashTable*, fields);
115 return (GRelation*) rel;
119 g_relation_free_array (gpointer key, gpointer value, gpointer user_data)
121 g_hash_table_destroy ((GHashTable*) value);
125 g_relation_destroy (GRelation *relation)
127 GRealRelation *rel = (GRealRelation *) relation;
132 g_hash_table_destroy (rel->all_tuples);
133 g_mem_chunk_destroy (rel->tuple_chunk);
135 for (i = 0; i < rel->fields; i += 1)
137 if (rel->hashed_tuple_tables[i])
139 g_hash_table_foreach (rel->hashed_tuple_tables[i], g_relation_free_array, NULL);
140 g_hash_table_destroy (rel->hashed_tuple_tables[i]);
144 g_free (rel->hashed_tuple_tables);
150 g_relation_index (GRelation *relation,
153 GCompareFunc key_compare_func)
155 GRealRelation *rel = (GRealRelation *) relation;
157 g_assert (rel->count == 0 && rel->hashed_tuple_tables[field] == NULL);
159 rel->hashed_tuple_tables[field] = g_hash_table_new (hash_func, key_compare_func);
163 g_relation_insert (GRelation *relation,
166 GRealRelation *rel = (GRealRelation *) relation;
167 gpointer* tuple = g_chunk_new (gpointer, rel->tuple_chunk);
171 va_start(args, relation);
173 for (i = 0; i < rel->fields; i += 1)
174 tuple[i] = va_arg(args, gpointer);
178 g_hash_table_insert (rel->all_tuples, tuple, tuple);
182 for (i = 0; i < rel->fields; i += 1)
186 GHashTable *per_key_table;
188 table = rel->hashed_tuple_tables[i];
194 per_key_table = g_hash_table_lookup (table, key);
196 if (per_key_table == NULL)
198 per_key_table = g_hash_table_new (tuple_hash (rel->fields), tuple_equal (rel->fields));
199 g_hash_table_insert (table, key, per_key_table);
202 g_hash_table_insert (per_key_table, tuple, tuple);
207 g_relation_delete_tuple (gpointer tuple_key, gpointer tuple_value, gpointer user_data)
209 gpointer *tuple = (gpointer*) tuple_value;
210 GRealRelation *rel = (GRealRelation *) user_data;
213 g_assert (tuple_key == tuple_value);
215 for (j = 0; j < rel->fields; j += 1)
217 GHashTable *one_table = rel->hashed_tuple_tables[j];
219 GHashTable *per_key_table;
221 if (one_table == NULL)
224 if (j == rel->current_field)
225 /* can't delete from the table we're foreaching in */
230 per_key_table = g_hash_table_lookup (one_table, one_key);
232 g_hash_table_remove (per_key_table, tuple);
235 g_hash_table_remove (rel->all_tuples, tuple);
241 g_relation_delete (GRelation *relation,
245 GRealRelation *rel = (GRealRelation *) relation;
246 GHashTable *table = rel->hashed_tuple_tables[field];
247 GHashTable *key_table;
248 gint count = rel->count;
252 key_table = g_hash_table_lookup (table, key);
257 rel->current_field = field;
259 g_hash_table_foreach (key_table, g_relation_delete_tuple, rel);
261 g_hash_table_remove (table, key);
263 g_hash_table_destroy (key_table);
265 /* @@@ FIXME: Remove empty hash tables. */
267 return count - rel->count;
271 g_relation_select_tuple (gpointer tuple_key, gpointer tuple_value, gpointer user_data)
273 gpointer *tuple = (gpointer*) tuple_value;
274 GRealTuples *tuples = (GRealTuples*) user_data;
275 gint stride = sizeof (gpointer) * tuples->width;
277 g_assert (tuple_key == tuple_value);
279 memcpy (tuples->data + (tuples->len * tuples->width),
287 g_relation_select (GRelation *relation,
291 GRealRelation *rel = (GRealRelation *) relation;
292 GHashTable *table = rel->hashed_tuple_tables[field];
293 GHashTable *key_table;
294 GRealTuples *tuples = g_new0 (GRealTuples, 1);
299 key_table = g_hash_table_lookup (table, key);
302 return (GTuples*)tuples;
304 count = g_relation_count (relation, key, field);
306 tuples->data = g_malloc (sizeof (gpointer) * rel->fields * count);
307 tuples->width = rel->fields;
309 g_hash_table_foreach (key_table, g_relation_select_tuple, tuples);
311 g_assert (count == tuples->len);
313 return (GTuples*)tuples;
317 g_relation_count (GRelation *relation,
321 GRealRelation *rel = (GRealRelation *) relation;
322 GHashTable *table = rel->hashed_tuple_tables[field];
323 GHashTable *key_table;
327 key_table = g_hash_table_lookup (table, key);
332 return g_hash_table_size (key_table);
336 g_relation_exists (GRelation *relation, ...)
338 GRealRelation *rel = (GRealRelation *) relation;
339 gpointer* tuple = g_chunk_new (gpointer, rel->tuple_chunk);
344 va_start(args, relation);
346 for (i = 0; i < rel->fields; i += 1)
347 tuple[i] = va_arg(args, gpointer);
351 result = g_hash_table_lookup (rel->all_tuples, tuple) != NULL;
353 g_mem_chunk_free (rel->tuple_chunk, tuple);
359 g_tuples_destroy (GTuples *tuples0)
361 GRealTuples *tuples = (GRealTuples*) tuples0;
365 g_free (tuples->data);
371 g_tuples_index (GTuples *tuples0,
375 GRealTuples *tuples = (GRealTuples*) tuples0;
377 g_assert (field < tuples->width);
379 return tuples->data[index * tuples->width + field];
386 g_relation_print_one (gpointer tuple_key,
387 gpointer tuple_value,
392 GRealRelation* rel = (GRealRelation*) user_data;
393 gpointer* tuples = (gpointer*) tuple_value;
395 gstring = g_string_new ("[");
397 for (i = 0; i < rel->fields; i += 1)
399 g_string_sprintfa (gstring, "%p", tuples[i]);
401 if (i < (rel->fields - 1))
402 g_string_append (gstring, ",");
405 g_string_append (gstring, "]");
406 g_log (g_log_domain_glib, G_LOG_LEVEL_INFO, gstring->str);
407 g_string_free (gstring, TRUE);
411 g_relation_print_index (gpointer tuple_key,
412 gpointer tuple_value,
415 GRealRelation* rel = (GRealRelation*) user_data;
416 GHashTable* table = (GHashTable*) tuple_value;
418 g_log (g_log_domain_glib, G_LOG_LEVEL_INFO, "*** key %p", tuple_key);
420 g_hash_table_foreach (table,
421 g_relation_print_one,
426 g_relation_print (GRelation *relation)
429 GRealRelation* rel = (GRealRelation*) relation;
431 g_log (g_log_domain_glib, G_LOG_LEVEL_INFO, "*** all tuples (%d)", rel->count);
433 g_hash_table_foreach (rel->all_tuples,
434 g_relation_print_one,
437 for (i = 0; i < rel->fields; i += 1)
439 if (rel->hashed_tuple_tables[i] == NULL)
442 g_log (g_log_domain_glib, G_LOG_LEVEL_INFO, "*** index %d", i);
444 g_hash_table_foreach (rel->hashed_tuple_tables[i],
445 g_relation_print_index,