diff options
Diffstat (limited to 'CHANGELOG')
| -rw-r--r-- | CHANGELOG | 899 |
1 files changed, 899 insertions, 0 deletions
diff --git a/CHANGELOG b/CHANGELOG new file mode 100644 index 0000000..bdd8f5c --- /dev/null +++ b/CHANGELOG @@ -0,0 +1,899 @@ +mdds 2.1.1 + +* flat_segment_tree + + * added a method that returns a segment range object compatible with ranged + for loop. + + * added a move constructor and a move assignment operator. + + * added variants of search() and search_tree() that return a result data + structure that contains the value, the start and end keys of the range. + +* multi_type_vector + + * added a range adaptor for mdds::mtv::element_block compatible with ranged + for loop. + +mdds 2.1.0 + +* general + + * switched to using ax_valgrind_check for running memory tests. This + introduces additional build targets, such as check-valgrind to run the + tests under valgrind. + +* multi_type_vector + + * delayed_delete_vector has been introduced as the new default storage type + for the element blocks. This storage type is optimized for use cases + where elements get repeatedly erased from the front of the array, by + delaying the actual deletion of the elements until much later. This + reduces the amount of element shifting associated with the element + deletions, which can be costly. + + * added an additional template parameter to the element block types in order + to allow the underlying storage type to be specified per element type. + This can be used to switch between std::vector, std::deque, + delayed_delete_vector, or any other compatible custom container types. + +* sorted_string_map + + * made the entry type a template parameter to allow optionally defining the + keys in the entry values as std::string_view. + +mdds 2.0.3 + +* general + + * defined clang-format rules, and globally applied them to all active source + files. + +* multi_type_vector + + * revised the block position lookup implementation to avoid using the + internal STL iterators. The new implementation should be able to handle + invalid position hints more gracefully without potential process + termination. + +mdds 2.0.2 + +* multi_type_vector + + * added optional trace function that gets called on every called public + method. + +mdds 2.0.1 + +* general + + * addressed various coverity issues. + +* multi_type_vector + + * fixed random compiler warnings. + + * fixed event handling in copy construction. In aos, the event object was + not copied when the parent container was copied. In soa, the + element_block_acquired() callback was not called for the cloned element + blocks. + + * added move constructors and move assignment operators to both aos and soa + variants. + +mdds 2.0.0 + +* general + + * set the baseline C++ version to C++17. + +* multi_type_vector + + * implemented structure-of-arrays (SoA) storage as its default storage + layout for better CPU cache efficiency. + + * added multiple block position adjustment implementations with various + loop-unrolling factors combined with SSE2 and AVX2 features. + + * added a tool called runtime-env to benchmark different block position + adjustment implementations to determine the optimal loop-unrolling factor. + +* rectangle_set + + * permanently removed. + +* rtree + + * fixed a bug where the memory positions of invalidated child nodes were not + properly updated after tree mutation. The problem manifested itself when + using libc++ as stdlib with clang. + +mdds 1.7.0 + +* trie_map + + * added copy and move constructors. + + * added a variant of find() method that returns a mutable iterator object. + The user can now update the value associated with a key directly via the + iterator object. + +* packed_trie_map + + * added copy and move constructors. + + * added load_state() and save_state() methods to allow loading state from + and saving state to binary files. + +mdds 1.6.0 + +* multi_type_vector + + * switched to using binary search on block position lookup, which + significantly improves element access performance in general, at the + expense of slight performance degradation on block shifting. + +* added support for lcov, to visualize test coverage. + +mdds 1.5.0 + +* documentation + + * moved the documentation hosting to readthedocs.io, and adjusted the build + steps. + + * moved the API incompatibility notes from README to the rst doc. + + * added the overview section for flat_segment_tree. + +* multi_type_vector + + * fixed the static get(const const_position_type& pos) method for the + boolean_element_block, by adding specialization for it to work around the + issue with std::vector<bool> not having the at() method. + + * fixed an issue with the const position() method not returning a valid end + position the same way the non-const variant does. + + * added steps to traverse blocks backward from the postiion specified in the + position hint. This may result in improved performance in some + situations. + + * the standard integer blocks now use fixed size integer types i.e. + + * (u)int8_t + + * (u)int16_t + + * (u)int32_t + + * (u)int64_t + + * The numeric_element_block has been renamed to double_element_block. + + * added new block type to store float element values. + +* general + + * added gdb pretty printers that prints the contents of the data structures. + +mdds 1.4.3 + +* documentation + + * added details on how to use two type of iterators with + flat_segment_tree. + + * added new section to describe how to use mtv::collection to iterate + through multiple multi_type_vector instances as a single collection + in the direction orthogonal to the direction of the individual + vectors. + + * added new page for R-tree. + +* flat_segment_tree + + * fixed invalid memory access issue related to the swap() method which + previously did not swap the non-leaf node pool store. The invalid + memory access may occur after the contents of two instances get + swapped, one instance get destroyed then the caller calls + search_tree() on the other instance still alive. + +mdds 1.4.2 + +* all + + * fixed CXXFLAGS incorrectly being overwritten. + + * addressed a number of Coverity issues. + +mdds 1.4.1 + +* all + + * fixed all warnings on shadowed variables. + +* multi_type_matrix + + * all of its walk() methods now return either a copied or moved + instance of the function object passed in as an input argument. + Previously these methods had no return values. + +mdds 1.4.0 + +* rtree (new) + + * new data structure designed for optimal storage and query + performance on multi-dimensional spatial data. The structure allows + storage of both point and extent-based boundaries as keys associated + with values. + +* multi_type_vector + + * mtv::elemnt_block now has the following methods: data(), cbegin(), + cend(), crbegin() and crend(). + + * multi_type_vector now has cbegin(), cend(), crbegin(), and crend() + methods. + + * some unnecessary user-provided special members have been removed to + avoid warnings with -Wdeprecated-copy with GCC 9. + +* multi_type_matrix + + * all of its walk() methods now allow in-line lambdas to be used, by + not taking a reference of the function object parameters. + +mdds 1.3.1 + +* flat_segment_tree + + * fixed a bug that caused an assertion error when inserting a + out-of-bound segment whose start value equals the max key value. + +mdds 1.3.0 + +* multi_type_vector + + * changed the primary block array storage to remove additional + indirection, for improved memory locality. + +mdds 1.2.3 + +* all + + * changed the configure script to use --docdir unmodified. + +* flat_segment_tree + + * added a segment iterator whose node value consists of the start + and end keys and the value associated with each segment. its + start and end positions can be retrieved via begin_segment() and + end_segment() methods. + +mdds 1.2.2 + +* flat_segment_tree + + * fixed a bug that would cause segmentation faults with the insert() + method with out-of-bound segment value pair. + +mdds 1.2.1 + +* multi_type_vector + + * added size() method to the element block type, which returns the + actual size of the element block, instead of the cached size value + stored in the parent structure that stores the element block. + + * fixed a double-deletion bug in the swap() method which would + triggered when used with a managed element block. + +* mtv::collection + + * fixed collection iterator's get() method to properly return values + from the boolean element block. + +mdds 1.2.0 + +* packed_trie_map + + * added begin() and end() methods that return read-only iterators. + + * find() method now returns a const_iterator instance. + + * prefix_search() method now returns a search_results instance that + can be iterated. + + * null value no longer needs to be passed to the constructor. + + * find() and prefix_search() now have a variant that can take a key + value that is of key_type directly. + +* trie_map + + * added begin() and end() methods that return read-only iterators. + + * find() method now returns a const_iterator instance. + + * prefix_search() method now returns a search_results instance that + can be iterated. + + * null value no longer needs to be passed to the constructor. + + * find(), insert, and prefix_search() now have a variant that can + take a key value that is of key_type directly. + +* sorted_string_map + + * fix build failure with _GLIBCXX_DEBUG defined. + +* multi_type_vector + + * remove compiler warning about shadowed variable. + + * added a supplemental class mdds::mtv::collection which allows + multiple multi_type_vector instances of the same length to be + grouped together in order to iterate through their elements + sideways. + + * a variant of advance_position() static method that takes + const_position_type has been added. + + * const_position_type advance_position(const const_position_type& pos, int steps) + +* multi_type_matrix + + * matrix_position() is now a const method. + + * the sub-matrix variant of walk() method now throws size_error + exception when invalid start and end positions are passed. + + * slight performance improvement with the sub-matrix variant of + walk() method that involves multiple column traversal. + + * added 2 new variants of walk() methods that allow parallel walking + with another matrix instance. + + * template<typename _Func> + void walk(_Func& func, const multi_type_matrix& right) const + + * template<typename _Func> + void walk(_Func& func, const multi_type_matrix& right, const size_pair_type& start, const size_pair_type& end) const + + * improved performance of copy() and resize() methods. + + * added a variant of copy() that takes an array of values. + + * template<typename _T> + void copy(size_type rows, size_type cols, const _T& it_begin, const _T& it_end) + + * integer type has been added to the list of types the matrix can + store. In conjunction with this change, what was formerly known + as the string trait structure is now known as the matrix trait, + which specifies the actual integer type the matrix stores. + +* point_quad_tree + + * search_result has been renamed to search_results. + +mdds 1.1.0 + +* all + + * switched our build system to using automake. + +* packed_trie_map (new) + + * new data structure that implements a trie also known as a prefix + tree. This implementation requires all key values be known at + construction time, after which its content is considered + immutable. Internally it packs all its nodes in a single + contiguous array for space and lookup efficiencies. + +* trie_map (new) + + * new data structure that implements a trie. It works similar to + packed_trie_map except that this version is mutable. + +* multi_type_matrix + + * added a variant of walk() that takes the upper-left and + lower-right corners to allow walking through a subset of the + original matrix. + +* multi_type_vector + + * fixed incorrect return values of the increment and decrement + operators of in-block iterators. They would previously return a + value_type pointer which did not conform to the behaviors of STL + iterators. + + * added support for custom event handlers for element block + acquisitions and releases. + +* flat_segment_tree + + * fixed incorrect return values of the increment and decrement + operators of its leaf-node iterators as in multi_type_vector's + fix. + +* sorted_string_map + + * significantly improved the performance of its find() method by + switching from using linear search to using binary search. The + improvement is especially visible with a large number of elements. + +mdds 1.0.0 + +* all + + * introduced API versioning to ease parallel installation of API + incompatible versions. Version 1.0.0 will have an API versoin of + 1.0. + + * C++11 is now a hard requirement. + + * added API documentation via Doxygen, Sphinx and Breathe. + +* mixed_type_matrix + + * officially removed for good in favor of multi_type_matrix. + +* multi_type_vector + + * added memory usage reduction by conditionally shrinking the + capacity of the underlying vector containers. + + * added slight performance gain by revising block adjustment policy + during splitting of blocks. + +* sorted_string_map + + * fixed a bug where a non-matching key was incorrectly returned as a + matching key. + +mdds 0.12.1 + +* flat_segment_tree + + * removed construction-from-int requirement from value_type to allow + non-numeric types to be stored. + +* multi_type_vector + + * added static method advance_position() to allow incrementing or + decrementing the logical position of a position_type object: + + * position_type advance_position(const position_type& pos, int steps) + +mdds 0.12.0 + +* segment_tree + + * removed pointer requirement from value_type to allow non-pointer + type to be stored. + +* multi_type_vector + + * fixed a bug in the equality operator method. + +mdds 0.11.2 + +* multi_type_vector + + * fixed various memory leaks associated with the set() method when a + value overwrites an existing element in a managed block. + +mdds 0.11.1 + +* all + + * fixed a large number of outstanding defects reported by Coverity + Scan. + +* multi_type_vector + + * fixed 2 cases of double-free bug in the variant of swap() that + allows segmented swapping. + +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 + + * added 2 variants of release_range() that take start and end positions, + to allow releasing of elements in specified interval. One of the + variants takes iterator as a block position hint. + + * iterator release_range(size_type start_pos, size_type end_pos) + + * iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos) + + * added push_back() and push_back_empty(), to allow efficient way to + append new values to the end of the container. + + * template<typename _T> + iterator push_back(const _T& value) + + * iterator push_back_empty() + +mdds 0.10.2 + +* multi_type_vector + + * fixed a bug in transfer() that would trigger an assertion and + eventually lead to a crash. The problem occurred when a range of + data to be transferred spanned over 2 blocks and consisted of the + lower part of an upper block and the upper part of a lower block. + +mdds 0.10.1 + +* multi_type_matrix + + * added a variant of set_empty() that takes an additional length + parameter. + + * void set_empty(size_type row, size_type col, size_type length) + +mdds 0.10.0 + +* flat_segment_tree + + * significant performance improvement on build_tree() and + search_tree(), by optimizing the non-leaf node object generation + and storage to achieve better locality of reference. + +* segment_tree + + * slight performance improvement on build_tree(), as a result of the + optimization done for flat_segment_tree since these two structures + share the same tree generation code. + +* multi_type_vector + + * improved debug message on mis-matched block types (only when + MDDS_MULTI_TYPE_VECTOR_DEBUG is defined). + +mdds 0.9.1 + +* multi_type_vector + + * added several convenience methods for position objects. + + * performance improvement on setting array values. + + * added new constructor that takes an array of values as initial + element values. + +* multi_type_matrix + + * setter methods that take a position object to also return a + position object. + + * added several convenience methods for position objects. + + * added new constructor that takes an array of values as initial + element values. + +mdds 0.9.0 + +* multi_type_vector + + * added another block function template to make it easier to declare + container with 3 custom element types. + + * added two variants of release(): + + * template<typename _T> iterator + release(size_type pos, _T& value) + + * template<typename _T> iterator + release(const iterator& pos_hint, size_type pos, _T& value) + + * added a variant of release() that takes no arguments. This one + releases all elements and makes the container empty afterward. + + * added a new variant of position() that takes const_iterator as + position hint. + + * std::pair<const_iterator, size_type> + position(const const_iterator& pos_hint, size_type pos) const + + * fixed a memory leak in + + * set(size_type pos, const _T& it_begin, const _T& it_end). + + * added compile-time macro MDDS_MULTI_TYPE_VECTOR_USE_DEQUE to allow + users to specify std::deque as the underlying data array. By + default, multi_type_vector uses std::vector as the underlying data + array container. + + * added a new variant of swap() that allows partial swapping of + content with another container. + + * added static block type identifier so that the numeric block type + ID can be deduced from the block type directly. + + * value_type (which is a type of object returned when dereferencing + an iterator) now stores 'position' which is the logical position + of the first element of a block. + + * added position_type and const_position_type which are typedefs to + the return types of position() methods. + +* multi_type_matrix: + + * get_numeric(), get_boolean(), and get_string() are made more + efficient. + + * added position() method that returns a reference object to an + element (position object). + + * added variants of get_numeric(), get_boolean() and get_string() + that retrieves elements from position objects. + + * added variants of set() that sets new element values via position + objects. + +mdds 0.8.1 + +* multi_type_vector + + * fixed a bug in the erase() method where adjacent blocks of the + same type would fail to merge after the erase() call. + + * add a variant of the position() method that takes an iterator as + positional hint. Note that there is no variant of position() that + takes const_iterator. + +mdds 0.8.0 + +* all + + * added .pc file for pkg-config. + +* flat_segment_tree + + * changed the return type of search_tree from bool to + std::pair<const_iterator,bool>, to make it consistent with the + search() method. Note that this is an API-incompatible change. + +* multi_type_vector + + * added char and unsigned char types to the standard types supported + by default. + + * added position() member method that takes a logical element + position and returns a pair of block iterator where the element + resides and its offset within that block. + + * added at() static member method to the data block, which calls the + at() method of the underlying std::vector container. + + * added release() member method to allow caller to release an object + stored inside a managed block. + + * added two templates to ease creation of custom element block + functions when using one or two custom element types. + + * added transfer() member method to allow elements in a specified + range to be transferred from one container to another. When + transferring elements stored in a managed element block, the + ownership of those elements is also transferred. + +mdds 0.7.1 + +* multi_type_vector + + * fixed a bug in set_empty() where emptying a whole or partial block + would fail to merge its adjacent block(s) even when they are also + empty. + +mdds 0.7.0 + +* multi_type_vector + + * add variants of set() methods (both single- and multi-value) + insert(), set_empty() and insert_empty() methods that take an + iterator as an additional position hint parameter for block lookup + speed optimization. + + * add support for non-const iterators which allow the client code to + modify values directly from the iterators. + + * set() methods (both single- and multi-parameter variants), + set_empty(), insert() and insert_empty() methods now return + iterator that references the block to which the values are set or + inserted. + + * fixed bugs in set() method (single-parameter variant) which would + insert a new block at incorrect position. + + * fixed bugs in set() method (multi-parameter variant) which would + fail to merge neighboring blocks of identical type under certain + conditions. + +mdds 0.6.1 + +* all + + * use property files in the Visual Studio project files, to share + some of the common custom build variables across all projects. + + * various build fixes and compiler warning eliminations. + + * fixed link error with boost 1.50. + + * fixed make installer script which previously would not install + mdds/compat headers. + +* flat_segment_tree + + * fixed a bug in its iterator implementation, which previously would + always treat the last valid position before the end position as + the end position. This fix affects both in const_iterator and + const_reverse_iterator. + +mdds 0.6.0 + +* all + + * added MSVS Solution file, to make it easier to build unit test + programs on Windows. + +* mixed_type_matrix + + * improved performance of size() method by caching it. + +* multi_type_vector (new) + + * new data structure to support efficient storage of data of different + types. + +* multi_type_matrix (new) + + * new data structure to eventually replace mixed_type_matrix. It uses + multi_type_vector as its backend storage. + +mdds 0.5.4 + +* segment_tree + + * fixed build breakage, to allow it to be buildable when UNIT_TEST + is not defined. + + * fixed a crasher with MSVC when comparing iterators of empty + search_result instances. + +* point_quad_tree + + * fixed a bug where de-referencing copied search_result iterators + would return an uninitialized node data. + +mdds 0.5.3 + +* mixed_type_matrix + + * re-implemented the filled storage for better performance, with two + separate implementations for zero and emtpy matrix types. The + newer implementation should improve object creation time + considerably. + +mdds 0.5.2 + +* flat_segment_tree + + * fixed a crash on assignment by properly implementing assignment + operator(). + + * fixed several bugs in shift_right(): + + * shifting of all existing nodes was not handled properly. + + * leaf nodes were not properly linked under certain conditions. + + * shifting with skip node option was not properly skipping the + node at insertion position when the insertion position was at + the leftmost node. + + * implemented min_key(), max_key(), default_value(), clear() and + swap(). + + * fixed a bug in operator==() where two different containers were + incorrectly evaluated to be equal. + + * added quickcheck test code. + +mdds 0.5.1 + + * fixed build issues on Windows, using MSVC compilers. + +mdds 0.5.0 + + * flat_segment_tree's search methods now return a std::pair of + const_iterator and bool, instead of just returning bool. + + * fixed a weird enum value mis-handling with mixed_type_matrix when + compiled with MSVC++. + + * added new insert() method to flat_segment_tree that takes a + positional hint in order to speed up insertion speed. Also, all + three insert() methods now return the start position of the + segment that an inserted segment belongs to. + + * slight performance improvement on the insert methods of + flat_segment_tree. + + * slight performance improvement on the iterators of + flat_segment_tree. + + * re-organized the structure of flat_segment_tree to split it into + multiple headers. + + * properly support prefix, docdir, includedir configure options. + + * support DESTDIR environment variable for make install. + +mdds 0.4.0 + + * implemented mixed_type_matrix. + +mdds 0.3.1 + + * added support for boost::unordered_map (boost) and std::hash_map + (stlport) in addition to C++0x's std::unordered_map. + +mdds 0.3.0 + + * implemented point_quad_tree. + +mdds 0.2.1 + + * added example files on how to use these data structures. + + * fixed a bug in segment_tree::search_result object, to make it work + with empty result set. + + * fixed segment_tree to make it really usable outside of unit test + code. + +mdds 0.2.0 + + * other general performance improvements. + + * lots of code cleanups. + + * support for search result iterator in segment_tree and + rectangle_set, for better search performance. + + * implemented rectnagle_set. + + * fixed lots of bugs in the segment_tree implementation. + +mdds 0.1.2 + + * implemented segment_tree. + + * node_base class is now without virtual methods to avoid vtable + generation. |