From: Thadeu Lima de Souza Cascardo <cascardo@holoscopio.com>
Date: Wed, 27 Aug 2008 17:28:42 +0000 (-0300)
Subject: Optimize a little and add some comments
X-Git-Url: http://git.cascardo.info/?p=cascardo%2Fgrammar.git;a=commitdiff_plain;h=25f6db6a70f3d138da9effa3e8c945e57cd83572

Optimize a little and add some comments
---

diff --git a/item.c b/item.c
index 8f4f4cf..657e764 100644
--- a/item.c
+++ b/item.c
@@ -385,20 +385,43 @@ GHashTable* item_collection_goto (GHashTable* collection, grammar_t* grammar,
 				  GHashTable* first, GHashTable* item_set,
 				  symbol_t* symbol)
 {
+
   GHashTable* symbols;
   GHashTable* newitem_set;
   GHashTable* goto_item_set;
   GHashTable* old_item_set;
+
+  /*
+   * Is it a new item set? Why should we insert a copy of it? Do we
+   * destroy the original later?
+   *
+   * TODO: Check why this code was once here. WTF! Caused some damn
+   * bug.
+   */
+  /*
   newitem_set = item_set_copy (item_set);
   if (!item_collection_add (collection, newitem_set, NULL))
     {
       g_hash_table_destroy (newitem_set);
     }
+  */
+
+  /*
+   * Is there a computed goto from this item set with this symbol
+   * already?
+   */
   symbols = item_collection_lookup (collection, item_set);
   if (g_hash_table_lookup_extended (symbols, symbol, NULL, NULL))
     {
       return NULL;
     }
+
+  /*
+   * If the computed goto already exists in the table, retrieve it and
+   * add the entry in the table pointing to it instead of the newly
+   * computed item set. Destroy the new copy. We don't need it. Only
+   * return the computed goto if it's a new item set.
+   */
   goto_item_set = item_set_goto (item_set, grammar, first, symbol);
   if (!item_collection_add (collection, goto_item_set, &old_item_set))
     {
@@ -413,55 +436,101 @@ GHashTable* item_collection_goto (GHashTable* collection, grammar_t* grammar,
     }
 }
 
+void get_symbol_at_dot (gpointer key, gpointer val, gpointer data)
+{
+  item_t* item;
+  GHashTable* symbols;
+  symbol_t* symbol;
+  item = (item_t*) key;
+  symbols = (GHashTable*) data;
+  if (item->dot != NULL)
+    {
+      symbol = item->dot->data;
+      if (!g_hash_table_lookup_extended (symbols, symbol, NULL, NULL))
+	{
+	  g_hash_table_insert (symbols, symbol, NULL);
+	}
+    }
+}
+
+/* Get the symbols at the dot in this item set */
+GList* item_set_symbols_at_dot (GHashTable* item_set)
+{
+  GHashTable* symbols;
+  GList* symbols_list;
+  symbols_list = NULL;
+  symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
+				   NULL, NULL);
+  g_hash_table_foreach (item_set, get_symbol_at_dot, symbols);
+  g_hash_table_foreach (symbols, put_key_on_list, &symbols_list);
+  g_hash_table_destroy (symbols);
+  return symbols_list;
+}
+
 GHashTable* item_set_collection (grammar_t* grammar, GHashTable* first,
 				 symbol_t* start)
 {
+
   GHashTable* collection;
   GHashTable* item_set;
   item_t* item;
   rule_t* rule;
   GList* new_item_sets;
+
+  /* Augmented grammar has start symbol S' -> S */
   rule = rule_new ();
   rule_append (rule, symbol_copy (start));
+
+  /* First item set is the closure of the item set with S' -> . S , $ */
   item = item_new (symbol_new (FALSE, -1), rule, symbol_new (TRUE, 0));
   item_set = item_set_new ();
   item_set_add (item_set, item);
   item_set_closure (item_set, grammar, first);
+
+  /* Insert first item set in the collection of item sets and start working */
   collection = g_hash_table_new_full (item_set_hash, item_set_equal,
 				      g_hash_table_destroy, NULL);
   item_collection_add (collection, item_set, NULL);
+
   new_item_sets = g_list_append (NULL, item_set);
+
   while (new_item_sets != NULL)
     {
       GHashTable* next_item_set;
       GHashTable* new_item_set;
-      GList* items;
+      GList* symbols;
+      /*
+       * For each item, compute the goto for the symbol at its
+       * dot. Should be done only for each symbol at a dot in the
+       * whole item set. Only new item sets are put in the new item
+       * sets list. Check item_collection_goto.
+       * 
+       * TODO: Only do this for each symbol at a dot in the item set.
+       */
       next_item_set = (GHashTable*) new_item_sets->data;
-      items = NULL;
-      g_hash_table_foreach (next_item_set, put_key_on_list, &items);
-      while (items != NULL)
+      symbols = item_set_symbols_at_dot (next_item_set);
+      while (symbols != NULL)
 	{
-	  item_t* item;
 	  symbol_t* symbol;
-	  item = (item_t*) items->data;
-	  if (item->dot != NULL)
+	  symbol = (symbol_t*) symbols->data;
+	  if ((new_item_set =
+	       item_collection_goto (collection, grammar, first,
+				     next_item_set, symbol)) != NULL)
 	    {
-	      symbol = (symbol_t*) item->dot->data;
-	      if ((new_item_set =
-		   item_collection_goto (collection, grammar, first,
-					 next_item_set, symbol)) != NULL)
-	      {
-		g_list_append (new_item_sets, new_item_set);
-	      }
+	      g_list_append (new_item_sets, new_item_set);
 	    }
-	  items = g_list_next (items);
+	  symbols = g_list_next (symbols);
 	}
-      g_list_free (items);
+      g_list_free (symbols);
       new_item_sets = g_list_next (new_item_sets);
     }
+
   g_list_free (new_item_sets);
+
 #ifdef DEBUG
   item_collection_print (collection);
 #endif
+
   return collection;
+
 }