datatype/RBTree.hh
// Insert key and empty value if key does not exist 
// If key exists, then add a read of the item version and return the node
// return value is a reference to the found or inserted node 
Insert key and empty value if key does not exist
If key exists, then add a read of the item version and return the node
return value is a reference to the found or inserted node
Insert key and empty value if key does not exist If key exists then add a read of the item version and return the node return value is a reference to the found or inserted node
inline wrapper_type* insert(const K& key) {
        rbwrapper<rbpair<K, T>> node( rbpair<K, T>(key, T()) );
        auto results = this->find_or_insert(node);
        wrapper_type* x = std::get<0>(results);
        Version ver = std::get<1>(results);
        bool found = std::get<2>(results);
        boundaries_type& boundaries = std::get<3>(results);
        node_info_type& pinfo = std::get<4>(results);
        wrapper_type* p = std::get<0>(pinfo);
        if (!found) {
#if DEBUG
            stats_.absent_insert++;
#endif
            wrapper_type* lhs = std::get<0>(boundaries.first);
            wrapper_type* rhs = std::get<0>(boundaries.second);
            if (p == nullptr) {
                assert(lhs == nullptr && rhs == nullptr);
                Sto::item(this, tree_key_).add_write(0);
            } else {
                auto item = Sto::item(this, reinterpret_cast<uintptr_t>(p) | 0x1);
                item.add_write(0);
                if (Sto::item(this, reinterpret_cast<uintptr_t>(lhs) | 0x1).has_read()
                    || Sto::item(this, reinterpret_cast<uintptr_t>(rhs) | 0x1).has_read()) {
                    Sto::item(this, reinterpret_cast<uintptr_t>(x) | 0x1).observe(ver);
                }
            }
            Sto::item(this, x).add_write(T()).add_flags(insert_tag);
            change_size_offset(1);
            return x;
        }
        else {
#if DEBUG
            stats_.present_insert++;
#endif
            auto item = Sto::item(this, x);
            if (has_delete(item)) {
                item.clear_flags(delete_tag);
                if (is_inserted(ver)) {
                    item.add_flags(insert_tag);
                }
                item.add_write(T());
                change_size_offset(1);
                return x;
            }
            item.observe(ver);
            return x;
        }
    }
inline wrapper_type * insert ( const K & key ) { rbwrapper < rbpair < K , T > > node ( rbpair < K , T > ( key , T ( ) ) ) ; auto results = this -> find_or_insert ( node ) ; wrapper_type * x = std :: get < 0 > ( results ) ; Version ver = std :: get < 1 > ( results ) ; bool found = std :: get < 2 > ( results ) ; boundaries_type & boundaries = std :: get < 3 > ( results ) ; node_info_type & pinfo = std :: get < 4 > ( results ) ; wrapper_type * p = std :: get < 0 > ( pinfo ) ; if ( ! found ) { #if DEBUG stats_ . absent_insert ++ ; #endif wrapper_type * lhs = std :: get < 0 > ( boundaries . first ) ; wrapper_type * rhs = std :: get < 0 > ( boundaries . second ) ; if ( p == nullptr ) { assert ( lhs == nullptr && rhs == nullptr ) ; Sto :: item ( this , tree_key_ ) . add_write ( 0 ) ; } else { auto item = Sto :: item ( this , reinterpret_cast < uintptr_t > ( p ) | 0x1 ) ; item . add_write ( 0 ) ; if ( Sto :: item ( this , reinterpret_cast < uintptr_t > ( lhs ) | 0x1 ) . has_read ( ) || Sto :: item ( this , reinterpret_cast < uintptr_t > ( rhs ) | 0x1 ) . has_read ( ) ) { Sto :: item ( this , reinterpret_cast < uintptr_t > ( x ) | 0x1 ) . observe ( ver ) ; } } Sto :: item ( this , x ) . add_write ( T ( ) ) . add_flags ( insert_tag ) ; change_size_offset ( 1 ) ; return x ; } else { #if DEBUG stats_ . present_insert ++ ; #endif auto item = Sto :: item ( this , x ) ; if ( has_delete ( item ) ) { item . clear_flags ( delete_tag ) ; if ( is_inserted ( ver ) ) { item . add_flags ( insert_tag ) ; } item . add_write ( T ( ) ) ; change_size_offset ( 1 ) ; return x ; } item . observe ( ver ) ; return x ; } }
Insert key and empty value if key does not exist
If key exists, then add a read of the item version and return the node
return value is a reference to the found or inserted node
Insert key and empty value if key does not exist If key exists then add a read of the item version and return the node return value is a reference to the found or inserted node
// p_ver is always nodeversion (not used right now) //Version p_ver = std::get<1>(pinfo); // INSERT: kvp did not exist // @ver is *nodeversion* // tree was empty, increment treeversion at COMMIT TIME // mark to update nodeversion at commit time // add the newly inserted node to boundary node set if it is adjacent to any tracked // boundary node // UPDATE: kvp is already inserted into the tree // @ver is *value version* // insert-my-delete // recover from delete-my-insert (engineer's induction all over the place...) // x->writeable_value() = T(); // overwrite value // we have to update the value of the size we will write // operator[] on RHS (THIS IS A READ!) // don't need to add a write to size because size isn't changing // STO won't add read of items in our write set // This is not ideal because a blind write also reads this version // It's a compromise since we don't want to acquire any more locks // at install time (to avoid deadlocks)