Невозможно вставить более 256 узлов в пользовательское дерево

Я застрял на этом довольно давно и даже протестировал проблему между 64-битной версией gcc в Ubuntu и 32-битной версией gcc в Windows (MinGW).

Каждый раз, когда я вставляю более 256 узлов в двоичное дерево (?), Он перестает считать количество узлов. Я все еще могу получить доступ ко всем моим данным. У меня есть ощущение, что это как-то связано с тем, как я настраиваю свою структуру, используя символы для получения каждого бита каждого байта, но я не знаю, как это исправить.

В этом заголовке, У меня есть структура и некоторые настройки функций, которые позволяют мне получить индивидуальный бит объекта.

Это фактическая реализация дерева. Чтобы найти, где хранить каждый объект, дерево выполняет итерацию каждого байта ключа, а затем повторяет итерацию каждого бита этих байтов. Функция «итерации» — вот что доставляет мне наибольшую сложность; Я понятия не имею, почему, но как только 256 узлов заполняются данными, моя структура перестает считать, а затем начинает заменять все предыдущие данные. Я считаю, что это как-то связано с тем фактом, что один символ может содержать только 0-256, но я не понимаю, где это может быть проблемой. Поскольку местоположение каждого узла определяется отдельными битами ключа, трудно определить, почему в дерево можно поместить только 256 элементов.

URL моей тестовой программы находится внизу поста. ТАК не позволит мне опубликовать более 2 в данный момент. Я хотел бы сделать это в ближайшее время, поэтому любая помощь будет принята с благодарностью.

Редактировать:
Просто, чтобы упростить задачу, это структура, которая дает мне отдельный бит байта, а также вспомогательную функцию:

struct bitMask {
char b1 : 1;
char b2 : 1;
char b3 : 1;
char b4 : 1;
char b5 : 1;
char b6 : 1;
char b7 : 1;
char b8 : 1;

char operator[] ( unsigned i ) const {
switch( i ) {
case 0 : return b1;
case 1 : return b2;
case 2 : return b3;
case 3 : return b4;
case 4 : return b5;
case 5 : return b6;
case 6 : return b7;
case 7 : return b8;
}
return 0; // Avoiding a compiler error
}
};

/******************************************************************************
*  Functions shared between tree-type objects
******************************************************************************/
namespace treeShared {

// Function to retrieve the next set of bits at the pointer "key"template <typename key_t>
inline const bitMask* getKeyByte( const key_t* key, unsigned iter );

/* template specializations */
template <>
inline const bitMask* getKeyByte( const char*, unsigned );

template <>
inline const bitMask* getKeyByte( const wchar_t*, unsigned );

template <>
inline const bitMask* getKeyByte( const char16_t*, unsigned );

template <>
inline const bitMask* getKeyByte( const char32_t*, unsigned );

} // end treeShared namespace

/*
* Tree Bit Mask Function
*/
template <typename key_t>
inline const bitMask* treeShared::getKeyByte( const key_t* k, unsigned iter ) {
return (iter < sizeof( key_t ))
? reinterpret_cast< const bitMask* >( k+iter )
: nullptr;
}

/*
* Tree Bit Mask Specializations
*/
template <>
inline const bitMask* treeShared::getKeyByte( const char* str, unsigned iter ) {
return (str[ iter ] != '\0')
? reinterpret_cast< const bitMask* >( str+iter )
: nullptr;
}

template <>
inline const bitMask* treeShared::getKeyByte( const wchar_t* str, unsigned iter ) {
return (str[ iter ] != '\0')
? reinterpret_cast< const bitMask* >( str+iter )
: nullptr;
}

template <>
inline const bitMask* treeShared::getKeyByte( const char16_t* str, unsigned iter ) {
return (str[ iter ] != '\0')
? reinterpret_cast< const bitMask* >( str+iter )
: nullptr;
}

template <>
inline const bitMask* treeShared::getKeyByte( const char32_t* str, unsigned iter ) {
return (str[ iter ] != '\0')
? reinterpret_cast< const bitMask* >( str+iter )
: nullptr;
}

И вот класс дерева:

template <typename data_t>
struct bTreeNode {
data_t*     data        = nullptr;
bTreeNode*  subNodes    = nullptr;

~bTreeNode() {
delete data;
delete [] subNodes;

data = nullptr;
subNodes = nullptr;
}
};

/******************************************************************************
*  Binary-Tree Structure Setup
******************************************************************************/
template <typename key_t, typename data_t>
class bTree {

enum node_dir : unsigned {
BNODE_LEFT   = 0,
BNODE_RIGHT  = 1,
BNODE_MAX
};

protected:
bTreeNode<data_t>   head;
unsigned            numNodes = 0;

private:
bTreeNode<data_t>* iterate( const key_t* k, bool createNodes );

public:
~bTree() {}

// STL-Map behavior
data_t&         operator [] ( const key_t& k );

void            push        ( const key_t& k, const data_t& d );
void            pop         ( const key_t& k );
bool            hasData     ( const key_t& k );
const data_t*   getData     ( const key_t& k );
unsigned        size        () const { return numNodes; }
void            clear       ();
};/*
* Binary-Tree -- Element iteration
*/
template <typename key_t, typename data_t>
bTreeNode<data_t>* bTree<key_t, data_t>::iterate( const key_t* k, bool createNodes ) {

node_dir            dir;
unsigned            bytePos     = 0;
bTreeNode<data_t>*  bNodeIter   = &head;
const bitMask*      byteIter    = nullptr;

while ( byteIter = treeShared::getKeyByte< key_t >( k, bytePos++ ) ) {

for ( int currBit = 0; currBit < HL_BITS_PER_BYTE; ++currBit ) {

// compare the bits of each byte in k
dir = byteIter->operator []( currBit ) ? BNODE_LEFT : BNODE_RIGHT;

// check to see if a new bTreeNode needs to be made
if ( !bNodeIter->subNodes ) {
if ( createNodes ) {
// create and initialize the upcoming sub bTreeNode
bNodeIter->subNodes = new bTreeNode<data_t>[ BNODE_MAX ];
}
else {
return nullptr;
}
}

// move to the next bTreeNode
bNodeIter = &(bNodeIter->subNodes[ dir ]);
}
}

return bNodeIter;
}

/*
* Binary-Tree -- Destructor
*/
template <typename key_t, typename data_t>
void bTree<key_t, data_t>::clear() {
delete head.data;
delete [] head.subNodes;

head.data = nullptr;
head.subNodes = nullptr;
numNodes = 0;
}

/*
* Binary-Tree -- Array Subscript operators
*/
template <typename key_t, typename data_t>
data_t& bTree<key_t, data_t>::operator []( const key_t& k ) {
bTreeNode<data_t>* iter = iterate( &k, true );

if ( !iter->data ) {
iter->data = new data_t();
++numNodes;
}

return *iter->data;
}

/*
* Binary-Tree -- Push
* Push a data element to the tree using a key
*/
template <typename key_t, typename data_t>
void bTree<key_t, data_t>::push( const key_t& k, const data_t& d ) {
bTreeNode<data_t>* iter = iterate( &k, true );

if ( !iter->data ) {
iter->data = new data_t( d );
++numNodes;
}
else {
*iter->data = d;
}
}

/*
* Binary-Tree -- Pop
* Remove whichever element lies at the key
*/
template <typename key_t, typename data_t>
void bTree<key_t, data_t>::pop( const key_t& k ) {
bTreeNode<data_t>* iter = iterate( &k, false );

if ( !iter || !iter->data )
return;

delete iter->data;
iter->data = nullptr;
--numNodes;
}

/*
* Binary-Tree -- Has Data
* Return true if there is a data element at the key
*/
template <typename key_t, typename data_t>
bool bTree<key_t, data_t>::hasData( const key_t& k ) {
bTreeNode<data_t>* iter = iterate( &k, false );

return iter && ( iter->data != nullptr );
}

/*
* Binary-Tree -- Push
* Return a pointer to the data that lies at a key
* Returns a nullptr if no data exists
*/
template <typename key_t, typename data_t>
const data_t* bTree<key_t, data_t>::getData( const key_t& k ) {
bTreeNode<data_t>* iter = iterate( &k, false );

if ( !iter )
return nullptr;

return iter->data;
}

pastebin.com/8MZ0TMpj

0

Решение

template <typename key_t>
inline const bitMask* treeShared::getKeyByte( const key_t* k, unsigned iter ) {
return (iter < sizeof( key_t ))
? reinterpret_cast< const bitMask* >( k+iter )
: nullptr;
}

Это не делает то, что вы, кажется, думаете. (k + iter) не извлекает итеральный байт k, но i-й элемент массива key_t [] указывает на k. Другими словами, k + iter продвигает указатель на байты iter * sizeof (key_t), а не на байты iter.

Формально этот код демонстрирует неопределенное поведение, превышая границы массива. Практически говоря, ваша программа использует только один байт ключа, а затем sizeof (key_t) -1 случайный байт, который просто оказывается в памяти над этим ключом. Вот почему вы фактически ограничены 8 битами состояния.

Кроме того, ваш reinterpret_cast также демонстрирует неопределенное поведение, формально говоря. Единственное законное использование для указателя, полученного с помощью reinterpret_cast, — это reinterpret_cast его обратно к исходному типу. Это не является непосредственной причиной вашей проблемы.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]