<commit_before>/* This file is part of VoltDB.
 * Copyright (C) 2008-2012 VoltDB Inc.
 *
 * VoltDB is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * VoltDB is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with VoltDB.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef COMPACTINGMAP_H_
#define COMPACTINGMAP_H_

#include <cstdlib>
#include <utility>
#include <cassert>
#include "ContiguousAllocator.h"

namespace voltdb {

/**
 * Basic Red-Black tree that is based on the pseudo-code from
 * Cormen's Algorithms book with a twist.
 *
 * The interface is stl::map-like, but is a loose subset with a few
 * simplifications and no STL inheritence compatibility.
 *
 * The twist is that the memory storage for all nodes is tightly
 * packed into a buffer chain (CongtiguousAllocator). When nodes
 * are removed, other nodes are moved into the holes to keep
 * the memory contiguous. This prevents fragmenting of memory on
 * the heap (or in a pool) and allows deletion to return memory
 * to the operating system.
 *
 * Three issues to be aware of:
 * 1. Nodes can be moved in memory randomly. This currently calls
 *    copy constructors.
 * 2. Key types and Value types may not have their destructors
 *    called in all scenarios.
 * 3. Iterators are invalidated by any table mutation. Further,
 *    use of an iterator after a delete or insert may work fine
 *    or may crash. This could lead to a difficult to debug
 *    problem so please be aware of this issue.
 * 4. Iterators have no overloaded operators yet. You can't
 *    compare them using ==. Compare keys and values instead.
 *
 * Some or all of these issues may be fixed in the future.
 *
 */

template<typename Key, typename Data, typename Compare>
class CompactingMap {
protected:
    static const char RED = 0;
    static const char BLACK = 1;

    struct TreeNode {
        Key key;
        Data value;
        TreeNode *parent;
        TreeNode *left;
        TreeNode *right;
        char color;
    };

    int64_t m_count;
    TreeNode *m_root;
    ContiguousAllocator m_allocator;
    bool m_unique;

    // rather than NULL, most tree pointers that don't point
    // to nodes point to NIL. This is taken from Cormen and
    // makes some aspects easier to deal with.
    TreeNode NIL;

    // templated comparison function object
    // follows STL conventions
    Compare m_comper;

public:

    class iterator {
        friend class CompactingMap<Key, Data, Compare>;
    protected:
        const CompactingMap *m_map;
        TreeNode *m_node;
        iterator(const CompactingMap *m, TreeNode* x) : m_map(m), m_node(x) {}
    public:
        iterator() : m_map(NULL), m_node(NULL) {}
        iterator(const iterator &iter) : m_map(iter.m_map), m_node(iter.m_node) {}
        Key &key() const { return m_node->key; }
        Data &value() const { return m_node->value; }
        void setValue(const Data &value) { m_node->value = value; }
        void moveNext() { m_node = m_map->successor(m_node); }
        void movePrev() { m_node = m_map->predecessor(m_node); }
        bool isEnd() const { return ((!m_map) || (m_node == &(m_map->NIL))); }
        bool equals(iterator &iter) {
            if (isEnd()) return iter.isEnd();
            return m_node == iter.m_node;
        }
    };

    CompactingMap(bool unique, Compare comper);
    ~CompactingMap();

    bool insert(std::pair<Key, Data> value);
    bool erase(const Key &key);
    bool erase(iterator &iter);
    iterator find(const Key &key) { return iterator(this, lookup(key)); }
    int64_t size() const { return m_count; }
    iterator begin() const {
        if (!m_count) return iterator();
        return iterator(this, minimum(m_root));
    }
    iterator rbegin() const {
        if (!m_count) return iterator();
        return iterator(this, maximum(m_root));
    }

    iterator lowerBound(const Key &key);
    iterator upperBound(const Key &key);

    std::pair<iterator, iterator> equalRange(const Key &key);

    size_t bytesAllocated() const { return m_allocator.bytesAllocated(); }

    /**
     * For debugging: verify the RB-tree constraints are met. SLOW.
     */
    bool verify() const;

protected:
    // main internal functions
    void erase(TreeNode *z);
    TreeNode *lookup(const Key &key);

    // static for iterator use
    TreeNode *minimum(const TreeNode *subRoot) const;
    TreeNode *maximum(const TreeNode *subRoot) const;
    TreeNode *successor(const TreeNode *x) const;
    TreeNode *predecessor(const TreeNode *x) const;

    // sub functions to make the magic happen
    void leftRotate(TreeNode *x);
    void rightRotate(TreeNode *x);
    void insertFixup(TreeNode *z);
    void deleteFixup(TreeNode *x);
    void fragmentFixup(TreeNode *x);

    // debugging and testing methods
    bool isReachableNode(const TreeNode* start, const TreeNode *dest) const;
    int verify(const TreeNode *n) const;
    int fullCount(const TreeNode *n) const;
};

template<typename Key, typename Data, typename Compare>
CompactingMap<Key, Data, Compare>::CompactingMap(bool unique, Compare comper)
    : m_count(0),
      m_root(&NIL),
      m_allocator(sizeof(TreeNode), 10000),
      m_unique(unique),
      m_comper(comper)
{
    NIL.left = NIL.right = NIL.parent = &NIL;
    NIL.color = BLACK;
}

template<typename Key, typename Data, typename Compare>
CompactingMap<Key, Data, Compare>::~CompactingMap() {
    iterator iter = begin();
    while (!iter.isEnd()) {
        iter.key().~Key();
        iter.value().~Data();
        iter.moveNext();
    }
}

template<typename Key, typename Data, typename Compare>
bool CompactingMap<Key, Data, Compare>::erase(const Key &key) {
    TreeNode *node = lookup(key);
    if (node == &NIL) return false;
    erase(node);
    return true;
}

template<typename Key, typename Data, typename Compare>
bool CompactingMap<Key, Data, Compare>::erase(iterator &iter) {
    assert(iter.m_node != &NIL);
    erase(iter.m_node);
    return true;
}

template<typename Key, typename Data, typename Compare>
bool CompactingMap<Key, Data, Compare>::insert(std::pair<Key, Data> value) {
    if (m_root != &NIL) {
        // find a place to put the new node
        TreeNode *y = &NIL;
        TreeNode *x = m_root;
        while (x != &NIL) {
            y = x;
            int cmp = m_comper(value.first, x->key);
            if (cmp < 0) x = x->left;
            else if (m_unique) {
                if (cmp == 0) return false;
                else x = x->right;
            }
            else x = x->right;
        }

        // create a new node
        void *memory = m_allocator.alloc();
        assert(memory);
        // placement new
        TreeNode *z = new(memory) TreeNode();
        z->key = value.first;
        z->value = value.second;
        z->left = z->right = &NIL;
        z->parent = y;
        z->color = RED;

        // stitch it in
        if (y == &NIL) m_root = z;
        else if (m_comper(z->key, y->key) < 0) y->left = z;
        else y->right = z;

        // rotate tree to balance if needed
        insertFixup(z);
    }
    else {
        // create a new node as root
        void *memory = m_allocator.alloc();
        assert(memory);
        // placement new
        TreeNode *z = new(memory) TreeNode();
        z->key = value.first;
        z->value = value.second;
        z->left = z->right = &NIL;
        z->parent = &NIL;
        z->color = BLACK;

        // make it root
        m_root = z;
    }
    m_count++;
    assert(m_allocator.count() == m_count);
    return true;
}

template<typename Key, typename Data, typename Compare>
typename CompactingMap<Key, Data, Compare>::iterator CompactingMap<Key, Data, Compare>::lowerBound(const Key &key) {
    TreeNode *x = m_root;
    TreeNode *y = &NIL;
    while (x != &NIL) {
        int cmp = m_comper(x->key, key);
        if (cmp < 0) {
            x = x->right;
        }
        else {
            y = x;
            x = x->left;
        }
    }
    return iterator(this, y);
}

template<typename Key, typename Data, typename Compare>
typename CompactingMap<Key, Data, Compare>::iterator CompactingMap<Key, Data, Compare>::upperBound(const Key &key) {<commit_msg>Add rank filed into compactingMap tree node<commit_after>/* This file is part of VoltDB.
 * Copyright (C) 2008-2012 VoltDB Inc.
 *
 * VoltDB is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * VoltDB is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with VoltDB.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef COMPACTINGMAP_H_
#define COMPACTINGMAP_H_

#include <cstdlib>
#include <utility>
#include <cassert>
#include "ContiguousAllocator.h"

namespace voltdb {

/**
 * Basic Red-Black tree that is based on the pseudo-code from
 * Cormen's Algorithms book with a twist.
 *
 * The interface is stl::map-like, but is a loose subset with a few
 * simplifications and no STL inheritence compatibility.
 *
 * The twist is that the memory storage for all nodes is tightly
 * packed into a buffer chain (CongtiguousAllocator). When nodes
 * are removed, other nodes are moved into the holes to keep
 * the memory contiguous. This prevents fragmenting of memory on
 * the heap (or in a pool) and allows deletion to return memory
 * to the operating system.
 *
 * Three issues to be aware of:
 * 1. Nodes can be moved in memory randomly. This currently calls
 *    copy constructors.
 * 2. Key types and Value types may not have their destructors
 *    called in all scenarios.
 * 3. Iterators are invalidated by any table mutation. Further,
 *    use of an iterator after a delete or insert may work fine
 *    or may crash. This could lead to a difficult to debug
 *    problem so please be aware of this issue.
 * 4. Iterators have no overloaded operators yet. You can't
 *    compare them using ==. Compare keys and values instead.
 *
 * Some or all of these issues may be fixed in the future.
 *
 */

template<typename Key, typename Data, typename Compare>
class CompactingMap {
protected:
    static const char RED = 0;
    static const char BLACK = 1;

    struct TreeNode {
        Key key;
        Data value;
        TreeNode *parent;
        TreeNode *left;
        TreeNode *right;
        int32_t rank;
        char color;
    };

    int64_t m_count;
    TreeNode *m_root;
    ContiguousAllocator m_allocator;
    bool m_unique;

    // rather than NULL, most tree pointers that don't point
    // to nodes point to NIL. This is taken from Cormen and
    // makes some aspects easier to deal with.
    TreeNode NIL;

    // templated comparison function object
    // follows STL conventions
    Compare m_comper;

public:

    class iterator {
        friend class CompactingMap<Key, Data, Compare>;
    protected:
        const CompactingMap *m_map;
        TreeNode *m_node;
        iterator(const CompactingMap *m, TreeNode* x) : m_map(m), m_node(x) {}
    public:
        iterator() : m_map(NULL), m_node(NULL) {}
        iterator(const iterator &iter) : m_map(iter.m_map), m_node(iter.m_node) {}
        Key &key() const { return m_node->key; }
        Data &value() const { return m_node->value; }
        void setValue(const Data &value) { m_node->value = value; }
        void moveNext() { m_node = m_map->successor(m_node); }
        void movePrev() { m_node = m_map->predecessor(m_node); }
        bool isEnd() const { return ((!m_map) || (m_node == &(m_map->NIL))); }
        bool equals(iterator &iter) {
            if (isEnd()) return iter.isEnd();
            return m_node == iter.m_node;
        }
    };

    CompactingMap(bool unique, Compare comper);
    ~CompactingMap();

    bool insert(std::pair<Key, Data> value);
    bool erase(const Key &key);
    bool erase(iterator &iter);
    iterator find(const Key &key) { return iterator(this, lookup(key)); }
    int64_t size() const { return m_count; }
    iterator begin() const {
        if (!m_count) return iterator();
        return iterator(this, minimum(m_root));
    }
    iterator rbegin() const {
        if (!m_count) return iterator();
        return iterator(this, maximum(m_root));
    }

    iterator lowerBound(const Key &key);
    iterator upperBound(const Key &key);

    std::pair<iterator, iterator> equalRange(const Key &key);

    size_t bytesAllocated() const { return m_allocator.bytesAllocated(); }

    /**
     * For debugging: verify the RB-tree constraints are met. SLOW.
     */
    bool verify() const;

protected:
    // main internal functions
    void erase(TreeNode *z);
    TreeNode *lookup(const Key &key);

    // static for iterator use
    TreeNode *minimum(const TreeNode *subRoot) const;
    TreeNode *maximum(const TreeNode *subRoot) const;
    TreeNode *successor(const TreeNode *x) const;
    TreeNode *predecessor(const TreeNode *x) const;

    // sub functions to make the magic happen
    void leftRotate(TreeNode *x);
    void rightRotate(TreeNode *x);
    void insertFixup(TreeNode *z);
    void deleteFixup(TreeNode *x);
    void fragmentFixup(TreeNode *x);

    // debugging and testing methods
    bool isReachableNode(const TreeNode* start, const TreeNode *dest) const;
    int verify(const TreeNode *n) const;
    int fullCount(const TreeNode *n) const;
};

template<typename Key, typename Data, typename Compare>
CompactingMap<Key, Data, Compare>::CompactingMap(bool unique, Compare comper)
    : m_count(0),
      m_root(&NIL),
      m_allocator(sizeof(TreeNode), 10000),
      m_unique(unique),
      m_comper(comper)
{
    NIL.left = NIL.right = NIL.parent = &NIL;
    NIL.color = BLACK;
    NIL.rank = 0;
}

template<typename Key, typename Data, typename Compare>
CompactingMap<Key, Data, Compare>::~CompactingMap() {
    iterator iter = begin();
    while (!iter.isEnd()) {
        iter.key().~Key();
        iter.value().~Data();
        iter.moveNext();
    }
}

template<typename Key, typename Data, typename Compare>
bool CompactingMap<Key, Data, Compare>::erase(const Key &key) {
    TreeNode *node = lookup(key);
    if (node == &NIL) return false;
    erase(node);
    return true;
}

template<typename Key, typename Data, typename Compare>
bool CompactingMap<Key, Data, Compare>::erase(iterator &iter) {
    assert(iter.m_node != &NIL);
    erase(iter.m_node);
    return true;
}

template<typename Key, typename Data, typename Compare>
bool CompactingMap<Key, Data, Compare>::insert(std::pair<Key, Data> value) {
    if (m_root != &NIL) {
        // find a place to put the new node
        TreeNode *y = &NIL;
        TreeNode *x = m_root;
        while (x != &NIL) {
            y = x;
            int cmp = m_comper(value.first, x->key);
            if (cmp < 0) {
            	x->rank++;
            	x = x->left;
            }
            else if (m_unique) {
                if (cmp == 0) return false;
                else x = x->right;
            }
            else x = x->right;
        }

        // create a new node
        void *memory = m_allocator.alloc();
        assert(memory);
        // placement new
        TreeNode *z = new(memory) TreeNode();
        z->key = value.first;
        z->value = value.second;
        z->left = z->right = &NIL;
        z->parent = y;
        z->color = RED;

        // stitch it in
        if (y == &NIL) m_root = z;
        else if (m_comper(z->key, y->key) < 0) y->left = z;
        else y->right = z;

        // rotate tree to balance if needed
        insertFixup(z);
    }
    else {
        // create a new node as root
        void *memory = m_allocator.alloc();
        assert(memory);
        // placement new
        TreeNode *z = new(memory) TreeNode();
        z->key = value.first;
        z->value = value.second;
        z->left = z->right = &NIL;
        z->parent = &NIL;
        z->color = BLACK;
        z->rank = 0;

        // make it root
        m_root = z;
    }
    m_count++;
    assert(m_allocator.count() == m_count);
    return true;
}

template<typename Key, typename Data, typename Compare>
typename CompactingMap<Key, Data, Compare>::iterator CompactingMap<Key, Data, Compare>::lowerBound(const Key &key) {
    TreeNode *x = m_root;
    TreeNode *y = &NIL;
    while (x != &NIL) {
        int cmp = m_comper(x->key, key);
        if (cmp < 0) {
            x = x->right;
        }
        else {
            y = x;
            x = x->left;
        }
    }
    return iterator(this, y);
}

template<typename Key, typename Data, typename Compare>
typename CompactingMap<Key, Data, Compare>::iterator CompactingMap<Key, Data, Compare>::upperBound(const Key &key) {
{'fraction_non_alphanumeric': 0.10964659836537355, 'fraction_numerical': 0.0035685507079544145, 'mean_word_length': 2.6235662148070906, 'pattern_counts': {'":': 0, '<': 59, '<?xml version=': 0, '>': 113, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4991125', 'n_tokens_mistral': 5457, 'n_tokens_neox': 5215, 'n_words': 1819}