Unable to insert more than 256 nodes into a custom tree

Question

I've been stuck on this for quite some time now and have even tested the issue between a 64-bit version of gcc on Ubuntu as welll as a 32-bit gcc on Windows (MinGW).

Any time I insert more than 256 nodes into a binary-tree(?), it stops counting the number of nodes. I can still access all of my data. I have a feeling that it has something to do with the way I have my structure setup, by using chars to acquire each bit of each byte, but I have no idea how to fix it.

In this header, I have a structure and some functions setup which allows me to acquire an individual bit of an object.

This is the actual tree implementation. In order to find where to store each object, the tree iterates through each byte of a key, then iterates again through each bit of those bytes. The "iterate" function is what is giving me the most difficulty though; I have no idea why, but once 256 nodes become filled with data, my structure stops counting further, then begins to replace all previous data. I believe this has something to do with the fact that a single char can only hold 0-256, but I can't see where this would be an issue. Since the location of each node is determined by the individual bits of the key, it's hard to determine why only 256 items can be placed into the tree.

The URL to my test program is at the bottom of the post. SO won't let me post more than 2 at the moment. I would like to get this done soon, so any help would be greatly appreciated.

Edit: Just to make things easier, this is the structure that gives me the individual bit of a byte, as well as a helper function:

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;
}

And here is the tree class:

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

Answer 1

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;
}

This doesn't do what you seem to think it does. (k+iter) doesn't retrieve the iter'th byte of k, but the iter'th element of the key_t[] array pointed to by k. In other words, k+iter advances the pointer by iter*sizeof(key_t) bytes, not by iter bytes.

Formally, this code exhibits undefined behavior, by overrunning array bounds. Practically speaking, your program uses just a single byte of the key, and then sizeof(key_t)-1 random bytes that just happen to sit in memory above that key. That's why you are effectively limited to 8 bits of state.

In addition, your reinterpret_cast also exhibits undefined behavior, formally speaking. The only legal use for a pointer obtained with reinterpret_cast is to reinterpret_cast it right back to the original type. This is not the immediate cause of your problem though.