index.hpp

Go to the documentation of this file.

/*
 * Copyright (c) 2015 Cryptonomex, Inc., and contributors.
 *
 * The MIT License
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */
#pragma once
#include <graphene/db/object.hpp>
 
#include <fc/interprocess/file_mapping.hpp>
#include <fc/io/raw.hpp>
#include <fc/io/json.hpp>
#include <fc/crypto/sha256.hpp>
 
#include <fstream>
#include <stack>
 
namespace graphene { namespace db {
   class object_database;
 
   class index_observer
   {
      public:
         virtual ~index_observer() = default;
         virtual void on_add( const object& obj ){}
         virtual void on_remove( const object& obj ){}
         virtual void on_modify( const object& obj ){}
   };
 
   class index
   {
      public:
         virtual ~index() = default;
 
         virtual uint8_t object_space_id()const = 0;
         virtual uint8_t object_type_id()const = 0;
 
         virtual object_id_type get_next_id()const = 0;
         virtual void           use_next_id() = 0;
         virtual void           set_next_id( object_id_type id ) = 0;
 
         virtual const object&  load( const std::vector<char>& data ) = 0;
         virtual const object& insert( object&& obj ) = 0;
 
         virtual const object&  create( const std::function<void(object&)>& constructor ) = 0;
 
         virtual void open( const fc::path& db ) = 0;
         virtual void save( const fc::path& db ) = 0;
 
 
 
         virtual const object*      find( object_id_type id )const = 0;
 
         const object&              get( object_id_type id )const
         {
            auto maybe_found = find( id );
            FC_ASSERT( maybe_found != nullptr, "Unable to find Object ${id}", ("id",id) );
            return *maybe_found;
         }
 
         virtual void               modify( const object& obj, const std::function<void(object&)>& ) = 0;
         virtual void               remove( const object& obj ) = 0;
 
         template<typename Object, typename Lambda>
         void modify( const Object& obj, const Lambda& l ) {
            modify( static_cast<const object&>(obj),
                    std::function<void(object&)>( [&l]( object& o ){ l( static_cast<Object&>(o) ); } ) );
         }
 
         virtual void inspect_all_objects(std::function<void(const object&)> inspector)const = 0;
         virtual void add_observer( const std::shared_ptr<index_observer>& ) = 0;
 
         virtual void object_from_variant( const fc::variant& var, object& obj, uint32_t max_depth )const = 0;
         virtual void object_default( object& obj )const = 0;
   };
 
   class secondary_index
   {
      public:
         virtual ~secondary_index() = default;
         virtual void object_inserted( const object& obj ){};
         virtual void object_removed( const object& obj ){};
         virtual void about_to_modify( const object& before ){};
         virtual void object_modified( const object& after  ){};
   };
 
   class base_primary_index
   {
      public:
         explicit base_primary_index( object_database& db ):_db(db){}
 
         virtual ~base_primary_index() = default;
 
         void save_undo( const object& obj );
 
         void on_add( const object& obj );
 
         void on_remove( const object& obj );
 
         void on_modify( const object& obj );
 
         template<typename T, typename... Args>
         T* add_secondary_index(Args... args)
         {
            _sindex.emplace_back( std::make_unique<T>(args...) );
            return static_cast<T*>(_sindex.back().get());
         }
 
         template<typename T>
         const T& get_secondary_index()const
         {
            for( const auto& item : _sindex )
            {
               const T* result = dynamic_cast<const T*>(item.get());
               if( result != nullptr ) return *result;
            }
            FC_THROW_EXCEPTION( fc::assert_exception, "invalid index type" );
         }
 
      protected:
         std::vector< std::shared_ptr<index_observer> >   _observers;
         std::vector< std::unique_ptr<secondary_index> >  _sindex;
 
      private:
         object_database& _db;
   };
 
   template<typename Object, uint8_t chunkbits>
   class direct_index : public secondary_index
   {
      static_assert( chunkbits < 64, "Do you really want arrays with more than 2^63 elements???" );
 
      // private
         static const size_t MAX_HOLE = 100;
         static const size_t _mask = ((1ULL << chunkbits) - 1);
         uint64_t next = 0;
         std::vector< std::vector< const Object* > > content;
         std::stack< object_id_type > ids_being_modified;
 
      public:
         direct_index() {
            FC_ASSERT( (1ULL << chunkbits) > MAX_HOLE, "Small chunkbits is inefficient." );
         }
 
         void object_inserted( const object& obj ) override
         {
            uint64_t instance = obj.id.instance();
            if( instance == next )
            {
               if( 0 == (next & _mask) )
               {
                  content.resize((next >> chunkbits) + 1);
                  content[next >> chunkbits].resize( 1ULL << chunkbits, nullptr );
               }
               next++;
            }
            else if( instance < next )
               FC_ASSERT( !content[instance >> chunkbits][instance & _mask],
                          "Overwriting insert at {id}!", ("id",obj.id) );
            else // instance > next, allow small "holes"
            {
               FC_ASSERT( instance <= next + MAX_HOLE,
                          "Out-of-order insert: {id} > {next}!", ("id",obj.id)("next",next) );
               if( 0 == (next & _mask) || (next & (~_mask)) != (instance & (~_mask)) )
               {
                  content.resize((instance >> chunkbits) + 1);
                  content[instance >> chunkbits].resize( 1ULL << chunkbits, nullptr );
               }
               while( next <= instance )
               {
                  content[next >> chunkbits][next & _mask] = nullptr;
                  next++;
               }
            }
            FC_ASSERT( nullptr != dynamic_cast<const Object*>(&obj), "Wrong object type!" );
            content[instance >> chunkbits][instance & _mask] = static_cast<const Object*>( &obj );
         }
 
         void object_removed( const object& obj ) override
         {
            FC_ASSERT( nullptr != dynamic_cast<const Object*>(&obj), "Wrong object type!" );
            uint64_t instance = obj.id.instance();
            FC_ASSERT( instance < next, "Removing out-of-range object: {id} > {next}!", ("id",obj.id)("next",next) );
            FC_ASSERT( content[instance >> chunkbits][instance & _mask],
                       "Removing non-existent object {id}!", ("id",obj.id) );
            content[instance >> chunkbits][instance & _mask] = nullptr;
         }
 
         void about_to_modify( const object& before ) override
         {
            ids_being_modified.emplace( before.id );
         }
 
         void object_modified( const object& after  ) override
         {
            FC_ASSERT( ids_being_modified.top() == after.id, "Modification of ID is not supported!");
            ids_being_modified.pop();
         }
 
         template< typename object_id >
         const Object* find( const object_id& id )const
         {
            static_assert( object_id::space_id == Object::space_id, "Space ID mismatch!" );
            static_assert( object_id::type_id == Object::type_id, "Type_ID mismatch!" );
            if( id.instance >= next ) return nullptr;
            return content[id.instance.value >> chunkbits][id.instance.value & _mask];
         };
 
         template< typename object_id >
         const Object& get( const object_id& id )const
         {
            const Object* ptr = find( id );
            FC_ASSERT( ptr != nullptr, "Object not found!" );
            return *ptr;
         };
 
         const Object* find( const object_id_type& id )const
         {
            FC_ASSERT( id.space() == Object::space_id, "Space ID mismatch!" );
            FC_ASSERT( id.type() == Object::type_id, "Type_ID mismatch!" );
            if( id.instance() >= next ) return nullptr;
            return content[id.instance() >> chunkbits][id.instance() & ((1ULL << chunkbits) - 1)];
         };
   };
 
   template<typename DerivedIndex, uint8_t DirectBits = 0>
   class primary_index  : public DerivedIndex, public base_primary_index
   {
      public:
         using object_type = typename DerivedIndex::object_type;
 
         explicit primary_index( object_database& db )
         :base_primary_index(db),_next_id(object_type::space_id,object_type::type_id,0)
         {
            if( DirectBits > 0 )
               _direct_by_id = add_secondary_index< direct_index< object_type, DirectBits > >();
         }
 
         uint8_t object_space_id()const override
         { return object_type::space_id; }
 
         uint8_t object_type_id()const override
         { return object_type::type_id; }
 
         object_id_type get_next_id()const override              { return _next_id;    }
         void           use_next_id()override                    { ++_next_id.number;  }
         void           set_next_id( object_id_type id )override { _next_id = id;      }
 
         const object*  find( object_id_type id )const override
         {
            if( DirectBits > 0 )
               return _direct_by_id->find( id );
            return DerivedIndex::find( id );
         }
 
         fc::sha256 get_object_version()const
         {
            std::string desc = "1.0";
            return fc::sha256::hash(desc);
         }
 
         void open( const fc::path& db )override
         {
            if( !fc::exists( db ) ) return;
            fc::file_mapping fm( db.generic_string().c_str(), fc::read_only );
            fc::mapped_region mr( fm, fc::read_only, 0, fc::file_size(db) );
            fc::datastream<const char*> ds( (const char*)mr.get_address(), mr.get_size() );
            fc::sha256 open_ver;
 
            fc::raw::unpack(ds, _next_id);
            fc::raw::unpack(ds, open_ver);
            FC_ASSERT( open_ver == get_object_version(),
                       "Incompatible Version, the serialization of objects in this index has changed" );
            std::vector<char> tmp;
            while( ds.remaining() > 0 )
            {
               fc::raw::unpack( ds, tmp );
               load( tmp );
            }
         }
 
         void save( const fc::path& db ) override
         {
            std::ofstream out( db.generic_string(),
                               std::ofstream::binary | std::ofstream::out | std::ofstream::trunc );
            FC_ASSERT( out );
            auto ver  = get_object_version();
            fc::raw::pack( out, _next_id );
            fc::raw::pack( out, ver );
            this->inspect_all_objects( [&out]( const object& o ) {
                auto vec = fc::raw::pack( static_cast<const object_type&>(o) );
                auto packed_vec = fc::raw::pack( vec );
                out.write( packed_vec.data(), packed_vec.size() );
            });
         }
 
         const object&  load( const std::vector<char>& data )override
         {
            const auto& result = DerivedIndex::insert( fc::raw::unpack<object_type>( data ) );
            for( const auto& item : _sindex )
               item->object_inserted( result );
            return result;
         }
 
 
         const object&  create(const std::function<void(object&)>& constructor )override
         {
            const auto& result = DerivedIndex::create( constructor );
            for( const auto& item : _sindex )
               item->object_inserted( result );
            on_add( result );
            return result;
         }
 
         const object& insert( object&& obj ) override
         {
            const auto& result = DerivedIndex::insert( std::move( obj ) );
            for( const auto& item : _sindex )
               item->object_inserted( result );
            on_add( result );
            return result;
         }
 
         void  remove( const object& obj ) override
         {
            for( const auto& item : _sindex )
               item->object_removed( obj );
            on_remove(obj);
            DerivedIndex::remove(obj);
         }
 
         void modify( const object& obj, const std::function<void(object&)>& m )override
         {
            save_undo( obj );
            for( const auto& item : _sindex )
               item->about_to_modify( obj );
            DerivedIndex::modify( obj, m );
            for( const auto& item : _sindex )
               item->object_modified( obj );
            on_modify( obj );
         }
 
         void add_observer( const std::shared_ptr<index_observer>& o ) override
         {
            _observers.emplace_back( o );
         }
 
         void object_from_variant( const fc::variant& var, object& obj, uint32_t max_depth )const override
         {
            object_id_type id = obj.id;
            object_type* result = dynamic_cast<object_type*>( &obj );
            FC_ASSERT( result != nullptr );
            fc::from_variant( var, *result, max_depth );
            obj.id = id;
         }
 
         void object_default( object& obj )const override
         {
            object_id_type id = obj.id;
            object_type* result = dynamic_cast<object_type*>( &obj );
            FC_ASSERT( result != nullptr );
            (*result) = object_type();
            obj.id = id;
         }
 
      private:
         object_id_type                                 _next_id;
         const direct_index< object_type, DirectBits >* _direct_by_id = nullptr;
   };
 
} } // graphene::db