This is an automated email from the git hooks/post-receive script. rene pushed a commit to branch master in repository mdds.
commit 409b8520dd73438cf23bfdcf09d0c9398abb5a4e Author: Rene Engelhard <[email protected]> Date: Thu Apr 21 14:50:53 2016 +0200 Imported Upstream version 0.11.0 --- Makefile.in | 21 ++++- NEWS | 21 +++++ configure | 34 +++---- configure.ac | 4 +- include/mdds/global.hpp | 8 +- include/mdds/multi_type_matrix.hpp | 5 + include/mdds/multi_type_vector.hpp | 7 +- include/mdds/multi_type_vector_custom_func1.hpp | 12 +++ include/mdds/multi_type_vector_custom_func2.hpp | 15 +++ include/mdds/multi_type_vector_custom_func3.hpp | 18 ++++ include/mdds/multi_type_vector_def.inl | 73 ++++++++++----- include/mdds/multi_type_vector_trait.hpp | 44 +++++++++ include/mdds/multi_type_vector_types.hpp | 20 +++- include/mdds/sorted_string_map.hpp | 101 +++++++++++++++++++++ .../mdds/{global.hpp => sorted_string_map_def.inl} | 58 +++++++----- src/multi_type_vector_test_custom.cpp | 54 +++++++++++ src/multi_type_vector_test_default.cpp | 90 ++++++++++++++++++ src/sorted_string_map_test.cpp | 94 +++++++++++++++++++ 18 files changed, 609 insertions(+), 70 deletions(-) diff --git a/Makefile.in b/Makefile.in index 3c824b4..828df63 100644 --- a/Makefile.in +++ b/Makefile.in @@ -19,7 +19,8 @@ EXECS= \ multi_type_matrix_test \ rectangle_set_test \ multi_type_vector_test_default \ - multi_type_vector_test_custom + multi_type_vector_test_custom \ + sorted_string_map_test HEADERS= \ @top_srcdir@/$(INCDIR)/mdds/compat/unique_ptr.hpp \ @@ -43,6 +44,8 @@ HEADERS= \ @top_srcdir@/$(INCDIR)/mdds/rectangle_set_def.inl \ @top_srcdir@/$(INCDIR)/mdds/rectangle_set.hpp \ @top_srcdir@/$(INCDIR)/mdds/segment_tree.hpp \ + @top_srcdir@/$(INCDIR)/mdds/sorted_string_map_def.inl \ + @top_srcdir@/$(INCDIR)/mdds/sorted_string_map.hpp \ @top_srcdir@/$(INCDIR)/mdds/multi_type_vector.hpp \ @top_srcdir@/$(INCDIR)/mdds/multi_type_vector_custom_func1.hpp \ @top_srcdir@/$(INCDIR)/mdds/multi_type_vector_custom_func2.hpp \ @@ -63,7 +66,8 @@ TESTS = \ test.st \ test.mtm \ test.mtv \ - test.mtmatrix + test.mtmatrix \ + test.ssmap TESTS_MEM = \ test.pqt.mem \ @@ -72,6 +76,7 @@ TESTS_MEM = \ test.st.mem \ test.mtm.mem \ test.mtmatrix \ + test.ssmap # You may add $(TESTS_MEM) if valgrind is available on your platform ALL_TESTS = $(TESTS) @@ -111,6 +116,9 @@ $(OBJDIR)/multi_type_vector_test_perf.o: @top_srcdir@/$(SRCDIR)/multi_type_vecto $(OBJDIR)/multi_type_matrix_test.o: @top_srcdir@/$(SRCDIR)/multi_type_matrix_test.cpp $(DEPENDS) $(CXX) $(CPPFLAGS) -c -o $@ @top_srcdir@/$(SRCDIR)/multi_type_matrix_test.cpp +$(OBJDIR)/sorted_string_map_test.o: @top_srcdir@/$(SRCDIR)/sorted_string_map_test.cpp $(DEPENDS) + $(CXX) $(CPPFLAGS) -c -o $@ @top_srcdir@/$(SRCDIR)/sorted_string_map_test.cpp + flat_segment_tree_test: pre $(OBJDIR)/flat_segment_tree_test.o $(CXX) $(LDFLAGS) $(OBJDIR)/flat_segment_tree_test.o -o $@ @@ -138,6 +146,9 @@ multi_type_vector_test_perf: pre $(OBJDIR)/multi_type_vector_test_perf.o multi_type_matrix_test: pre $(OBJDIR)/multi_type_matrix_test.o $(CXX) $(LDFLAGS) $(OBJDIR)/multi_type_matrix_test.o -o $@ +sorted_string_map_test: pre $(OBJDIR)/sorted_string_map_test.o + $(CXX) $(LDFLAGS) $(OBJDIR)/sorted_string_map_test.o -o $@ + multi_type_vector_test: multi_type_vector_test_default multi_type_vector_test_custom multi_type_vector_test_perf stlperf_test: pre @top_srcdir@/$(SRCDIR)/stlperf_test.cpp @@ -208,6 +219,12 @@ test.mtmatrix.perf: multi_type_matrix_test test.mtmatrix.mem: multi_type_matrix_test valgrind --tool=memcheck --leak-check=full ./multi_type_matrix_test func +test.ssmap: sorted_string_map_test + ./sorted_string_map_test func + +test.ssmap.mem: sorted_string_map_test + valgrind --tool=memcheck --leak-check=full ./sorted_string_map_test func + test.stl: stlperf_test ./stlperf_test diff --git a/NEWS b/NEWS index db4b75f..65287d3 100644 --- a/NEWS +++ b/NEWS @@ -1,3 +1,24 @@ +mdds 0.11.0 + +* sorted_string_map (new) + + * new data structure to support efficient mapping of textural keys + to numeric values when the key values are known at compile time. + +* multi_type_vector + + * fixed a bug in transfer() where two adjacent blocks of identical + type would fail to be merged in some circumstances. + + * added shrink_to_fit() to allow trimming of any excess capacity + from all non-empty blocks. + + * fixed a double-free bug in the variant of swap() that allows + segmented swapping. + + * improved the exception message when the block position lookup + fails to find valid block position, to make it easier to debug. + mdds 0.10.3 * multi_type_vector diff --git a/configure b/configure index 6880c85..46d9ba5 100755 --- a/configure +++ b/configure @@ -1,6 +1,6 @@ #! /bin/sh # Guess values for system-dependent variables and create Makefiles. -# Generated by GNU Autoconf 2.69 for mdds 0.10.3. +# Generated by GNU Autoconf 2.69 for mdds 0.11.0. # # Report bugs to <[email protected]>. # @@ -579,8 +579,8 @@ MAKEFLAGS= # Identity of this package. PACKAGE_NAME='mdds' PACKAGE_TARNAME='mdds' -PACKAGE_VERSION='0.10.3' -PACKAGE_STRING='mdds 0.10.3' +PACKAGE_VERSION='0.11.0' +PACKAGE_STRING='mdds 0.11.0' PACKAGE_BUGREPORT='[email protected]' PACKAGE_URL='' @@ -1181,7 +1181,7 @@ if test "$ac_init_help" = "long"; then # Omit some internal or obsolete options to make the list less imposing. # This message is too long to be a string in the A/UX 3.1 sh. cat <<_ACEOF -\`configure' configures mdds 0.10.3 to adapt to many kinds of systems. +\`configure' configures mdds 0.11.0 to adapt to many kinds of systems. Usage: $0 [OPTION]... [VAR=VALUE]... @@ -1242,7 +1242,7 @@ fi if test -n "$ac_init_help"; then case $ac_init_help in - short | recursive ) echo "Configuration of mdds 0.10.3:";; + short | recursive ) echo "Configuration of mdds 0.11.0:";; esac cat <<\_ACEOF @@ -1335,7 +1335,7 @@ fi test -n "$ac_init_help" && exit $ac_status if $ac_init_version; then cat <<\_ACEOF -mdds configure 0.10.3 +mdds configure 0.11.0 generated by GNU Autoconf 2.69 Copyright (C) 2012 Free Software Foundation, Inc. @@ -1352,7 +1352,7 @@ cat >config.log <<_ACEOF This file contains any messages produced by compilers while running configure, to aid debugging if configure makes a mistake. -It was created by mdds $as_me 0.10.3, which was +It was created by mdds $as_me 0.11.0, which was generated by GNU Autoconf 2.69. Invocation command line was $ $0 $@ @@ -1701,7 +1701,7 @@ ac_compiler_gnu=$ac_cv_c_compiler_gnu -VERSION=0.10.3 +VERSION=0.11.0 PACKAGE_TARNAME=mdds @@ -1745,7 +1745,7 @@ elif test $with_hash_container = boost; then CPPFLAGS_NODEBUG="$CPPFLAGS_NODEBUG -DMDDS_HASH_CONTAINER_BOOST" fi -CPPFLAGS="$CPPFLAGS_NODEBUG -DMDDS_DEBUG_NODE_BASE -DMDDS_UNIT_TEST -std=c++0x" +CPPFLAGS="$CPPFLAGS $CPPFLAGS_NODEBUG -DMDDS_DEBUG_NODE_BASE -DMDDS_UNIT_TEST -std=c++0x" if test "$debug_stdcxx" = "yes"; then CPPFLAGS="$CPPFLAGS -D_GLIBCXX_DEBUG" @@ -2298,7 +2298,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by mdds $as_me 0.10.3, which was +This file was extended by mdds $as_me 0.11.0, which was generated by GNU Autoconf 2.69. Invocation command line was CONFIG_FILES = $CONFIG_FILES @@ -2351,7 +2351,7 @@ _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\ -mdds config.status 0.10.3 +mdds config.status 0.11.0 configured by $0, generated by GNU Autoconf 2.69, with options \\"\$ac_cs_config\\" @@ -3455,7 +3455,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by mdds $as_me 0.10.3, which was +This file was extended by mdds $as_me 0.11.0, which was generated by GNU Autoconf 2.69. Invocation command line was CONFIG_FILES = $CONFIG_FILES @@ -3508,7 +3508,7 @@ _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\ -mdds config.status 0.10.3 +mdds config.status 0.11.0 configured by $0, generated by GNU Autoconf 2.69, with options \\"\$ac_cs_config\\" @@ -4613,7 +4613,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by mdds $as_me 0.10.3, which was +This file was extended by mdds $as_me 0.11.0, which was generated by GNU Autoconf 2.69. Invocation command line was CONFIG_FILES = $CONFIG_FILES @@ -4666,7 +4666,7 @@ _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\ -mdds config.status 0.10.3 +mdds config.status 0.11.0 configured by $0, generated by GNU Autoconf 2.69, with options \\"\$ac_cs_config\\" @@ -5772,7 +5772,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by mdds $as_me 0.10.3, which was +This file was extended by mdds $as_me 0.11.0, which was generated by GNU Autoconf 2.69. Invocation command line was CONFIG_FILES = $CONFIG_FILES @@ -5825,7 +5825,7 @@ _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\ -mdds config.status 0.10.3 +mdds config.status 0.11.0 configured by $0, generated by GNU Autoconf 2.69, with options \\"\$ac_cs_config\\" diff --git a/configure.ac b/configure.ac index 678d2a2..25e597b 100644 --- a/configure.ac +++ b/configure.ac @@ -1,4 +1,4 @@ -AC_INIT(mdds, 0.10.3, [email protected]) +AC_INIT(mdds, 0.11.0, [email protected]) VERSION=AC_PACKAGE_VERSION AC_SUBST(VERSION) @@ -49,7 +49,7 @@ elif test $with_hash_container = boost; then CPPFLAGS_NODEBUG="$CPPFLAGS_NODEBUG -DMDDS_HASH_CONTAINER_BOOST" fi -CPPFLAGS="$CPPFLAGS_NODEBUG -DMDDS_DEBUG_NODE_BASE -DMDDS_UNIT_TEST -std=c++0x" +CPPFLAGS="$CPPFLAGS $CPPFLAGS_NODEBUG -DMDDS_DEBUG_NODE_BASE -DMDDS_UNIT_TEST -std=c++0x" if test "$debug_stdcxx" = "yes"; then CPPFLAGS="$CPPFLAGS -D_GLIBCXX_DEBUG" diff --git a/include/mdds/global.hpp b/include/mdds/global.hpp index 7e70588..b54fba8 100644 --- a/include/mdds/global.hpp +++ b/include/mdds/global.hpp @@ -1,6 +1,6 @@ /************************************************************************* * - * Copyright (c) 2008-2011 Kohei Yoshida + * Copyright (c) 2008-2014 Kohei Yoshida * * Permission is hereby granted, free of charge, to any person * obtaining a copy of this software and associated documentation @@ -25,12 +25,14 @@ * ************************************************************************/ -#ifndef __MDDS_GLOBAL_HPP__ -#define __MDDS_GLOBAL_HPP__ +#ifndef MDDS_GLOBAL_HPP +#define MDDS_GLOBAL_HPP #include <exception> #include <string> +#define MDDS_ASCII(literal) literal, sizeof(literal)-1 + namespace mdds { class general_error : public ::std::exception diff --git a/include/mdds/multi_type_matrix.hpp b/include/mdds/multi_type_matrix.hpp index 0574466..d555162 100644 --- a/include/mdds/multi_type_matrix.hpp +++ b/include/mdds/multi_type_matrix.hpp @@ -63,6 +63,11 @@ struct std_string_trait } +/** + * Matrix that can store double, bool, empty and string types. The string + * type is specified by the string trait template parameter. To use + * std::string as the string type, use mdds::mtm::std_string_trait. + */ template<typename _StringTrait> class multi_type_matrix { diff --git a/include/mdds/multi_type_vector.hpp b/include/mdds/multi_type_vector.hpp index 57c8734..7baecef 100644 --- a/include/mdds/multi_type_vector.hpp +++ b/include/mdds/multi_type_vector.hpp @@ -37,9 +37,9 @@ #include <vector> #include <algorithm> #include <cassert> +#include <sstream> #if defined(MDDS_UNIT_TEST) || defined (MDDS_MULTI_TYPE_VECTOR_DEBUG) -#include <sstream> #include <iostream> using std::cout; using std::cerr; @@ -872,6 +872,11 @@ public: */ void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos); + /** + * Trim excess capacity from all non-empty blocks. + */ + void shrink_to_fit(); + bool operator== (const multi_type_vector& other) const; bool operator!= (const multi_type_vector& other) const; diff --git a/include/mdds/multi_type_vector_custom_func1.hpp b/include/mdds/multi_type_vector_custom_func1.hpp index 7f91886..3717e06 100644 --- a/include/mdds/multi_type_vector_custom_func1.hpp +++ b/include/mdds/multi_type_vector_custom_func1.hpp @@ -219,6 +219,18 @@ struct custom_block_func1 element_block_func::overwrite_values(block, pos, len); } } + + static void shrink_to_fit(base_element_block& block) + { + switch (get_block_type(block)) + { + case _Block::block_type: + _Block::shrink_to_fit(block); + break; + default: + element_block_func::shrink_to_fit(block); + } + } }; }} diff --git a/include/mdds/multi_type_vector_custom_func2.hpp b/include/mdds/multi_type_vector_custom_func2.hpp index b6e9d3b..bc05bef 100644 --- a/include/mdds/multi_type_vector_custom_func2.hpp +++ b/include/mdds/multi_type_vector_custom_func2.hpp @@ -266,6 +266,21 @@ struct custom_block_func2 element_block_func::overwrite_values(block, pos, len); } } + + static void shrink_to_fit(base_element_block& block) + { + switch (get_block_type(block)) + { + case _Block1::block_type: + _Block1::shrink_to_fit(block); + break; + case _Block2::block_type: + _Block2::shrink_to_fit(block); + break; + default: + element_block_func::shrink_to_fit(block); + } + } }; }} diff --git a/include/mdds/multi_type_vector_custom_func3.hpp b/include/mdds/multi_type_vector_custom_func3.hpp index b107801..7ee0555 100644 --- a/include/mdds/multi_type_vector_custom_func3.hpp +++ b/include/mdds/multi_type_vector_custom_func3.hpp @@ -310,6 +310,24 @@ struct custom_block_func3 element_block_func::overwrite_values(block, pos, len); } } + + static void shrink_to_fit(base_element_block& block) + { + switch (get_block_type(block)) + { + case _Block1::block_type: + _Block1::shrink_to_fit(block); + break; + case _Block2::block_type: + _Block2::shrink_to_fit(block); + break; + case _Block3::block_type: + _Block3::shrink_to_fit(block); + break; + default: + element_block_func::shrink_to_fit(block); + } + } }; }} diff --git a/include/mdds/multi_type_vector_def.inl b/include/mdds/multi_type_vector_def.inl index d20a9df..ba2cfeb 100644 --- a/include/mdds/multi_type_vector_def.inl +++ b/include/mdds/multi_type_vector_def.inl @@ -31,6 +31,19 @@ namespace mdds { +namespace detail { + +inline void throw_block_position_not_found( + const char* method_sig, int line, size_t pos, size_t block_size, size_t container_size) +{ + std::ostringstream os; + os << method_sig << "#" << line << ": block position not found! (logical pos=" + << pos << ", block size=" << block_size << ", logical size=" << container_size << ")"; + throw std::out_of_range(os.str()); +} + +} + MDDS_MTV_DEFINE_ELEMENT_CALLBACKS(double, mtv::element_type_numeric, 0.0, mtv::numeric_element_block) MDDS_MTV_DEFINE_ELEMENT_CALLBACKS(std::string, mtv::element_type_string, std::string(), mtv::string_element_block) MDDS_MTV_DEFINE_ELEMENT_CALLBACKS(short, mtv::element_type_short, 0, mtv::short_element_block) @@ -250,7 +263,7 @@ multi_type_vector<_CellBlockFunc>::set(size_type pos, const _T& value) size_type start_row = 0; size_type block_index = 0; if (!get_block_position(pos, start_row, block_index)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::set", __LINE__, pos, block_size(), size()); #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG std::ostringstream os_prev_block; @@ -471,7 +484,7 @@ multi_type_vector<_CellBlockFunc>::set(size_type pos, const _T& it_begin, const size_type block_index1 = 0, start_row1 = 0; if (!get_block_position(pos, start_row1, block_index1)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::set", __LINE__, pos, block_size(), size()); return set_cells_impl(pos, end_pos, start_row1, block_index1, it_begin, it_end); } @@ -561,7 +574,7 @@ multi_type_vector<_CellBlockFunc>::insert(size_type pos, const _T& it_begin, con { size_type block_index = 0, start_pos = 0; if (!get_block_position(pos, start_pos, block_index)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::insert", __LINE__, pos, block_size(), size()); #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG std::ostringstream os_prev_block; @@ -657,7 +670,7 @@ void multi_type_vector<_CellBlockFunc>::get_block_position( } if (!get_block_position(pos, start_row, block_index)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::get_block_position", __LINE__, pos, block_size(), size()); } template<typename _CellBlockFunc> @@ -1184,7 +1197,7 @@ void multi_type_vector<_CellBlockFunc>::get(size_type pos, _T& value) const size_type start_row = 0; size_type block_index = 0; if (!get_block_position(pos, start_row, block_index)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::get", __LINE__, pos, block_size(), size()); const block* blk = m_blocks[block_index]; assert(blk); @@ -1218,7 +1231,7 @@ _T multi_type_vector<_CellBlockFunc>::release(size_type pos) size_type start_pos = 0; size_type block_index = 0; if (!get_block_position(pos, start_pos, block_index)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::release", __LINE__, pos, block_size(), size()); _T value; release_impl(pos, start_pos, block_index, value); @@ -1233,7 +1246,7 @@ multi_type_vector<_CellBlockFunc>::release(size_type pos, _T& value) size_type start_pos = 0; size_type block_index = 0; if (!get_block_position(pos, start_pos, block_index)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::release", __LINE__, pos, block_size(), size()); return release_impl(pos, start_pos, block_index, value); } @@ -1273,7 +1286,7 @@ multi_type_vector<_CellBlockFunc>::release_range(size_type start_pos, size_type size_type start_pos_in_block1 = 0; size_type block_index1 = 0; if (!get_block_position(start_pos, start_pos_in_block1, block_index1)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::release_range", __LINE__, start_pos, block_size(), size()); return set_empty_impl(start_pos, end_pos, start_pos_in_block1, block_index1, false); } @@ -1296,7 +1309,7 @@ multi_type_vector<_CellBlockFunc>::position(size_type pos) size_type start_pos = 0; size_type block_index = 0; if (!get_block_position(pos, start_pos, block_index)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::position", __LINE__, pos, block_size(), size()); iterator it = get_iterator(block_index, start_pos); return position_type(it, pos - start_pos); @@ -1321,7 +1334,7 @@ multi_type_vector<_CellBlockFunc>::position(size_type pos) const size_type start_row = 0; size_type block_index = 0; if (!get_block_position(pos, start_row, block_index)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::position", __LINE__, pos, block_size(), size()); typename blocks_type::const_iterator block_pos = m_blocks.begin(); std::advance(block_pos, block_index); @@ -1352,7 +1365,7 @@ multi_type_vector<_CellBlockFunc>::transfer( size_type start_pos_in_block1 = 0; size_type block_index1 = 0; if (!get_block_position(start_pos, start_pos_in_block1, block_index1)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::transfer", __LINE__, start_pos, block_size(), size()); #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG std::ostringstream os_prev_block; @@ -1418,7 +1431,7 @@ mtv::element_t multi_type_vector<_CellBlockFunc>::get_type(size_type pos) const size_type start_row = 0; size_type block_index = 0; if (!get_block_position(pos, start_row, block_index)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::get_type", __LINE__, pos, block_size(), size()); const block* blk = m_blocks[block_index]; if (!blk->mp_data) @@ -1433,7 +1446,7 @@ bool multi_type_vector<_CellBlockFunc>::is_empty(size_type pos) const size_type start_row = 0; size_type block_index = 0; if (!get_block_position(pos, start_row, block_index)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::is_empty", __LINE__, pos, block_size(), size()); return m_blocks[block_index]->mp_data == NULL; } @@ -1445,7 +1458,7 @@ multi_type_vector<_CellBlockFunc>::set_empty(size_type start_pos, size_type end_ size_type start_pos_in_block1 = 0; size_type block_index1 = 0; if (!get_block_position(start_pos, start_pos_in_block1, block_index1)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::set_empty", __LINE__, start_pos, block_size(), size()); return set_empty_impl(start_pos, end_pos, start_pos_in_block1, block_index1, true); } @@ -1477,7 +1490,7 @@ multi_type_vector<_CellBlockFunc>::transfer_impl( size_type start_pos_in_block2 = start_pos_in_block1; size_type block_index2 = block_index1; if (!get_block_position(end_pos, start_pos_in_block2, block_index2)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::transfer_impl", __LINE__, end_pos, block_size(), size()); size_type len = end_pos - start_pos + 1; size_type last_dest_pos = dest_pos + len - 1; @@ -1545,6 +1558,7 @@ multi_type_vector<_CellBlockFunc>::transfer_single_block( dest.m_blocks.insert(dest.m_blocks.begin()+dest_block_index+1, new block(len)); blk_dest->m_size -= len; blk_dest = dest.m_blocks[dest_block_index+1]; + ++dest_block_index; // Must point to the new copied block. } else { @@ -1558,6 +1572,8 @@ multi_type_vector<_CellBlockFunc>::transfer_single_block( blk_dest->m_size = dest_pos_in_block; blk_dest = dest.m_blocks[dest_block_index+1]; + + ++dest_block_index; // Must point to the new copied block. } assert(blk_dest->m_size == len); @@ -1844,7 +1860,7 @@ multi_type_vector<_CellBlockFunc>::set_empty_impl( size_type start_pos_in_block2 = start_pos_in_block1; size_type block_index2 = block_index1; if (!get_block_position(end_pos, start_pos_in_block2, block_index2)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::set_empty_impl", __LINE__, end_pos, block_size(), size()); #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG std::ostringstream os_prev_block; @@ -1974,6 +1990,8 @@ void multi_type_vector<_CellBlockFunc>::swap_single_blocks( mdds::unique_ptr<element_block_type, element_block_deleter> src_data(blk_src->mp_data); blk_src->mp_data = other.exchange_elements( *src_data, src_offset, other_block_index, dst_offset, len); + // Release elements in the source block to prevent double-deletion. + element_block_func::resize_block(*src_data, 0); merge_with_adjacent_blocks(block_index); return; } @@ -2270,12 +2288,12 @@ void multi_type_vector<_CellBlockFunc>::erase_impl(size_type start_row, size_typ size_type start_row_in_block1 = 0; size_type block_pos1 = 0; if (!get_block_position(start_row, start_row_in_block1, block_pos1)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::erase_impl", __LINE__, start_row, block_size(), size()); size_type start_row_in_block2 = start_row_in_block1; size_type block_pos2 = block_pos1; if (!get_block_position(end_row, start_row_in_block2, block_pos2)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::erase_impl", __LINE__, end_row, block_size(), size()); if (block_pos1 == block_pos2) { @@ -2418,7 +2436,7 @@ multi_type_vector<_CellBlockFunc>::insert_empty(size_type pos, size_type length) size_type start_pos = 0, block_index = 0; if (!get_block_position(pos, start_pos, block_index)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::insert_empty", __LINE__, pos, block_size(), size()); #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG std::ostringstream os_prev_block; @@ -2561,7 +2579,7 @@ multi_type_vector<_CellBlockFunc>::set_cells_impl( size_type start_row2 = start_row1; size_type block_index2 = block_index1; if (!get_block_position(end_row, start_row2, block_index2)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::set_cells_impl", __LINE__, end_row, block_size(), size()); if (block_index1 == block_index2) { @@ -3587,7 +3605,7 @@ void multi_type_vector<_CellBlockFunc>::resize(size_type new_size) size_type new_end_row = new_size - 1; size_type start_row_in_block = 0, block_index = 0; if (!get_block_position(new_end_row, start_row_in_block, block_index)) - throw std::out_of_range("Block position not found!"); + detail::throw_block_position_not_found("multi_type_vector::resize", __LINE__, new_end_row, block_size(), size()); block* blk = m_blocks[block_index]; size_type end_row_in_block = start_row_in_block + blk->m_size - 1; @@ -3673,6 +3691,19 @@ void multi_type_vector<_CellBlockFunc>::swap(size_type start_pos, size_type end_ } template<typename _CellBlockFunc> +void multi_type_vector<_CellBlockFunc>::shrink_to_fit() +{ + typename blocks_type::iterator it = m_blocks.begin(), it_end = m_blocks.end(); + for (; it != it_end; ++it) + { + block* blk = *it; + assert(blk); + if (blk->mp_data) + element_block_func::shrink_to_fit(*blk->mp_data); + } +} + +template<typename _CellBlockFunc> bool multi_type_vector<_CellBlockFunc>::operator== (const multi_type_vector& other) const { if (this == &other) diff --git a/include/mdds/multi_type_vector_trait.hpp b/include/mdds/multi_type_vector_trait.hpp index c99ec17..03ed36b 100644 --- a/include/mdds/multi_type_vector_trait.hpp +++ b/include/mdds/multi_type_vector_trait.hpp @@ -74,6 +74,8 @@ struct element_block_func_base * store primitive values), this method can be left empty. */ inline static void overwrite_values(base_element_block& block, size_t pos, size_t len); + + inline static void shrink_to_fit(base_element_block& block); }; base_element_block* element_block_func_base::create_new_block(element_t type, size_t init_size) @@ -608,6 +610,48 @@ void element_block_func_base::overwrite_values(base_element_block&, size_t, size // Do nothing for the standard types. } +void element_block_func_base::shrink_to_fit(base_element_block& block) +{ + switch (get_block_type(block)) + { + case element_type_numeric: + numeric_element_block::shrink_to_fit(block); + break; + case element_type_string: + string_element_block::shrink_to_fit(block); + break; + case element_type_short: + short_element_block::shrink_to_fit(block); + break; + case element_type_ushort: + ushort_element_block::shrink_to_fit(block); + break; + case element_type_int: + int_element_block::shrink_to_fit(block); + break; + case element_type_uint: + uint_element_block::shrink_to_fit(block); + break; + case element_type_long: + long_element_block::shrink_to_fit(block); + break; + case element_type_ulong: + ulong_element_block::shrink_to_fit(block); + break; + case element_type_boolean: + boolean_element_block::shrink_to_fit(block); + break; + case element_type_char: + char_element_block::shrink_to_fit(block); + break; + case element_type_uchar: + uchar_element_block::shrink_to_fit(block); + break; + default: + throw general_error("shrink_to_fit: failed to print a block of unknown type."); + } +} + /** * Default cell block function definitions. Implementation can use this if * it only uses the default block types implemented by the library. diff --git a/include/mdds/multi_type_vector_types.hpp b/include/mdds/multi_type_vector_types.hpp index 3fb31cc..bb8fdbe 100644 --- a/include/mdds/multi_type_vector_types.hpp +++ b/include/mdds/multi_type_vector_types.hpp @@ -1,6 +1,6 @@ /************************************************************************* * - * Copyright (c) 2012 Kohei Yoshida + * Copyright (c) 2012-2014 Kohei Yoshida * * Permission is hereby granted, free of charge, to any person * obtaining a copy of this software and associated documentation @@ -378,6 +378,24 @@ public: blk.insert(blk.begin()+pos, it_begin, it_end); } + static size_t capacity(const base_element_block& block) + { +#ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE + return 0; +#else + const store_type& blk = get(block).m_array; + return blk.capacity(); +#endif + } + + static void shrink_to_fit(base_element_block& block) + { +#ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE + store_type& blk = get(block).m_array; + store_type(blk).swap(blk); +#endif + } + private: static std::pair<const_iterator,const_iterator> get_iterator_pair(const store_type& array, size_t begin_pos, size_t len) diff --git a/include/mdds/sorted_string_map.hpp b/include/mdds/sorted_string_map.hpp new file mode 100644 index 0000000..e98b930 --- /dev/null +++ b/include/mdds/sorted_string_map.hpp @@ -0,0 +1,101 @@ +/************************************************************************* + * + * Copyright (c) 2014 Kohei Yoshida + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + * + ************************************************************************/ + +#ifndef MDDS_SORTED_STRING_MAP_HPP +#define MDDS_SORTED_STRING_MAP_HPP + +#include <cstdlib> + +namespace mdds { + +/** + * sorted_string_map provides an efficient way to map string keys to + * arbitrary values, provided that the keys are known at compile time and + * are sorted in ascending order. + */ +template<typename _ValueT> +class sorted_string_map +{ +public: + typedef _ValueT value_type; + typedef size_t size_type; + + /** + * Single key-value entry. Caller must provide at compile time a static + * array of these entries. + */ + struct entry + { + const char* key; + size_type keylen; + value_type value; + }; + + /** + * Constructor. + * + * @param entries pointer to the array of key-value entries. + * @param entry_size size of the key-value entry array. + * @param null_value null value to return when the find method fails to + * find a matching entry. + */ + sorted_string_map(const entry* entries, size_type entry_size, value_type null_value); + + /** + * Find a value associated with a specified string key. + * + * @param input pointer to a C-style string whose value represents the key + * to match. + * @param len length of the matching string value. + * + * @return value associated with the key, or the null value in case the + * key is not found. + */ + value_type find(const char* input, size_type len) const; + + /** + * Return the number of entries in the map. Since the number of entries + * is statically defined at compile time, this method always returns the + * same value. + * + * @return the number of entries in the map. + */ + size_type size() const; + +private: + + const entry* m_entries; + value_type m_null_value; + size_type m_entry_size; + const entry* m_entry_end; +}; + +} + +#include "sorted_string_map_def.inl" + +#endif diff --git a/include/mdds/global.hpp b/include/mdds/sorted_string_map_def.inl similarity index 54% copy from include/mdds/global.hpp copy to include/mdds/sorted_string_map_def.inl index 7e70588..20d9dc9 100644 --- a/include/mdds/global.hpp +++ b/include/mdds/sorted_string_map_def.inl @@ -1,6 +1,6 @@ /************************************************************************* * - * Copyright (c) 2008-2011 Kohei Yoshida + * Copyright (c) 2014 Kohei Yoshida * * Permission is hereby granted, free of charge, to any person * obtaining a copy of this software and associated documentation @@ -25,34 +25,46 @@ * ************************************************************************/ -#ifndef __MDDS_GLOBAL_HPP__ -#define __MDDS_GLOBAL_HPP__ - -#include <exception> -#include <string> - namespace mdds { -class general_error : public ::std::exception -{ -public: - general_error(const ::std::string& msg) : m_msg(msg) {} - virtual ~general_error() throw() {} +template<typename _ValueT> +sorted_string_map<_ValueT>::sorted_string_map(const entry* entries, size_type entry_size, value_type null_value) : + m_entries(entries), + m_null_value(null_value), + m_entry_size(entry_size), + m_entry_end(m_entries+m_entry_size) {} - virtual const char* what() const throw() +template<typename _ValueT> +typename sorted_string_map<_ValueT>::value_type +sorted_string_map<_ValueT>::find(const char* input, size_type len) const +{ + const entry* p = m_entries; + size_type pos = 0; + for (; p != m_entry_end; ++p) { - return m_msg.c_str(); + const char* key = p->key; + size_type keylen = p->keylen; + for (; pos < len && pos < keylen; ++pos) + { + if (input[pos] != key[pos]) + // Move to the next entry. + break; + } + + if (pos == len && len == keylen) + { + // Match found! + return p->value; + } } -private: - ::std::string m_msg; -}; + return m_null_value; +} -class invalid_arg_error : public general_error +template<typename _ValueT> +typename sorted_string_map<_ValueT>::size_type +sorted_string_map<_ValueT>::size() const { -public: - invalid_arg_error(const ::std::string& msg) : general_error(msg) {} -}; - + return m_entry_size; } -#endif +} diff --git a/src/multi_type_vector_test_custom.cpp b/src/multi_type_vector_test_custom.cpp index 42d9156..96b61ee 100644 --- a/src/multi_type_vector_test_custom.cpp +++ b/src/multi_type_vector_test_custom.cpp @@ -1395,6 +1395,60 @@ void mtv_test_swap() db2.set(1, string("B")); db1.swap(2, 3, db2, 0); + + // swap blocks of equal size, one managed, and one default. + + db1.clear(); + db1.resize(10); + db2.clear(); + db2.resize(10); + + db1.set(3, 2.1); + db1.set(4, 2.2); + db1.set(5, 2.3); + + db2.set(3, new muser_cell(3.1)); + db2.set(4, new muser_cell(3.2)); + db2.set(5, new muser_cell(3.3)); + + db2.swap(3, 5, db1, 3); + + assert(db1.size() == 10); + assert(db1.block_size() == 3); + assert(db2.size() == 10); + assert(db2.block_size() == 3); + + assert(db1.get<muser_cell*>(3)->value == 3.1); + assert(db1.get<muser_cell*>(4)->value == 3.2); + assert(db1.get<muser_cell*>(5)->value == 3.3); + assert(db2.get<double>(3) == 2.1); + assert(db2.get<double>(4) == 2.2); + assert(db2.get<double>(5) == 2.3); + + db2.swap(3, 5, db1, 3); + + assert(db1.get<double>(3) == 2.1); + assert(db1.get<double>(4) == 2.2); + assert(db1.get<double>(5) == 2.3); + assert(db2.get<muser_cell*>(3)->value == 3.1); + assert(db2.get<muser_cell*>(4)->value == 3.2); + assert(db2.get<muser_cell*>(5)->value == 3.3); + + // Same as above, except that the source segment splits the block into 2. + + db1.clear(); + db1.resize(10); + db2.clear(); + db2.resize(10); + + db1.set(3, 2.1); + db1.set(4, 2.2); + + db2.set(3, new muser_cell(3.1)); + db2.set(4, new muser_cell(3.2)); + db2.set(5, new muser_cell(3.3)); + + db2.swap(3, 4, db1, 3); } void mtv_test_custom_block_func3() diff --git a/src/multi_type_vector_test_default.cpp b/src/multi_type_vector_test_default.cpp index 8345b0f..28ff59e 100644 --- a/src/multi_type_vector_test_default.cpp +++ b/src/multi_type_vector_test_default.cpp @@ -4878,6 +4878,76 @@ void mtv_test_transfer() db1.set(2, 12.8); it = db1.transfer(1, 2, db2, 1); + + // Reset and start over. + db1.clear(); + db1.resize(20); + db2.clear(); + db2.resize(20); + + db1.set(9, 1.1); + + db2.set(10, 1.2); + db2.set(11, 1.3); + + it = db1.transfer(9, 9, db2, 9); + + // The source should be entirely empty after the transfer. + assert(db1.block_size() == 1); + assert(it == db1.begin()); + assert(it->__private_data.block_index == 0); + assert(it->size == 20); + assert(it->type == mtv::element_type_empty); + ++it; + assert(it == db1.end()); + + // Check the destination as well. + assert(db2.block_size() == 3); + it = db2.begin(); + assert(it->size == 9); + assert(it->__private_data.block_index == 0); + assert(it->type == mtv::element_type_empty); + ++it; + assert(it->size == 3); + assert(it->__private_data.block_index == 1); + assert(it->type == mtv::element_type_numeric); + ++it; + assert(it->size == 8); + assert(it->__private_data.block_index == 2); + assert(it->type == mtv::element_type_empty); + ++it; + assert(it == db2.end()); + assert(db2.get<double>(9) == 1.1); + assert(db2.get<double>(10) == 1.2); + assert(db2.get<double>(11) == 1.3); + + // Reset and start over. + db1.clear(); + db1.resize(20); + db2.clear(); + db2.resize(20); + + db1.set(8, 1.0); + db1.set(9, 1.1); + + db2.set(10, 1.2); + db2.set(11, 1.3); + + it = db1.transfer(9, 9, db2, 9); + assert(it->__private_data.block_index == 2); + assert(db1.block_size() == 3); + assert(db1.get<double>(8) == 1.0); + it = db1.begin(); + assert(it->size == 8); + assert(it->type == mtv::element_type_empty); + ++it; + assert(it->size == 1); + assert(it->type == mtv::element_type_numeric); + ++it; + assert(it->size == 11); + assert(it->type == mtv::element_type_empty); + ++it; + assert(it == db1.end()); } void mtv_test_push_back() @@ -4978,6 +5048,25 @@ void mtv_test_push_back() assert(it->type == mtv::element_type_numeric); } +void mtv_test_capacity() +{ + stack_printer __stack_printer__("::mtv_test_capacity"); + mtv_type db(10, 1.1); + assert(db.block_size() == 1); + mtv_type::const_iterator it = db.begin(); + assert(it->type == mtv::element_type_numeric); + size_t cap = mtv::numeric_element_block::capacity(*it->data); + assert(cap == 10); + + db.set_empty(3, 3); + assert(db.block_size() == 3); + db.shrink_to_fit(); + it = db.begin(); + assert(it->type == mtv::element_type_numeric); + cap = mtv::numeric_element_block::capacity(*it->data); + assert(cap == 3); +} + } int main (int argc, char **argv) @@ -5015,6 +5104,7 @@ int main (int argc, char **argv) mtv_test_block_identifier(); mtv_test_transfer(); mtv_test_push_back(); + mtv_test_capacity(); cout << "Test finished successfully!" << endl; return EXIT_SUCCESS; diff --git a/src/sorted_string_map_test.cpp b/src/sorted_string_map_test.cpp new file mode 100644 index 0000000..7d2070d --- /dev/null +++ b/src/sorted_string_map_test.cpp @@ -0,0 +1,94 @@ +/************************************************************************* + * + * Copyright (c) 2014 Kohei Yoshida + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + * + ************************************************************************/ + +#define MDDS_MULTI_TYPE_VECTOR_DEBUG 1 +#include "mdds/sorted_string_map.hpp" +#include "mdds/global.hpp" + +#include "test_global.hpp" + +#include <cassert> + +using namespace std; + +enum name_type { + name_none = 0, + name_andy, + name_bruce, + name_charlie, + name_david +}; + +void ssmap_test_basic() +{ + stack_printer __stack_printer__("::ssmap_test_basic"); + + typedef mdds::sorted_string_map<name_type> map_type; + + map_type::entry entries[] = + { + { MDDS_ASCII("andy"), name_andy }, + { MDDS_ASCII("andy1"), name_andy }, + { MDDS_ASCII("andy13"), name_andy }, + { MDDS_ASCII("bruce"), name_bruce }, + { MDDS_ASCII("charlie"), name_charlie }, + { MDDS_ASCII("david"), name_david }, + }; + + size_t entry_count = sizeof(entries)/sizeof(entries[0]); + map_type names(entries, entry_count, name_none); + for (size_t i = 0; i < entry_count; ++i) + { + cout << "* key = " << entries[i].key << endl; + bool res = names.find(entries[i].key, strlen(entries[i].key)) == entries[i].value; + assert(res); + } + + // Try invalid keys. + assert(names.find("foo", 3) == name_none); + assert(names.find("andy133", 7) == name_none); +} + +int main (int argc, char **argv) +{ + cmd_options opt; + if (!parse_cmd_options(argc, argv, opt)) + return EXIT_FAILURE; + + if (opt.test_func) + { + ssmap_test_basic(); + } + + if (opt.test_perf) + { + } + + fprintf(stdout, "Test finished successfully!\n"); + return 0; +} + -- Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-openoffice/mdds.git
