1 /* GLIB - Library of useful routines for C programming

     2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald

     3  * Portions copyright (c) 2006 Nokia Corporation.  All rights reserved.

     4  *

     5  * This library is free software; you can redistribute it and/or

     6  * modify it under the terms of the GNU Lesser General Public

     7  * License as published by the Free Software Foundation; either

     8  * version 2 of the License, or (at your option) any later version.

     9  *

    10  * This library is distributed in the hope that it will be useful,

    11  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    13  * Lesser General Public License for more details.

    14  *

    15  * You should have received a copy of the GNU Lesser General Public

    16  * License along with this library; if not, write to the Free

    17  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

    18  */

    19 

    20 /*

    21  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS

    22  * file for a list of people on the GLib Team.  See the ChangeLog

    23  * files for a list of changes.  These files are distributed with

    24  * GLib at ftp://ftp.gtk.org/pub/gtk/. 

    25  */

    26 

    27 /* 

    28  * MT safe

    29  */

    30 

    31 #include "config.h"

    32 

    33 #include <stdarg.h>

    34 #include <string.h>

    35 

    36 #include "glib.h"

    37 #include "galias.h"

    38 

    39 

    40 typedef struct _GRealTuples        GRealTuples;

    41 

    42 struct _GRelation

    43 {

    44   gint fields;

    45   gint current_field;

    46   

    47   GHashTable   *all_tuples;

    48   GHashTable  **hashed_tuple_tables;

    49   

    50   gint count;

    51 };

    52 

    53 struct _GRealTuples

    54 {

    55   gint      len;

    56   gint      width;

    57   gpointer *data;

    58 };

    59 

    60 static gboolean

    61 tuple_equal_2 (gconstpointer v_a,

    62 	       gconstpointer v_b)

    63 {

    64   gpointer* a = (gpointer*) v_a;

    65   gpointer* b = (gpointer*) v_b;

    66   

    67   return a[0] == b[0] && a[1] == b[1];

    68 }

    69 

    70 static guint

    71 tuple_hash_2 (gconstpointer v_a)

    72 {

    73   gpointer* a = (gpointer*) v_a;

    74   

    75   return (gulong)a[0] ^ (gulong)a[1];

    76 }

    77 

    78 static GHashFunc

    79 tuple_hash (gint fields)

    80 {

    81   switch (fields)

    82     {

    83     case 2:

    84       return tuple_hash_2;

    85     default:

    86       g_error ("no tuple hash for %d", fields);

    87     }

    88   

    89   return NULL;

    90 }

    91 

    92 static GEqualFunc

    93 tuple_equal (gint fields)

    94 {

    95   switch (fields)

    96     {

    97     case 2:

    98       return tuple_equal_2;

    99     default:

   100       g_error ("no tuple equal for %d", fields);

   101     }

   102   

   103   return NULL;

   104 }

   105 

   106 EXPORT_C GRelation*

   107 g_relation_new (gint fields)

   108 {

   109   GRelation* rel = g_new0 (GRelation, 1);

   110   

   111   rel->fields = fields;

   112   rel->all_tuples = g_hash_table_new (tuple_hash (fields), tuple_equal (fields));

   113   rel->hashed_tuple_tables = g_new0 (GHashTable*, fields);  

   114   

   115   return rel;

   116 }

   117 

   118 static void

   119 relation_delete_value_tuple (gpointer tuple_key,

   120                              gpointer tuple_value,

   121                              gpointer user_data)

   122 {

   123   GRelation *relation = user_data;

   124   gpointer *tuple = tuple_value;

   125   g_slice_free1 (relation->fields * sizeof (gpointer), tuple);

   126 }

   127 

   128 static void

   129 g_relation_free_array (gpointer key, gpointer value, gpointer user_data)

   130 {

   131   g_hash_table_destroy ((GHashTable*) value);

   132 }

   133 

   134 EXPORT_C void

   135 g_relation_destroy (GRelation *relation)

   136 {

   137   gint i;

   138   

   139   if (relation)

   140     {

   141       for (i = 0; i < relation->fields; i += 1)

   142 	{

   143 	  if (relation->hashed_tuple_tables[i])

   144 	    {

   145 	      g_hash_table_foreach (relation->hashed_tuple_tables[i], g_relation_free_array, NULL);

   146 	      g_hash_table_destroy (relation->hashed_tuple_tables[i]);

   147 	    }

   148 	}

   149 

   150       g_hash_table_foreach (relation->all_tuples, relation_delete_value_tuple, relation);

   151       g_hash_table_destroy (relation->all_tuples);

   152       

   153       g_free (relation->hashed_tuple_tables);

   154       g_free (relation);

   155     }

   156 }

   157 

   158 EXPORT_C void

   159 g_relation_index (GRelation   *relation,

   160 		  gint         field,

   161 		  GHashFunc    hash_func,

   162 		  GEqualFunc   key_equal_func)

   163 {

   164   g_return_if_fail (relation != NULL);

   165   

   166   g_return_if_fail (relation->count == 0 && relation->hashed_tuple_tables[field] == NULL);

   167   

   168   relation->hashed_tuple_tables[field] = g_hash_table_new (hash_func, key_equal_func);

   169 }

   170 

   171 EXPORT_C void

   172 g_relation_insert (GRelation   *relation,

   173 		   ...)

   174 {

   175   gpointer* tuple = g_slice_alloc (relation->fields * sizeof (gpointer));

   176   va_list args;

   177   gint i;

   178   

   179   va_start (args, relation);

   180   

   181   for (i = 0; i < relation->fields; i += 1)

   182     tuple[i] = va_arg (args, gpointer);

   183   

   184   va_end (args);

   185   

   186   g_hash_table_insert (relation->all_tuples, tuple, tuple);

   187   

   188   relation->count += 1;

   189   

   190   for (i = 0; i < relation->fields; i += 1)

   191     {

   192       GHashTable *table;

   193       gpointer    key;

   194       GHashTable *per_key_table;

   195       

   196       table = relation->hashed_tuple_tables[i];

   197       

   198       if (table == NULL)

   199 	continue;

   200       

   201       key = tuple[i];

   202       per_key_table = g_hash_table_lookup (table, key);

   203       

   204       if (per_key_table == NULL)

   205 	{

   206 	  per_key_table = g_hash_table_new (tuple_hash (relation->fields), tuple_equal (relation->fields));

   207 	  g_hash_table_insert (table, key, per_key_table);

   208 	}

   209       

   210       g_hash_table_insert (per_key_table, tuple, tuple);

   211     }

   212 }

   213 

   214 static void

   215 g_relation_delete_tuple (gpointer tuple_key,

   216 			 gpointer tuple_value,

   217 			 gpointer user_data)

   218 {

   219   gpointer      *tuple = (gpointer*) tuple_value;

   220   GRelation     *relation = (GRelation *) user_data;

   221   gint           j;

   222   

   223   g_assert (tuple_key == tuple_value);

   224   

   225   for (j = 0; j < relation->fields; j += 1)

   226     {

   227       GHashTable *one_table = relation->hashed_tuple_tables[j];

   228       gpointer    one_key;

   229       GHashTable *per_key_table;

   230       

   231       if (one_table == NULL)

   232 	continue;

   233       

   234       if (j == relation->current_field)

   235 	/* can't delete from the table we're foreaching in */

   236 	continue;

   237       

   238       one_key = tuple[j];

   239       

   240       per_key_table = g_hash_table_lookup (one_table, one_key);

   241       

   242       g_hash_table_remove (per_key_table, tuple);

   243     }

   244   

   245   if (g_hash_table_remove (relation->all_tuples, tuple))

   246     g_slice_free1 (relation->fields * sizeof (gpointer), tuple);

   247   

   248   relation->count -= 1;

   249 }

   250 

   251 EXPORT_C gint

   252 g_relation_delete  (GRelation     *relation,

   253 		    gconstpointer  key,

   254 		    gint           field)

   255 {

   256   GHashTable *table = relation->hashed_tuple_tables[field];

   257   GHashTable *key_table;

   258   gint        count = relation->count;

   259   

   260   g_return_val_if_fail (relation != NULL, 0);

   261   g_return_val_if_fail (table != NULL, 0);

   262   

   263   key_table = g_hash_table_lookup (table, key);

   264   

   265   if (!key_table)

   266     return 0;

   267   

   268   relation->current_field = field;

   269   

   270   g_hash_table_foreach (key_table, g_relation_delete_tuple, relation);

   271   

   272   g_hash_table_remove (table, key);

   273   

   274   g_hash_table_destroy (key_table);

   275   

   276   /* @@@ FIXME: Remove empty hash tables. */

   277   

   278   return count - relation->count;

   279 }

   280 

   281 static void

   282 g_relation_select_tuple (gpointer tuple_key,

   283 			 gpointer tuple_value,

   284 			 gpointer user_data)

   285 {

   286   gpointer    *tuple = (gpointer*) tuple_value;

   287   GRealTuples *tuples = (GRealTuples*) user_data;

   288   gint stride = sizeof (gpointer) * tuples->width;

   289   

   290   g_assert (tuple_key == tuple_value);

   291   

   292   memcpy (tuples->data + (tuples->len * tuples->width),

   293 	  tuple,

   294 	  stride);

   295   

   296   tuples->len += 1;

   297 }

   298 

   299 EXPORT_C GTuples*

   300 g_relation_select (GRelation     *relation,

   301 		   gconstpointer  key,

   302 		   gint           field)

   303 {

   304   GHashTable  *table = relation->hashed_tuple_tables[field];

   305   GHashTable  *key_table;

   306   GRealTuples *tuples = g_new0 (GRealTuples, 1);

   307   gint count;

   308   

   309   g_return_val_if_fail (relation != NULL, NULL);

   310   g_return_val_if_fail (table != NULL, NULL);

   311   

   312   key_table = g_hash_table_lookup (table, key);

   313   

   314   if (!key_table)

   315     return (GTuples*)tuples;

   316   

   317   count = g_relation_count (relation, key, field);

   318   tuples->data = g_malloc (sizeof (gpointer) * relation->fields * count);

   319   tuples->width = relation->fields;

   320   

   321   g_hash_table_foreach (key_table, g_relation_select_tuple, tuples);

   322   

   323   g_assert (count == tuples->len);

   324   

   325   return (GTuples*)tuples;

   326 }

   327 

   328 EXPORT_C gint

   329 g_relation_count (GRelation     *relation,

   330 		  gconstpointer  key,

   331 		  gint           field)

   332 {

   333   GHashTable  *table = relation->hashed_tuple_tables[field];

   334   GHashTable  *key_table;

   335   

   336   g_return_val_if_fail (relation != NULL, 0);

   337   g_return_val_if_fail (table != NULL, 0);

   338   

   339   key_table = g_hash_table_lookup (table, key);

   340   

   341   if (!key_table)

   342     return 0;

   343   

   344   return g_hash_table_size (key_table);

   345 }

   346 

   347 EXPORT_C gboolean

   348 g_relation_exists (GRelation   *relation, ...)

   349 {

   350   gpointer *tuple = g_slice_alloc (relation->fields * sizeof (gpointer));

   351   va_list args;

   352   gint i;

   353   gboolean result;

   354   

   355   va_start(args, relation);

   356   

   357   for (i = 0; i < relation->fields; i += 1)

   358     tuple[i] = va_arg(args, gpointer);

   359   

   360   va_end(args);

   361   

   362   result = g_hash_table_lookup (relation->all_tuples, tuple) != NULL;

   363   

   364   g_slice_free1 (relation->fields * sizeof (gpointer), tuple);

   365   

   366   return result;

   367 }

   368 

   369 EXPORT_C void

   370 g_tuples_destroy (GTuples *tuples0)

   371 {

   372   GRealTuples *tuples = (GRealTuples*) tuples0;

   373   

   374   if (tuples)

   375     {

   376       g_free (tuples->data);

   377       g_free (tuples);

   378     }

   379 }

   380 

   381 EXPORT_C gpointer

   382 g_tuples_index (GTuples     *tuples0,

   383 		gint         index,

   384 		gint         field)

   385 {

   386   GRealTuples *tuples = (GRealTuples*) tuples0;

   387   

   388   g_return_val_if_fail (tuples0 != NULL, NULL);

   389   g_return_val_if_fail (field < tuples->width, NULL);

   390   

   391   return tuples->data[index * tuples->width + field];

   392 }

   393 

   394 /* Print

   395  */

   396 

   397 static void

   398 g_relation_print_one (gpointer tuple_key,

   399 		      gpointer tuple_value,

   400 		      gpointer user_data)

   401 {

   402   gint i;

   403   GString *gstring;

   404   GRelation* rel = (GRelation*) user_data;

   405   gpointer* tuples = (gpointer*) tuple_value;

   406 

   407   gstring = g_string_new ("[");

   408   

   409   for (i = 0; i < rel->fields; i += 1)

   410     {

   411       g_string_append_printf (gstring, "%p", tuples[i]);

   412       

   413       if (i < (rel->fields - 1))

   414 	g_string_append (gstring, ",");

   415     }

   416   

   417   g_string_append (gstring, "]");

   418   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, gstring->str);

   419   g_string_free (gstring, TRUE);

   420 }

   421 

   422 static void

   423 g_relation_print_index (gpointer tuple_key,

   424 			gpointer tuple_value,

   425 			gpointer user_data)

   426 {

   427   GRelation* rel = (GRelation*) user_data;

   428   GHashTable* table = (GHashTable*) tuple_value;

   429   

   430   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** key %p", tuple_key);

   431   

   432   g_hash_table_foreach (table,

   433 			g_relation_print_one,

   434 			rel);

   435 }

   436 

   437 EXPORT_C void

   438 g_relation_print (GRelation *relation)

   439 {

   440   gint i;

   441   

   442   g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** all tuples (%d)", relation->count);

   443   

   444   g_hash_table_foreach (relation->all_tuples,

   445 			g_relation_print_one,

   446 			relation);

   447   

   448   for (i = 0; i < relation->fields; i += 1)

   449     {

   450       if (relation->hashed_tuple_tables[i] == NULL)

   451 	continue;

   452       

   453       g_log (G_LOG_DOMAIN, G_LOG_LEVEL_INFO, "*** index %d", i);

   454       

   455       g_hash_table_foreach (relation->hashed_tuple_tables[i],

   456 			    g_relation_print_index,

   457 			    relation);

   458     }

   459   

   460 }

   461 

   462 #define __G_REL_C__

   463 #include "galiasdef.c"