zorba-coders team mailing list archive
-
zorba-coders team
-
Mailing list archive
-
Message #11008
[Merge] lp:~paul-lucas/zorba/feature-unordered_map into lp:zorba
Paul J. Lucas has proposed merging lp:~paul-lucas/zorba/feature-unordered_map into lp:zorba.
Requested reviews:
Matthias Brantner (matthias-brantner)
For more details, see:
https://code.launchpad.net/~paul-lucas/zorba/feature-unordered_map/+merge/110657
Added C++98 subset of C++11's unordered_map. The configure process checks for a working C++11 unordered_map first: if found, it will be used instead. The goal is to phase out the old hash*map* classes over time.
--
https://code.launchpad.net/~paul-lucas/zorba/feature-unordered_map/+merge/110657
Your team Zorba Coders is subscribed to branch lp:zorba.
=== modified file 'CMakeLists.txt'
--- CMakeLists.txt 2012-06-15 21:31:03 +0000
+++ CMakeLists.txt 2012-06-16 14:48:21 +0000
@@ -123,15 +123,29 @@
CHECK_TYPE_SIZE("__int32" ZORBA_HAVE_MS_INT32)
CHECK_TYPE_SIZE("int64_t" ZORBA_HAVE_INT64_T)
-CHECK_CXX_SOURCE_COMPILES ("#include <type_traits>\nint main() { std::enable_if<true,int> x; }" ZORBA_CXX_ENABLE_IF)
+# C++ built-in type sizes
+CHECK_TYPE_SIZE("double" ZORBA_SIZEOF_DOUBLE BUILTIN_TYPES_ONLY)
+CHECK_TYPE_SIZE("float" ZORBA_SIZEOF_FLOAT BUILTIN_TYPES_ONLY)
+CHECK_TYPE_SIZE("int" ZORBA_SIZEOF_INT BUILTIN_TYPES_ONLY)
+CHECK_TYPE_SIZE("long" ZORBA_SIZEOF_LONG BUILTIN_TYPES_ONLY)
+CHECK_TYPE_SIZE("long long" ZORBA_SIZEOF_LONG_LONG BUILTIN_TYPES_ONLY)
+CHECK_TYPE_SIZE("void*" ZORBA_SIZEOF_POINTER BUILTIN_TYPES_ONLY)
+CHECK_TYPE_SIZE("short" ZORBA_SIZEOF_SHORT BUILTIN_TYPES_ONLY)
+CHECK_TYPE_SIZE("size_t" ZORBA_SIZEOF_SIZE_T)
SET(CMAKE_EXTRA_INCLUDE_FILES wchar.h)
CHECK_TYPE_SIZE("wchar_t" ZORBA_SIZEOF_WCHAR_T)
SET(CMAKE_EXTRA_INCLUDE_FILES)
-CHECK_CXX_SOURCE_COMPILES ("#include <memory>\nint main() { std::unique_ptr<int> p; }" ZORBA_CXX_UNIQUE_PTR)
+# C++11 langauge features
CHECK_CXX_SOURCE_COMPILES("int main() { int *p = nullptr; }" ZORBA_CXX_NULLPTR)
CHECK_CXX_SOURCE_COMPILES("int main() { static_assert(1,\"\"); }" ZORBA_CXX_STATIC_ASSERT)
+# C++11 standard library types
+CHECK_CXX_SOURCE_COMPILES ("#include <type_traits>\nint main() { std::enable_if<true,int> x; }" ZORBA_HAVE_ENABLE_IF)
+CHECK_CXX_SOURCE_COMPILES ("#include <memory>\nint main() { std::unique_ptr<int> p; }" ZORBA_HAVE_UNIQUE_PTR)
+CHECK_CXX_SOURCE_COMPILES ("#include <unordered_map>\nint main() { std::unordered_map<int,int> m; }" ZORBA_HAVE_UNORDERED_MAP)
+CHECK_CXX_SOURCE_COMPILES ("#include <unordered_set>\nint main() { std::unordered_set<int> s; }" ZORBA_HAVE_UNORDERED_SET)
+
################################################################################
# Various cmake macros
=== modified file 'include/zorba/config.h.cmake'
--- include/zorba/config.h.cmake 2012-06-15 21:31:03 +0000
+++ include/zorba/config.h.cmake 2012-06-16 14:48:21 +0000
@@ -68,6 +68,15 @@
#cmakedefine ZORBA_HAVE_MS_INT32
#cmakedefine ZORBA_HAVE_MS_UINT32
#cmakedefine ZORBA_HAVE_UINT32_T
+#cmakedefine ZORBA_SIZEOF_DOUBLE @ZORBA_SIZEOF_DOUBLE@
+#cmakedefine ZORBA_SIZEOF_FLOAT @ZORBA_SIZEOF_FLOAT@
+#cmakedefine ZORBA_SIZEOF_INT @ZORBA_SIZEOF_INT@
+#cmakedefine ZORBA_SIZEOF_LONG @ZORBA_SIZEOF_LONG@
+#cmakedefine ZORBA_SIZEOF_LONG_LONG @ZORBA_SIZEOF_LONG_LONG@
+#cmakedefine ZORBA_SIZEOF_POINTER @ZORBA_SIZEOF_POINTER@
+#cmakedefine ZORBA_SIZEOF_SHORT @ZORBA_SIZEOF_SHORT@
+#cmakedefine ZORBA_SIZEOF_SIZE_T @ZORBA_SIZEOF_SIZE_T@
+#cmakedefine ZORBA_SIZEOF_WCHAR_T @ZORBA_SIZEOF_WCHAR_T@
// Platform libraries
#cmakedefine ZORBA_HAVE_CURL
@@ -96,8 +105,6 @@
typedef __int64 int64_t;
#endif /* ZORBA_HAVE_INT64_T */
-#cmakedefine ZORBA_SIZEOF_WCHAR_T @ZORBA_SIZEOF_WCHAR_T@
-
// Compiler
#cmakedefine CLANG
#cmakedefine MSVC
@@ -106,11 +113,15 @@
#cmakedefine MSVC71
#cmakedefine MSVC80
-// C++ language features
-#cmakedefine ZORBA_CXX_ENABLE_IF
+// C++11 language features
#cmakedefine ZORBA_CXX_NULLPTR
#cmakedefine ZORBA_CXX_STATIC_ASSERT
-#cmakedefine ZORBA_CXX_UNIQUE_PTR
+
+// C++11 types
+#cmakedefine ZORBA_HAVE_ENABLE_IF
+#cmakedefine ZORBA_HAVE_UNORDERED_MAP
+#cmakedefine ZORBA_HAVE_UNORDERED_SET
+#cmakedefine ZORBA_HAVE_UNIQUE_PTR
////////// C++ tr1 include directory & namespace //////////////////////////////
=== modified file 'include/zorba/internal/type_traits.h'
--- include/zorba/internal/type_traits.h 2012-06-15 21:31:03 +0000
+++ include/zorba/internal/type_traits.h 2012-06-16 14:48:21 +0000
@@ -27,7 +27,7 @@
///////////////////////////////////////////////////////////////////////////////
-#ifndef ZORBA_CXX_ENABLE_IF
+#ifndef ZORBA_HAVE_ENABLE_IF
namespace std {
/**
@@ -49,11 +49,11 @@
};
} // namespace std
-#endif /* ZORBA_CXX_ENABLE_IF */
+#endif /* ZORBA_HAVE_ENABLE_IF */
///////////////////////////////////////////////////////////////////////////////
-#ifndef ZORBA_CXX_UNIQUE_PTR
+#ifndef ZORBA_HAVE_UNIQUE_PTR
namespace zorba {
namespace internal {
@@ -90,7 +90,7 @@
} // namespace internal
} // namespace zorba
-#endif /* ZORBA_CXX_UNIQUE_PTR */
+#endif /* ZORBA_HAVE_UNIQUE_PTR */
///////////////////////////////////////////////////////////////////////////////
=== modified file 'include/zorba/internal/unique_ptr.h'
--- include/zorba/internal/unique_ptr.h 2012-06-15 21:31:03 +0000
+++ include/zorba/internal/unique_ptr.h 2012-06-16 14:48:21 +0000
@@ -19,7 +19,7 @@
#include <zorba/config.h>
-#ifdef ZORBA_CXX_UNIQUE_PTR
+#ifdef ZORBA_HAVE_UNIQUE_PTR
# include <memory> /* for unique_ptr */
# include <utility> /* for forward, move */
#else
@@ -577,6 +577,6 @@
} // namespace std
-#endif /* ZORBA_CXX_UNIQUE_PTR */
+#endif /* ZORBA_HAVE_UNIQUE_PTR */
#endif /* ZORBA_UNIQUE_PTR_H */
/* vim:set et sw=2 ts=2: */
=== modified file 'src/compiler/codegen/plan_visitor.cpp'
--- src/compiler/codegen/plan_visitor.cpp 2012-06-15 21:31:03 +0000
+++ src/compiler/codegen/plan_visitor.cpp 2012-06-16 14:48:21 +0000
@@ -26,7 +26,6 @@
#include "util/tracer.h"
#include "util/stl_util.h"
-#include "util/hashmap32.h"
#include "system/globalenv.h"
#include "system/properties.h"
=== modified file 'src/functions/function.cpp'
--- src/functions/function.cpp 2012-06-15 21:31:03 +0000
+++ src/functions/function.cpp 2012-06-16 14:48:21 +0000
@@ -24,7 +24,6 @@
#include "types/typeops.h"
-#include "util/hashmap32.h"
#include "util/string_util.h"
#include "diagnostics/assert.h"
=== modified file 'src/unit_tests/CMakeLists.txt'
--- src/unit_tests/CMakeLists.txt 2012-06-15 21:31:03 +0000
+++ src/unit_tests/CMakeLists.txt 2012-06-16 14:48:21 +0000
@@ -35,4 +35,11 @@
test_icu_streambuf.cpp)
ENDIF (NOT ZORBA_NO_ICU)
-# vim:set et sw=2 tw=2:
+IF (NOT ZORBA_CXX_UNORDERE_MAP)
+ LIST (APPEND UNIT_TEST_SRCS
+ unordered_map.cpp
+ unordered_map_instantiate.cpp
+ unordered_set.cpp)
+ENDIF (NOT ZORBA_CXX_UNORDERE_MAP)
+
+# vim:set et sw=2 ts=2:
=== modified file 'src/unit_tests/unit_test_list.h'
--- src/unit_tests/unit_test_list.h 2012-06-15 21:31:03 +0000
+++ src/unit_tests/unit_test_list.h 2012-06-16 14:48:21 +0000
@@ -34,19 +34,21 @@
int test_thesaurus( int, char*[] );
int test_tokenizer( int, char*[] );
#endif /* ZORBA_NO_FULL_TEXT */
- /**
- * ADD NEW UNIT TESTS HERE
- */
#ifndef ZORBA_NO_ICU
int test_icu_streambuf( int, char*[] );
#endif /* ZORBA_NO_ICU */
int json_parser( int, char*[] );
+#ifndef ZORBA_HAVE_UNORDERED_MAP
+ int test_unordered_map( int, char*[] );
+#endif /* ZORBA_HAVE_UNORDERED_MAP */
+#ifndef ZORBA_HAVE_UNORDERED_MAP
+ int test_unordered_set( int, char*[] );
+#endif /* ZORBA_HAVE_UNORDERED_MAP */
void initializeTestList();
};
-
-} /* namespace zorba */
+} // namespace zorba
#endif /* ZORBA_UNIT_TEST_LIST_H */
/* vim:set et sw=2 ts=2: */
=== modified file 'src/unit_tests/unit_tests.cpp'
--- src/unit_tests/unit_tests.cpp 2012-06-15 21:31:03 +0000
+++ src/unit_tests/unit_tests.cpp 2012-06-16 14:48:21 +0000
@@ -50,6 +50,12 @@
libunittests["thesaurus"] = test_thesaurus;
libunittests["tokenizer"] = test_tokenizer;
#endif /* ZORBA_NO_FULL_TEXT */
+#ifndef ZORBA_HAVE_UNORDERED_MAP
+ libunittests["unordered_map"] = test_unordered_map;
+#endif /* ZORBA_HAVE_UNORDERED_MAP */
+#ifndef ZORBA_HAVE_UNORDERED_MAP
+ libunittests["unordered_set"] = test_unordered_set;
+#endif /* ZORBA_HAVE_UNORDERED_MAP */
#ifdef ZORBA_WITH_DEBUGGER
// libunittests["debugger_protocol"] = runDebuggerProtocolTest;
=== added file 'src/unit_tests/unordered_map.cpp'
--- src/unit_tests/unordered_map.cpp 1970-01-01 00:00:00 +0000
+++ src/unit_tests/unordered_map.cpp 2012-06-16 14:48:21 +0000
@@ -0,0 +1,263 @@
+/*
+ * Copyright 2006-2008 The FLWOR Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "stdafx.h"
+#include <iostream>
+#include <string>
+
+#include "util/unordered_map.h"
+
+using namespace std;
+
+typedef unordered_map<string,int> map_type;
+typedef pair<map_type::iterator,bool> insert_return_type;
+typedef pair<map_type::iterator,map_type::iterator> equal_range_return_type;
+
+///////////////////////////////////////////////////////////////////////////////
+
+static int failures;
+
+static bool assert_true( char const *expr, int line, bool result ) {
+ if ( !result ) {
+ cout << "FAILED, line " << line << ": " << expr << endl;
+ ++failures;
+ }
+ return result;
+}
+
+static void print_exception( char const *expr, int line,
+ std::exception const &e ) {
+ assert_true( expr, line, false );
+ cout << "+ exception: " << e.what() << endl;
+}
+
+#define ASSERT_TRUE( EXPR ) assert_true( #EXPR, __LINE__, !!(EXPR) )
+
+#define ASSERT_TRUE_AND_NO_EXCEPTION( EXPR ) \
+ try { ASSERT_TRUE( EXPR ); } \
+ catch ( std::exception const &e ) { print_exception( #EXPR, __LINE__, e ); } \
+ catch ( ... ) { assert_true( #EXPR, __LINE__, false ); }
+
+#define ASSERT_EXCEPTION( EXPR, EXCEPTION ) \
+ try { EXPR; assert_true( #EXPR, __LINE__, false ); } \
+ catch ( EXCEPTION const& ) { }
+
+///////////////////////////////////////////////////////////////////////////////
+
+static void test_at() {
+ map_type m;
+ m[ "a" ] = 1;
+ m[ "b" ] = 2;
+ ASSERT_TRUE_AND_NO_EXCEPTION( m.at( "a" ) == 1 );
+ ASSERT_TRUE_AND_NO_EXCEPTION( m.at( "b" ) == 2 );
+ ASSERT_EXCEPTION( m.at( "c" ), out_of_range );
+
+ map_type const mc( m );
+ ASSERT_TRUE_AND_NO_EXCEPTION( mc.at( "a" ) == 1 );
+ ASSERT_TRUE_AND_NO_EXCEPTION( mc.at( "b" ) == 2 );
+ ASSERT_EXCEPTION( mc.at( "c" ), out_of_range );
+}
+
+static void test_basics() {
+ map_type m;
+
+ ASSERT_TRUE( m.empty() );
+ ASSERT_TRUE( m.size() == 0 );
+
+ m[ "a" ] = 1;
+ m[ "b" ] = 2;
+
+ ASSERT_TRUE( !m.empty() );
+ ASSERT_TRUE( m.size() == 2 );
+
+ map_type m2( m );
+
+ ASSERT_TRUE( !m2.empty() );
+ ASSERT_TRUE( m2.size() == 2 );
+
+ m2.clear();
+ ASSERT_TRUE( m2.empty() );
+ ASSERT_TRUE( m2.size() == 0 );
+
+ // Ensure 'm' is unaffected by changes to 'm2'.
+ ASSERT_TRUE( !m.empty() );
+ ASSERT_TRUE( m.size() == 2 );
+}
+
+static void test_erase() {
+ map_type m;
+ map_type::iterator i;
+
+ m[ "a" ] = 1;
+ m[ "b" ] = 2;
+
+ ASSERT_TRUE( m.erase( "a" ) == 1 );
+ ASSERT_TRUE( m.erase( "a" ) == 0 );
+ ASSERT_TRUE( !m.empty() );
+ ASSERT_TRUE( m.size() == 1 );
+
+ if ( ASSERT_TRUE( (i = m.find( "b" )) != m.end() ) ) {
+ m.erase( i );
+ ASSERT_TRUE( m.empty() );
+ ASSERT_TRUE( m.size() == 0 );
+ }
+}
+
+static void test_insert() {
+ map_type m;
+ equal_range_return_type err;
+ map_type::const_iterator i;
+ insert_return_type ir;
+
+ ir = m.insert( make_pair( "a", 1 ) );
+ if ( ASSERT_TRUE( ir.second == true ) )
+ if ( ASSERT_TRUE( ir.first != m.end() ) ) {
+ ASSERT_TRUE( ir.first->first == "a" );
+ ASSERT_TRUE( ir.first->second == 1 );
+ }
+ ASSERT_TRUE( !m.empty() );
+ ASSERT_TRUE( m.size() == 1 );
+ ASSERT_TRUE_AND_NO_EXCEPTION( m.at( "a" ) == 1 );
+ ASSERT_TRUE( m[ "a" ] == 1 );
+ ASSERT_TRUE( m.count( "a" ) == 1 );
+ if ( ASSERT_TRUE( (i = m.find( "a" )) != m.end() ) ) {
+ ASSERT_TRUE( i->first == "a" );
+ ASSERT_TRUE( i->second == 1 );
+ }
+
+ err = m.equal_range( "a" );
+ if ( ASSERT_TRUE( err.first != m.end() ) )
+ ASSERT_TRUE( err.first->second == 1 );
+
+ ir = m.insert( make_pair( "b", 2 ) );
+ if ( ASSERT_TRUE( ir.second == true ) ) {
+ ASSERT_TRUE( ir.first->first == "b" );
+ ASSERT_TRUE( ir.first->second == 2 );
+ }
+ ASSERT_TRUE( !m.empty() );
+ ASSERT_TRUE( m.size() == 2 );
+ ASSERT_TRUE_AND_NO_EXCEPTION( m.at( "b" ) == 2 );
+ ASSERT_TRUE( m[ "b" ] == 2 );
+ ASSERT_TRUE( m.count( "b" ) == 1 );
+ if ( ASSERT_TRUE( (i = m.find( "b" )) != m.end() ) ) {
+ ASSERT_TRUE( i->first == "b" );
+ ASSERT_TRUE( i->second == 2 );
+ }
+ ASSERT_TRUE( m.equal_range( "b" ).first->second == 2 );
+
+ // Ensure "a" is still there.
+ ASSERT_TRUE_AND_NO_EXCEPTION( m.at( "a" ) == 1 );
+ ASSERT_TRUE( m[ "a" ] == 1 );
+ ASSERT_TRUE( m.count( "a" ) == 1 );
+ if ( ASSERT_TRUE( (i = m.find( "a" )) != m.end() ) ) {
+ ASSERT_TRUE( i->first == "a" );
+ ASSERT_TRUE( i->second == 1 );
+ }
+ ASSERT_TRUE( m.equal_range( "a" ).first->second == 1 );
+}
+
+static void test_local_iterator() {
+ map_type m;
+
+ char s[2];
+ s[1] = '\0';
+ for ( int i = 0; i < 26; ++i ) {
+ *s = (char)('a' + i);
+ m[ s ] = i + 1;
+ }
+
+ map_type::size_type b = m.bucket( "a" );
+ ASSERT_TRUE( m.bucket_size( b ) > 0 );
+
+ bool found_a = false;
+ map_type::local_iterator i( m.begin( b ) );
+ map_type::local_iterator const j( m.end( b ) );
+ for ( ; i != j; ++i )
+ if ( i->first == "a" ) {
+ found_a = true;
+ break;
+ }
+ ASSERT_TRUE( found_a );
+}
+
+static void test_rehash() {
+ unordered_map<int,int> m;
+ unordered_map<int,int>::size_type const initial_buckets = m.bucket_count();
+
+ // Add elements until bucket_count() changes which implies a rehash was done.
+ for ( int i = 0; m.bucket_count() == initial_buckets; ++i )
+ m[ i ] = i;
+
+ ASSERT_TRUE( m.bucket_count() > initial_buckets );
+
+ // Ensure all the elements are still there.
+ unordered_map<int,int>::size_type const size = m.size();
+ for ( int i = 0; i < size; ++i )
+ ASSERT_TRUE_AND_NO_EXCEPTION( m.at( i ) == i );
+}
+
+static void test_swap() {
+ map_type m;
+ m[ "a" ] = 1;
+ m[ "b" ] = 2;
+
+ map_type m2;
+ m2[ "c" ] = 3;
+ m2[ "d" ] = 4;
+ m2[ "e" ] = 5;
+
+ m.swap( m2 );
+
+ ASSERT_TRUE( m.size() == 3 );
+ ASSERT_TRUE( m2.size() == 2 );
+
+ ASSERT_EXCEPTION( m.at( "a" ), out_of_range );
+ ASSERT_EXCEPTION( m.at( "b" ), out_of_range );
+ ASSERT_TRUE_AND_NO_EXCEPTION( m.at( "c" ) == 3 );
+ ASSERT_TRUE_AND_NO_EXCEPTION( m.at( "d" ) == 4 );
+ ASSERT_TRUE_AND_NO_EXCEPTION( m.at( "e" ) == 5 );
+
+ ASSERT_TRUE_AND_NO_EXCEPTION( m2.at( "a" ) == 1 );
+ ASSERT_TRUE_AND_NO_EXCEPTION( m2.at( "b" ) == 2 );
+ ASSERT_EXCEPTION( m2.at( "c" ), out_of_range );
+ ASSERT_EXCEPTION( m2.at( "d" ), out_of_range );
+ ASSERT_EXCEPTION( m2.at( "e" ), out_of_range );
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+namespace zorba {
+namespace UnitTests {
+
+int test_unordered_map( int, char*[] ) {
+ test_basics();
+ test_at();
+ test_erase();
+ test_insert();
+ test_local_iterator();
+ test_rehash();
+ test_swap();
+
+ cout << failures << " test(s) failed\n";
+ return failures ? 1 : 0;
+}
+
+} // namespace UnitTests
+} // namespace zorba
+
+///////////////////////////////////////////////////////////////////////////////
+
+/* vim:set et sw=2 ts=2: */
=== added file 'src/unit_tests/unordered_map_instantiate.cpp'
--- src/unit_tests/unordered_map_instantiate.cpp 1970-01-01 00:00:00 +0000
+++ src/unit_tests/unordered_map_instantiate.cpp 2012-06-16 14:48:21 +0000
@@ -0,0 +1,118 @@
+/*
+ * Copyright 2006-2008 The FLWOR Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <string>
+
+#include "util/unordered_map.h"
+
+using namespace std;
+
+static void instantiate() {
+ return;
+
+ typedef unordered_map<string,int> map_type;
+
+ map_type::iterator i, j;
+ map_type::const_iterator ci, cj;
+
+ (void)*i;
+ (void)i->first;
+ (void)i->second;
+ (void)++i;
+ (void)i++;
+ (void)(i == j);
+ (void)(i != j);
+
+ (void)*ci;
+ (void)ci->first;
+ (void)ci->second;
+ (void)++ci;
+ (void)ci++;
+ (void)(ci == cj);
+ (void)(ci != cj);
+
+ map_type::local_iterator li, lj;
+ map_type::const_local_iterator cli, clj;
+
+ (void)*li;
+ (void)li->first;
+ (void)li->second;
+ (void)++li;
+ (void)li++;
+ (void)(li == lj);
+ (void)(li != lj);
+
+ (void)*cli;
+ (void)cli->first;
+ (void)cli->second;
+ (void)++cli;
+ (void)cli++;
+ (void)(cli == clj);
+ (void)(cli != clj);
+
+ map_type m;
+ map_type m2( m );
+ m = m2;
+ map_type const cm;
+
+ i = m.begin();
+ ci = m.cbegin();
+ j = m.end();
+ cj = m.cend();
+
+ li = m.begin( 0 );
+ cli = m.cbegin( 0 );
+ lj = m.end( 0 );
+ clj = m.cend( 0 );
+
+ m.clear();
+ m.erase( i );
+ m.erase( ci );
+ m.erase( ci, ci );
+ m.erase( "x" );
+
+ m.insert( make_pair( "a", 1 ) );
+ m.insert( ci, make_pair( "a", 1 ) );
+
+ m.rehash( 41 );
+ m.swap( m2 );
+
+ m.at( "x" );
+ cm.at( "x" );
+
+ m[ "b" ] = 2;
+
+ m.count( "x" );
+ m.find( "x" );
+ cm.find( "x" );
+ m.equal_range( "x" );
+ cm.equal_range( "x" );
+
+ m.bucket( "x" );
+ m.bucket_count();
+ m.bucket_size( 0 );
+ m.max_bucket_count();
+
+ m.empty();
+ m.get_allocator();
+ m.hash_function();
+ m.key_eq();
+ m.load_factor();
+ m.max_load_factor();
+ m.max_size();
+ m.size();
+}
+/* vim:set et sw=2 ts=2: */
=== added file 'src/unit_tests/unordered_set.cpp'
--- src/unit_tests/unordered_set.cpp 1970-01-01 00:00:00 +0000
+++ src/unit_tests/unordered_set.cpp 2012-06-16 14:48:21 +0000
@@ -0,0 +1,248 @@
+/*
+ * Copyright 2006-2008 The FLWOR Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "stdafx.h"
+#include <iostream>
+#include <string>
+
+#include "util/unordered_set.h"
+
+using namespace std;
+
+typedef unordered_set<string> set_type;
+typedef pair<set_type::iterator,bool> insert_return_type;
+typedef pair<set_type::iterator,set_type::iterator> equal_range_return_type;
+
+///////////////////////////////////////////////////////////////////////////////
+
+static int failures;
+
+static bool assert_true( char const *expr, int line, bool result ) {
+ if ( !result ) {
+ cout << "FAILED, line " << line << ": " << expr << endl;
+ ++failures;
+ }
+ return result;
+}
+
+static void print_exception( char const *expr, int line,
+ std::exception const &e ) {
+ assert_true( expr, line, false );
+ cout << "+ exception: " << e.what() << endl;
+}
+
+#define ASSERT_TRUE( EXPR ) assert_true( #EXPR, __LINE__, !!(EXPR) )
+
+///////////////////////////////////////////////////////////////////////////////
+
+static void test_basics() {
+ set_type set;
+ insert_return_type ir;
+
+ ASSERT_TRUE( set.empty() );
+ ASSERT_TRUE( set.size() == 0 );
+
+ ir = set.insert( "a" );
+ if ( ASSERT_TRUE( ir.second ) )
+ if ( ASSERT_TRUE( ir.first != set.end() ) )
+ ASSERT_TRUE( *ir.first == "a" );
+
+ ir = set.insert( "b" );
+ if ( ASSERT_TRUE( ir.second ) )
+ if ( ASSERT_TRUE( ir.first != set.end() ) )
+ ASSERT_TRUE( *ir.first == "b" );
+
+ ASSERT_TRUE( !set.empty() );
+ ASSERT_TRUE( set.size() == 2 );
+
+ set_type set2( set );
+
+ ASSERT_TRUE( !set2.empty() );
+ ASSERT_TRUE( set2.size() == 2 );
+
+ set2.clear();
+ ASSERT_TRUE( set2.empty() );
+ ASSERT_TRUE( set2.size() == 0 );
+
+ // Ensure 'set' is unaffected by changes to 'set2'.
+ ASSERT_TRUE( !set.empty() );
+ ASSERT_TRUE( set.size() == 2 );
+}
+
+static void test_erase() {
+ set_type set;
+ set_type::iterator i;
+
+ set.insert( "a" );
+ set.insert( "b" );
+
+ ASSERT_TRUE( set.erase( "a" ) == 1 );
+ ASSERT_TRUE( set.erase( "a" ) == 0 );
+ ASSERT_TRUE( !set.empty() );
+ ASSERT_TRUE( set.size() == 1 );
+
+ if ( ASSERT_TRUE( (i = set.find( "b" )) != set.end() ) ) {
+ set.erase( i );
+ ASSERT_TRUE( set.empty() );
+ ASSERT_TRUE( set.size() == 0 );
+ }
+}
+
+static void test_insert() {
+ set_type set;
+ equal_range_return_type err;
+ set_type::iterator i;
+ insert_return_type ir;
+
+ ir = set.insert( "a" );
+ if ( ASSERT_TRUE( ir.second ) )
+ ASSERT_TRUE( *ir.first == "a" );
+ ASSERT_TRUE( !set.empty() );
+ ASSERT_TRUE( set.size() == 1 );
+ ASSERT_TRUE( set.count( "a" ) == 1 );
+
+ if ( ASSERT_TRUE( (i = set.find( "a" )) != set.end() ) )
+ ASSERT_TRUE( *i == "a" );
+ err = set.equal_range( "a" );
+ if ( ASSERT_TRUE( err.first != set.end() ) )
+ ASSERT_TRUE( *err.first == "a" );
+
+ ir = set.insert( "b" );
+ if ( ASSERT_TRUE( ir.second ) )
+ if ( ASSERT_TRUE( ir.first != set.end() ) )
+ ASSERT_TRUE( *ir.first == "b" );
+ ASSERT_TRUE( !set.empty() );
+ ASSERT_TRUE( set.size() == 2 );
+ ASSERT_TRUE( set.count( "b" ) == 1 );
+
+ if ( ASSERT_TRUE( (i = set.find( "b" )) != set.end() ) )
+ ASSERT_TRUE( *i == "b" );
+ err = set.equal_range( "b" );
+ if ( ASSERT_TRUE( err.first != set.end() ) )
+ ASSERT_TRUE( *err.first == "b" );
+
+ // Ensure "a" is still there.
+ if ( ASSERT_TRUE( (i = set.find( "a" )) != set.end() ) )
+ ASSERT_TRUE( *i == "a" );
+ ASSERT_TRUE( set.count( "a" ) == 1 );
+ err = set.equal_range( "a" );
+ if ( ASSERT_TRUE( err.first != set.end() ) )
+ ASSERT_TRUE( *err.first == "a" );
+}
+
+static void test_local_iterator() {
+ set_type set;
+
+ char s[2];
+ s[1] = '\0';
+ for ( int i = 0; i < 26; ++i ) {
+ *s = (char)('a' + i);
+ set.insert( s );
+ }
+
+ set_type::size_type b = set.bucket( "a" );
+ ASSERT_TRUE( set.bucket_size( b ) > 0 );
+
+ bool found_a = false;
+ set_type::local_iterator i( set.begin( b ) );
+ set_type::local_iterator const j( set.end( b ) );
+ for ( ; i != j; ++i )
+ if ( *i == "a" ) {
+ found_a = true;
+ break;
+ }
+ ASSERT_TRUE( found_a );
+}
+
+static void test_rehash() {
+ unordered_set<int> set;
+ unordered_set<int>::const_iterator i;
+
+ unordered_set<int>::size_type const initial_buckets = set.bucket_count();
+
+ // Add elements until bucket_count() changes which implies a rehash was done.
+ for ( int n = 0; set.bucket_count() == initial_buckets; ++n )
+ set.insert( n );
+
+ ASSERT_TRUE( set.bucket_count() > initial_buckets );
+
+ // Ensure all the elements are still there.
+ unordered_set<int>::size_type const size = set.size();
+ for ( int n = 0; n < size; ++n ) {
+ if ( ASSERT_TRUE( (i = set.find( n )) != set.end() ) )
+ ASSERT_TRUE( *i == n );
+ }
+}
+
+static void test_swap() {
+ unordered_set<string>::iterator i;
+
+ set_type set;
+ set.insert( "a" );
+ set.insert( "b" );
+
+ set_type set2;
+ set2.insert( "c" );
+ set2.insert( "d" );
+ set2.insert( "e" );
+
+ set.swap( set2 );
+
+ ASSERT_TRUE( set.size() == 3 );
+ ASSERT_TRUE( set2.size() == 2 );
+
+ ASSERT_TRUE( set.find( "a" ) == set.end() );
+ ASSERT_TRUE( set.find( "b" ) == set.end() );
+
+ if ( ASSERT_TRUE( (i = set.find( "c" )) != set.end() ) )
+ ASSERT_TRUE( *i == "c" );
+ if ( ASSERT_TRUE( (i = set.find( "d" )) != set.end() ) )
+ ASSERT_TRUE( *i == "d" );
+ if ( ASSERT_TRUE( (i = set.find( "e" )) != set.end() ) )
+ ASSERT_TRUE( *i == "e" );
+
+ if ( ASSERT_TRUE( (i = set2.find( "a" )) != set2.end() ) )
+ ASSERT_TRUE( *i == "a" );
+ if ( ASSERT_TRUE( (i = set2.find( "b" )) != set2.end() ) )
+ ASSERT_TRUE( *i == "b" );
+ ASSERT_TRUE( set2.find( "c" ) == set2.end() );
+ ASSERT_TRUE( set2.find( "d" ) == set2.end() );
+ ASSERT_TRUE( set2.find( "e" ) == set2.end() );
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+namespace zorba {
+namespace UnitTests {
+
+int test_unordered_set( int, char*[] ) {
+ test_basics();
+ test_erase();
+ test_insert();
+ test_local_iterator();
+ test_rehash();
+ test_swap();
+
+ cout << failures << " test(s) failed\n";
+ return failures ? 1 : 0;
+}
+
+} // namespace UnitTests
+} // namespace zorba
+
+///////////////////////////////////////////////////////////////////////////////
+
+/* vim:set et sw=2 ts=2: */
=== modified file 'src/util/CMakeLists.txt'
--- src/util/CMakeLists.txt 2012-06-15 21:31:03 +0000
+++ src/util/CMakeLists.txt 2012-06-16 14:48:21 +0000
@@ -50,3 +50,7 @@
HEADER_GROUP_SUBFOLDER(UTIL_SRCS fx)
HEADER_GROUP_SUBFOLDER(UTIL_SRCS win32)
+
+IF (NOT (ZORBA_HAVE_UNORDERED_MAP AND ZORBA_HAVE_UNORDERED_SET))
+ ADD_SRC_SUBFOLDER(UTIL_SRCS hash UTIL_HASH_SRCS)
+ENDIF (NOT (ZORBA_HAVE_UNORDERED_MAP AND ZORBA_HAVE_UNORDERED_SET))
=== added directory 'src/util/hash'
=== added file 'src/util/hash/CMakeLists.txt'
--- src/util/hash/CMakeLists.txt 1970-01-01 00:00:00 +0000
+++ src/util/hash/CMakeLists.txt 2012-06-16 14:48:21 +0000
@@ -0,0 +1,18 @@
+# Copyright 2006-2008 The FLWOR Foundation.
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+SET(UTIL_HASH_SRCS
+ hash.cpp
+ rehash_policy.cpp
+ )
=== added file 'src/util/hash/hash.cpp'
--- src/util/hash/hash.cpp 1970-01-01 00:00:00 +0000
+++ src/util/hash/hash.cpp 2012-06-16 14:48:21 +0000
@@ -0,0 +1,75 @@
+/*
+ * Copyright 2006-2008 The FLWOR Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// standard
+#include <limits>
+
+// local
+#include "hash.h"
+
+using namespace std;
+
+namespace zorba {
+namespace ztd {
+
+///////////////////////////////////////////////////////////////////////////////
+
+size_t hash_bytes( void const *p, size_t len, size_t result ) {
+ unsigned char const *c = reinterpret_cast<unsigned char const*>( p );
+ unsigned char const *const end = c + len;
+#ifdef ZORBA_HASH_FN_FNV_1a
+ //
+ // FNV-1a (Fowler/Noll/Vo) hashing algorithm.
+ //
+ while ( c < end ) {
+ result *= Hash_Prime;
+ result ^= *c++;
+ }
+#endif /* ZORBA_HASH_FN_FNV_1a */
+#ifdef ZORBA_HASH_FN_PJW
+ //
+ // An adaptation of Peter J. Weinberger's (PJW) generic hashing algorithm
+ // based on Allen Holub's version. This version works for any hash code
+ // size (in this case, size_t) and not only 'unsigned' as in PJW's version.
+ //
+ // The original PJW algorithm can be found in:
+ //
+ // Fig. 7.35: Hash function hashpjw, written in C
+ // "Compilers: Principles, Techniques, and Tools," Section 7.6: "Symbol
+ // Tables," Alfred Aho, Ravi Sethi, and Jeffrey D. Ullman, Addison-Wesley,
+ // Reading, MA, 1986, pp. 435-436.
+ //
+ static size_t const BitsInSizeT = sizeof( size_t ) *
+ numeric_limits<unsigned char>::digits;
+ static size_t const ThreeFourths = BitsInSizeT * 3 / 4;
+ static size_t const OneEighth = BitsInSizeT / 8;
+ static size_t const HighBits = ~( (size_t)(~0ul) >> OneEighth );
+
+ while ( c < end ) {
+ result = (result << OneEighth) + *c++;
+ if ( size_t temp = result & HighBits )
+ result = (result ^ (temp >> ThreeFourths)) & ~HighBits;
+ }
+#endif /* ZORBA_HASH_FN_PJW */
+ return result;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+} // namespace ztd
+} // namespace zorba
+
+/* vim:set et ts=2 sw=2: */
=== added file 'src/util/hash/hash.h'
--- src/util/hash/hash.h 1970-01-01 00:00:00 +0000
+++ src/util/hash/hash.h 2012-06-16 14:48:21 +0000
@@ -0,0 +1,165 @@
+/*
+ * Copyright 2006-2008 The FLWOR Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ZORBA_HASH_H
+#define ZORBA_HASH_H
+
+// zorba
+#include <zorba/config.h>
+
+// standard
+#include <functional>
+#include <string>
+#include <sys/types.h>
+
+// Exactly ONE of these should be defined.
+#define ZORBA_HASH_FN_FNV_1a 1 /* Fowler/Noll/Vo (FNV-1a) algorithm */
+//#define ZORBA_HASH_FN_PJW 1 /* Peter J. Weinberger's (PJW) algorithm */
+
+///////////////////////////////////////////////////////////////////////////////
+
+namespace zorba {
+
+template<class RepType> class rstring;
+
+namespace ztd {
+
+#ifdef ZORBA_HASH_FN_FNV_1a
+#if ZORBA_SIZEOF_SIZE_T == 4
+size_t const Hash_Init = 2166136261ul;
+size_t const Hash_Prime = 16777619ul;
+#elif ZORBA_SIZEOF_SIZE_T == 8
+size_t const Hash_Init = 14695981039346656037ul;
+size_t const Hash_Prime = 1099511628211ul;
+#endif /* ZORBA_SIZEOF_SIZE_T */
+#endif /* ZORBA_HASH_FN_FNV_1a */
+
+#ifdef ZORBA_HASH_FN_PJW
+size_t const Hash_Init = 3339675911ul;
+#endif /* ZORBA_HASH_FN_PJW */
+
+/**
+ * Generic hash function that hashes a byte sequence.
+ *
+ * @param p A pointer to the first byte in the sequence to hash.
+ * @param len The number of bytes in the sequence.
+ * @param init The initialization value.
+ * @return Returns the hash code for the given byte sequence.
+ */
+size_t hash_bytes( void const *p, size_t len, size_t init = Hash_Init );
+
+/**
+ * Generic hash function that hashes the memory occupied by a value of some
+ * type \a T.
+ *
+ * @tparam T The value's type.
+ * @param v The value to hash.
+ * @return Returns the hash code for the given value.
+ */
+template<typename T> inline
+size_t hash_bytes( T const &v ) {
+ return hash_bytes( &v, sizeof( v ) );
+}
+
+} // namespace ztd
+} // namespace zorba
+
+///////////////////////////////////////////////////////////////////////////////
+
+namespace std {
+
+#ifndef ZORBA_HAVE_UNORDERED_MAP
+
+/**
+ * The generic %hash unary_function class.
+ *
+ * @tparam T The type to hash.
+ */
+template<typename T>
+struct hash : unary_function<T,size_t> {
+ size_t operator()( T ) const; // not defined
+};
+
+#define ZORBA_INTEGRAL_HASH(T) \
+ template<> inline \
+ size_t hash<T>::operator()( T a ) const { \
+ return static_cast<size_t>( a ); \
+ }
+
+ZORBA_INTEGRAL_HASH( bool )
+ZORBA_INTEGRAL_HASH( char )
+ZORBA_INTEGRAL_HASH( signed char )
+ZORBA_INTEGRAL_HASH( wchar_t )
+ZORBA_INTEGRAL_HASH( short )
+ZORBA_INTEGRAL_HASH( int )
+ZORBA_INTEGRAL_HASH( long )
+ZORBA_INTEGRAL_HASH( long long )
+ZORBA_INTEGRAL_HASH( unsigned char )
+ZORBA_INTEGRAL_HASH( unsigned short )
+ZORBA_INTEGRAL_HASH( unsigned int )
+ZORBA_INTEGRAL_HASH( unsigned long )
+ZORBA_INTEGRAL_HASH( unsigned long long )
+
+#undef ZORBA_INTEGRAL_HASH
+
+/** Specialization for \c float. */
+template<> inline
+size_t hash<float>::operator()( float v ) const {
+ return v != 0.0F ? zorba::ztd::hash_bytes( v ) : 0;
+}
+
+/** Specialization for \c double. */
+template<> inline
+size_t hash<double>::operator()( double v ) const {
+ return v != 0.0 ? zorba::ztd::hash_bytes( v ) : 0;
+}
+
+/** Partial specialization for pointer types. */
+template<typename T>
+struct hash<T*> : unary_function<T*,size_t> {
+ size_t operator()( T *p ) const {
+ return reinterpret_cast<size_t>( p );
+ }
+};
+
+/** Specialization for \c string. */
+template<typename CharT,class Traits,class Alloc>
+struct hash< basic_string<CharT,Traits,Alloc> > :
+ unary_function<basic_string<CharT,Traits,Alloc> const&,size_t>
+{
+ size_t operator()( basic_string<CharT,Traits,Alloc> const &s ) const {
+ return zorba::ztd::hash_bytes( s.data(), s.size() );
+ }
+};
+
+#endif /* ZORBA_HAVE_UNORDERED_MAP */
+
+/** Specialization for \c rstring. */
+template<class RepType>
+struct hash< zorba::rstring<RepType> > :
+ unary_function<zorba::rstring<RepType> const&,size_t>
+{
+ size_t operator()( zorba::rstring<RepType> const &s ) const {
+ return zorba::ztd::hash_bytes( s.data(), s.size() );
+ }
+};
+
+} // namespace std
+
+///////////////////////////////////////////////////////////////////////////////
+
+#endif /* ZORBA_HASH_H */
+/* vim:set et ts=2 sw=2: */
=== added file 'src/util/hash/hashtable.h'
--- src/util/hash/hashtable.h 1970-01-01 00:00:00 +0000
+++ src/util/hash/hashtable.h 2012-06-16 14:48:21 +0000
@@ -0,0 +1,1067 @@
+/*
+ * Copyright 2006-2008 The FLWOR Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ZORBA_HASHTABLE_H
+#define ZORBA_HASHTABLE_H
+
+// standard
+#include <algorithm>
+#include <iterator>
+#include <sys/types.h>
+#include <utility> /* for pair */
+
+// local
+#include "util/cxx_util.h"
+#include "util/stl_util.h"
+
+namespace zorba {
+namespace ztd {
+
+///////////////////////////////////////////////////////////////////////////////
+
+/**
+ * The base class for a hash-table implementation.
+ *
+ * @tparam KeyType They map's key type.
+ * @tparam ValueType The type the keys are mapped to.
+ * @tparam KeyExtract The unary_function to use to extract a key from a value.
+ * @tparam KeyHash The unary_function to use for generating hash codes.
+ * @tparam KeyEqual The binary_function to use to test for key equality.
+ * @tparam Allocator The allocator to use.
+ * @tparam RehashPolicy The rehash policy class to use.
+ */
+template<
+ typename KeyType,
+ typename ValueType,
+ class KeyExtract,
+ class KeyHash,
+ class KeyEqual,
+ class Allocator,
+ class RehashPolicy
+>
+class hashtable_base {
+protected:
+ struct node;
+ typedef RehashPolicy rehash_policy_type;
+public:
+ typedef KeyType key_type;
+ typedef ValueType value_type;
+ typedef KeyHash hasher;
+ typedef KeyEqual key_equal;
+ typedef Allocator allocator_type;
+ typedef std::size_t size_type;
+ typedef std::ptrdiff_t difference_type;
+
+ typedef typename allocator_type::pointer pointer;
+ typedef typename allocator_type::const_pointer const_pointer;
+ typedef typename allocator_type::reference reference;
+ typedef typename allocator_type::const_reference const_reference;
+
+ /**
+ * Constructs a %hashtable_base.
+ *
+ * @param bucket_count The initial number of buckets to use.
+ * @param hash The hash-code unary functor to use.
+ * @param equal The key-equality functor to use.
+ * @param alloc The allocator to use.
+ */
+ hashtable_base( size_type bucket_count, hasher const &hash,
+ key_equal const &equal, allocator_type const &alloc );
+
+ /**
+ * Copy constructor.
+ *
+ * @param that The %hashtable_base to copy from.
+ */
+ hashtable_base( hashtable_base const &that );
+
+ /**
+ * Destructor.
+ */
+ ~hashtable_base();
+
+ /**
+ * Assignment operator.
+ *
+ * @param that The %hashtable_base to assign from.
+ * @return Returns \c *this.
+ */
+ hashtable_base& operator=( hashtable_base const &that );
+
+ ////////// local_iterator ///////////////////////////////////////////////////
+
+ class local_iterator :
+ public std::iterator<std::forward_iterator_tag,value_type> {
+ public:
+ local_iterator() : cur_node_( nullptr ) { }
+
+ reference operator*() const;
+ pointer operator->() const;
+ local_iterator& operator++();
+ local_iterator operator++(int);
+
+ friend bool operator==( local_iterator const &i, local_iterator const &j ) {
+ return i.cur_node_ == j.cur_node_;
+ }
+
+ friend bool operator!=( local_iterator const &i, local_iterator const &j ) {
+ return i.cur_node_ != j.cur_node_;
+ }
+
+ private:
+ node *cur_node_;
+
+ local_iterator( node *p ) : cur_node_( p ) { }
+ friend class hashtable_base;
+ };
+
+ ////////// const_local_iterator /////////////////////////////////////////////
+
+ class const_local_iterator :
+ public std::iterator<std::forward_iterator_tag,value_type const> {
+ public:
+ const_local_iterator() : cur_node_( nullptr ) { }
+
+ const_reference operator*() const;
+ const_pointer operator->() const;
+ const_local_iterator& operator++();
+ const_local_iterator operator++(int);
+
+ friend bool operator==( const_local_iterator const &i,
+ const_local_iterator const &j ) {
+ return i.cur_node_ == j.cur_node_;
+ }
+
+ friend bool operator!=( const_local_iterator const &i,
+ const_local_iterator const &j ) {
+ return i.cur_node_ != j.cur_node_;
+ }
+
+ private:
+ node const *cur_node_;
+
+ const_local_iterator( node const *p ) : cur_node_( p ) { }
+ friend class hashtable_base;
+ };
+
+ ////////// iterator /////////////////////////////////////////////////////////
+
+ class iterator : public std::iterator<std::forward_iterator_tag,value_type> {
+ public:
+ iterator() : cur_bkt_( nullptr ), cur_node_( nullptr ) { }
+
+ reference operator*() const;
+ pointer operator->() const;
+ iterator& operator++();
+ iterator operator++(int);
+
+ friend bool operator==( iterator const &i, iterator const &j ) {
+ return i.cur_node_ == j.cur_node_;
+ }
+
+ friend bool operator!=( iterator const &i, iterator const &j ) {
+ return i.cur_node_ != j.cur_node_;
+ }
+
+ private:
+ node **cur_bkt_;
+ node *cur_node_;
+
+ iterator( node **bkt, node *p );
+ void inc_bucket();
+
+ friend class hashtable_base;
+ friend class const_iterator;
+ };
+
+ ////////// const_iterator ///////////////////////////////////////////////////
+
+ class const_iterator :
+ public std::iterator<std::forward_iterator_tag,value_type const> {
+ public:
+ const_iterator() : cur_bkt_( nullptr ), cur_node_( nullptr ) { }
+ const_iterator( iterator const& );
+
+ const_reference operator*() const;
+ const_pointer operator->() const;
+ const_iterator& operator++();
+ const_iterator operator++(int);
+
+ friend bool operator==( const_iterator const &i, const_iterator const &j ) {
+ return i.cur_node_ == j.cur_node_;
+ }
+
+ friend bool operator!=( const_iterator const &i, const_iterator const &j ) {
+ return i.cur_node_ != j.cur_node_;
+ }
+
+ private:
+ node **cur_bkt_;
+ node *cur_node_;
+
+ const_iterator( node **bkt, node *p );
+ void inc_bucket();
+
+ friend class hashtable_base;
+ };
+
+ ////////// iteration ////////////////////////////////////////////////////////
+
+ /**
+ * Creates an iterator positioned at the "first" element. (Because this is
+ * an \e unordered map, "first" is arbitrary.)
+ *
+ * @return Returns said iterator.
+ */
+ iterator begin();
+
+ /**
+ * Creates an iterator positioned at the "first" element. (Because this is
+ * an \e unordered map, "first" is arbitrary.)
+ *
+ * @return Returns said iterator.
+ */
+ const_iterator begin() const;
+
+ /**
+ * Creates an iterator positioned at the "first" element. (Because this is
+ * an \e unordered map, "first" is arbitrary.)
+ *
+ * @return Returns said iterator.
+ */
+ const_iterator cbegin() const;
+
+ /**
+ * Creates an iterator positioned one past the "last" element. (Because this
+ * is an \e unordered map, "last" is arbitrary.)
+ *
+ * @return Returns said iterator.
+ */
+ iterator end();
+
+ /**
+ * Creates a const_iterator positioned one past the "last" element. (Because
+ * this is an \e unordered map, "last" is arbitrary.)
+ *
+ * @return Returns said iterator.
+ */
+ const_iterator end() const;
+
+ /**
+ * Creates a const_iterator positioned one past the "last" element. (Because
+ * this is an \e unordered map, "last" is arbitrary.)
+ *
+ * @return Returns said iterator.
+ */
+ const_iterator cend() const;
+
+ /**
+ * Creates a local_iterator positioned at the first element in the given
+ * bucket.
+ *
+ * @param bkt The index of the bucket.
+ * @return Returns said iterator.
+ */
+ local_iterator begin( size_type bkt );
+
+ /**
+ * Creates a const_local_iterator positioned at the first element in the
+ * given bucket.
+ *
+ * @param bkt The index of the bucket.
+ * @return Returns said iterator.
+ */
+ const_local_iterator begin( size_type bkt ) const;
+
+ /**
+ * Creates a const_local_iterator positioned at the first element in the
+ * given bucket.
+ *
+ * @param bkt The index of the bucket.
+ * @return Returns said iterator.
+ */
+ const_local_iterator cbegin( size_type bkt ) const;
+
+ /**
+ * Creates a local_iterator positioned at one past the last element in the
+ * given bucket.
+ *
+ * @param bkt The index of the bucket.
+ * @return Returns said iterator.
+ */
+ local_iterator end( size_type bkt );
+
+ /**
+ * Creates a const_local_iterator positioned at one past the last element in
+ * the given bucket.
+ *
+ * @param bkt The index of the bucket.
+ * @return Returns said iterator.
+ */
+ const_local_iterator end( size_type bkt ) const;
+
+ /**
+ * Creates a const_local_iterator positioned at one past the last element in
+ * the given bucket.
+ *
+ * @param bkt The index of the bucket.
+ * @return Returns said iterator.
+ */
+ const_local_iterator cend( size_type bkt ) const;
+
+ ////////// modifiers ////////////////////////////////////////////////////////
+
+ /**
+ * Clears this %hashtable_base, i.e., erases all elements.
+ */
+ void clear();
+
+ /**
+ * Erases the element at \a pos.
+ *
+ * @param pos The %iterator positioned at the element to erase.
+ * @return Returns an iterator positioned one past the erased element.
+ */
+ iterator erase( iterator pos );
+
+ /**
+ * Erases the element at \a pos.
+ *
+ * @param pos The %iterator positioned at the element to erase.
+ * @return Returns an iterator positioned one past the erased element.
+ */
+ iterator erase( const_iterator pos );
+
+ /**
+ * Erases all the elements in the range [<em>first</em>,<em>last</em>).
+ *
+ * @param first The %iterator positioned at the first element to erase.
+ * @param last The %iterator positioned one past the last element to erase.
+ * @return Returns an iterator positioned one past the last erased element.
+ */
+ iterator erase( const_iterator first, const_iterator last );
+
+ /**
+ * Erases the element having the given key.
+ *
+ * @param key The key.
+ * @return Returns the number of elements erased.
+ */
+ size_type erase( key_type const &key );
+
+ /**
+ * Attempts to insert a new value.
+ *
+ * @param value The value to insert.
+ * @return If a value with the given key is already in the %hashtable_base,
+ * returns [i,false] where \a i is positioned at the existing element;
+ * otherwise returns [i,true] where \a i is positioned at the new element.
+ */
+ std::pair<iterator,bool> insert( value_type const &value );
+
+ /**
+ * Attempts to insert a new value.
+ *
+ * @param hint An iterator providing a hint as to where to attempt to insert
+ * the new value.
+ * @param value The value to insert.
+ * @return If a value with the given key is already in the %hashtable_base,
+ * returns [i,false] where \a i is positioned at the existing element;
+ * otherwise returns [i,true] where \a i is positioned at the new element.
+ */
+ iterator insert( const_iterator hint, value_type const &value );
+
+ /**
+ * Attempts to insert the values provided by the given iterator.
+ *
+ * @tparam InputIterator The input iterator type.
+ * @param first An iterator positioned at the first element to insert.
+ * @param last An iterator positioned one past the last element to insert.
+ */
+ template<class InputIterator>
+ void insert( InputIterator first, InputIterator last );
+
+ /**
+ * Rehashes the %hashtable_base.
+ *
+ * @param bucket_count The new number of buckets.
+ */
+ void rehash( size_type bucket_count );
+
+ /**
+ * Swaps this %hashtable_base with another.
+ *
+ * @param that The %hashtable_base to swap with.
+ */
+ void swap( hashtable_base &that );
+
+ ////////// look-up //////////////////////////////////////////////////////////
+
+ /**
+ * Counts the number of elements having the given key.
+ *
+ * @param key The key to count.
+ * @return Returns said number.
+ */
+ size_type count( key_type const &key ) const;
+
+ /**
+ * Attempts to find the given \a key.
+ *
+ * @param key The key to find.
+ * @return If found, returns an iterator positioned at \a key; if not,
+ * returns an iterator positioned at end().
+ */
+ iterator find( key_type const &key );
+
+ /**
+ * Attempts to find the given \a key.
+ *
+ * @param key The key to find.
+ * @return If found, returns an iterator positioned at \a key; if not,
+ * returns an iterator positioned at end().
+ */
+ const_iterator find( key_type const &key ) const;
+
+ /**
+ * Creates a pair of iterators giving the range of elements that have the
+ * given key.
+ *
+ * @param key The key.
+ * @return Returns said iterators.
+ */
+ std::pair<iterator,iterator> equal_range( key_type const &key );
+
+ /**
+ * Creates a pair of const_iterators giving the range of elements that have
+ * the given key.
+ *
+ * @param key The key.
+ * @return Returns said iterators.
+ */
+ std::pair<const_iterator,const_iterator>
+ equal_range( key_type const &key ) const;
+
+ ////////// buckets //////////////////////////////////////////////////////////
+
+ /**
+ * Gets the index of the bucket for the \a key. Note that \a key isn't
+ * necessarily in the %hashtable_base.
+ *
+ * @param key The key.
+ * @return Returns an index in the range [0,max_bucket_count).
+ */
+ size_type bucket( key_type const &key ) const;
+
+ /**
+ * Gets the current number of buckets.
+ *
+ * @return Returns said number of buckets.
+ */
+ size_type bucket_count() const;
+
+ /**
+ * Gets the number of elements in the bucket specified by the given index.
+ *
+ * @param bucket_index The index of the bucket.
+ * @return Returns said number of elements.
+ */
+ size_type bucket_size( size_type bucket_index ) const;
+
+ /**
+ * Gets the maximum possible number of buckets.
+ *
+ * @return Returns said number of buckets.
+ */
+ size_type max_bucket_count() const;
+
+ ////////// miscellaneous ////////////////////////////////////////////////////
+
+ /**
+ * Gets whether this %hashtable_base is empty.
+ *
+ * @return Returns \c true only if it's empty.
+ */
+ bool empty() const;
+
+ /**
+ * Gets the allocator being used.
+ *
+ * @return Returns said allocator.
+ */
+ allocator_type get_allocator() const;
+
+ /**
+ * Gets the hash function being used.
+ *
+ * @return Returns said function.
+ */
+ hasher hash_function() const;
+
+ /**
+ * Gets the key equality function being used.
+ *
+ * @return Returns said function.
+ */
+ key_equal key_eq() const;
+
+ /**
+ * Gets the current load factor.
+ *
+ * @return Returns said load factor.
+ */
+ float load_factor() const;
+
+ /**
+ * Gets the maximim load factor.
+ *
+ * @return Returns said load factor.
+ */
+ float max_load_factor() const;
+
+ /**
+ * Sets the load factor that affects the number of buckets. If the new
+ * number of buckets is greater than the old number, performs a rehash.
+ *
+ * @param load_factor The new maximum load factor.
+ * @throws std::invalid_argument if \a load_factor <= 0.
+ */
+ void max_load_factor( float load_factor );
+
+ /**
+ * Gets the maximum possible number of elements.
+ *
+ * @return Returns said number of elements.
+ */
+ size_type max_size() const;
+
+ /**
+ * Gets the number of elements.
+ *
+ * @return Returns said number of elements.
+ */
+ size_type size() const;
+
+ /////////////////////////////////////////////////////////////////////////////
+
+protected:
+ struct node {
+ value_type value_;
+ node *next_;
+
+ node() : value_( value_type() ), next_( nullptr ) { }
+ node( value_type const &v ) : value_( v ), next_( nullptr ) { }
+ };
+
+ node* find_node( key_type const &key ) const {
+ return find_node( bucket( key ), key );
+ }
+
+ node* find_node( node*, key_type const& ) const;
+
+ node* find_node( size_type bkt, key_type const &key ) const {
+ return find_node( buckets_[ bkt ], key );
+ }
+
+ std::pair<iterator,bool> insert( size_type bkt, value_type const &value );
+
+private:
+ typedef typename allocator_type::template rebind<node*>::other
+ bucket_alloc_type;
+
+ typedef typename allocator_type::template rebind<node>::other
+ node_alloc_type;
+
+ typedef typename hasher::result_type hash_code_type;
+
+ node** alloc_buckets( size_type n_bkt );
+ void dealloc_buckets( node**, size_type n_bkt );
+
+ node* alloc_node( value_type const& );
+ void dealloc_node( node* );
+ void dealloc_nodes( node**, size_type n_bkt );
+
+ size_type bucket( key_type const &key, size_type n_bkt ) const {
+ return bucket_for_code( hasher_( key ), n_bkt );
+ }
+
+ size_type bucket_for_code( hash_code_type code ) const {
+ return bucket_for_code( code, n_bkt_ );
+ }
+
+ size_type bucket_for_code( hash_code_type code, size_type n_bkt ) const {
+ return code % n_bkt;
+ }
+
+ void rehash_impl( size_type new_n_bkt );
+
+ node **buckets_;
+ hasher hasher_;
+ KeyEqual equal_;
+ KeyExtract key_of;
+ size_type n_bkt_;
+ size_type n_elt_;
+ node_alloc_type node_alloc_;
+ rehash_policy_type rehash_policy_;
+};
+
+#define ZORBA_HASHTABLE_TEMPLATE \
+ template<typename K,typename V,class X,class H,class E,class A,class RP>
+
+#define ZORBA_HASHTABLE_CLASS hashtable_base<K,V,X,H,E,A,RP>
+
+////////// hashtable_base inline functions ////////////////////////////////////
+
+ZORBA_HASHTABLE_TEMPLATE inline
+ZORBA_HASHTABLE_CLASS::~hashtable_base() {
+ clear();
+ dealloc_buckets( buckets_, n_bkt_ );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::iterator
+ZORBA_HASHTABLE_CLASS::begin() {
+ return iterator( buckets_, buckets_[0] );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_iterator
+ZORBA_HASHTABLE_CLASS::begin() const {
+ return const_iterator( buckets_, buckets_[0] );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_iterator
+ZORBA_HASHTABLE_CLASS::cbegin() const {
+ return begin();
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::local_iterator
+ZORBA_HASHTABLE_CLASS::begin( size_type bkt ) {
+ return local_iterator( buckets_[ bkt ] );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_local_iterator
+ZORBA_HASHTABLE_CLASS::begin( size_type bkt ) const {
+ return const_local_iterator( buckets_[ bkt ] );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_local_iterator
+ZORBA_HASHTABLE_CLASS::cbegin( size_type bkt ) const {
+ return begin( bkt );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::size_type
+ZORBA_HASHTABLE_CLASS::bucket( key_type const &key ) const {
+ return bucket_for_code( hasher_( key ) );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::size_type
+ZORBA_HASHTABLE_CLASS::bucket_count() const {
+ return n_bkt_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::size_type
+ZORBA_HASHTABLE_CLASS::bucket_size( size_type bkt ) const {
+ return std::distance( begin( bkt ), end( bkt ) );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+void ZORBA_HASHTABLE_CLASS::clear() {
+ dealloc_nodes( buckets_, n_bkt_ );
+ n_elt_ = 0;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+bool ZORBA_HASHTABLE_CLASS::empty() const {
+ return size() == 0;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::iterator
+ZORBA_HASHTABLE_CLASS::end() {
+ return iterator( buckets_ + n_bkt_, buckets_[ n_bkt_ ] );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_iterator
+ZORBA_HASHTABLE_CLASS::end() const {
+ return const_iterator( buckets_ + n_bkt_, buckets_[ n_bkt_ ] );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_iterator
+ZORBA_HASHTABLE_CLASS::cend() const {
+ return end();
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::local_iterator
+ZORBA_HASHTABLE_CLASS::end( size_type bkt ) {
+ return local_iterator( nullptr );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_local_iterator
+ZORBA_HASHTABLE_CLASS::end( size_type bkt ) const {
+ return const_local_iterator( nullptr );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_local_iterator
+ZORBA_HASHTABLE_CLASS::cend( size_type bkt ) const {
+ return end( bkt );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::iterator
+ZORBA_HASHTABLE_CLASS::erase( iterator i ) {
+ return erase( const_iterator( i ) );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::allocator_type
+ZORBA_HASHTABLE_CLASS::get_allocator() const {
+ return allocator_type( node_alloc_ );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::hasher
+ZORBA_HASHTABLE_CLASS::hash_function() const {
+ return hasher_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::iterator
+ZORBA_HASHTABLE_CLASS::insert( const_iterator, value_type const &value ) {
+ return insert( value ).first;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::key_equal
+ZORBA_HASHTABLE_CLASS::key_eq() const {
+ return equal_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+float ZORBA_HASHTABLE_CLASS::load_factor() const {
+ return static_cast<float>( size() ) / static_cast<float>( bucket_count() );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::size_type
+ZORBA_HASHTABLE_CLASS::max_bucket_count() const {
+ return max_size();
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+float ZORBA_HASHTABLE_CLASS::max_load_factor() const {
+ return rehash_policy_.max_load_factor();
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::size_type
+ZORBA_HASHTABLE_CLASS::max_size() const {
+ return node_alloc_.max_size();
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+void ZORBA_HASHTABLE_CLASS::rehash( size_type new_n_bkt ) {
+ rehash_impl(
+ std::max(
+ rehash_policy_.adjust_buckets( new_n_bkt ),
+ rehash_policy_.buckets_for_elements( n_elt_ + 1 )
+ )
+ );
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::size_type
+ZORBA_HASHTABLE_CLASS::size() const {
+ return n_elt_;
+}
+
+////////// local_iterator inline functions ////////////////////////////////////
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::reference
+ZORBA_HASHTABLE_CLASS::local_iterator::operator*() const {
+ return cur_node_->value_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::pointer
+ZORBA_HASHTABLE_CLASS::local_iterator::operator->() const {
+ return &cur_node_->value_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::local_iterator&
+ZORBA_HASHTABLE_CLASS::local_iterator::operator++() {
+ cur_node_ = cur_node_->next_;
+ return *this;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::local_iterator
+ZORBA_HASHTABLE_CLASS::local_iterator::operator++(int) {
+ local_iterator const temp( cur_node_ );
+ cur_node_ = cur_node_->next_;
+ return temp;
+}
+
+////////// const_local_iterator inline functions //////////////////////////////
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_reference
+ZORBA_HASHTABLE_CLASS::const_local_iterator::operator*() const {
+ return cur_node_->value_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_pointer
+ZORBA_HASHTABLE_CLASS::const_local_iterator::operator->() const {
+ return &cur_node_->value_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_local_iterator&
+ZORBA_HASHTABLE_CLASS::const_local_iterator::operator++() {
+ cur_node_ = cur_node_->next_;
+ return *this;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_local_iterator
+ZORBA_HASHTABLE_CLASS::const_local_iterator::operator++(int) {
+ const_local_iterator const temp( cur_node_ );
+ cur_node_ = cur_node_->next_;
+ return temp;
+}
+
+////////// iterator inline functions //////////////////////////////////////////
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::reference
+ZORBA_HASHTABLE_CLASS::iterator::operator*() const {
+ return cur_node_->value_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::pointer
+ZORBA_HASHTABLE_CLASS::iterator::operator->() const {
+ return &cur_node_->value_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::iterator&
+ZORBA_HASHTABLE_CLASS::iterator::operator++() {
+ if ( !(cur_node_ = cur_node_->next_) )
+ inc_bucket();
+ return *this;
+}
+
+////////// const_iterator inline functions ////////////////////////////////////
+
+ZORBA_HASHTABLE_TEMPLATE inline
+ZORBA_HASHTABLE_CLASS::const_iterator::const_iterator( iterator const &i ) :
+ cur_bkt_( i.cur_bkt_ ), cur_node_( i.cur_node_ )
+{
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_reference
+ZORBA_HASHTABLE_CLASS::const_iterator::operator*() const {
+ return cur_node_->value_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_pointer
+ZORBA_HASHTABLE_CLASS::const_iterator::operator->() const {
+ return &cur_node_->value_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE inline
+typename ZORBA_HASHTABLE_CLASS::const_iterator&
+ZORBA_HASHTABLE_CLASS::const_iterator::operator++() {
+ if ( !(cur_node_ = cur_node_->next_) )
+ inc_bucket();
+ return *this;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+/**
+ * A hash-table implementation for when KeyType is the same as ValueType. This
+ * is used as the base class for unordered_set.
+ *
+ * @tparam KeyType They map's key type.
+ * @tparam ValueType The type the keys are mapped to.
+ * @tparam KeyExtract The unary_function to use to extract a key from a value.
+ * @tparam KeyHash The unary_function to use for generating hash codes.
+ * @tparam KeyEqual The binary_function to use to test for key equality.
+ * @tparam Allocator The allocator to use.
+ * @tparam RehashPolicy The rehash policy class to use.
+ */
+template<
+ typename KeyType,
+ typename ValueType,
+ class KeyExtract,
+ class KeyHash,
+ class KeyEqual,
+ class Allocator,
+ class RehashPolicy
+>
+class hashtable :
+ public hashtable_base<KeyType,ValueType,KeyExtract,KeyHash,KeyEqual,Allocator,
+ RehashPolicy>
+{
+ typedef hashtable_base<KeyType,ValueType,KeyExtract,KeyHash,KeyEqual,
+ Allocator,RehashPolicy> base_type;
+public:
+ typedef typename base_type::key_type key_type;
+ typedef typename base_type::value_type value_type;
+ typedef typename base_type::hasher hasher;
+ typedef typename base_type::key_equal key_equal;
+ typedef typename base_type::allocator_type allocator_type;
+ typedef typename base_type::size_type size_type;
+ typedef typename base_type::difference_type difference_type;
+
+ typedef typename base_type::pointer pointer;
+ typedef typename base_type::const_pointer const_pointer;
+ typedef typename base_type::reference reference;
+ typedef typename base_type::const_reference const_reference;
+
+ /**
+ * Constructs a %hashtable.
+ *
+ * @param bucket_count The initial number of buckets to use.
+ * @param hash The hash-code unary functor to use.
+ * @param equal The key-equality functor to use.
+ * @param alloc The allocator to use.
+ */
+ hashtable( size_type bucket_count, hasher const &hash, key_equal const &equal,
+ allocator_type const &alloc ) :
+ base_type( bucket_count, hash, equal, alloc )
+ {
+ }
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+/**
+ * Specialization of %hashtable for use when the "value" is actually a
+ * <code>pair<KeyType const,Value></code>. This is used as the base
+ * class for unordered_map. This specialization also adds \c mapped_type,
+ * \c at(), and \c operator[]() members.
+ *
+ * @tparam KeyType They map's key type.
+ * @tparam PairType The <code>pair<KeyType const,Value></code>.
+ * @tparam KeyExtract The unary_function to use to extract a key from a pair.
+ * @tparam KeyHash The unary_function to use for generating hash codes.
+ * @tparam KeyEqual The binary_function to use to test for key equality.
+ * @tparam Allocator The allocator to use.
+ * @tparam RehashPolicy The rehash policy class to use.
+ */
+template<
+ typename KeyType,
+ class PairType,
+ class KeyHash,
+ class KeyEqual,
+ class Allocator,
+ class RehashPolicy
+>
+class hashtable<KeyType,PairType,select1st<PairType>,KeyHash,KeyEqual,
+ Allocator,RehashPolicy> :
+ public hashtable_base<KeyType,PairType,select1st<PairType>,KeyHash,KeyEqual,
+ Allocator,RehashPolicy>
+{
+ typedef hashtable_base<KeyType,PairType,select1st<PairType>,KeyHash,KeyEqual,
+ Allocator,RehashPolicy> base_type;
+ typedef typename base_type::node node;
+public:
+ typedef typename base_type::key_type key_type;
+ typedef typename base_type::value_type value_type;
+ typedef typename PairType::second_type mapped_type;
+ typedef typename base_type::hasher hasher;
+ typedef typename base_type::key_equal key_equal;
+ typedef typename base_type::allocator_type allocator_type;
+ typedef typename base_type::size_type size_type;
+ typedef typename base_type::difference_type difference_type;
+
+ typedef typename base_type::pointer pointer;
+ typedef typename base_type::const_pointer const_pointer;
+ typedef typename base_type::reference reference;
+ typedef typename base_type::const_reference const_reference;
+
+ /**
+ * Constructs a %hashtable.
+ *
+ * @param bucket_count The initial number of buckets to use.
+ * @param hash The hash-code unary functor to use.
+ * @param equal The key-equality functor to use.
+ * @param alloc The allocator to use.
+ */
+ hashtable( size_type bucket_count, hasher const &hash, key_equal const &equal,
+ allocator_type const &alloc ) :
+ base_type( bucket_count, hash, equal, alloc )
+ {
+ }
+
+ /**
+ * Attempts to find the given \a key.
+ *
+ * @param key The key to find.
+ * @return Returns a reference to the value associated with \a key.
+ * @throws std::out_of_range if \a key is not found.
+ */
+ mapped_type& at( key_type const &key );
+
+ /**
+ * Attempts to find the given \a key.
+ *
+ * @param key The key to find.
+ * @return Returns a reference to the value associated with \a key.
+ * @throws std::out_of_range if \a key is not found.
+ */
+ mapped_type const& at( key_type const &key ) const;
+
+ /**
+ * Attempts to find the given \a key.
+ *
+ * @param key The key to find.
+ * @return If found, returns a reference to the value associated with \a key;
+ * if not, creates a new key/value pair and returns a reference to the newly
+ * created value.
+ */
+ mapped_type& operator[]( key_type const &key );
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+} // namespace ztd
+} // namespace zorba
+
+#include "hashtable.tcc"
+
+#endif /* ZORBA_HASHTABLE_H */
+/* vim:set et ts=2 sw=2: */
=== added file 'src/util/hash/hashtable.tcc'
--- src/util/hash/hashtable.tcc 1970-01-01 00:00:00 +0000
+++ src/util/hash/hashtable.tcc 2012-06-16 14:48:21 +0000
@@ -0,0 +1,447 @@
+/*
+ * Copyright 2006-2008 The FLWOR Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ZORBA_HASHTABLE_TCC
+#define ZORBA_HASHTABLE_TCC
+
+#include <stdexcept>
+
+#ifndef ZORBA_HASHTABLE_H
+#error "This file is not meant to be included directly."
+#endif /* ZORBA_HASHTABLE_H */
+
+namespace zorba {
+namespace ztd {
+
+////////// hashtable_base functions ///////////////////////////////////////////
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::node**
+ZORBA_HASHTABLE_CLASS::alloc_buckets( size_type n_bkt ) {
+ bucket_alloc_type alloc( node_alloc_ );
+ //
+ // Allocate one extra bucket to be a sentinel containing an arbitrary
+ // non-null value. Iteration relies on this.
+ //
+ node **const p = alloc.allocate( n_bkt + 1 );
+ std::fill( p, p + n_bkt, static_cast<node*>( nullptr ) );
+ p[ n_bkt ] = reinterpret_cast<node*>( 0x1000 );
+ return p;
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::node*
+ZORBA_HASHTABLE_CLASS::alloc_node( value_type const &v ) {
+ node *const p = node_alloc_.allocate( 1 );
+ try {
+ node_alloc_.construct( p, v );
+ p->next_ = nullptr;
+ return p;
+ }
+ catch ( ... ) {
+ node_alloc_.deallocate( p, 1 );
+ throw;
+ }
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+void ZORBA_HASHTABLE_CLASS::dealloc_buckets( node **p, size_type n_bkt ) {
+ bucket_alloc_type alloc( node_alloc_ );
+ alloc.deallocate( p, n_bkt + 1 /* sentinel */ );
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+void ZORBA_HASHTABLE_CLASS::dealloc_node( node *p ) {
+ node_alloc_.destroy( p );
+ node_alloc_.deallocate( p, 1 );
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+void ZORBA_HASHTABLE_CLASS::dealloc_nodes( node **buckets, size_type n_bkt ) {
+ for ( size_type bkt = 0; bkt < n_bkt; ++bkt ) {
+ node *p = buckets[ bkt ];
+ while ( p ) {
+ node *const q = p;
+ p = p->next_;
+ dealloc_node( q );
+ }
+ buckets[ bkt ] = nullptr;
+ }
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+ZORBA_HASHTABLE_CLASS::hashtable_base( size_type bucket_count,
+ hasher const &hash,
+ key_equal const &equal,
+ allocator_type const &alloc ) :
+ equal_( equal ),
+ hasher_( hash ),
+ n_bkt_( bucket_count ),
+ n_elt_( 0 ),
+ node_alloc_( alloc )
+{
+ buckets_ = alloc_buckets( n_bkt_ );
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+ZORBA_HASHTABLE_CLASS::hashtable_base( hashtable_base const &that ) :
+ equal_( that.equal_ ),
+ hasher_( that.hasher_ ),
+ n_bkt_( that.n_bkt_ ),
+ n_elt_( that.n_elt_ ),
+ node_alloc_( that.node_alloc_ )
+{
+ buckets_ = alloc_buckets( n_bkt_ );
+ try {
+ for ( size_type bkt = 0; bkt < n_bkt_; ++bkt ) {
+ node **tail = buckets_ + bkt;
+ for ( node *p = that.buckets_[ bkt ]; p; p = p->next_ ) {
+ *tail = alloc_node( p->value_ );
+ tail = &(*tail)->next_;
+ }
+ }
+ }
+ catch ( ... ) {
+ clear();
+ dealloc_buckets( buckets_, n_bkt_ );
+ throw;
+ }
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+ZORBA_HASHTABLE_CLASS&
+ZORBA_HASHTABLE_CLASS::operator=( hashtable_base const &that ) {
+ hashtable_base temp( that );
+ this->swap( temp );
+ return *this;
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::size_type
+ZORBA_HASHTABLE_CLASS::count( key_type const &key ) const {
+ return !!find_node( key );
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::iterator
+ZORBA_HASHTABLE_CLASS::erase( const_iterator pos ) {
+ iterator result( pos.cur_bkt_, pos.cur_node_ );
+ ++result;
+
+ node *cur = *pos.cur_bkt_;
+ if ( cur == pos.cur_node_ )
+ *pos.cur_bkt_ = cur->next_;
+ else {
+ node *next = cur->next_;
+ while ( next != pos.cur_node_ ) {
+ cur = next;
+ next = cur->next_;
+ }
+ cur->next_ = next->next_;
+ }
+
+ dealloc_node( pos.cur_node_ );
+ --n_elt_;
+
+ return result;
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::iterator
+ZORBA_HASHTABLE_CLASS::erase( const_iterator i, const_iterator j ) {
+ while ( i != j )
+ i = erase( i );
+ return iterator( j.cur_bkt_, j.cur_node_ );
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::size_type
+ZORBA_HASHTABLE_CLASS::erase( key_type const &key ) {
+ size_type const bkt = bucket( key );
+ for ( node *p = buckets_[ bkt ], **pp = &buckets_[ bkt ]; p;
+ pp = &p->next_, p = p->next_ ) {
+ if ( equal_( key_of( p->value_ ), key ) ) {
+ *pp = p->next_;
+ dealloc_node( p );
+ --n_elt_;
+ return 1;
+ }
+ }
+ return 0;
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::iterator
+ZORBA_HASHTABLE_CLASS::find( key_type const &key ) {
+ size_type const bkt = bucket( key );
+ if ( node *const p = find_node( bkt, key ) )
+ return iterator( buckets_ + bkt, p );
+ return end();
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::const_iterator
+ZORBA_HASHTABLE_CLASS::find( key_type const &key ) const {
+ size_type const bkt = bucket( key );
+ if ( node *const p = find_node( bkt, key ) )
+ return const_iterator( buckets_ + bkt, p );
+ return end();
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+std::pair<typename ZORBA_HASHTABLE_CLASS::iterator,
+ typename ZORBA_HASHTABLE_CLASS::iterator>
+ZORBA_HASHTABLE_CLASS::equal_range( key_type const &key ) {
+ size_type const bkt = bucket( key );
+ node **const head = buckets_ + bkt;
+ if ( node *p = find_node( *head, key ) ) {
+ node *q = p->next_;
+ for ( ; q; q = q->next_ )
+ if ( !equal_( key_of( q->value_ ), key ) )
+ break;
+ iterator first( head, p );
+ iterator last( head, q );
+ if ( !q )
+ last.inc_bucket();
+ return std::make_pair( first, last );
+ }
+ return std::make_pair( end(), end() );
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+std::pair<typename ZORBA_HASHTABLE_CLASS::const_iterator,
+ typename ZORBA_HASHTABLE_CLASS::const_iterator>
+ZORBA_HASHTABLE_CLASS::equal_range( key_type const &key ) const {
+ size_type const bkt = bucket( key );
+ node **const head = buckets_ + bkt;
+ if ( node *p = find_node( *head, key ) ) {
+ node *q = p->next_;
+ for ( ; q; q = q->next_ )
+ if ( !equal_( key_of( q->value_ ), key ) )
+ break;
+ const_iterator first( head, p );
+ const_iterator last( head, q );
+ if ( !q )
+ last.inc_bucket();
+ return std::make_pair( first, last );
+ }
+ return std::make_pair( end(), end() );
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::node*
+ZORBA_HASHTABLE_CLASS::find_node( node *p, key_type const &key ) const {
+ for ( ; p; p = p->next_ )
+ if ( equal_( key_of( p->value_ ), key ) )
+ return p;
+ return nullptr;
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+std::pair<typename ZORBA_HASHTABLE_CLASS::iterator,bool>
+ZORBA_HASHTABLE_CLASS::insert( value_type const &value ) {
+ key_type const &key = key_of( value );
+ size_type const bkt = bucket( key );
+ node *&head = buckets_[ bkt ];
+
+ if ( node *const p = find_node( head, key ) )
+ return std::make_pair( iterator( &head, p ), false );
+ return insert( bkt, value );
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+std::pair<typename ZORBA_HASHTABLE_CLASS::iterator,bool>
+ZORBA_HASHTABLE_CLASS::insert( size_type bkt, value_type const &value ) {
+ //
+ // Allocate the new node before doing the rehash (if any) so that we don't do
+ // a rehash if the allocation throws an exception.
+ //
+ node *const p = alloc_node( value );
+
+ size_type const new_n_bkt = rehash_policy_.need_rehash( n_bkt_, n_elt_, 1 );
+
+ try {
+ if ( new_n_bkt ) {
+ rehash_impl( new_n_bkt );
+ bkt = bucket( key_of( value ) );
+ }
+ node *&head = buckets_[ bkt ];
+ p->next_ = head;
+ head = p;
+ ++n_elt_;
+ return std::make_pair( iterator( &head, p ), true );
+ }
+ catch ( ... ) {
+ dealloc_node( p );
+ throw;
+ }
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+template<class InputIterator>
+void ZORBA_HASHTABLE_CLASS::insert( InputIterator first, InputIterator last ) {
+ size_type const n_ins = std::distance( first, last );
+ size_type const new_n_bkt =
+ rehash_policy_.need_rehash( n_bkt_, n_elt_, n_ins );
+ if ( new_n_bkt )
+ rehash_impl( new_n_bkt );
+ for ( ; first != last; ++first )
+ insert( *first );
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+void ZORBA_HASHTABLE_CLASS::max_load_factor( float load_factor ) {
+ if ( load_factor <= 0 )
+ throw std::invalid_argument( "load_factor <= 0" );
+ rehash_policy_ = rehash_policy_type( load_factor );
+ size_type const n_bkt = rehash_policy_.buckets_for_elements( n_elt_ );
+ if ( n_bkt > n_bkt_ )
+ rehash_impl( n_bkt );
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+void ZORBA_HASHTABLE_CLASS::rehash_impl( size_type new_n_bkt ) {
+ node **const new_buckets = alloc_buckets( new_n_bkt );
+ try {
+ for ( size_type bkt = 0; bkt < n_bkt_; ++bkt ) {
+ node *&head = buckets_[ bkt ];
+ while ( node *p = head ) {
+ size_type const new_bkt = bucket( key_of( p->value_ ), new_n_bkt );
+ head = p->next_;
+ p->next_ = new_buckets[ new_bkt ];
+ new_buckets[ new_bkt ] = p;
+ }
+ }
+ dealloc_buckets( buckets_, n_bkt_ );
+ buckets_ = new_buckets;
+ n_bkt_ = new_n_bkt;
+ }
+ catch ( ... ) {
+ dealloc_nodes( new_buckets, new_n_bkt );
+ dealloc_buckets( new_buckets, new_n_bkt );
+ clear();
+ throw;
+ }
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+void ZORBA_HASHTABLE_CLASS::swap( hashtable_base &that ) {
+ std::swap( buckets_, that.buckets_ );
+ std::swap( equal_, that.equal_ );
+ std::swap( hasher_, that.hasher_ );
+ std::swap( n_bkt_, that.n_bkt_ );
+ std::swap( n_elt_, that.n_elt_ );
+ std::swap( node_alloc_, that.node_alloc_ );
+ std::swap( rehash_policy_, that.rehash_policy_ );
+}
+
+////////// iterator functions /////////////////////////////////////////////////
+
+ZORBA_HASHTABLE_TEMPLATE
+ZORBA_HASHTABLE_CLASS::iterator::iterator( node **bkt, node *p ) :
+ cur_bkt_( bkt ), cur_node_( p )
+{
+ while ( !cur_node_ )
+ cur_node_ = *++cur_bkt_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+void ZORBA_HASHTABLE_CLASS::iterator::inc_bucket() {
+ while ( !*++cur_bkt_ )
+ ;
+ cur_node_ = *cur_bkt_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::iterator
+ZORBA_HASHTABLE_CLASS::iterator::operator++(int) {
+ iterator const temp( cur_bkt_, cur_node_ );
+ operator++();
+ return temp;
+}
+
+////////// const_iterator functions ///////////////////////////////////////////
+
+ZORBA_HASHTABLE_TEMPLATE
+ZORBA_HASHTABLE_CLASS::const_iterator::const_iterator( node **bkt, node *p ) :
+ cur_bkt_( bkt ), cur_node_( p )
+{
+ while ( !cur_node_ )
+ cur_node_ = *++cur_bkt_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+void ZORBA_HASHTABLE_CLASS::const_iterator::inc_bucket() {
+ while ( !*++cur_bkt_ )
+ ;
+ cur_node_ = *cur_bkt_;
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::const_iterator
+ZORBA_HASHTABLE_CLASS::const_iterator::operator++(int) {
+ const_iterator const temp( cur_bkt_, cur_node_ );
+ operator++();
+ return temp;
+}
+
+#undef ZORBA_HASHTABLE_CLASS
+#undef ZORBA_HASHTABLE_TEMPLATE
+
+////////// hashtable specialization members ///////////////////////////////////
+
+#define ZORBA_HASHTABLE_TEMPLATE \
+ template<typename K,class P,class H,class E,class A,class RP>
+
+#define ZORBA_HASHTABLE_CLASS hashtable<K,P,select1st<P>,H,E,A,RP>
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::mapped_type&
+ZORBA_HASHTABLE_CLASS::at( key_type const &key ) {
+ if ( node *const p = this->find_node( key ) )
+ return p->value_.second;
+ throw std::out_of_range( "at()" );
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::mapped_type const&
+ZORBA_HASHTABLE_CLASS::at( key_type const &key ) const {
+ if ( node const *const p = this->find_node( key ) )
+ return p->value_.second;
+ throw std::out_of_range( "at()" );
+}
+
+ZORBA_HASHTABLE_TEMPLATE
+typename ZORBA_HASHTABLE_CLASS::mapped_type&
+ZORBA_HASHTABLE_CLASS::operator[]( key_type const &key ) {
+ size_type const bkt = this->bucket( key );
+ if ( node *const p = this->find_node( bkt, key ) )
+ return p->value_.second;
+ return this->insert(
+ bkt, std::make_pair( key, mapped_type() )
+ ).first->second;
+}
+
+#undef ZORBA_HASHTABLE_CLASS
+#undef ZORBA_HASHTABLE_TEMPLATE
+
+///////////////////////////////////////////////////////////////////////////////
+
+} // namespace ztd
+} // namespace zorba
+
+#endif /* ZORBA_HASHTABLE_TCC */
+/* vim:set et ts=2 sw=2: */
=== added file 'src/util/hash/rehash_policy.cpp'
--- src/util/hash/rehash_policy.cpp 1970-01-01 00:00:00 +0000
+++ src/util/hash/rehash_policy.cpp 2012-06-16 14:48:21 +0000
@@ -0,0 +1,146 @@
+/*
+ * Copyright 2006-2008 The FLWOR Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// standard
+#include <algorithm>
+#include <cmath>
+#include <iostream>
+
+// zorba
+#include <zorba/config.h>
+
+// local
+#include "rehash_policy.h"
+
+using namespace std;
+
+namespace zorba {
+namespace ztd {
+
+///////////////////////////////////////////////////////////////////////////////
+
+typedef unsigned long prime_type;
+
+static prime_type const primes[] = {
+ 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul, 37ul, 41ul,
+ 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul, 83ul, 89ul, 97ul,
+ 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul, 157ul, 167ul, 179ul, 193ul,
+ 199ul, 211ul, 227ul, 241ul, 257ul, 277ul, 293ul, 313ul, 337ul, 359ul, 383ul,
+ 409ul, 439ul, 467ul, 503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul,
+ 887ul, 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul, 1741ul,
+ 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul, 3209ul, 3469ul,
+ 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul, 5953ul, 6427ul, 6949ul,
+ 7517ul, 8123ul, 8783ul, 9497ul, 10273ul, 11113ul, 12011ul, 12983ul, 14033ul,
+ 15173ul, 16411ul, 17749ul, 19183ul, 20753ul, 22447ul, 24281ul, 26267ul,
+ 28411ul, 30727ul, 33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul,
+ 53201ul, 57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
+ 99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul, 159871ul,
+ 172933ul, 187091ul, 202409ul, 218971ul, 236897ul, 256279ul, 277261ul,
+ 299951ul, 324503ul, 351061ul, 379787ul, 410857ul, 444487ul, 480881ul,
+ 520241ul, 562841ul, 608903ul, 658753ul, 712697ul, 771049ul, 834181ul,
+ 902483ul, 976369ul, 1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul,
+ 1565659ul, 1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,
+ 2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul, 4355707ul,
+ 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul, 6984629ul, 7556579ul,
+ 8175383ul, 8844859ul, 9569143ul, 10352717ul, 11200489ul, 12117689ul,
+ 13109983ul, 14183539ul, 15345007ul, 16601593ul, 17961079ul, 19431899ul,
+ 21023161ul, 22744717ul, 24607243ul, 26622317ul, 28802401ul, 31160981ul,
+ 33712729ul, 36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,
+ 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul, 80131819ul,
+ 86693767ul, 93793069ul, 101473717ul, 109783337ul, 118773397ul, 128499677ul,
+ 139022417ul, 150406843ul, 162723577ul, 176048909ul, 190465427ul, 206062531ul,
+ 222936881ul, 241193053ul, 260944219ul, 282312799ul, 305431229ul, 330442829ul,
+ 357502601ul, 386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
+ 573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul, 849749479ul,
+ 919334987ul, 994618837ul, 1076067617ul, 1164186217ul, 1259520799ul,
+ 1362662261ul, 1474249943ul, 1594975441ul, 1725587117ul, 1866894511ul,
+ 2019773507ul, 2185171673ul, 2364114217ul, 2557710269ul, 2767159799ul,
+ 2993761039ul, 3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul,
+ 4294967291ul,
+
+#if ZORBA_SIZEOF_LONG < 8
+ // Sentinel so we don't have to test the result of lower_bound().
+ 4294967291ul
+#else
+ 6442450933ul, 8589934583ul, 12884901857ul, 17179869143ul, 25769803693ul,
+ 34359738337ul, 51539607367ul, 68719476731ul, 103079215087ul, 137438953447ul,
+ 206158430123ul, 274877906899ul, 412316860387ul, 549755813881ul,
+ 824633720731ul, 1099511627689ul, 1649267441579ul, 2199023255531ul,
+ 3298534883309ul, 4398046511093ul, 6597069766607ul, 8796093022151ul,
+ 13194139533241ul, 17592186044399ul, 26388279066581ul, 35184372088777ul,
+ 52776558133177ul, 70368744177643ul, 105553116266399ul, 140737488355213ul,
+ 211106232532861ul, 281474976710597ul, 562949953421231ul, 1125899906842597ul,
+ 2251799813685119ul, 4503599627370449ul, 9007199254740881ul,
+ 18014398509481951ul, 36028797018963913ul, 72057594037927931ul,
+ 144115188075855859ul, 288230376151711717ul, 576460752303423433ul,
+ 1152921504606846883ul, 2305843009213693951ul, 4611686018427387847ul,
+ 9223372036854775783ul, 18446744073709551557ul, 18446744073709551557ul
+#endif /* ZORBA_SIZEOF_LONG */
+};
+
+static prime_type const *const primes_end =
+ primes + sizeof( primes ) / sizeof( primes[0] );
+
+///////////////////////////////////////////////////////////////////////////////
+
+inline void prime_rehash_policy::update_next_resize( size_type n_bkt ) const {
+ next_resize_ = static_cast<size_type>( ceil( n_bkt * max_load_factor_ ) );
+}
+
+prime_rehash_policy::prime_rehash_policy( float max_load_factor ) :
+ growth_factor_( 2.0F ),
+ max_load_factor_( max_load_factor ),
+ next_resize_( 0 )
+{
+}
+
+prime_rehash_policy::size_type
+prime_rehash_policy::adjust_buckets( size_type n_bkt ) const {
+ prime_type const *const p = lower_bound( primes, primes_end, n_bkt );
+ update_next_resize( *p );
+ return *p;
+}
+
+prime_rehash_policy::size_type
+prime_rehash_policy::buckets_for_elements( size_type n_elt ) const {
+ float const min_bkts = n_elt / max_load_factor_;
+ prime_type const *const p = lower_bound( primes, primes_end, min_bkts );
+ update_next_resize( *p );
+ return *p;
+}
+
+prime_rehash_policy::size_type
+prime_rehash_policy::need_rehash( size_type n_bkt, size_type n_elt,
+ size_type n_ins ) const {
+ if ( n_elt + n_ins > next_resize_ ) {
+ float min_bkts = (n_elt + n_ins) / max_load_factor_;
+ if ( min_bkts > n_bkt ) {
+ min_bkts = max( min_bkts, growth_factor_ * n_bkt );
+ prime_type const *const p = lower_bound( primes, primes_end, min_bkts );
+ update_next_resize( *p );
+ return *p;
+ } else {
+ update_next_resize( n_bkt );
+ }
+ }
+ return 0;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+} // namespace ztd
+} // namespace zorba
+/* vim:set et sw=2 ts=2: */
=== added file 'src/util/hash/rehash_policy.h'
--- src/util/hash/rehash_policy.h 1970-01-01 00:00:00 +0000
+++ src/util/hash/rehash_policy.h 2012-06-16 14:48:21 +0000
@@ -0,0 +1,106 @@
+/*
+ * Copyright 2006-2008 The FLWOR Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ZORBA_HASHTABLE_REHASH_POLICY_H
+#define ZORBA_HASHTABLE_REHASH_POLICY_H
+
+// standard
+#include <sys/types.h>
+
+namespace zorba {
+namespace ztd {
+
+///////////////////////////////////////////////////////////////////////////////
+
+/**
+ * Provides a rehashing policy for hash tables that always uses prime numbers
+ * for the number of buckets.
+ */
+class prime_rehash_policy {
+public:
+ typedef std::size_t size_type;
+
+ enum {
+ /**
+ * The default number of buckets to create.
+ */
+ default_bucket_count = 11 // a prime number
+ };
+
+ /**
+ * Constructs a %prime_rehash_policy.
+ *
+ * @param max_load_factor The maximum load factor.
+ */
+ prime_rehash_policy( float max_load_factor = 1.0F );
+
+ /**
+ * Gets an adjusted bucket count for the given proposed number of buckets.
+ *
+ * @param n_bkt The proposed number of buckets.
+ * @return Returns a bucket count adjusted so as to be more optimal.
+ */
+ size_type adjust_buckets( size_type n_bkt ) const;
+
+ /**
+ * Calculates the number of buckets needed for the given number of elements
+ * under the maximum load factor.
+ *
+ * @param n_elt The number of elements.
+ * @return Returns said number of buckets.
+ */
+ size_type buckets_for_elements( size_type n_elt ) const;
+
+ /**
+ * Gets the maximum load factor.
+ *
+ * @return Returns said load factor.
+ */
+ float max_load_factor() const;
+
+ /**
+ * Determines whether a rehash ought to be done.
+ *
+ * @param n_bkt The current number of buckets.
+ * @param n_elt The current number of elements.
+ * @param n_ins The number of elements to be inserted.
+ * @return Returns a value > 0 (where the value is the new bucket count)
+ * if a rehash ought to be done; returns 0 if not.
+ */
+ size_type need_rehash( size_type n_bkt, size_type n_elt,
+ size_type n_ins ) const;
+
+private:
+ float growth_factor_;
+ float max_load_factor_;
+ mutable size_type next_resize_;
+
+ void update_next_resize( size_type ) const;
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+inline float prime_rehash_policy::max_load_factor() const {
+ return max_load_factor_;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+} // namespace ztd
+} // namespace std
+
+#endif /* ZORBA_HASHTABLE_REHASH_POLICY_H */
+/* vim:set et ts=2 sw=2: */
=== added file 'src/util/stl_misc.h'
--- src/util/stl_misc.h 1970-01-01 00:00:00 +0000
+++ src/util/stl_misc.h 2012-06-16 14:48:21 +0000
@@ -0,0 +1,47 @@
+/*
+ * Copyright 2006-2008 The FLWOR Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ZORBA_STL_MISC_H
+#define ZORBA_STL_MISC_H
+
+#include <zorba/config.h>
+
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef ZORBA_CXX_NULLPTR
+
+
+#endif /* ZORBA_CXX_NULLPTR */
+
+///////////////////////////////////////////////////////////////////////////////
+
+#ifndef ZORBA_CXX_STATIC_ASSERT
+
+template<bool> struct zorba_static_assert; // intentionally undefined
+template<> struct zorba_static_assert<true> { };
+template<int> struct zorba_static_assert_type { };
+
+#define static_assert(expr,msg) \
+ typedef ::zorba_static_assert_type< \
+ sizeof( ::zorba_static_assert<(expr) != 0> ) \
+ > zorba_static_assert_type_##__LINE__
+
+#endif /* ZORBA_CXX_STATIC_ASSERT */
+
+///////////////////////////////////////////////////////////////////////////////
+
+#endif /* ZORBA_STL_MISC_H */
+/* vim:set et sw=2 ts=2: */
=== modified file 'src/util/stl_util.h'
--- src/util/stl_util.h 2012-06-15 21:31:03 +0000
+++ src/util/stl_util.h 2012-06-16 14:48:21 +0000
@@ -20,6 +20,7 @@
#include <algorithm>
#include <cassert>
#include <cstring>
+#include <functional>
#include <iterator>
#include <limits>
#include <set>
@@ -92,6 +93,36 @@
///////////////////////////////////////////////////////////////////////////////
/**
+ * Implementation of SGI's %identity extension.
+ * See: http://www.sgi.com/tech/stl/identity.html
+ */
+template<typename T>
+struct identity : std::unary_function<T,T> {
+ typedef T argument_type;
+ typedef T result_type;
+
+ result_type const& operator()( argument_type const &a ) const {
+ return a;
+ }
+};
+
+/**
+ * Implementation of SGI's %select1st extension.
+ * See: http://www.sgi.com/tech/stl/select1st.html
+ */
+template<typename PairType>
+struct select1st : std::unary_function<PairType,typename PairType::first_type> {
+ typedef PairType argument_type;
+ typedef typename PairType::first_type result_type;
+
+ result_type const& operator()( argument_type const &a ) const {
+ return a.first;
+ }
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+/**
* Determines whether the given type \c T is efficiently passed by value.
*/
template<typename T>
=== added file 'src/util/unordered_map.h'
--- src/util/unordered_map.h 1970-01-01 00:00:00 +0000
+++ src/util/unordered_map.h 2012-06-16 14:48:21 +0000
@@ -0,0 +1,159 @@
+/*
+ * Copyright 2006-2008 The FLWOR Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+#ifndef ZORBA_UNORDERED_MAP_H
+#define ZORBA_UNORDERED_MAP_H
+
+#include <zorba/config.h>
+
+#ifdef ZORBA_HAVE_UNORDERED_MAP
+# include <unordered_map> /* use the implementation version */
+#else
+
+// standard
+#include <utility> /* for pair */
+
+// local
+#include "util/hash/hash.h"
+#include "util/hash/hashtable.h"
+#include "util/hash/rehash_policy.h"
+#ifndef ZORBA_UNORDERED_MAP_REHASH_POLICY
+# define ZORBA_UNORDERED_MAP_REHASH_POLICY zorba::ztd::prime_rehash_policy
+#endif /* ZORBA_UNORDERED_MAP_REHASH_POLICY */
+#include "cxx_util.h"
+#include "stl_util.h"
+
+namespace std {
+
+///////////////////////////////////////////////////////////////////////////////
+
+/**
+ * This is an implementation of the C++ %unordered_map class, but for C++98.
+ * As such, it lacks member functions that use r-value references.
+ *
+ * @tparam KeyType They map's key type.
+ * @tparam MappedType The type the keys are mapped to.
+ * @tparam KeyHash The unary_function to use for generating hash codes.
+ * @tparam KeyEqual The binary_function to use to test for key equality.
+ * @tparam Allocator The allocator to use.
+ */
+template<
+ typename KeyType,
+ typename ValueType,
+ class KeyHash = std::hash<KeyType>,
+ class KeyEqual = std::equal_to<KeyType>,
+ class Allocator = std::allocator< std::pair<KeyType const,ValueType> >
+>
+class unordered_map :
+ public zorba::ztd::hashtable<
+ KeyType, std::pair<KeyType const,ValueType>,
+ zorba::ztd::select1st<std::pair<KeyType const,ValueType> >,
+ KeyHash, KeyEqual, Allocator, ZORBA_UNORDERED_MAP_REHASH_POLICY
+ >
+{
+ typedef zorba::ztd::hashtable<
+ KeyType, std::pair<KeyType const,ValueType>,
+ zorba::ztd::select1st<std::pair<KeyType const,ValueType> >,
+ KeyHash, KeyEqual, Allocator, ZORBA_UNORDERED_MAP_REHASH_POLICY
+ > base_type;
+
+ typedef typename base_type::rehash_policy_type rehash_policy_type;
+public:
+ typedef typename base_type::key_type key_type;
+ typedef typename base_type::value_type value_type;
+ typedef typename base_type::hasher hasher;
+ typedef typename base_type::key_equal key_equal;
+ typedef typename base_type::allocator_type allocator_type;
+
+ typedef typename base_type::pointer pointer;
+ typedef typename base_type::const_pointer const_pointer;
+ typedef typename base_type::reference reference;
+ typedef typename base_type::const_reference const_reference;
+
+ typedef typename base_type::size_type size_type;
+ typedef typename base_type::difference_type difference_type;
+
+ typedef typename base_type::local_iterator local_iterator;
+ typedef typename base_type::const_local_iterator const_local_iterator;
+ typedef typename base_type::iterator iterator;
+ typedef typename base_type::const_iterator const_iterator;
+
+ /**
+ * Constructs an %unordered_map.
+ *
+ * @param bucket_count The initial number of buckets.
+ * @param hash The unary_function to use for generating hash codes.
+ * @param equal The binary_function to use to test for key equality.
+ * @param alloc The allocator to use.
+ */
+ explicit unordered_map(
+ size_type bucket_count = rehash_policy_type::default_bucket_count,
+ hasher const &hash = hasher(),
+ key_equal const &equal = key_equal(),
+ allocator_type const &alloc = allocator_type()
+ ) :
+ base_type( bucket_count, hash, equal, alloc )
+ {
+ }
+
+ /**
+ * Constructs an %unordered_map.
+ *
+ * @param alloc The allocator to use.
+ */
+ explicit unordered_map( allocator_type const &alloc ) : base_type( alloc ) {
+ }
+
+ /**
+ * Copy-constructs an %unordered_map.
+ *
+ * @param that The %unordered_map to copy from.
+ */
+ unordered_map( unordered_map const &that ) : base_type( that ) {
+ }
+
+ /**
+ * Assignment.
+ *
+ * @param that The %unordered_map to assign from.
+ */
+ unordered_map& operator=( unordered_map const &that ) {
+ base_type::operator=( that );
+ return *this;
+ }
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+/**
+ * Global %swap operator for unordered_map.
+ *
+ * @param a The first unordered_map.
+ * @param b The second unordered_map.
+ */
+template<typename K,typename M,class H,class E,class A> inline
+void swap( unordered_map<K,M,H,E,A> &a, unordered_map<K,M,H,E,A> &b ) {
+ a.swap( b );
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+} // namespace std
+
+#endif /* ZORBA_HAVE_UNORDERED_MAP */
+#endif /* ZORBA_UNORDERED_MAP_H */
+/* vim:set et ts=2 sw=2: */
=== added file 'src/util/unordered_set.h'
--- src/util/unordered_set.h 1970-01-01 00:00:00 +0000
+++ src/util/unordered_set.h 2012-06-16 14:48:21 +0000
@@ -0,0 +1,152 @@
+/*
+ * Copyright 2006-2008 The FLWOR Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+#ifndef ZORBA_UNORDERED_SET_H
+#define ZORBA_UNORDERED_SET_H
+
+#include <zorba/config.h>
+
+#ifdef ZORBA_HAVE_UNORDERED_SET
+# include <unordered_set> /* use the implementation version */
+#else
+
+// local
+#include "util/hash/hash.h"
+#include "util/hash/hashtable.h"
+#include "util/hash/rehash_policy.h"
+#ifndef ZORBA_UNORDERED_SET_REHASH_POLICY
+# define ZORBA_UNORDERED_SET_REHASH_POLICY zorba::ztd::prime_rehash_policy
+#endif /* ZORBA_UNORDERED_SET_REHASH_POLICY */
+#include "cxx_util.h"
+#include "stl_util.h"
+
+namespace std {
+
+///////////////////////////////////////////////////////////////////////////////
+
+/**
+ * This is an implementation of the C++ %unordered_set class, but for C++98.
+ * As such, it lacks member functions that use r-value references.
+ *
+ * @tparam KeyType They set's key type.
+ * @tparam KeyHash The unary_function to use for generating hash codes.
+ * @tparam KeyEqual The binary_function to use to test for value equality.
+ * @tparam Allocator The allocator to use.
+ */
+template<
+ typename KeyType,
+ class KeyHash = std::hash<KeyType>,
+ class KeyEqual = std::equal_to<KeyType>,
+ class Allocator = std::allocator<KeyType>
+>
+class unordered_set :
+ public zorba::ztd::hashtable<
+ KeyType, KeyType, zorba::ztd::identity<KeyType>,
+ KeyHash, KeyEqual, Allocator, ZORBA_UNORDERED_SET_REHASH_POLICY
+ >
+{
+ typedef zorba::ztd::hashtable<
+ KeyType, KeyType, zorba::ztd::identity<KeyType>,
+ KeyHash, KeyEqual, Allocator, ZORBA_UNORDERED_SET_REHASH_POLICY
+ > base_type;
+
+ typedef typename base_type::rehash_policy_type rehash_policy_type;
+public:
+ typedef typename base_type::key_type key_type;
+ typedef typename base_type::value_type value_type;
+ typedef typename base_type::hasher hasher;
+ typedef typename base_type::key_equal key_equal;
+ typedef typename base_type::allocator_type allocator_type;
+
+ typedef typename base_type::pointer pointer;
+ typedef typename base_type::const_pointer const_pointer;
+ typedef typename base_type::reference reference;
+ typedef typename base_type::const_reference const_reference;
+
+ typedef typename base_type::size_type size_type;
+ typedef typename base_type::difference_type difference_type;
+
+ typedef typename base_type::local_iterator local_iterator;
+ typedef typename base_type::const_local_iterator const_local_iterator;
+ typedef typename base_type::iterator iterator;
+ typedef typename base_type::const_iterator const_iterator;
+
+ /**
+ * Constructs an %unordered_set.
+ *
+ * @param bucket_count The initial number of buckets.
+ * @param hash The unary_function to use for generating hash codes.
+ * @param equal The binary_function to use to test for key equality.
+ * @param alloc The allocator to use.
+ */
+ explicit unordered_set(
+ size_type bucket_count = rehash_policy_type::default_bucket_count,
+ hasher const &hash = hasher(),
+ key_equal const &equal = key_equal(),
+ allocator_type const &alloc = allocator_type()
+ ) :
+ base_type( bucket_count, hash, equal, alloc )
+ {
+ }
+
+ /**
+ * Constructs an %unordered_set.
+ *
+ * @param alloc The allocator to use.
+ */
+ explicit unordered_set( allocator_type const &alloc ) : base_type( alloc ) {
+ }
+
+ /**
+ * Copy-constructs an %unordered_set.
+ *
+ * @param that The %unordered_set to copy from.
+ */
+ unordered_set( unordered_set const &that ) : base_type( that ) {
+ }
+
+ /**
+ * Assignment.
+ *
+ * @param that The %unordered_set to assign from.
+ */
+ unordered_set& operator=( unordered_set const &that ) {
+ base_type::operator=( that );
+ return *this;
+ }
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+/**
+ * Global %swap operator for unordered_set.
+ *
+ * @param a The first unordered_set.
+ * @param b The second unordered_set.
+ */
+template<typename V,class H,class E,class A> inline
+void swap( unordered_set<V,H,E,A> &a, unordered_set<V,H,E,A> &b ) {
+ a.swap( b );
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+} // namespace std
+
+#endif /* ZORBA_HAVE_UNORDERED_SET */
+#endif /* ZORBA_UNORDERED_SET_H */
+/* vim:set et ts=2 sw=2: */
Follow ups
