#ifndef UTIL_INDEXED_FILE_H
#define UTIL_INDEXED_FILE_H
// XDR Stream headers
#include "Util/XDRStream.h"
#include "Util/XIO.h"
// Standard C++ headers
#include <functional>
#include <string>
#include <ios>
#include <list>
namespace Util {
template <typename Item>
struct XDR_Traits {
typedef XIOFileStream xio_type;
static oXDR_Stream& encode(oXDR_Stream& oxs, const Item& val)
{ return oxs << val; }
static iXDR_Stream& decode(iXDR_Stream& ixs, Item& val)
{ return ixs >> val; }
};
//
// BtreeIndex --
//
template<typename Key,
typename Compare = std::less<Key>,
typename KeyTraits = XDR_Traits<Key>,
size_t PageSize = 4096>
class BtreeIndex {
public:
// public types
// forward declartions
class StreamposProxy;
class Iterator;
class PageCache;
class Page;
class RootPage;
class XIODataStreambuf;
class XInDataBuf;
class XoutDataBuf;
typedef Key key_type;
typedef std::pair<const Key, size_t>
value_type;
typedef Compare key_compare;
typedef Iterator iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
enum DeleteStrategy { None, Compact, Shuffle };
enum UpdateStrategy { Unsafe, MostlySafe, Safe };
//
// class BtreeIndex::Iterator --
//
class StreamposProxy {
friend class BtreeIndex;
// data
size_t _link;
BtreeIndex* _btree;
size_t _page;
size_t _slot;
public:
// LWC - default copy and destroy Ok
// conversion
operator size_t();
// assignment
void operator=(size_t newlink);
private:
StreamposProxy(size_t link,
BtreeIndex* btree,
size_t page,
size_t slot);
};
class Iterator :
public std::iterator<
std::bidirectional_iterator_tag,
std::pair<const Key, StreamposProxy> > {
friend class BtreeIndex;
// data
BtreeIndex* _btree;
size_t _page;
size_t _slot;
public:
Iterator() {}
std::pair<const Key, StreamposProxy> operator*();
Iterator& operator++();
Iterator operator++(int);
Iterator& operator--();
Iterator operator--(int);
bool operator==(const Iterator& rhs) const;
bool operator!=(const Iterator& rhs) const;
private:
Iterator(BtreeIndex* btree, size_t page, size_t slot);
};
class PageCache {
// types
typedef std::list<Page*> PageList;
// data
XDR_Stream& _xstream;
size_t _minSize;
size_t _maxSize;
PageList _pageList;
public:
PageCache(XDR_Stream&);
~PageCache();
Page* get_page(size_t page);
void add_page(Page* p); // puts a new page into the cache
void reset(); // deletes any excess pages
void clear(); // deletes all pages
void flush(); // writes any dirty pages out
void min_size(size_t size) { _minSize = size; }
int max_size() { return _maxSize; }
void max_size(size_t size) { _minSize = size; }
}; //> BtreeIndex::PageCache
//
// BtreeIndex::Page
//
class Page {
public:
struct KeyInfo {
Key key;
size_t link;
short xlen; // length of encoded <key,link>
// in data area
KeyInfo(Key k, size_t l, short xl) :
key(k), link(l), xlen(xl) {}
KeyInfo() {}
};
typedef std::list<KeyInfo> KeyList;
protected:
// data
const size_t _pageId;
size_t _dataLen;
size_t _prevPage;
size_t _nextPage;
bool _dirty; // set when changed;
// cleared by encode
KeyList _keyList;
static const int HeaderSize = 16;
public:
Page(size_t pageId);
virtual ~Page();
// access
size_t page_id() const { return _pageId; }
size_t data_len() const { return _dataLen; }
size_t prev_page() const { return _prevPage; }
size_t next_page() const { return _nextPage; }
bool is_dirty() const { return _dirty; }
size_t num_keys() const { return _keyList.size(); }
// update
KeyList& key_list() { return _keyList; }
void data_len(size_t len) {
_dataLen = len; _dirty = true; }
void prev_page(size_t pid) {
_prevPage = pid; _dirty = true; }
void next_page(size_t pid) {
_nextPage = pid; _dirty = true; }
// test
bool must_split() const;
// access / update the key list
size_t add_key(BtreeIndex&, const std::pair<const Key,
size_t>&);
bool remove_key(int slot);
void update_key(size_t slot, size_t link);
void insert_page_link(KeyList::iterator kit, Page* p);
void update_page_link(Page* p);
bool remove_page_link(Page* p);
// virtual functions
virtual Page* split(BtreeIndex&);
virtual Page* consolidate(BtreeIndex&);
virtual Page* shuffle(BtreeIndex&);
virtual oXDR_Stream& encode(oXDR_Stream&);
virtual iXDR_Stream& decode(iXDR_Stream&);
private:
Page(const Page&);
Page& operator=(const Page&);
}; //> BtreeIndex::Page
//
// BtreeIndex::RootPage
//
class RootPage : public Page {
public:
// data
size_t _totalKeys;
short _depth;
bool _dirtyTotal;
public:
RootPage();
virtual ~RootPage();
// access
size_t total_keys() const {
return _totalKeys; }
short depth() const {
return _depth; }
size_t next_free_page() const {
return _nextPage;}
bool is_total_dirty() const {
return _dirtyTotal; }
// update
void incr_total() {
++_totalKeys; _dirtyTotal = true; }
void decr_total() {
--_totalKeys; _dirtyTotal = true; }
void add_free_page(Page* p) {
p->next_page(next_page());
next_page(p->page_id()); }
void rem_free_page(Page* p) {
next_page(p->next_page()); }
// virtual functions
virtual Page* split(BtreeIndex&);
virtual Page* consolidate(BtreeIndex&);
virtual oXDR_Stream& encode(oXDR_Stream&);
virtual iXDR_Stream& decode(iXDR_Stream&);
}; //> BtreeIndex::RootPage
// class which handles read/write to/from
// an externally specified memory area
class XIODataStreambuf : public XDR_Streambuf {
// data
XDR_Char* _buf;
size_t _size;
size_t _len;
public:
XIODataStreambuf(char* buf, size_t size, size_t len = 0);
~XIODataStreambuf();
virtual pos_type seekoff(off_type off,
std::ios_base::seekdir dir,
std::ios_base::openmode which);
virtual pos_type seekpos(pos_type pos,
std::ios_base::openmode which);
};
class XOutDataBuf : public oXDR_Stream {
// data
oXDR_Stream& _refstrm;
XIODataStreambuf _xstreambuf;
public:
XOutDataBuf(oXDR_Stream&, char* buf, size_t size);
~XOutDataBuf();
};
class XInDataBuf : public iXDR_Stream {
// data
iXDR_Stream& _refstrm;
XIODataStreambuf _xstreambuf;
public:
XInDataBuf(iXDR_Stream&, char* buf, size_t len);
~XInDataBuf();
};
// construct / destroy
explicit BtreeIndex(Compare comp = Compare());
explicit BtreeIndex(const std::string& name,
std::ios_base::openmode mode =
std::ios_base::in|std::ios_base::out,
Compare comp = Compare());
~BtreeIndex();
// open/close/test state
bool is_open();
void open(
const std::string& name,
std::ios_base::openmode mode =
std::ios_base::in|std::ios_base::out);
void close();
void flush();
operator void*() const;
bool operator!() const;
// iterators
iterator begin();
iterator end();
// capacity
bool empty();
size_type size();
// modifiers
iterator insert(const value_type& x);
iterator insert(const Key& k);
template<typename InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(Iterator pos);
size_type erase(const Key& x);
void erase(iterator first, iterator last);
void clear();
// observers
key_compare key_comp() const;
size_type page_size() const;
XDR_Stream& xdrstream();
// operations
iterator find(const Key& x);
size_type count(const Key& x);
iterator lower_bound(const Key& x);
iterator upper_bound(const Key& x);
std::pair<iterator, iterator>
equal_range(const Key& x);
// utilities
void reindex();
DeleteStrategy set_delete_strategy(DeleteStrategy strategy);
UpdateStrategy set_update_strategy(UpdateStrategy strategy);
int set_cache_size(int size);
private:
// friends
friend class Iterator;
friend class StreamposProxy;
friend class Page;
friend class RootPage;
// data
Compare _comp;
KeyTraits::xio_type _xstream;
RootPage* _root;
PageCache _pageCache;
DeleteStrategy _dStrategy;
UpdateStrategy _uStrategy;
// Iterator utility functions - used by friends
std::pair<const Key, StreamposProxy>
get_value(size_t page, size_t slot);
void prev_iter(Iterator& it);
void next_iter(Iterator& it);
// StreamposProxy utility functions - used by friends
void update_link(size_t page, size_t offset,
size_t link);
// BtreeIndex utility functions
Page* get_page(size_t pageId);
Page* get_free_page();
void add_free_page(Page* p);
iterator lower_bound(Page* p, int depth, const Key& k);
iterator upper_bound(Page* p, int depth, const Key& k);
iterator insert(Page*, int depth, const value_type& x);
std::pair<bool,bool>
erase(Page* p, int depth, const Key& k, iterator pos);
void flush(UpdateStrategy s);
}; //> BtreeIndex
//
// Class IndexedFile
//
template<typename Key,
typename Item,
typename Compare = std::less<Key>,
typename KeyTraits = XDR_Traits<Key>,
typename ItemTraits = XDR_Traits<Item>,
size_t PageSize = 4096>
class IndexedFile {
public:
// types
class ItemProxy;
class Iterator;
typedef Key key_type;
typedef std::pair<const Key, Item> value_type;
typedef Compare key_compare;
typedef Iterator iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef BtreeIndex<Key, Compare, KeyTraits, PageSize>
index_type;
class ItemProxy {
friend Iterator;
// data
IndexedFile* _ifile;
index_type::StreamposProxy _posProxy;
public:
// conversion
operator Item() {
return _ifile->read( _posProxy ); }
// assignment
void operator=(const Item& item) { _posProxy =
_ifile->write(item); }
private:
ItemProxy(IndexedFile* ifile,
index_type::StreamposProxy posProxy)
: _ifile(ifile), _posProxy(posProxy) {}
};
class Iterator : public std::iterator<
std::bidirectional_iterator_tag,
std::pair<const Key, ItemProxy> > {
friend IndexedFile;
// data
IndexedFile* _ifile;
index_type::iterator _base;
public:
Iterator() {}
std::pair<const Key, ItemProxy> operator*();
Iterator& operator++();
Iterator operator++(int);
Iterator& operator--();
Iterator operator--(int);
index_type::iterator base();
bool operator==(const Iterator& x) const;
bool operator!=(const Iterator& x) const;
private:
Iterator(IndexedFile* ifile, index_type::iterator base)
: _ifile(ifile), _base(base) {}
};
// construct / destroy
explicit IndexedFile(Compare comp = Compare());
explicit IndexedFile(
const std::string& name,
std::ios_base::openmode mode =
std::ios_base::in|std::ios_base::out,
Compare comp = Compare());
~IndexedFile();
// open/close
bool is_open();
void open(
const std::string& name,
std::ios_base::openmode mode =
std::ios_base::in|std::ios_base::out);
void close();
void flush();
operator void*() const;
bool operator!() const;
// iterators
Iterator begin();
Iterator end();
// capacity
bool empty();
size_type size();
// modifiers
Iterator insert(const value_type& x);
template<typename InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(Iterator pos);
size_type erase(const Key& x);
void erase(Iterator first, Iterator last);
void clear();
// observers
Compare key_comp() const;
size_t page_size() const;
index_type& index();
XDR_Stream& xdrstream();
// operations
Iterator find(const Key& x);
size_type count(const Key& x);
Iterator lower_bound(const Key& x);
Iterator upper_bound(const Key& x);
std::pair<Iterator, Iterator>
equal_range(const Key& x);
// utilities
void compact();
Item read(size_t pos); // decodes and returns
// the Item at pos
private:
// data
index_type _index;
ItemTraits::xio_type _xstream;
// friendly utilities
size_t write(const Item& item); // returns the
// streampos
};
} //> namespace
#endif