r66555 MediaWiki - Code Review archive

Repository:MediaWiki
Revision:< r66554‎ | r66555 | r66556 >
Date:02:26, 17 May 2010
Author:tstarling
Status:deferred
Tags:
Comment:
Cache server with "GD-Size-Frequency" cost optimisation strategy. Work in progress.
Modified paths:
  • /trunk/tools/maxcache (added) (history)
  • /trunk/tools/maxcache/App.cpp (added) (history)
  • /trunk/tools/maxcache/App.h (added) (history)
  • /trunk/tools/maxcache/Cache.cpp (added) (history)
  • /trunk/tools/maxcache/Cache.h (added) (history)
  • /trunk/tools/maxcache/CacheEntry.cpp (added) (history)
  • /trunk/tools/maxcache/CacheEntry.h (added) (history)
  • /trunk/tools/maxcache/Makefile (added) (history)
  • /trunk/tools/maxcache/boost-config.h (added) (history)
  • /trunk/tools/maxcache/maxcache.cpp (added) (history)
  • /trunk/tools/maxcache/typedefs.h (added) (history)

Diff [purge]

Index: trunk/tools/maxcache/boost-config.h
——@@ -0,0 +1,8 @@
 2+#ifndef MAXCACHE_BOOST_CONFIG_H
 3+#define MAXCACHE_BOOST_CONFIG_H
 4+
 5+// push the go fast button
 6+#define BOOST_SP_DISABLE_THREADS
 7+#define BOOST_ASIO_DISABLE_THREADS
 8+
 9+#endif
Property changes on: trunk/tools/maxcache/boost-config.h
___________________________________________________________________
Name: svn:eol-style
110 + native
Index: trunk/tools/maxcache/App.cpp
——@@ -0,0 +1,225 @@
 2+#include "App.h"
 3+
 4+#include <boost/bind.hpp>
 5+#include <stdexcept>
 6+#include <iostream>
 7+#include <iterator>
 8+#include <cstring>
 9+#include <boost/array.hpp>
 10+
 11+using namespace MaxCache;
 12+
 13+const Time App::NO_TIME( boost::posix_time::not_a_date_time );
 14+
 15+void App::run( int argc, char** argv ) {
 16+ Endpoint endpoint( Tcp::v4(), 9999 );
 17+ mAcceptor = AcceptorPtr( new Acceptor( mService, endpoint ) );
 18+ startAccept();
 19+ std::size_t numHandlers;
 20+ do {
 21+ resetTimeCache();
 22+ numHandlers = mService.run_one();
 23+ } while ( numHandlers );
 24+}
 25+
 26+void App::startAccept() {
 27+ // Create the peer socket
 28+ SocketPtr peer( new Socket( mService ) );
 29+ // Start accepting connections
 30+ mAcceptor->async_accept( *peer, boost::bind( &App::onAccept, this, peer, _1 ) );
 31+}
 32+
 33+void App::onAccept( SocketPtr peer, const ErrorCode & acceptError ) {
 34+ if ( acceptError ) {
 35+ throw SystemError( acceptError );
 36+ }
 37+ // Handle this connection
 38+ startRead( peer );
 39+ // Listen for another connection
 40+ startAccept();
 41+}
 42+
 43+void App::startRead( SocketPtr peer ) {
 44+ BufferPtr buffer( new Buffer( getMaxCmdLength() ) );
 45+ Asio::async_read_until( *peer, *buffer, "\r\n",
 46+ boost::bind( &App::onLineReady, this, peer, buffer, _1, _2 ) );
 47+}
 48+
 49+void App::onLineReady( SocketPtr peer, BufferPtr buffer,
 50+ const ErrorCode & readError, std::size_t n )
 51+{
 52+ if ( readError ) {
 53+ // Close connection
 54+ return;
 55+ }
 56+
 57+ std::istream stream( buffer.get() );
 58+ std::string command;
 59+
 60+ // Formatted extraction requires a sensible locale to be set
 61+ stream.imbue( std::locale( "C" ) );
 62+
 63+ stream >> command;
 64+ if ( handleTooFewParams( peer, stream ) ) return;
 65+
 66+ if ( command == "get" ) {
 67+ std::string key;
 68+ stream >> key;
 69+ if ( handleTooFewParams( peer, stream ) ) return;
 70+
 71+ CacheEntry * entry = mCache.getEntry( key );
 72+ if ( !entry ) {
 73+ writeMessage( peer, "NO: Item not found\r\n" );
 74+ return;
 75+ }
 76+
 77+ writeCacheEntry( peer, entry->getValue() );
 78+
 79+ } else if ( command == "set" ) {
 80+ // Usage: set <key> <expiry> <cost> <value>
 81+ std::string key;
 82+ boost::uint32_t expiryInterval, clientCost;
 83+ StringPtr value( new std::string );
 84+
 85+ stream.width( mMaxKeyLength + 1 );
 86+ stream >> key;
 87+ if ( handleTooFewParams( peer, stream ) ) return;
 88+ if ( key.size() > mMaxKeyLength ) {
 89+ writeMessage( peer, "ERROR: Key too long\r\n" );
 90+ return;
 91+ }
 92+
 93+ stream >> expiryInterval;
 94+ if ( handleTooFewParams( peer, stream ) ) return;
 95+ if ( stream.fail() ) {
 96+ writeMessage( peer, "ERROR: invalid expiry interval\r\n" );
 97+ return;
 98+ }
 99+
 100+ // Read the client cost, which is later divided by the size to get the
 101+ // real cost
 102+ stream >> clientCost;
 103+ if ( handleTooFewParams( peer, stream ) ) return;
 104+ if ( stream.fail() ) {
 105+ writeMessage( peer, "ERROR: invalid clientCost\r\n" );
 106+ return;
 107+ }
 108+
 109+ stream >> *value;
 110+ if ( handleTooFewParams( peer, stream ) ) return;
 111+ if ( value->size() > mCache.getMaxEntrySize() ) {
 112+ writeMessage( peer, "ERROR: value too big\r\n" );
 113+ return;
 114+ }
 115+
 116+ Time expiry;
 117+ if ( expiryInterval ) {
 118+ expiry = getTime() + boost::posix_time::microseconds( expiryInterval );
 119+ } else {
 120+ expiry = Time( boost::posix_time::pos_infin );
 121+ }
 122+
 123+ mCache.setEntry( key, value, clientCost, expiry );
 124+ writeMessage( peer, "OK: value set\r\n" );
 125+ } else if ( command == "delete" ) {
 126+ std::string key;
 127+ stream.width( mMaxKeyLength + 1 );
 128+ stream >> key;
 129+ if ( handleTooFewParams( peer, stream ) ) return;
 130+ if ( key.size() > mMaxKeyLength ) {
 131+ writeMessage( peer, "ERROR: Key too long\r\n" );
 132+ return;
 133+ }
 134+
 135+ if ( mCache.deleteEntry( key ) ) {
 136+ writeMessage( peer, "OK: deleted\r\n" );
 137+ } else {
 138+ writeMessage( peer, "NO: not found\r\n" );
 139+ }
 140+ } else if ( command == "quit" ) {
 141+ // Let peer go out of scope and die
 142+ } else if ( command == "stats" ) {
 143+ writeStats( peer );
 144+ } else if ( command == "kill" ) {
 145+ // TODO: for debugging only, remove this
 146+ mService.stop();
 147+ } else {
 148+ writeMessage( peer, "ERROR: Unknown command\r\n" );
 149+ }
 150+}
 151+
 152+void App::writeMessage( SocketPtr peer, const char * msg ) {
 153+ Asio::async_write(
 154+ *peer,
 155+ Asio::const_buffers_1( msg, std::strlen( msg ) ),
 156+ boost::bind( &App::onWriteMessageDone, this, peer, _1, _2 ) );
 157+}
 158+
 159+void App::onWriteMessageDone( SocketPtr peer, const ErrorCode & writeError, std::size_t n ) {
 160+ if ( writeError ) {
 161+ // Close connection
 162+ return;
 163+ }
 164+
 165+ startRead( peer );
 166+}
 167+
 168+void App::writeCacheEntry( SocketPtr peer, StringPtr entry ) {
 169+ const char prefix[] = "VALUE: ";
 170+ boost::array<Asio::const_buffer, 3> buffers;
 171+ buffers[0] = Asio::const_buffer( prefix, sizeof( prefix ) );
 172+ buffers[1] = Asio::const_buffer( entry->data(), entry->size() );
 173+ buffers[2] = Asio::const_buffer( "\r\n", 2 );
 174+
 175+ Asio::async_write( *peer, buffers,
 176+ boost::bind(
 177+ &App::onWriteCacheEntryDone, this, peer,
 178+ entry, // just to keep a reference in memory so buffers[1] doesn't dangle
 179+ _1, _2
 180+ )
 181+ );
 182+}
 183+
 184+void App::onWriteCacheEntryDone( SocketPtr peer, StringPtr entry,
 185+ const ErrorCode & writeError, std::size_t n )
 186+{
 187+ if ( writeError ) {
 188+ // Close connection
 189+ return;
 190+ }
 191+ startRead( peer );
 192+ // entry will go out of scope here and may be deleted
 193+}
 194+
 195+void App::writeStats( SocketPtr peer ) {
 196+ std::stringstream s;
 197+ s << "STATS:"
 198+ << " num-bytes=" << mCache.getNumBytes()
 199+ << " num-entries=" << mCache.getSize()
 200+ << " load-factor=" << mCache.getLoadFactor()
 201+ << " max-bytes=" << mCache.getMaxBytes()
 202+ << " max-load-factor=" << mCache.getMaxLoadFactor()
 203+ << "\r\n";
 204+ StringPtr sp( new std::string( s.str() ) );
 205+ Asio::async_write(
 206+ *peer,
 207+ Asio::const_buffers_1( sp->data(), sp->size() ),
 208+ boost::bind(
 209+ &App::onWriteStatsDone, this, peer,
 210+ sp, // just to keep a reference to sp
 211+ _1, _2
 212+ )
 213+ );
 214+}
 215+
 216+void App::onWriteStatsDone( SocketPtr peer, StringPtr buffer,
 217+ const ErrorCode & writeError, std::size_t n )
 218+{
 219+ if ( writeError ) {
 220+ // Close connection
 221+ return;
 222+ }
 223+ startRead( peer );
 224+ // buffer will go out of scope here and will be deleted
 225+}
 226+
Property changes on: trunk/tools/maxcache/App.cpp
___________________________________________________________________
Name: svn:eol-style
1227 + native
Index: trunk/tools/maxcache/Cache.cpp
——@@ -0,0 +1,159 @@
 2+#include "Cache.h"
 3+#include "App.h"
 4+
 5+using namespace MaxCache;
 6+
 7+Cache::Cache( App & app, std::size_t maxBytes )
 8+ : mMaxLoadFactor( 0.75 ),
 9+ mNumBuckets( 65536 ), // must be a power of 2
 10+ mBuckets( new KeyTable::bucket_type[mNumBuckets] ),
 11+ mKeyTable( KeyTable::bucket_traits( mBuckets.get(), mNumBuckets ) ),
 12+ mClock( 0 ),
 13+ mNumBytes( mNumBuckets * sizeof( KeyTable::bucket_type ) ),
 14+ mMaxBytes( maxBytes ),
 15+ mMaxEntrySizeLog2( 28 ),
 16+ mApp( app )
 17+{}
 18+
 19+Cache::~Cache() {
 20+ CostTree::iterator i;
 21+ for ( i = mCostTree.begin(); i != mCostTree.end(); i = mCostTree.begin() ) {
 22+ erase( *i );
 23+ }
 24+}
 25+
 26+/**
 27+ * Create a new CacheEntry from the specified params and insert it into
 28+ * the container.
 29+ */
 30+void Cache::setEntry( const std::string & key, StringPtr value,
 31+ boost::uint32_t clientCost, Time expiry )
 32+{
 33+ boost::uint64_t cost = ( (boost::uint64_t)clientCost << mMaxEntrySizeLog2 )
 34+ / value->size();
 35+ CacheEntry * entry = new CacheEntry( *this, key, value, cost, expiry );
 36+ setEntryPointer( entry );
 37+}
 38+
 39+/**
 40+ * Insert an entry and take ownership of the pointer.
 41+ * If necessary, evict entries from the cache to make room for the new one.
 42+ */
 43+void Cache::setEntryPointer( CacheEntry * entry ) {
 44+ std::size_t entrySize = entry->getSize();
 45+ if ( entrySize > mMaxBytes ) {
 46+ // Too big, ignore this request.
 47+ // This is equivalent to immediate eviction, so it doesn't break
 48+ // the semantics of the insert operation.
 49+ delete entry;
 50+ return;
 51+ }
 52+
 53+ // Try to insert the item into the hashtable
 54+ mNumBytes += entrySize;
 55+ std::pair< KeyTable::iterator, bool > status = mKeyTable.insert( *entry );
 56+
 57+ // If it failed, delete the offending entry
 58+ if ( !status.second ) {
 59+ erase( *status.first );
 60+ } else {
 61+ // Hashtable grew, does it need more buckets?
 62+ if ( getLoadFactor() > mMaxLoadFactor ) {
 63+ // Double the bucket count
 64+ mNumBytes += sizeof( KeyTable::bucket_type ) * mNumBuckets;
 65+ mNumBuckets <<= 1;
 66+ boost::shared_array<KeyTable::bucket_type> newBuckets(
 67+ new KeyTable::bucket_type[mNumBuckets] );
 68+ mKeyTable.rehash( KeyTable::bucket_traits( newBuckets.get(), mNumBuckets ) );
 69+ mBuckets.swap( newBuckets );
 70+ }
 71+ }
 72+
 73+ // Evict entries until there is enough room
 74+ if ( mNumBytes > mMaxBytes ) {
 75+ evictUntilNormalSize();
 76+ entry->adjustCost();
 77+ }
 78+
 79+ // Insert the item again if it failed before
 80+ if ( !status.second ) {
 81+ status = mKeyTable.insert( *entry );
 82+ if ( !status.second ) {
 83+ throw std::runtime_error( "Cache insertion failed unexpectedly" );
 84+ }
 85+ }
 86+
 87+ // Insert it into the other indexes
 88+ mCostTree.insert( *entry );
 89+ mExpiryTree.insert( *entry );
 90+}
 91+
 92+void Cache::erase( CacheEntry & entry ) {
 93+ mNumBytes -= entry.getSize();
 94+ mKeyTable.erase( mKeyTable.iterator_to( entry ) );
 95+ mCostTree.erase( mCostTree.iterator_to( entry ) );
 96+ mExpiryTree.erase( mExpiryTree.iterator_to( entry ) );
 97+ delete &entry;
 98+}
 99+
 100+void Cache::evictUntilNormalSize() {
 101+ evictExpiredEntries();
 102+
 103+ while ( mNumBytes > mMaxBytes ) {
 104+ CostTree::iterator begin = mCostTree.begin();
 105+ mClock = begin->getCost();
 106+ erase( *begin );
 107+ }
 108+}
 109+
 110+void Cache::evictExpiredEntries() {
 111+ Time now = mApp.getTime();
 112+ for ( ExpiryTree::iterator iter = mExpiryTree.begin();
 113+ iter != mExpiryTree.end() && iter->getExpiry() < now ;
 114+ iter++ )
 115+ {
 116+ erase( *iter );
 117+ }
 118+}
 119+
 120+CacheEntry * Cache::getEntry( const std::string & key ) {
 121+ // Find the entry
 122+ KeyTable::iterator iter = mKeyTable.find(
 123+ key, boost::hash<std::string>(), CacheEntry::KeyValueEqual() );
 124+
 125+ if ( iter == mKeyTable.end() ) {
 126+ return NULL;
 127+ }
 128+
 129+ // Skip expiry check for keys that have no expiry
 130+ if ( !iter->getExpiry().is_pos_infinity() ) {
 131+ Time now = mApp.getTime();
 132+ if ( iter->getExpiry() < mApp.getTime() ) {
 133+ // Key is expired, delete it and return miss
 134+ erase( *iter );
 135+ return NULL;
 136+ }
 137+ }
 138+
 139+ // Pull the entry out of the cost tree and recalculate its cost
 140+ mCostTree.erase( mCostTree.iterator_to( *iter ) );
 141+ iter->incrementHitCount();
 142+ iter->adjustCost();
 143+
 144+ // Reinsert the item into the cost tree
 145+ mCostTree.insert( *iter );
 146+
 147+ return &*iter;
 148+}
 149+
 150+bool Cache::deleteEntry( const std::string & key ) {
 151+ // Find the entry
 152+ KeyTable::iterator iter = mKeyTable.find(
 153+ key, boost::hash<std::string>(), CacheEntry::KeyValueEqual() );
 154+ if ( iter == mKeyTable.end() ) {
 155+ return false;
 156+ } else {
 157+ erase( *iter );
 158+ return true;
 159+ }
 160+}
Property changes on: trunk/tools/maxcache/Cache.cpp
___________________________________________________________________
Name: svn:eol-style
1161 + native
Index: trunk/tools/maxcache/App.h
——@@ -0,0 +1,103 @@
 2+#ifndef MAXCACHE_APP_H
 3+#define MAXCACHE_APP_H
 4+
 5+#include "boost-config.h"
 6+#include <boost/asio.hpp>
 7+#include <boost/shared_ptr.hpp>
 8+#include <boost/system/system_error.hpp>
 9+#include <list>
 10+#include <string>
 11+#include "typedefs.h"
 12+#include "Cache.h"
 13+
 14+namespace MaxCache {
 15+
 16+namespace Asio = boost::asio;
 17+typedef boost::asio::ip::tcp Tcp;
 18+typedef boost::asio::io_service Service;
 19+typedef Tcp::endpoint Endpoint;
 20+typedef Tcp::acceptor Acceptor;
 21+typedef boost::shared_ptr<Acceptor> AcceptorPtr;
 22+typedef Tcp::socket Socket;
 23+typedef boost::shared_ptr<Socket> SocketPtr;
 24+typedef boost::system::error_code ErrorCode;
 25+typedef boost::system::system_error SystemError;
 26+typedef boost::asio::streambuf Buffer;
 27+typedef boost::shared_ptr<Buffer> BufferPtr;
 28+typedef boost::asio::buffers_iterator< Buffer::const_buffers_type > BufferIterator;
 29+
 30+class App {
 31+ public:
 32+ App()
 33+ : mMaxKeyLength( 1000 ),
 34+ mCache( *this, 100000000 )
 35+ {}
 36+
 37+ void run( int argc, char** argv );
 38+
 39+ Service & getService() {
 40+ return mService;
 41+ }
 42+
 43+ /**
 44+ * Get the time with a cache reset on every select()
 45+ */
 46+ Time getTime() {
 47+ if ( mTime == NO_TIME ) {
 48+ mTime = boost::posix_time::microsec_clock::universal_time();
 49+ }
 50+ return mTime;
 51+ }
 52+
 53+ /**
 54+ * Reset the time cache
 55+ */
 56+ void resetTimeCache() {
 57+ mTime = NO_TIME;
 58+ }
 59+
 60+ std::size_t getMaxCmdLength() const {
 61+ return mCache.getMaxEntrySize() + mMaxKeyLength + sizeof( "blah\r\n" );
 62+ }
 63+
 64+ void startAccept();
 65+ void onAccept( SocketPtr peer, const ErrorCode & acceptError );
 66+
 67+ void startRead( SocketPtr peer );
 68+ void onLineReady( SocketPtr peer, BufferPtr buffer,
 69+ const ErrorCode & readError, std::size_t n );
 70+
 71+ void writeMessage( SocketPtr peer, const char * msg );
 72+ void onWriteMessageDone( SocketPtr peer, const ErrorCode & writeMessage, std::size_t n );
 73+
 74+ void writeCacheEntry( SocketPtr peer, StringPtr entry );
 75+ void onWriteCacheEntryDone( SocketPtr peer, StringPtr entry,
 76+ const ErrorCode & writeError, std::size_t n );
 77+
 78+ void writeStats( SocketPtr peer );
 79+ void onWriteStatsDone( SocketPtr peer, StringPtr buffer,
 80+ const ErrorCode & writeError, std::size_t n );
 81+ protected:
 82+ bool handleTooFewParams( SocketPtr peer, std::istream & stream ) {
 83+ if ( stream.eof() ) {
 84+ writeMessage( peer, "ERROR: Not enough parameters\r\n" );
 85+ return true;
 86+ } else {
 87+ return false;
 88+ }
 89+ }
 90+
 91+
 92+ Service mService;
 93+ AcceptorPtr mAcceptor;
 94+
 95+ const std::size_t mMaxKeyLength;
 96+
 97+ Cache mCache;
 98+ Time mTime;
 99+
 100+ const static Time NO_TIME;
 101+};
 102+
 103+}
 104+#endif
Property changes on: trunk/tools/maxcache/App.h
___________________________________________________________________
Name: svn:eol-style
1105 + native
Index: trunk/tools/maxcache/CacheEntry.cpp
——@@ -0,0 +1,11 @@
 2+#include "CacheEntry.h"
 3+#include "Cache.h"
 4+
 5+MaxCache::CacheEntry::CacheEntry( const Cache & parent, const std::string & key, StringPtr value,
 6+ boost::uint64_t cost, Time expiry )
 7+ : mKey( key ), mValue( value ), mHitCount( 0 ), mOriginalCost( cost ), mExpiry( expiry ),
 8+ mClock( parent.getClock() )
 9+{
 10+ adjustCost();
 11+}
 12+
Property changes on: trunk/tools/maxcache/CacheEntry.cpp
___________________________________________________________________
Name: svn:eol-style
113 + native
Index: trunk/tools/maxcache/Cache.h
——@@ -0,0 +1,140 @@
 2+#ifndef MAXCACHE_CACHE_H
 3+#define MAXCACHE_CACHE_H
 4+
 5+#include "boost-config.h"
 6+#include "CacheEntry.h"
 7+#include <boost/shared_array.hpp>
 8+
 9+namespace MaxCache {
 10+
 11+typedef Intrusive::unordered_set<
 12+ CacheEntry,
 13+ KeyMemberOption,
 14+ equal< CacheEntry::KeysEqual >,
 15+ hash< CacheEntry::HashFunction >,
 16+ power_2_buckets< true >
 17+ > KeyTable;
 18+
 19+typedef Intrusive::multiset<
 20+ CacheEntry,
 21+ CostMemberOption,
 22+ compare< CacheEntry::CompareCosts >
 23+ > CostTree;
 24+
 25+typedef Intrusive::multiset<
 26+ CacheEntry,
 27+ ExpiryMemberOption,
 28+ compare< CacheEntry::CompareExpiries >
 29+ > ExpiryTree;
 30+
 31+class App;
 32+
 33+class Cache {
 34+ public:
 35+ /**
 36+ * Get a reference to the clock value
 37+ */
 38+ const boost::uint64_t & getClock() const {
 39+ return mClock;
 40+ }
 41+ boost::uint64_t & getClock() {
 42+ return mClock;
 43+ }
 44+
 45+ /**
 46+ * Constructor.
 47+ */
 48+ Cache( App & app, std::size_t maxBytes );
 49+
 50+ /**
 51+ * Destructor.
 52+ */
 53+ ~Cache();
 54+
 55+ /**
 56+ * Create an entry and insert it
 57+ */
 58+ void setEntry( const std::string & key, StringPtr value,
 59+ boost::uint32_t clientCost, Time expiry );
 60+
 61+ /**
 62+ * Insert an entry and take ownership of the pointer.
 63+ * If necessary, evict entries from the cache to make room for the new one.
 64+ */
 65+ void setEntryPointer( CacheEntry * entry );
 66+
 67+ /**
 68+ * Get an entry from the cache and update frequency data.
 69+ * Returns NULL if the entry does not exist
 70+ */
 71+ CacheEntry * getEntry( const std::string & key );
 72+
 73+ /**
 74+ * Delete an entry. Returns true if it existed, false otherwise.
 75+ */
 76+ bool deleteEntry( const std::string & key );
 77+
 78+ float getMaxLoadFactor() const {
 79+ return mMaxLoadFactor;
 80+ }
 81+
 82+ float getLoadFactor() const {
 83+ return (float)getSize() / getNumBuckets();
 84+ }
 85+
 86+ std::size_t getNumBuckets() const {
 87+ return mNumBuckets;
 88+ }
 89+
 90+ std::size_t getNumBytes() const {
 91+ return mNumBytes;
 92+ }
 93+
 94+ std::size_t getMaxBytes() const {
 95+ return mMaxBytes;
 96+ }
 97+
 98+ std::size_t getSize() const {
 99+ return mKeyTable.size();
 100+ }
 101+
 102+ std::size_t getMaxEntrySize() const {
 103+ return (size_t)1 << mMaxEntrySizeLog2;
 104+ }
 105+
 106+ protected:
 107+
 108+ /**
 109+ * Erase an item which is in the container
 110+ */
 111+ void erase( CacheEntry & entry );
 112+
 113+ /**
 114+ * Evict entries until the size of the container is less than the maximum
 115+ */
 116+ void evictUntilNormalSize();
 117+
 118+ /**
 119+ * Evict any entries that have expired
 120+ */
 121+ void evictExpiredEntries();
 122+
 123+ float mMaxLoadFactor;
 124+ std::size_t mNumBuckets;
 125+ boost::shared_array<KeyTable::bucket_type> mBuckets;
 126+ KeyTable mKeyTable;
 127+
 128+ CostTree mCostTree;
 129+ ExpiryTree mExpiryTree;
 130+ boost::uint64_t mClock;
 131+
 132+ std::size_t mNumBytes;
 133+ std::size_t mMaxBytes;
 134+ unsigned char mMaxEntrySizeLog2;
 135+
 136+ App & mApp;
 137+};
 138+
 139+}
 140+
 141+#endif
Property changes on: trunk/tools/maxcache/Cache.h
___________________________________________________________________
Name: svn:eol-style
1142 + native
Index: trunk/tools/maxcache/typedefs.h
——@@ -0,0 +1,12 @@
 2+#ifndef MAXCACHE_TYPEDEFS_H
 3+#define MAXCACHE_TYPEDEFS_H
 4+
 5+#include <string>
 6+#include <boost/shared_ptr.hpp>
 7+#include <boost/date_time/posix_time/posix_time_types.hpp>
 8+namespace MaxCache {
 9+ typedef boost::shared_ptr<std::string> StringPtr;
 10+ typedef boost::posix_time::ptime Time;
 11+}
 12+
 13+#endif
Property changes on: trunk/tools/maxcache/typedefs.h
___________________________________________________________________
Name: svn:eol-style
114 + native
Index: trunk/tools/maxcache/maxcache.cpp
——@@ -0,0 +1,16 @@
 2+#include "boost-config.h"
 3+#include <boost/asio.hpp>
 4+#include <iostream>
 5+#include "App.h"
 6+
 7+int main(int argc, char** argv)
 8+{
 9+ try {
 10+ MaxCache::App app;
 11+ app.run(argc, argv);
 12+ } catch (std::exception & e) {
 13+ std::cerr << "Exception: " << e.what() << "\n";
 14+ return 1;
 15+ }
 16+ return 0;
 17+}
Property changes on: trunk/tools/maxcache/maxcache.cpp
___________________________________________________________________
Name: svn:eol-style
118 + native
Index: trunk/tools/maxcache/CacheEntry.h
——@@ -0,0 +1,129 @@
 2+#ifndef MAXCACHE_CACHEENTRY_H
 3+#define MAXCACHE_CACHEENTRY_H
 4+
 5+#include "boost-config.h"
 6+#include <boost/cstdint.hpp>
 7+#include <boost/shared_ptr.hpp>
 8+#include <boost/intrusive/set.hpp>
 9+#include <boost/intrusive/unordered_set.hpp>
 10+#include <ctime>
 11+#include <limits>
 12+#include "typedefs.h"
 13+
 14+using namespace boost::intrusive;
 15+
 16+namespace MaxCache {
 17+
 18+namespace Intrusive = boost::intrusive;
 19+
 20+typedef Intrusive::unordered_set_member_hook< store_hash<true> > HashHook;
 21+typedef Intrusive::set_base_hook<> TreeHook;
 22+
 23+class Cache;
 24+
 25+class CacheEntry {
 26+ public:
 27+ HashHook mKeyHook;
 28+ TreeHook mCostHook;
 29+ TreeHook mExpiryHook;
 30+
 31+ struct KeysEqual {
 32+ bool operator()( const CacheEntry & e1, const CacheEntry & e2 ) const {
 33+ return e1.mKey == e2.mKey;
 34+ }
 35+ };
 36+
 37+ struct KeyValueEqual {
 38+ bool operator()( const std::string & key, const CacheEntry & entry ) const {
 39+ return key == entry.mKey;
 40+ }
 41+ };
 42+
 43+ struct HashFunction {
 44+ boost::hash<std::string> mHash;
 45+
 46+ std::size_t operator()( const CacheEntry & e ) const {
 47+ return mHash( e.mKey );
 48+ }
 49+ };
 50+
 51+ struct CompareCosts {
 52+ bool operator()( const CacheEntry & e1, const CacheEntry & e2 ) const {
 53+ if ( ( e1.mCost >= e1.mClock && e2.mCost >= e1.mClock )
 54+ || ( e1.mCost < e1.mClock && e2.mCost < e1.mClock ) )
 55+ {
 56+ return e1.mCost < e2.mCost;
 57+ } else {
 58+ return e2.mCost < e1.mClock && e1.mCost >= e1.mClock;
 59+ }
 60+ }
 61+ };
 62+
 63+ struct CompareExpiries {
 64+ bool operator()( const CacheEntry & e1, const CacheEntry & e2 ) const {
 65+ return e1.mExpiry < e2.mExpiry;
 66+ }
 67+ };
 68+
 69+ CacheEntry( const Cache & parent, const std::string & key, StringPtr value,
 70+ boost::uint64_t cost, Time expiry );
 71+
 72+ void incrementHitCount() {
 73+ if ( mHitCount < std::numeric_limits<boost::uint32_t>::max() ) {
 74+ mHitCount++;
 75+ }
 76+ }
 77+
 78+ void adjustCost() {
 79+ mCost = mClock + mHitCount * mOriginalCost;
 80+ }
 81+
 82+ boost::uint32_t getHitCount() const {
 83+ return mHitCount;
 84+ }
 85+
 86+ boost::uint64_t getOriginalCost() const {
 87+ return mOriginalCost;
 88+ }
 89+
 90+ boost::uint64_t getCost() const {
 91+ return mCost;
 92+ }
 93+
 94+ Time getExpiry() const {
 95+ return mExpiry;
 96+ }
 97+
 98+ const std::string & getKey() const {
 99+ return mKey;
 100+ }
 101+
 102+ StringPtr getValue() {
 103+ return mValue;
 104+ }
 105+
 106+ std::size_t getSize() {
 107+ return sizeof(*this) +
 108+ sizeof(std::string) + // dynamically allocated value structure
 109+ mKey.size() + // key storage
 110+ mValue->size(); // value storage
 111+ }
 112+
 113+ protected:
 114+ std::string mKey;
 115+ StringPtr mValue;
 116+
 117+ boost::uint32_t mHitCount;
 118+ boost::uint64_t mOriginalCost;
 119+ boost::uint64_t mCost;
 120+ Time mExpiry;
 121+ const boost::uint64_t & mClock;
 122+};
 123+
 124+typedef Intrusive::member_hook< CacheEntry, HashHook, &CacheEntry::mKeyHook > KeyMemberOption;
 125+typedef Intrusive::member_hook< CacheEntry, TreeHook, &CacheEntry::mCostHook > CostMemberOption;
 126+typedef Intrusive::member_hook< CacheEntry, TreeHook, &CacheEntry::mExpiryHook > ExpiryMemberOption;
 127+
 128+}
 129+
 130+#endif
Property changes on: trunk/tools/maxcache/CacheEntry.h
___________________________________________________________________
Name: svn:eol-style
1131 + native
Index: trunk/tools/maxcache/Makefile
——@@ -0,0 +1,9 @@
 2+all: maxcache
 3+
 4+CFLAGS:=$(CFLAGS) -ggdb3 -Wall
 5+
 6+maxcache: maxcache.o App.o CacheEntry.o Cache.o
 7+ g++ $^ $(CFLAGS) -lboost_system -o $@
 8+
 9+%.o : %.cpp
 10+ g++ -c $(CFLAGS) $< -o $@
Property changes on: trunk/tools/maxcache/Makefile
___________________________________________________________________
Name: svn:eol-style
111 + native

Status & tagging log