ned14
Few nedtrie issues
Hi, I found few new nedtrie issues on Linux. Code was compiled using gcc 4.4.7. Most of them are in C++ code. I used it in our testing tool, and looks that it works quite stable.
- nedtrie.h header does not contain protection against multiple inclusion (ifndef/define/endif).
- Following code fails one of internal nedtrie asserts:
#define DEBUG 1
#include "nedtrie.h"
#include <string.h>
#include <assert.h>
struct IndexStruct
{
int index;
explicit IndexStruct(int index) : index(index) {}
};
struct IndexStructKey : public std::unary_function<IndexStruct*, size_t>
{
size_t operator()(const IndexStruct *RESTRICT v) const
{ return v->index; }
};
typedef nedtries::trie_map<size_t, IndexStruct*, IndexStructKey> IndexTrie;
#define INDEX_COUNT 40
int main()
{
IndexTrie trie;
for (int n = 0; n < INDEX_COUNT; ++n)
trie.insert(new IndexStruct(n));
return 0;
}
Compiled using this command:
g++ -o test2 test2.cc -O2 -g -Wno-invalid-offsetof -m64 -fno-strict-aliasing
Failed assert details:
test2: nedtrie.h:1459: void nedtries::triecheckvalidity(trietype*) [with trietype = nedtries::trie_map_head<nedtries::trie_maptype<long unsigned int, IndexStruct*, IndexStructKey, std::_List_iterator<long unsigned int> > >, type = nedtries::trie_maptype<long unsigned int, IndexStruct*, IndexStructKey, std::_List_iterator<long unsigned int> >, long unsigned int fieldoffset = 16ul, size_t (* keyfunct)(const type*) = nedtries::intern::to_Ckeyfunct [with keyfunct_ = IndexStructKey, mapvaluetype = nedtries::trie_maptype<long unsigned int, IndexStruct*, IndexStructKey, std::_List_iterator<long unsigned int> >]]: Assertion `((((size_t)-1)<<bitidx) & nodekey)==((size_t) 1<<bitidx)' failed.
Program received signal SIGABRT, Aborted.
0x0000003922a32625 in raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
64 return INLINE_SYSCALL (tgkill, 3, pid, selftid, sig);
Missing separate debuginfos, use: debuginfo-install libgcc-4.4.7-11.el6.x86_64 libstdc++-4.4.7-11.el6.x86_64
(gdb) bt
#0 0x0000003922a32625 in raise (sig=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
#1 0x0000003922a33e05 in abort () at abort.c:92
#2 0x0000003922a2b74e in __assert_fail_base (fmt=<value optimized out>, assertion=0x401820 "((((size_t)-1)<<bitidx) & nodekey)==((size_t) 1<<bitidx)",
file=0x4015d0 "nedtrie.h", line=<value optimized out>, function=<value optimized out>) at assert.c:96
#3 0x0000003922a2b810 in __assert_fail (assertion=0x401820 "((((size_t)-1)<<bitidx) & nodekey)==((size_t) 1<<bitidx)", file=0x4015d0 "nedtrie.h",
line=1459,
function=0x401e40 "void nedtries::triecheckvalidity(trietype*) [with trietype = nedtries::trie_map_head<nedtries::trie_maptype<long unsigned int, IndexStruct*, IndexStructKey, std::_List_iterator<long unsigned int> > >,"...) at assert.c:105
#4 0x0000000000401267 in nedtries::triecheckvalidity<nedtries::trie_map_head<nedtries::trie_maptype<long unsigned int, IndexStruct*, IndexStructKey, std::_List_iterator<long unsigned int> > >, nedtries::trie_maptype<long unsigned int, IndexStruct*, IndexStructKey, std::_List_iterator<long unsigned int> >, 16ul, nedtries::intern::to_Ckeyfunct [with keyfunct_ = IndexStructKey, mapvaluetype = nedtries::trie_maptype<long unsigned int, IndexStruct*, IndexStructKey, std::_List_iterator<long unsigned int> >]>(nedtries::trie_map_head<nedtries::trie_maptype<unsigned long, IndexStruct*, IndexStructKey, std::_List_iterator<unsigned long> > > *) (head=0x7fffffffdcb0) at nedtrie.h:1459
#5 0x0000000000400859 in triehead_insert () at nedtrie.h:1915
#6 insert () at nedtrie.h:2031
#7 main () at test2.cc:35
- Please add assert() checks to make sure that dereferenced or incremented iterator is not equal end().
- When new element is added using insert() and has the same key as existing one, something strange happens. My testing tool executed code like below. During debugging I found that code tried to insert element with key = 0 twice, and later it was able to get both values as described in comments below (I checked addresses of returned structures). However when I tried to write this short code which reproduces this scenario, it crashed when dereferencing it2. Not sure why, my testing tool searches trie multiple times too, maybe this is important here.
BTW, according to http://www.cplusplus.com/reference/map/map/insert/ std::map::insert() does not insert element nor replace existing one in such scenario. Maybe nedtrie should work this way this too?
inline IndexStruct* remove(IndexTrie& trie, int n)
{
IndexTrie::iterator it = trie.find(n);
assert (it != trie.end());
trie.erase(it);
}
void test()
{
IndexTrie trie2;
IndexTrie::iterator it2;
trie2.insert(new IndexStruct(0)); // element 1
for (int n = 80; n <= 99; ++n)
trie2.insert(new IndexStruct(n));
remove(trie2, 80);
trie2.insert(new IndexStruct(0)); // element 2
remove(trie2, 0); // this removes element 2
trie2.insert(new IndexStruct(80));
remove(trie2, 80);
it2 = trie2.find(0); // this returns element 1
++it2; // SEGFAULT here
}
Thanks for the report. Especially that it's missing header guards, I am astonished I didn't notice that before.
I am unwilling to fix the C++ STL container side of things though. In the docs I mention the STL container implementation is hacked together and you should avoid it. I really mean it - you shouldn't use that STL container implementation in any production code.
I am strongly considering purging that STL container implementation in fact from the source code and leave nedtries be a straightforward C macro library.
What about another approach - remove current C++ STL code, and create new one from scratch which will be a simple wrapper around C API?
What about another approach - remove current C++ STL code, and create new one from scratch which will be a simple wrapper around C API?
That's a non-trivial amount of work. I'd estimate approximately 100-150 hours to make bitwise tries available to Boost.Intrusive (http://www.boost.org/doc/libs/1_58_0/doc/html/intrusive.html) with full validation suite. My rate would be €75/hour for this kind of work.
Alternatively, a donated implementation is welcome. It would need to be STL quality i.e. full validation and conformance test suite. I'd suggest looking into contributing it to Eric's Ranges (https://github.com/ericniebler/range-v3) as he's effectively architecting the new STL for C++ 1z so any implementation would have the most value if contributed there. I'm sure Eric would be more than happy for such a contribution.
Let me know if you're interested in either option.
No, thanks :) We will stick to current version.
BTW, why estimate is so high? In the past I wrote simple STL-compatible wrapper for our C list code plus simple test for it in one work day.
It's easy to write something which looks a bit like a stl container. The conformance suite alone with exception safety testing etc would take 50 hours on its own. You would need complexity testing I.e. how many opcodes are generated per common sequence of operations. You would need benchmarking. And you would need full documentation with complexity guarantees and pre and post conditions per api. That's the stuff which takes the time, but you get a very high quality ready for standardisation outcome.
I see. Such scope of work definitely needs more time. I had simple thin wrapper in mind in my post above.