/*******************************************************************
File: IndexedFile.hpp
Copyright (c) 2002 Bleading Edge Software Technologies, Inc.
This Software is distributed under the open source, free software
model. Permission to use, modify, and distribute this Software,
including incorporating it into proprietary software, is granted
without fee, provided this copyright notice appear in all copies
of the code. You are under no obligation to distribute source
code which is derived from or uses this Software. You may not do
anything however, such as copyrighting or claiming authorship, to
prevent the continued distribution of this Software under an open
source distribution model. This Software is distributed in the
hope that it will be useful, but it is provide "as is",
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
//$----------------------------------------------------------------
Author: Jack W. Reeves
//!----------------------------------------------------------------|
Description:
//#----------------------------------------------------------------|
Notes:
//%****************************************************************/
#ifndef UTIL_INDEXED_FILE_HPP
#define UTIL_INDEXED_FILE_HPP
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; }
};
template<typename Key,
typename Compare = std::less<Key>,
typename KeyTraits = XDR_Traits<Key>,
size_t PageSize = 4096>
class BtreeIndex {
public:
class Iterator;
class StreamposProxy;
friend class Iterator;
friend class StreamposProxy;
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 };
// iterators
class StreamposProxy {
public:
// LWC - default copy and destroy Ok
// conversion
operator size_t();
// assignment
void operator=(size_t newlink);
};
class Iterator :
public std::iterator<std::bidirectional_iterator_tag,
std::pair<const Key,
StreamposProxy> > {
public:
Iterator();
Iterator(const Iterator& x);
Iterator& operator=(const Iterator& x);
std::pair<const Key, StreamposProxy> operator*();
Iterator& operator++();
Iterator operator++(int);
Iterator& operator--();
Iterator operator--(int);
bool operator==(const Iterator& x) const;
bool operator!=(const Iterator& x) const;
};
// 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);
};
//
// 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 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 class Iterator;
public:
// conversion
operator const Item&();
// assignment
void operator=(const Item& itm);
};
class Iterator :
public std::iterator<std::bidirectional_iterator_tag,
std::pair<const Key, ItemProxy> > {
public:
Iterator();
Iterator(const Iterator& x);
Iterator& operator=(const Iterator& x);
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
{ return !(*this == x); }
};
// 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();
// 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
};
} //> namespace Util
#endif