X-Git-Url: http://git.cascardo.eti.br/?a=blobdiff_plain;f=item.c;h=8634d90aefb6ff314894a2e980ac92d89bb9a063;hb=0032416ad5a69d4d040121e4f3c34aded139abe6;hp=fd017e24f3089ade781f075be40cd8bf1233ffeb;hpb=615eebcbb67a7f22c8248d862ac3e27fea8198cc;p=cascardo%2Fgrammar.git

diff --git a/item.c b/item.c
index fd017e2..8634d90 100644
--- a/item.c
+++ b/item.c
@@ -74,7 +74,7 @@ void item_print (item_t* item)
 {
   GList* l;
   fprintf (stdout, "%s -> ", g_quark_to_string (item->left->value));
-  l = grammar_rule_get (item->right);
+  l = grammar_get_rule (item->right);
   while (l != NULL)
     {
       symbol_t* symbol;
@@ -84,6 +84,7 @@ void item_print (item_t* item)
 	  fprintf (stdout, ".");
 	}
       fprintf (stdout, " %s ", g_quark_to_string (symbol->value));
+      l = g_list_next (l);
     }
   if (item->dot == NULL)
     {
@@ -108,16 +109,29 @@ gboolean item_set_add (GHashTable* item_set, item_t* item)
   return FALSE;
 }
 
-gboolean item_set_find (gpointer key, gpointer val, gpointer data)
+static void put_key_on_list (gpointer key, gpointer val, gpointer data)
 {
-  return !g_hash_table_lookup_extended (data, key, NULL, NULL);
+  GList** l;
+  l = (GList**) data;
+  *l = g_list_prepend (*l, key);
 }
 
 gboolean item_set_equal (gconstpointer a, gconstpointer b)
 {
+  GList* l;
+  gboolean equal;
   if (g_hash_table_size (a) != g_hash_table_size (b))
     return FALSE;
-  return (g_hash_table_find (a, item_set_find, b) == NULL);
+  l = NULL;
+  g_hash_table_foreach (a, put_key_on_list, (gpointer) &l);
+  equal = TRUE;
+  while (l != NULL && equal == TRUE)
+    {
+      equal = g_hash_table_lookup_extended (b, l->data, NULL, NULL);
+      l = g_list_next (l);
+    }
+  g_list_free (l);
+  return equal;
 }
 
 void hash_item (gpointer key, gpointer val, gpointer data)
@@ -184,13 +198,6 @@ void item_set_closure_step (GHashTable* item_set, Grammar* grammar,
     }
 }
 
-void put_key_on_list (gpointer key, gpointer val, gpointer data)
-{
-  GList** l;
-  l = (GList**) data;
-  *l = g_list_prepend (*l, key);
-}
-
 GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar)
 {
   int size;
@@ -275,66 +282,46 @@ GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar,
  * In fact, the counter may be the hash table size.
  */
 
-typedef struct
-{
-  GHashTable* symbols;
-  gint code;
-} state_t;
-
-state_t* state_new (gint code)
-{
-  state_t* state;
-  state = g_malloc (sizeof (state_t));
-  state->code = code;
-  state->symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
-					  g_free, NULL);
-  return state;
-}
-
-void state_delete (state_t* state)
-{
-  g_hash_table_destroy (state->symbols);
-  g_free (state);
-}
-
 GHashTable* item_collection_new ()
 {
   return g_hash_table_new_full (item_set_hash, item_set_equal,
-				g_hash_table_destroy, state_delete);
+				g_hash_table_destroy, g_hash_table_destroy);
 }
 
-gboolean item_collection_add (GHashTable* collection, GHashTable* item_set)
+gboolean item_collection_add (GHashTable* collection, GHashTable* item_set,
+			      GHashTable** key)
 {
-  if (!g_hash_table_lookup_extended (collection, item_set, NULL, NULL))
+  if (!g_hash_table_lookup_extended (collection, item_set,
+				     (gpointer*)key, NULL))
     {
-      state_t* state;
-      state = state_new (g_hash_table_size (collection));
-      g_hash_table_insert (collection, item_set, state);
+      GHashTable* symbols;
+      symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
+				       g_free, NULL);
+      g_hash_table_insert (collection, item_set, symbols);
       return TRUE;
     }
   return FALSE;
 }
 
-state_t* item_collection_lookup (GHashTable* collection,
-				 GHashTable* item_set)
+GHashTable* item_collection_lookup (GHashTable* collection,
+				    GHashTable* item_set)
 {
-  state_t* state;
+  GHashTable* symbols;
   if (!g_hash_table_lookup_extended (collection, item_set,
-				     NULL, (gpointer*)&state))
+				     NULL, (gpointer*)&symbols))
     {
       return NULL;
     }
-  return state;
+  return symbols;
 }
 
+#define HASH_ITEM_SET(item_set) (((GPOINTER_TO_INT(item_set) & 0x3f00) >> 8))
 #ifdef DEBUG
 void item_collection_print_each (gpointer key, gpointer val, gpointer data)
 {
   GHashTable* item_set;
-  state_t* state;
   item_set = (GHashTable*) key;
-  state = (state_t*) val;
-  fprintf (stdout, "Item %d:\n", state->code);
+  fprintf (stdout, "Item %x:\n", HASH_ITEM_SET(key));
   item_set_print (item_set);
   fprintf (stdout, "\n");
 }
@@ -342,20 +329,16 @@ void item_collection_print_each (gpointer key, gpointer val, gpointer data)
 void item_set_print_goto (gpointer key, gpointer val, gpointer data)
 {
   symbol_t* symbol;
-  gint code;
-  state_t* state;
-  symbol = (symbol_t*) symbol;
-  code = GINT_TO_POINTER (val);
-  state = (state_t*) data;
-  fprintf (stdout, "GOTO (%d, %s) =\t %d\n", state->code,
-	   g_quark_to_string (symbol->value), code);
+  symbol = (symbol_t*) key;
+  fprintf (stdout, "GOTO (%x, %s) =\t %x\n", HASH_ITEM_SET(data),
+	   g_quark_to_string (symbol->value), HASH_ITEM_SET(val));
 }
 
 void item_collection_print_goto (gpointer key, gpointer val, gpointer data)
 {
-  state_t* state;
-  state = (state_t*) val;
-  g_hash_table_foreach (state->symbols, item_set_print_goto, state);
+  GHashTable* symbols;
+  symbols = (GHashTable*) val;
+  g_hash_table_foreach (symbols, item_set_print_goto, key);
   fprintf (stdout, "\n");
 }
 
@@ -369,30 +352,32 @@ void item_collection_print (GHashTable* collection)
 GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
 				  GHashTable* item_set, symbol_t* symbol)
 {
-  state_t* state;
-  state_t* goto_state;
+  GHashTable* symbols;
   GHashTable* newitem_set;
   GHashTable* goto_item_set;
-  GHashTable* return_item_set;
+  GHashTable* old_item_set;
   newitem_set = item_set_copy (item_set);
-  if (!item_collection_add (collection, newitem_set))
+  if (!item_collection_add (collection, newitem_set, NULL))
     {
       g_hash_table_destroy (newitem_set);
     }
-  state = item_collection_lookup (collection, item_set);
-  if (g_hash_table_lookup_extended (state->symbols, symbol, NULL, NULL))
+  symbols = item_collection_lookup (collection, item_set);
+  if (g_hash_table_lookup_extended (symbols, symbol, NULL, NULL))
     {
       return NULL;
     }
   goto_item_set = item_set_goto (item_set, grammar, symbol);
-  if (!item_collection_add (collection, goto_item_set))
-    return_item_set = NULL;
+  if (!item_collection_add (collection, goto_item_set, &old_item_set))
+    {
+      g_hash_table_insert (symbols, symbol, old_item_set);
+      g_hash_table_destroy (goto_item_set);
+      return NULL;
+    }
   else
-    return_item_set = goto_item_set;
-  goto_state = item_collection_lookup (collection, goto_item_set);
-  g_hash_table_insert (state->symbols, symbol,
-		       GINT_TO_POINTER (goto_state->code));
-  return return_item_set;
+    {
+      g_hash_table_insert (symbols, symbol, goto_item_set);
+      return goto_item_set;
+    }
 }
 
 void item_set_collection (Grammar* grammar, symbol_t* start)
@@ -410,7 +395,7 @@ void item_set_collection (Grammar* grammar, symbol_t* start)
   item_set_closure (item_set, grammar);
   collection = g_hash_table_new_full (item_set_hash, item_set_equal,
 				      g_hash_table_destroy, NULL);
-  item_collection_add (collection, item_set);
+  item_collection_add (collection, item_set, NULL);
   new_item_sets = g_list_append (NULL, item_set);
   while (new_item_sets != NULL)
     {