| /* GLIB - Library of useful routines for C programming |
| * Copyright (C) 1995-1997 Peter Mattis, Spencer Kimball and Josh MacDonald |
| * |
| * This library is free software; you can redistribute it and/or |
| * modify it under the terms of the GNU Library General Public |
| * License as published by the Free Software Foundation; either |
| * version 2 of the License, or (at your option) any later version. |
| * |
| * This library is distributed in the hope that it will be useful, |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| * Library General Public License for more details. |
| * |
| * You should have received a copy of the GNU Library General Public |
| * License along with this library; if not, write to the Free |
| * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. |
| */ |
| #include "glib.h" |
| #include <stdarg.h> |
| #include <string.h> |
| |
| typedef struct _GRealRelation GRealRelation; |
| typedef struct _GRealTuples GRealTuples; |
| |
| struct _GRealRelation |
| { |
| gint fields; |
| gint current_field; |
| |
| GHashTable *all_tuples; |
| GHashTable **hashed_tuple_tables; |
| GMemChunk *tuple_chunk; |
| |
| gint count; |
| }; |
| |
| struct _GRealTuples |
| { |
| gint len; |
| gint width; |
| gpointer *data; |
| }; |
| |
| static gboolean |
| tuple_equal_2 (gconstpointer v_a, |
| gconstpointer v_b) |
| { |
| gpointer* a = (gpointer*) v_a; |
| gpointer* b = (gpointer*) v_b; |
| |
| return a[0] == b[0] && a[1] == b[1]; |
| } |
| |
| static guint |
| tuple_hash_2 (gconstpointer v_a) |
| { |
| gpointer* a = (gpointer*) v_a; |
| |
| return (gulong)a[0] ^ (gulong)a[1]; |
| } |
| |
| static GHashFunc |
| tuple_hash (gint fields) |
| { |
| switch (fields) |
| { |
| case 2: |
| return tuple_hash_2; |
| default: |
| g_error ("no tuple hash for %d", fields); |
| } |
| |
| return NULL; |
| } |
| |
| static GCompareFunc |
| tuple_equal (gint fields) |
| { |
| switch (fields) |
| { |
| case 2: |
| return tuple_equal_2; |
| default: |
| g_error ("no tuple equal for %d", fields); |
| } |
| |
| return NULL; |
| } |
| |
| GRelation* |
| g_relation_new (gint fields) |
| { |
| GRealRelation* rel = g_new0 (GRealRelation, 1); |
| |
| rel->fields = fields; |
| rel->tuple_chunk = g_mem_chunk_new ("Relation Chunk", |
| fields * sizeof (gpointer), |
| fields * sizeof (gpointer) * 128, |
| G_ALLOC_AND_FREE); |
| rel->all_tuples = g_hash_table_new (tuple_hash (fields), tuple_equal (fields)); |
| rel->hashed_tuple_tables = g_new0 (GHashTable*, fields); |
| |
| return (GRelation*) rel; |
| } |
| |
| static void |
| g_relation_free_array (gpointer key, gpointer value, gpointer user_data) |
| { |
| g_hash_table_destroy ((GHashTable*) value); |
| } |
| |
| void |
| g_relation_destroy (GRelation *relation) |
| { |
| GRealRelation *rel = (GRealRelation *) relation; |
| gint i; |
| |
| if (rel) |
| { |
| g_hash_table_destroy (rel->all_tuples); |
| g_mem_chunk_destroy (rel->tuple_chunk); |
| |
| for (i = 0; i < rel->fields; i += 1) |
| { |
| if (rel->hashed_tuple_tables[i]) |
| { |
| g_hash_table_foreach (rel->hashed_tuple_tables[i], g_relation_free_array, NULL); |
| g_hash_table_destroy (rel->hashed_tuple_tables[i]); |
| } |
| } |
| |
| g_free (rel->hashed_tuple_tables); |
| g_free (rel); |
| } |
| } |
| |
| void |
| g_relation_index (GRelation *relation, |
| gint field, |
| GHashFunc hash_func, |
| GCompareFunc key_compare_func) |
| { |
| GRealRelation *rel = (GRealRelation *) relation; |
| |
| g_assert (rel->count == 0 && rel->hashed_tuple_tables[field] == NULL); |
| |
| rel->hashed_tuple_tables[field] = g_hash_table_new (hash_func, key_compare_func); |
| } |
| |
| void |
| g_relation_insert (GRelation *relation, |
| ...) |
| { |
| GRealRelation *rel = (GRealRelation *) relation; |
| gpointer* tuple = g_chunk_new (gpointer, rel->tuple_chunk); |
| va_list args; |
| gint i; |
| |
| va_start(args, relation); |
| |
| for (i = 0; i < rel->fields; i += 1) |
| tuple[i] = va_arg(args, gpointer); |
| |
| va_end(args); |
| |
| g_hash_table_insert (rel->all_tuples, tuple, tuple); |
| |
| rel->count += 1; |
| |
| for (i = 0; i < rel->fields; i += 1) |
| { |
| GHashTable *table; |
| gpointer key; |
| GHashTable *per_key_table; |
| |
| table = rel->hashed_tuple_tables[i]; |
| |
| if (table == NULL) |
| continue; |
| |
| key = tuple[i]; |
| per_key_table = g_hash_table_lookup (table, key); |
| |
| if (per_key_table == NULL) |
| { |
| per_key_table = g_hash_table_new (tuple_hash (rel->fields), tuple_equal (rel->fields)); |
| g_hash_table_insert (table, key, per_key_table); |
| } |
| |
| g_hash_table_insert (per_key_table, tuple, tuple); |
| } |
| } |
| |
| static void |
| g_relation_delete_tuple (gpointer tuple_key, gpointer tuple_value, gpointer user_data) |
| { |
| gpointer *tuple = (gpointer*) tuple_value; |
| GRealRelation *rel = (GRealRelation *) user_data; |
| gint j; |
| |
| g_assert (tuple_key == tuple_value); |
| |
| for (j = 0; j < rel->fields; j += 1) |
| { |
| GHashTable *one_table = rel->hashed_tuple_tables[j]; |
| gpointer one_key; |
| GHashTable *per_key_table; |
| |
| if (one_table == NULL) |
| continue; |
| |
| if (j == rel->current_field) |
| /* can't delete from the table we're foreaching in */ |
| continue; |
| |
| one_key = tuple[j]; |
| |
| per_key_table = g_hash_table_lookup (one_table, one_key); |
| |
| g_hash_table_remove (per_key_table, tuple); |
| } |
| |
| g_hash_table_remove (rel->all_tuples, tuple); |
| |
| rel->count -= 1; |
| } |
| |
| gint |
| g_relation_delete (GRelation *relation, |
| gconstpointer key, |
| gint field) |
| { |
| GRealRelation *rel = (GRealRelation *) relation; |
| GHashTable *table = rel->hashed_tuple_tables[field]; |
| GHashTable *key_table; |
| gint count = rel->count; |
| |
| g_assert (table); |
| |
| key_table = g_hash_table_lookup (table, key); |
| |
| if (!key_table) |
| return 0; |
| |
| rel->current_field = field; |
| |
| g_hash_table_foreach (key_table, g_relation_delete_tuple, rel); |
| |
| g_hash_table_remove (table, key); |
| |
| g_hash_table_destroy (key_table); |
| |
| /* @@@ FIXME: Remove empty hash tables. */ |
| |
| return count - rel->count; |
| } |
| |
| static void |
| g_relation_select_tuple (gpointer tuple_key, gpointer tuple_value, gpointer user_data) |
| { |
| gpointer *tuple = (gpointer*) tuple_value; |
| GRealTuples *tuples = (GRealTuples*) user_data; |
| gint stride = sizeof (gpointer) * tuples->width; |
| |
| g_assert (tuple_key == tuple_value); |
| |
| memcpy (tuples->data + (tuples->len * tuples->width), |
| tuple, |
| stride); |
| |
| tuples->len += 1; |
| } |
| |
| GTuples* |
| g_relation_select (GRelation *relation, |
| gconstpointer key, |
| gint field) |
| { |
| GRealRelation *rel = (GRealRelation *) relation; |
| GHashTable *table = rel->hashed_tuple_tables[field]; |
| GHashTable *key_table; |
| GRealTuples *tuples = g_new0 (GRealTuples, 1); |
| gint count; |
| |
| g_assert (table); |
| |
| key_table = g_hash_table_lookup (table, key); |
| |
| if (!key_table) |
| return (GTuples*)tuples; |
| |
| count = g_relation_count (relation, key, field); |
| |
| tuples->data = g_malloc (sizeof (gpointer) * rel->fields * count); |
| tuples->width = rel->fields; |
| |
| g_hash_table_foreach (key_table, g_relation_select_tuple, tuples); |
| |
| g_assert (count == tuples->len); |
| |
| return (GTuples*)tuples; |
| } |
| |
| gint |
| g_relation_count (GRelation *relation, |
| gconstpointer key, |
| gint field) |
| { |
| GRealRelation *rel = (GRealRelation *) relation; |
| GHashTable *table = rel->hashed_tuple_tables[field]; |
| GHashTable *key_table; |
| |
| g_assert (table); |
| |
| key_table = g_hash_table_lookup (table, key); |
| |
| if (!key_table) |
| return 0; |
| |
| return g_hash_table_size (key_table); |
| } |
| |
| gboolean |
| g_relation_exists (GRelation *relation, ...) |
| { |
| GRealRelation *rel = (GRealRelation *) relation; |
| gpointer* tuple = g_chunk_new (gpointer, rel->tuple_chunk); |
| va_list args; |
| gint i; |
| gboolean result; |
| |
| va_start(args, relation); |
| |
| for (i = 0; i < rel->fields; i += 1) |
| tuple[i] = va_arg(args, gpointer); |
| |
| va_end(args); |
| |
| result = g_hash_table_lookup (rel->all_tuples, tuple) != NULL; |
| |
| g_mem_chunk_free (rel->tuple_chunk, tuple); |
| |
| return result; |
| } |
| |
| void |
| g_tuples_destroy (GTuples *tuples0) |
| { |
| GRealTuples *tuples = (GRealTuples*) tuples0; |
| |
| if (tuples) |
| { |
| g_free (tuples->data); |
| g_free (tuples); |
| } |
| } |
| |
| gpointer |
| g_tuples_index (GTuples *tuples0, |
| gint index, |
| gint field) |
| { |
| GRealTuples *tuples = (GRealTuples*) tuples0; |
| |
| g_assert (field < tuples->width); |
| |
| return tuples->data[index * tuples->width + field]; |
| } |
| |
| /* Print |
| */ |
| |
| static void |
| g_relation_print_one (gpointer tuple_key, |
| gpointer tuple_value, |
| gpointer user_data) |
| { |
| gint i; |
| GString *gstring; |
| GRealRelation* rel = (GRealRelation*) user_data; |
| gpointer* tuples = (gpointer*) tuple_value; |
| |
| gstring = g_string_new ("["); |
| |
| for (i = 0; i < rel->fields; i += 1) |
| { |
| g_string_sprintfa (gstring, "%p", tuples[i]); |
| |
| if (i < (rel->fields - 1)) |
| g_string_append (gstring, ","); |
| } |
| |
| g_string_append (gstring, "]"); |
| g_log (g_log_domain_glib, G_LOG_LEVEL_INFO, gstring->str); |
| g_string_free (gstring, TRUE); |
| } |
| |
| static void |
| g_relation_print_index (gpointer tuple_key, |
| gpointer tuple_value, |
| gpointer user_data) |
| { |
| GRealRelation* rel = (GRealRelation*) user_data; |
| GHashTable* table = (GHashTable*) tuple_value; |
| |
| g_log (g_log_domain_glib, G_LOG_LEVEL_INFO, "*** key %p", tuple_key); |
| |
| g_hash_table_foreach (table, |
| g_relation_print_one, |
| rel); |
| } |
| |
| void |
| g_relation_print (GRelation *relation) |
| { |
| gint i; |
| GRealRelation* rel = (GRealRelation*) relation; |
| |
| g_log (g_log_domain_glib, G_LOG_LEVEL_INFO, "*** all tuples (%d)", rel->count); |
| |
| g_hash_table_foreach (rel->all_tuples, |
| g_relation_print_one, |
| rel); |
| |
| for (i = 0; i < rel->fields; i += 1) |
| { |
| if (rel->hashed_tuple_tables[i] == NULL) |
| continue; |
| |
| g_log (g_log_domain_glib, G_LOG_LEVEL_INFO, "*** index %d", i); |
| |
| g_hash_table_foreach (rel->hashed_tuple_tables[i], |
| g_relation_print_index, |
| rel); |
| } |
| |
| } |