[Eliot-dev] eliot configure.in dic/Makefile.am dic/compdic....

[Olivier Teulière]

CVSROOT:        /cvsroot/eliot
Module name:    eliot
Changes by:     Olivier Teulière <ipkiss>       09/05/01 09:04:48

Modified files:
        .              : configure.in 
        dic            : Makefile.am compdic.cpp 
Removed files:
        dic            : hashtable.cpp hashtable.h hashtable.i 

Log message:
        Got rid of the custom HashTable class: Boost.Unordered provides a 
better one for free...

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/eliot/configure.in?cvsroot=eliot&r1=1.35&r2=1.36
http://cvs.savannah.gnu.org/viewcvs/eliot/dic/Makefile.am?cvsroot=eliot&r1=1.20&r2=1.21
http://cvs.savannah.gnu.org/viewcvs/eliot/dic/compdic.cpp?cvsroot=eliot&r1=1.8&r2=1.9
http://cvs.savannah.gnu.org/viewcvs/eliot/dic/hashtable.cpp?cvsroot=eliot&r1=1.3&r2=0
http://cvs.savannah.gnu.org/viewcvs/eliot/dic/hashtable.h?cvsroot=eliot&r1=1.8&r2=0
http://cvs.savannah.gnu.org/viewcvs/eliot/dic/hashtable.i?cvsroot=eliot&r1=1.2&r2=0

Patches:
Index: configure.in
===================================================================
RCS file: /cvsroot/eliot/eliot/configure.in,v
retrieving revision 1.35
retrieving revision 1.36
diff -u -b -r1.35 -r1.36
--- configure.in        22 Feb 2009 16:43:28 -0000      1.35
+++ configure.in        1 May 2009 09:04:47 -0000       1.36
@@ -105,7 +105,8 @@
 dnl --------------------------------------------------------------
 
 dnl Check for the Boost libraries (in fact we only need the headers)
-AX_BOOST_BASE([1.33.1])
+dnl We need at least version 1.36, for Boost.Unordered
+AX_BOOST_BASE([1.36.0])
 
 PKG_CHECK_MODULES(LIBCONFIG, [libconfig++],
                   [has_libconfig=1

Index: dic/Makefile.am
===================================================================
RCS file: /cvsroot/eliot/eliot/dic/Makefile.am,v
retrieving revision 1.20
retrieving revision 1.21
diff -u -b -r1.20 -r1.21
--- dic/Makefile.am     7 Sep 2008 13:17:40 -0000       1.20
+++ dic/Makefile.am     1 May 2009 09:04:47 -0000       1.21
@@ -42,8 +42,7 @@
        listdic \
        regexp
 
-compdic_SOURCES=compdic.cpp \
-       hashtable.h hashtable.cpp hashtable.i
+compdic_SOURCES=compdic.cpp
 compdic_CPPFLAGS=$(AM_CPPFLAGS) @BOOST_CPPFLAGS@
 compdic_LDADD=libdic.a @LIBINTL@
 

Index: dic/compdic.cpp
===================================================================
RCS file: /cvsroot/eliot/eliot/dic/compdic.cpp,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -b -r1.8 -r1.9
--- dic/compdic.cpp     28 Feb 2009 09:23:07 -0000      1.8
+++ dic/compdic.cpp     1 May 2009 09:04:47 -0000       1.9
@@ -27,6 +27,8 @@
 #include <vector>
 #include <map>
 #include <boost/tokenizer.hpp>
+#include <boost/unordered_map.hpp>
+#include <boost/functional/hash.hpp>
 #include <getopt.h>
 #include <ctime>
 #include <sys/types.h>
@@ -60,7 +62,6 @@
 #   include <windows.h>
 #endif
 
-#include "hashtable.h"
 #include "encoding.h"
 #include "header.h"
 #include "dic_internals.h"
@@ -247,15 +248,13 @@
 
 // Hashing function for a vector of DicEdge, based on the hashing function
 // of the HashTable
-struct HashVector
+size_t hash_value(const DicEdge &iEdge)
 {
-    unsigned int operator()(const vector<DicEdge> &iKey) const
-    {
-        if (iKey.empty())
-            return 0;
-        return HashPtr(&iKey.front(), iKey.size() * sizeof(DicEdge));
-    }
-};
+    const uint32_t *num = reinterpret_cast<const uint32_t*>(&iEdge);
+    size_t seed = 0;
+    boost::hash_combine(seed, *num);
+    return seed;
+}
 
 #ifdef CHECK_RECURSION
 class IncDec
@@ -280,7 +279,9 @@
 #endif
 
 /* global variables */
-HashTable<vector<DicEdge>, unsigned int, HashVector> *global_hashtable;
+typedef boost::unordered_map<vector<DicEdge>, unsigned int> HashMap;
+
+HashMap *global_hashmap;
 
 wchar_t  global_stringbuf[MAX_STRING_LENGTH]; /* Space for current string */
 wchar_t* global_endstring;                    /* Marks END of current string */
@@ -373,18 +374,18 @@
     // Mark the last edge
     edges.back().last = 1;
 
-    const unsigned int *saved_position = global_hashtable->find(edges);
-    if (saved_position)
+    HashMap::const_iterator itMap = global_hashmap->find(edges);
+    if (itMap != global_hashmap->end())
     {
         ioHeaderInfo.edgessaved += numedges;
         ioHeaderInfo.nodessaved++;
 
-        return *saved_position;
+        return itMap->second;
     }
     else
     {
         unsigned int node_pos = ioHeaderInfo.edgesused;
-        global_hashtable->add(edges, ioHeaderInfo.edgesused);
+        (*global_hashmap)[edges] = ioHeaderInfo.edgesused;
         ioHeaderInfo.edgesused += numedges;
         ioHeaderInfo.nodesused++;
         write_node(reinterpret_cast<uint32_t*>(&edges.front()),
@@ -530,9 +531,7 @@
         global_input = uncompressed;
         global_endofinput = global_input + dicsize;
 
-#define SCALE 0.6
-        global_hashtable = new HashTable<vector<DicEdge>, unsigned int, 
HashVector>((unsigned int)(dicsize * SCALE));
-#undef SCALE
+        global_hashmap = new HashMap();
 
         headerInfo.dawg = true;
         Header tempHeader = skip_init_header(outfile, headerInfo);
@@ -562,7 +561,7 @@
         Header aHeader(headerInfo);
         aHeader.print();
 
-        delete global_hashtable;
+        delete global_hashmap;
         delete[] uncompressed;
         outfile.close();
 

Index: dic/hashtable.cpp
===================================================================
RCS file: dic/hashtable.cpp
diff -N dic/hashtable.cpp
--- dic/hashtable.cpp   22 Nov 2008 13:09:28 -0000      1.3
+++ /dev/null   1 Jan 1970 00:00:00 -0000
@@ -1,45 +0,0 @@
-/*****************************************************************************
- * Eliot
- * Copyright (C) 1999-2007 Antoine Fraboulet & Olivier Teulière
- * Authors: Antoine Fraboulet <antoine.fraboulet @@ free.fr>
- *          Olivier Teulière <ipkiss @@ gmail.com>
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program 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 General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
- *****************************************************************************/
-
-#include "hashtable.h"
-
-
-unsigned int HashPtr(const void *iPtr, unsigned int iSize)
-{
-    unsigned int key = 0;
-
-    if (iSize % sizeof(unsigned int) == 0)
-    {
-        const unsigned int *ptr =
-            reinterpret_cast<const unsigned int*>(iPtr);
-        for (unsigned int i = 0; i < (iSize / sizeof(unsigned int)); ++i)
-            key ^= (key << 3) ^ (key >> 1) ^ ptr[i];
-    }
-    else
-    {
-        const unsigned char *ptr =
-            reinterpret_cast<const unsigned char*>(iPtr);
-        for (unsigned int i = 0; i < iSize; ++i)
-            key ^= (key << 3) ^ (key >> 1) ^ ptr[i];
-    }
-    return key;
-}
-

Index: dic/hashtable.h
===================================================================
RCS file: dic/hashtable.h
diff -N dic/hashtable.h
--- dic/hashtable.h     22 Nov 2008 13:09:28 -0000      1.8
+++ /dev/null   1 Jan 1970 00:00:00 -0000
@@ -1,75 +0,0 @@
-/*****************************************************************************
- * Eliot
- * Copyright (C) 1999-2007 Antoine Fraboulet & Olivier Teulière
- * Authors: Antoine Fraboulet <antoine.fraboulet @@ free.fr>
- *          Olivier Teulière <ipkiss @@ gmail.com>
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program 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 General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
- *****************************************************************************/
-
-#ifndef _HASHTABLE_H
-#define _HASHTABLE_H
-
-
-/// Compute a hash for the data pointed to by iPtr
-/**
- * This function is useful to define the HASH_FCN template parameter
- * of HashTable.
- */
-unsigned int HashPtr(const void *iPtr, unsigned int iSize);
-
-
-template<typename KEY, typename VALUE, typename HASH_FCN>
-class HashTable
-{
-    public:
-        /// Constructor taking the number of records in the table
-        HashTable(unsigned int iSize);
-
-        /// Destructor
-        ~HashTable();
-
-        /// Return the number of records in the table
-        unsigned int size() const { return m_size; }
-
-        /// Return the value corresponding to the given key, or NULL if not 
found
-        const VALUE *find(const KEY &iKey) const;
-
-        /// Add a new key/value pair (both the key and the value are copied)
-        void add(const KEY& iKey, const VALUE &iValue);
-
-    private:
-        /// Maximum number of records
-        unsigned int m_size;
-
-        /// Definition of a record
-        class Node
-        {
-            public:
-                Node(const KEY &iKey, const VALUE &iValue, const Node *iNext);
-                ~Node();
-                KEY m_key;
-                VALUE m_value;
-                const Node *m_next;
-        };
-
-        /// All the nodes
-        const Node **m_nodes;
-};
-
-// Include the implementation of the template
-#include "hashtable.i"
-
-#endif /* _HASHTABLE_H_ */

Index: dic/hashtable.i
===================================================================
RCS file: dic/hashtable.i
diff -N dic/hashtable.i
--- dic/hashtable.i     8 Jan 2008 13:52:35 -0000       1.2
+++ /dev/null   1 Jan 1970 00:00:00 -0000
@@ -1,88 +0,0 @@
-/*****************************************************************************
- * Eliot
- * Copyright (C) 1999-2007 Antoine Fraboulet & Olivier Teulière
- * Authors: Antoine Fraboulet
- *          Olivier Teulière <ipkiss @@ gmail.com>
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program 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 General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
- *****************************************************************************/
-
-#include <cstdlib>
-
-#include "hashtable.h"
-
-
-template<typename KEY, typename VALUE, typename HASH_FCN>
-HashTable<KEY, VALUE, HASH_FCN>::HashTable(unsigned int iSize)
-    : m_size(iSize)
-{
-    m_nodes = new const Node*[m_size];
-    for (unsigned int i = 0; i < m_size; ++i)
-    {
-        m_nodes[i] = NULL;
-    }
-}
-
-
-template<typename KEY, typename VALUE, typename HASH_FCN>
-HashTable<KEY, VALUE, HASH_FCN>::~HashTable()
-{
-    for (unsigned int i = 0; i < m_size; ++i)
-        delete m_nodes[i];
-    delete[] m_nodes;
-}
-
-
-template<typename KEY, typename VALUE, typename HASH_FCN>
-HashTable<KEY, VALUE, HASH_FCN>::Node::Node(const KEY &iKey, const VALUE 
&iValue, const Node *iNext)
-    : m_key(iKey), m_value(iValue), m_next(iNext)
-{
-}
-
-
-template<typename KEY, typename VALUE, typename HASH_FCN>
-HashTable<KEY, VALUE, HASH_FCN>::Node::~Node()
-{
-    delete m_next;
-}
-
-
-template<typename KEY, typename VALUE, typename HASH_FCN>
-const VALUE *HashTable<KEY, VALUE, HASH_FCN>::find(const KEY &iKey) const
-{
-    HASH_FCN aHashFunc;
-    unsigned int h_key = aHashFunc(iKey) % m_size;
-    for (const Node *entry = m_nodes[h_key]; entry; entry = entry->m_next)
-    {
-        // Note: we need to be able to call == on a type KEY
-        if (entry->m_key == iKey)
-        {
-            return &entry->m_value;
-        }
-    }
-    return NULL;
-}
-
-
-template<typename KEY, typename VALUE, typename HASH_FCN>
-void HashTable<KEY, VALUE, HASH_FCN>::add(const KEY &iKey, const VALUE &iValue)
-{
-    HASH_FCN aHashFunc;
-    unsigned int h_key = aHashFunc(iKey) % m_size;
-    const Node *entry = new Node(iKey, iValue, m_nodes[h_key]);
-    m_nodes[h_key] = entry;
-}
-
-// vim: ft=cpp