Index: ps/trunk/source/lib/cache_adt.h =================================================================== --- ps/trunk/source/lib/cache_adt.h (revision 9363) +++ ps/trunk/source/lib/cache_adt.h (nonexistent) @@ -1,753 +0,0 @@ -/* Copyright (c) 2010 Wildfire Games - * - * 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. - */ - -/* - * Customizable cache data structure. - */ - -#ifndef INCLUDED_CACHE_ADT -#define INCLUDED_CACHE_ADT - -#include - -#include -#include -#include // std::priority_queue - -#if CONFIG_ENABLE_BOOST -# include -# define MAP boost::unordered_map -#else -# define MAP stdext::hash_map -#endif - -/* -Cache for items of variable size and value/"cost". -underlying displacement algorithm is pluggable; default is "Landlord". - -template reference: -Entry provides size, cost, credit and credit_density(). - rationale: - - made a template instead of exposing Cache::Entry because - that would drag a lot of stuff out of Cache. - - calculates its own density since that entails a Divider functor, - which requires storage inside Entry. -Entries is a collection with iterator and begin()/end() and - "static Entry& entry_from_it(iterator)". - rationale: - - STL map has pair as its value_type, so this - function would return it->second. however, we want to support - other container types (where we'd just return *it). -Manager is a template parameterized on typename Key and class Entry. - its interface is as follows: - - // is the cache empty? - bool empty() const; - - // add (key, entry) to cache. - void add(const Key& key, const Entry& entry); - - // if the entry identified by is not in cache, return false; - // otherwise return true and pass back a pointer to it. - bool find(const Key& key, const Entry** pentry) const; - - // remove an entry from cache, which is assumed to exist! - // this makes sense because callers will typically first use find() to - // return info about the entry; this also checks if present. - void remove(const Key& key); - - // mark as just accessed for purpose of cache management. - // it will tend to be kept in cache longer. - void on_access(Entry& entry); - - // caller's intent is to remove the least valuable entry. - // in implementing this, you have the latitude to "shake loose" - // several entries (e.g. because their 'value' is equal). - // they must all be push_back-ed into the list; Cache will dole - // them out one at a time in FIFO order to callers. - // - // rationale: - // - it is necessary for callers to receive a copy of the - // Entry being evicted - e.g. file_cache owns its items and - // they must be passed back to allocator when evicted. - // - e.g. Landlord can potentially see several entries become - // evictable in one call to remove_least_valuable. there are - // several ways to deal with this: - // 1) generator interface: we return one of { empty, nevermind, - // removed, remove-and-call-again }. this greatly complicates - // the call site. - // 2) return immediately after finding an item to evict. - // this changes cache behavior - entries stored at the - // beginning would be charged more often (unfair). - // resuming charging at the next entry doesn't work - this - // would have to be flushed when adding, at which time there - // is no provision for returning any items that may be evicted. - // 3) return list of all entries "shaken loose". this incurs - // frequent mem allocs, which can be alleviated via suballocator. - // note: an intrusive linked-list doesn't make sense because - // entries to be returned need to be copied anyway (they are - // removed from the manager's storage). - void remove_least_valuable(std::list& entry_list) -*/ - - -// -// functors to calculate minimum credit density (MCD) -// - -// MCD is required for the Landlord algorithm's evict logic. -// [Young02] calls it '\delta'. - -// scan over all entries and return MCD. -template float ll_calc_min_credit_density(const Entries& entries) -{ - float min_credit_density = FLT_MAX; - for(typename Entries::const_iterator it = entries.begin(); it != entries.end(); ++it) - { - const float credit_density = Entries::entry_from_it(it).credit_density(); - min_credit_density = std::min(min_credit_density, credit_density); - } - return min_credit_density; -} - -// note: no warning is given that the MCD entry is being removed! -// (reduces overhead in remove_least_valuable) -// these functors must account for that themselves (e.g. by resetting -// their state directly after returning MCD). - -// determine MCD by scanning over all entries. -// tradeoff: O(N) time complexity, but all notify* calls are no-ops. -template -class McdCalc_Naive -{ -public: - void notify_added(const Entry&) const {} - void notify_decreased(const Entry&) const {} - void notify_impending_increase_or_remove(const Entry&) const {} - void notify_increased_or_removed(const Entry&) const {} - float operator()(const Entries& entries) const - { - const float mcd = ll_calc_min_credit_density(entries); - return mcd; - } -}; - -// cache previous MCD and update it incrementally (when possible). -// tradeoff: amortized O(1) time complexity, but notify* calls must -// perform work whenever something in the cache changes. -template -class McdCalc_Cached -{ -public: - McdCalc_Cached() : min_credit_density(FLT_MAX), min_valid(false) {} - - void notify_added(const Entry& entry) - { - // when adding a new item, the minimum credit density can only - // decrease or remain the same; acting as if entry's credit had - // been decreased covers both cases. - notify_decreased(entry); - } - - void notify_decreased(const Entry& entry) - { - min_credit_density = std::min(min_credit_density, entry.credit_density()); - } - - void notify_impending_increase_or_remove(const Entry& entry) - { - // remember if this entry had the smallest density - is_min_entry = feq(min_credit_density, entry.credit_density()); - } - - void notify_increased_or_removed(const Entry& UNUSED(entry)) - { - // .. it did and was increased or removed. we must invalidate - // MCD and recalculate it next time. - if(is_min_entry) - { - min_valid = false; - min_credit_density = -1.0f; - } - } - - float operator()(const Entries& entries) - { - if(min_valid) - { - // the entry that has MCD will be removed anyway by caller; - // we need to invalidate here because they don't call - // notify_increased_or_removed. - min_valid = false; - return min_credit_density; - } - - // this is somewhat counterintuitive. since we're calculating - // MCD directly, why not mark our cached version of it valid - // afterwards? reason is that our caller will remove the entry with - // MCD, so it'll be invalidated anyway. - // instead, our intent is to calculate MCD for the *next time*. - const float ret = ll_calc_min_credit_density(entries); - min_valid = true; - min_credit_density = FLT_MAX; - return ret; - } - -private: - float min_credit_density; - bool min_valid; - - // temporary flag set by notify_impending_increase_or_remove - bool is_min_entry; -}; - - -// -// Landlord cache management policy: see [Young02]. -// - -// in short, each entry has credit initially set to cost. when wanting to -// remove an item, all are charged according to MCD and their size; -// entries are evicted if their credit is exhausted. accessing an entry -// restores "some" of its credit. -template class McdCalc = McdCalc_Cached> -class Landlord -{ -public: - bool empty() const - { - return map.empty(); - } - - void add(const Key& key, const Entry& entry) - { - // adapter for add_ (which returns an iterator) - (void)add_(key, entry); - } - - bool find(const Key& key, const Entry** pentry) const - { - MapCIt it = map.find(key); - if(it == map.end()) - return false; - *pentry = &it->second; - return true; - } - - void remove(const Key& key) - { - MapIt it = map.find(key); - // note: don't complain if not in the cache: this happens after - // writing a file and invalidating its cache entry, which may - // or may not exist. - if(it != map.end()) - remove_(it); - } - - void on_access(Entry& entry) - { - mcd_calc.notify_impending_increase_or_remove(entry); - - // Landlord algorithm calls for credit to be reset to anything - // between its current value and the cost. - const float gain = 0.75f; // restore most credit - entry.credit = gain*entry.cost + (1.0f-gain)*entry.credit; - - mcd_calc.notify_increased_or_removed(entry); - } - - void remove_least_valuable(std::list& entry_list) - { - // we are required to evict at least one entry. one iteration - // ought to suffice, due to definition of min_credit_density and - // tolerance; however, we provide for repeating if necessary. -again: - - // messing with this (e.g. raising if tiny) would result in - // different evictions than Landlord_Lazy, which is unacceptable. - // nor is doing so necessary: if mcd is tiny, so is credit. - const float min_credit_density = mcd_calc(map); - ENSURE(min_credit_density > 0.0f); - - for(MapIt it = map.begin(); it != map.end();) // no ++it - { - Entry& entry = it->second; - - charge(entry, min_credit_density); - if(should_evict(entry)) - { - entry_list.push_back(entry); - - // annoying: we have to increment before erasing - MapIt it_to_remove = it++; - map.erase(it_to_remove); - } - else - { - mcd_calc.notify_decreased(entry); - ++it; - } - } - - if(entry_list.empty()) - goto again; - } - -protected: - class Map : public MAP - { - public: - static Entry& entry_from_it(typename Map::iterator it) { return it->second; } - static const Entry& entry_from_it(typename Map::const_iterator it) { return it->second; } - }; - typedef typename Map::iterator MapIt; - typedef typename Map::const_iterator MapCIt; - Map map; - - // add entry and return iterator pointing to it. - MapIt add_(const Key& key, const Entry& entry) - { - typedef std::pair PairIB; - typename Map::value_type val = std::make_pair(key, entry); - PairIB ret = map.insert(val); - ENSURE(ret.second); // must not already be in map - - mcd_calc.notify_added(entry); - - return ret.first; - } - - // remove entry (given by iterator) directly. - void remove_(MapIt it) - { - const Entry& entry = it->second; - mcd_calc.notify_impending_increase_or_remove(entry); - mcd_calc.notify_increased_or_removed(entry); - map.erase(it); - } - - void charge(Entry& entry, float delta) - { - entry.credit -= delta * entry.size; - - // don't worry about entry.size being 0 - if so, cost - // should also be 0, so credit will already be 0 anyway. - } - - // for each entry, 'charge' it (i.e. reduce credit by) delta * its size. - // delta is typically MCD (see above); however, several such updates - // may be lumped together to save time. Landlord_Lazy does this. - void charge_all(float delta) - { - for(MapIt it = map.begin(); it != map.end(); ++it) - { - Entry& entry = it->second; - entry.credit -= delta * entry.size; - if(!should_evict(entry)) - mcd_calc.notify_decreased(entry); - } - } - - // is entry's credit exhausted? if so, it should be evicted. - bool should_evict(const Entry& entry) - { - // we need a bit of leeway because density calculations may not - // be exact. choose value carefully: must not be high enough to - // trigger false positives. - return entry.credit < 0.0001f; - } - -private: - McdCalc mcd_calc; -}; - -// Cache manger policies. (these are partial specializations of Landlord, -// adapting it to the template params required by Cache) -template class Landlord_Naive : public Landlord {}; -template class Landlord_Cached: public Landlord {}; - -// variant of Landlord that adds a priority queue to directly determine -// which entry to evict. this allows lumping several charge operations -// together and thus reduces iteration over all entries. -// tradeoff: O(logN) removal (instead of N), but additional O(N) storage. -template -class Landlord_Lazy : public Landlord_Naive -{ - typedef typename Landlord_Naive::Map Map; - typedef typename Landlord_Naive::MapIt MapIt; - typedef typename Landlord_Naive::MapCIt MapCIt; - -public: - Landlord_Lazy() { pending_delta = 0.0f; } - - void add(const Key& key, const Entry& entry) - { - // we must apply pending_delta now - otherwise, the existing delta - // would later be applied to this newly added item (incorrect). - commit_pending_delta(); - - MapIt it = Parent::add_(key, entry); - pri_q.push(it); - } - - void remove(const Key& key) - { - Parent::remove(key); - - // reconstruct pri_q from current map. this is slow (N*logN) and - // could definitely be done better, but we don't bother since - // remove is a very rare operation (e.g. invalidating entries). - while(!pri_q.empty()) - pri_q.pop(); - for(MapCIt it = this->map.begin(); it != this->map.end(); ++it) - pri_q.push(it); - } - - void on_access(Entry& entry) - { - Parent::on_access(entry); - - // entry's credit was changed. we now need to reshuffle the - // pri queue to reflect this. - pri_q.ensure_heap_order(); - } - - void remove_least_valuable(std::list& entry_list) - { - MapIt least_valuable_it = pri_q.top(); pri_q.pop(); - Entry& entry = Map::entry_from_it(least_valuable_it); - - entry_list.push_back(entry); - - // add to pending_delta the MCD that would have resulted - // if removing least_valuable_it normally. - // first, calculate actual credit (i.e. apply pending_delta to - // this entry); then add the resulting density to pending_delta. - entry.credit -= pending_delta*entry.size; - const float credit_density = entry.credit_density(); - ENSURE(credit_density > 0.0f); - pending_delta += credit_density; - - Parent::remove_(least_valuable_it); - } - -private: - typedef Landlord_Naive Parent; - - // sort iterators by credit_density of the Entry they reference. - struct CD_greater - { - bool operator()(MapIt it1, MapIt it2) const - { - return Map::entry_from_it(it1).credit_density() > - Map::entry_from_it(it2).credit_density(); - } - }; - // wrapper on top of priority_queue that allows 'heap re-sift' - // (see on_access). - // notes: - // - greater comparator makes pri_q.top() the one with - // LEAST credit_density, which is what we want. - // - deriving from an STL container is a bit dirty, but we need this - // to get at the underlying data (priority_queue interface is not - // very capable). - class PriQ: public std::priority_queue, CD_greater> - { - public: - void ensure_heap_order() - { - // TODO: this is actually N*logN - ouch! that explains high - // CPU cost in profile. this is called after only 1 item has - // changed, so a logN "sift" operation ought to suffice. - // that's not supported by the STL heap functions, so we'd - // need a better implementation. pending.. - std::make_heap(this->c.begin(), this->c.end(), this->comp); - } - }; - PriQ pri_q; - - // delta values that have accumulated over several - // remove_least_valuable() calls. applied during add(). - float pending_delta; - - void commit_pending_delta() - { - if(pending_delta > 0.0f) - { - this->charge_all(pending_delta); - pending_delta = 0.0f; - - // we've changed entry credit, so the heap order *may* have been - // violated; reorder the pri queue. (I don't think so, - // due to definition of delta, but we'll play it safe) - pri_q.ensure_heap_order(); - } - } -}; - - -// -// functor that implements division of first arg by second -// - -// this is used to calculate credit_density(); performance matters -// because this is called for each entry during each remove operation. - -// floating-point division (fairly slow) -class Divider_Naive -{ -public: - Divider_Naive() {} // needed for default CacheEntry ctor - Divider_Naive(float UNUSED(x)) {} - float operator()(float val, float divisor) const - { - return val / divisor; - } -}; - -// caches reciprocal of divisor and multiplies by that. -// tradeoff: only 4 clocks (instead of 20), but 4 bytes extra per entry. -class Divider_Recip -{ - float recip; -public: - Divider_Recip() {} // needed for default CacheEntry ctor - Divider_Recip(float x) { recip = 1.0f / x; } - float operator()(float val, float UNUSED(divisor)) const - { - return val * recip; - } -}; - -// TODO: use SSE/3DNow RCP instruction? not yet, because not all systems -// support it and overhead of detecting this support eats into any gains. - -// initial implementation for testing purposes; quite inefficient. -template -class LRU -{ -public: - bool empty() const - { - return lru.empty(); - } - - void add(const Key& key, const Entry& entry) - { - lru.push_back(KeyAndEntry(key, entry)); - } - - bool find(const Key& key, const Entry** pentry) const - { - CIt it = std::find_if(lru.begin(), lru.end(), KeyEq(key)); - if(it == lru.end()) - return false; - *pentry = &it->entry; - return true; - } - - void remove(const Key& key) - { - std::remove_if(lru.begin(), lru.end(), KeyEq(key)); - } - - void on_access(Entry& entry) - { - for(It it = lru.begin(); it != lru.end(); ++it) - { - if(&entry == &it->entry) - { - add(it->key, it->entry); - lru.erase(it); - return; - } - } - ENSURE(0); // entry not found in list - } - - void remove_least_valuable(std::list& entry_list) - { - entry_list.push_back(lru.front().entry); - lru.pop_front(); - } - -private: - struct KeyAndEntry - { - Key key; - Entry entry; - KeyAndEntry(const Key& key_, const Entry& entry_) - : key(key_), entry(entry_) {} - }; - class KeyEq - { - Key key; - public: - KeyEq(const Key& key_) : key(key_) {} - bool operator()(const KeyAndEntry& ke) const - { - return ke.key == key; - } - }; - - typedef std::list List; - typedef typename List::iterator It; - typedef typename List::const_iterator CIt; - List lru; -}; - - -// this is applicable to all cache management policies and stores all -// required information. a Divider functor is used to implement -// division for credit_density. -template struct CacheEntry -{ - Item item; - size_t size; - size_t cost; - float credit; - - Divider divider; - - // needed for mgr.remove_least_valuable's entry_copy - CacheEntry() - { - } - - CacheEntry(const Item& item_, size_t size_, size_t cost_) - : item(item_), divider((float)size_) - { - size = size_; - cost = cost_; - credit = (float)cost; - - // else divider will fail - ENSURE(size != 0); - } - - float credit_density() const - { - return divider(credit, (float)size); - } -}; - - -// -// Cache -// - -template -< -typename Key, typename Item, -// see documentation above for Manager's interface. -template class Manager = Landlord_Cached, -class Divider = Divider_Naive -> -class Cache -{ -public: - Cache() : mgr() {} - - void add(const Key& key, const Item& item, size_t size, size_t cost) - { - return mgr.add(key, Entry(item, size, cost)); - } - - // remove the entry identified by . expected usage is to check - // if present and determine size via retrieve(), so no need for - // error checking. - // useful for invalidating single cache entries. - void remove(const Key& key) - { - mgr.remove(key); - } - - // if there is no entry for in the cache, return false. - // otherwise, return true and pass back item and (optionally) size. - // - // if refill_credit (default), the cache manager 'rewards' this entry, - // tending to keep it in cache longer. this parameter is not used in - // normal operation - it's only for special cases where we need to - // make an end run around the cache accounting (e.g. for cache simulator). - bool retrieve(const Key& key, Item& item, size_t* psize = 0, bool refill_credit = true) - { - const Entry* entry; - if(!mgr.find(key, &entry)) - return false; - - item = entry->item; - if(psize) - *psize = entry->size; - - if(refill_credit) - mgr.on_access((Entry&)*entry); - - return true; - } - - bool peek(const Key& key, Item& item, size_t* psize = 0) - { - return retrieve(key, item, psize, false); - } - - // toss out the least valuable entry. return false if cache is empty, - // otherwise true and (optionally) pass back its item and size. - bool remove_least_valuable(Item* pItem = 0, size_t* pSize = 0) - { - // as an artefact of the cache eviction policy, several entries - // may be "shaken loose" by one call to remove_least_valuable. - // we cache them in a list to disburden callers (they always get - // exactly one). - if(entries_awaiting_eviction.empty()) - { - if(empty()) - return false; - - mgr.remove_least_valuable(entries_awaiting_eviction); - ENSURE(!entries_awaiting_eviction.empty()); - } - - const Entry& entry = entries_awaiting_eviction.front(); - if(pItem) - *pItem = entry.item; - if(pSize) - *pSize = entry.size; - entries_awaiting_eviction.pop_front(); - - return true; - } - - bool empty() const - { - return mgr.empty(); - } - -private: - typedef CacheEntry Entry; - - // see note in remove_least_valuable(). - std::list entries_awaiting_eviction; - - Manager mgr; -}; - -#endif // #ifndef INCLUDED_CACHE_ADT Property changes on: ps/trunk/source/lib/cache_adt.h ___________________________________________________________________ Deleted: svn:eol-style ## -1 +0,0 ## -native \ No newline at end of property Index: ps/trunk/source/lib/adts.h =================================================================== --- ps/trunk/source/lib/adts.h (revision 9363) +++ ps/trunk/source/lib/adts.h (nonexistent) @@ -1,655 +0,0 @@ -/* Copyright (c) 2010 Wildfire Games - * - * 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. - */ - -/* - * useful Abstract Data Types not provided by STL. - */ - -#ifndef INCLUDED_ADTS -#define INCLUDED_ADTS - -#include "lib/fnv_hash.h" -#include "lib/bits.h" - -#include // strcmp - -//----------------------------------------------------------------------------- -// dynamic (grow-able) hash table -//----------------------------------------------------------------------------- - -template class DHT_Traits -{ -public: - static const size_t initial_entries = 16; - size_t hash(Key key) const; - bool equal(Key k1, Key k2) const; - Key get_key(T t) const; -}; - -template<> class DHT_Traits -{ -public: - static const size_t initial_entries = 512; - size_t hash(const char* key) const - { - return (size_t)fnv_lc_hash(key); - } - bool equal(const char* k1, const char* k2) const - { - return !strcmp(k1, k2); - } - const char* get_key(const char* t) const - { - return t; - } -}; - - -// intended for pointer types -template > -class DynHashTbl -{ - T* tbl; - u16 num_entries; - u16 max_entries; // when initialized, = 2**n for faster modulo - Traits tr; - - T& get_slot(Key key) const - { - size_t hash = tr.hash(key); - ENSURE(max_entries != 0); // otherwise, mask will be incorrect - const size_t mask = max_entries-1; - for(;;) - { - T& t = tbl[hash & mask]; - // empty slot encountered => not found - if(!t) - return t; - // keys are actually equal => found it - if(tr.equal(key, tr.get_key(t))) - return t; - // keep going (linear probing) - hash++; - } - } - - void expand_tbl() - { - // alloc a new table (but don't assign it to unless successful) - T* old_tbl = tbl; - tbl = (T*)calloc(max_entries*2, sizeof(T)); - if(!tbl) - { - tbl = old_tbl; - throw std::bad_alloc(); - } - - max_entries *= 2; - // must be set before get_slot - - // newly initialized, nothing to copy - done - if(!old_tbl) - return; - - // re-hash from old table into the new one - for(size_t i = 0; i < max_entries/2u; i++) - { - T t = old_tbl[i]; - if(t) - get_slot(tr.get_key(t)) = t; - } - free(old_tbl); - } - - -public: - - DynHashTbl() - { - tbl = 0; - clear(); - } - - ~DynHashTbl() - { - free(tbl); - } - - void clear() - { - // must remain usable after calling clear, so shrink the table to - // its initial size but don't deallocate it completely - SAFE_FREE(tbl); - num_entries = 0; - // rationale: must not set to 0 because expand_tbl only doubles the size. - // don't keep the previous size when clearing because it may have become - // huge and there is no provision for shrinking. - max_entries = tr.initial_entries/2; // will be doubled in expand_tbl - expand_tbl(); - } - - void insert(const Key key, const T t) - { - // more than 75% full - increase table size. - // do so before determining slot; this will invalidate previous pnodes. - if(num_entries*4 >= max_entries*3) - expand_tbl(); - - T& slot = get_slot(key); - ENSURE(slot == 0); // not already present - slot = t; - num_entries++; - } - - T find(Key key) const - { - return get_slot(key); - } - - size_t size() const - { - return num_entries; - } - - - class iterator - { - public: - typedef std::forward_iterator_tag iterator_category; - typedef T value_type; - typedef ptrdiff_t difference_type; - typedef const T* pointer; - typedef const T& reference; - - iterator() - { - } - iterator(T* pos_, T* end_) : pos(pos_), end(end_) - { - } - T& operator*() const - { - return *pos; - } - iterator& operator++() // pre - { - do - pos++; - while(pos != end && *pos == 0); - return (*this); - } - bool operator==(const iterator& rhs) const - { - return pos == rhs.pos; - } - bool operator<(const iterator& rhs) const - { - return (pos < rhs.pos); - } - - // derived - const T* operator->() const - { - return &**this; - } - bool operator!=(const iterator& rhs) const - { - return !(*this == rhs); - } - iterator operator++(int) // post - { - iterator tmp = *this; ++*this; return tmp; - } - - protected: - T* pos; - T* end; - // only used when incrementing (avoid going beyond end of table) - }; - - iterator begin() const - { - T* pos = tbl; - while(pos != tbl+max_entries && *pos == 0) - pos++; - return iterator(pos, tbl+max_entries); - } - iterator end() const - { - return iterator(tbl+max_entries, 0); - } -}; - - -//----------------------------------------------------------------------------- -// FIFO bit queue -//----------------------------------------------------------------------------- - -struct BitBuf -{ - uintptr_t buf; - uintptr_t cur; // bit to be appended (toggled by add()) - size_t len; // |buf| [bits] - - void reset() - { - buf = 0; - cur = 0; - len = 0; - } - - // toggle current bit if desired, and add to buffer (new bit is LSB) - void add(uintptr_t toggle) - { - cur ^= toggle; - buf <<= 1; - buf |= cur; - len++; - } - - // extract LS n bits - size_t extract(uintptr_t n) - { - const uintptr_t bits = buf & bit_mask(n); - buf >>= n; - - return bits; - } -}; - - -//----------------------------------------------------------------------------- -// ring buffer - static array, accessible modulo n -//----------------------------------------------------------------------------- - -template class RingBuf -{ - size_t size_; // # of entries in buffer - size_t head; // index of oldest item - size_t tail; // index of newest item - T data[n]; - -public: - RingBuf() : data() { clear(); } - void clear() { size_ = 0; head = 0; tail = n-1; } - - size_t size() const { return size_; } - bool empty() const { return size_ == 0; } - - const T& operator[](int ofs) const - { - ENSURE(!empty()); - size_t idx = (size_t)(head + ofs); - return data[idx % n]; - } - T& operator[](int ofs) - { - ENSURE(!empty()); - size_t idx = (size_t)(head + ofs); - return data[idx % n]; - } - - T& front() - { - ENSURE(!empty()); - return data[head]; - } - const T& front() const - { - ENSURE(!empty()); - return data[head]; - } - T& back() - { - ENSURE(!empty()); - return data[tail]; - } - const T& back() const - { - ENSURE(!empty()); - return data[tail]; - } - - void push_back(const T& item) - { - if(size_ < n) - size_++; - // do not complain - overwriting old values is legit - // (e.g. sliding window). - else - head = (head + 1) % n; - - tail = (tail + 1) % n; - data[tail] = item; - } - - void pop_front() - { - if(size_ != 0) - { - size_--; - head = (head + 1) % n; - } - else - ENSURE(0); // underflow - } - - class iterator - { - public: - typedef std::random_access_iterator_tag iterator_category; - typedef T value_type; - typedef ptrdiff_t difference_type; - typedef T* pointer; - typedef T& reference; - - iterator() : data(0), pos(0) - {} - iterator(T* data_, size_t pos_) : data(data_), pos(pos_) - {} - T& operator[](int idx) const - { return data[(pos+idx) % n]; } - T& operator*() const - { return data[pos % n]; } - T* operator->() const - { return &**this; } - iterator& operator++() // pre - { ++pos; return (*this); } - iterator operator++(int) // post - { iterator tmp = *this; ++*this; return tmp; } - bool operator==(const iterator& rhs) const - { return data == rhs.data && pos == rhs.pos; } - bool operator!=(const iterator& rhs) const - { return !(*this == rhs); } - bool operator<(const iterator& rhs) const - { return (pos < rhs.pos); } - iterator& operator+=(difference_type ofs) - { pos += ofs; return *this; } - iterator& operator-=(difference_type ofs) - { return (*this += -ofs); } - iterator operator+(difference_type ofs) const - { iterator tmp = *this; return (tmp += ofs); } - iterator operator-(difference_type ofs) const - { iterator tmp = *this; return (tmp -= ofs); } - difference_type operator-(const iterator right) const - { return (difference_type)(pos - right.pos); } - - protected: - T* data; - size_t pos; - // not mod-N so that begin != end when buffer is full. - }; - - class const_iterator - { - public: - typedef std::random_access_iterator_tag iterator_category; - typedef T value_type; - typedef ptrdiff_t difference_type; - typedef const T* pointer; - typedef const T& reference; - - const_iterator() : data(0), pos(0) - {} - const_iterator(const T* data_, size_t pos_) : data(data_), pos(pos_) - {} - const T& operator[](int idx) const - { return data[(pos+idx) % n]; } - const T& operator*() const - { return data[pos % n]; } - const T* operator->() const - { return &**this; } - const_iterator& operator++() // pre - { ++pos; return (*this); } - const_iterator operator++(int) // post - { const_iterator tmp = *this; ++*this; return tmp; } - bool operator==(const const_iterator& rhs) const - { return data == rhs.data && pos == rhs.pos; } - bool operator!=(const const_iterator& rhs) const - { return !(*this == rhs); } - bool operator<(const const_iterator& rhs) const - { return (pos < rhs.pos); } - iterator& operator+=(difference_type ofs) - { pos += ofs; return *this; } - iterator& operator-=(difference_type ofs) - { return (*this += -ofs); } - iterator operator+(difference_type ofs) const - { iterator tmp = *this; return (tmp += ofs); } - iterator operator-(difference_type ofs) const - { iterator tmp = *this; return (tmp -= ofs); } - difference_type operator-(const iterator right) const - { return (difference_type)(pos - right.pos); } - - protected: - const T* data; - size_t pos; - // not mod-N so that begin != end when buffer is full. - }; - - iterator begin() - { - return iterator(data, head); - } - const_iterator begin() const - { - return const_iterator(data, head); - } - iterator end() - { - return iterator(data, head+size_); - } - const_iterator end() const - { - return const_iterator(data, head+size_); - } -}; - - -// Matei's slightly friendlier hashtable for value-type keys -template -class MateiHashTbl -{ - static const size_t initial_entries = 16; - - struct Entry { - bool valid; - K key; - T value; - Entry() : valid(false) {} - Entry(const K& k, T v) { key=k; value=v; } - Entry& operator=(const Entry& other) { - valid = other.valid; - key = other.key; - value = other.value; - return *this; - } - }; - - Entry* tbl; - u16 num_entries; - u16 max_entries; // when initialized, = 2**n for faster modulo - HashCompare hashFunc; - - Entry& get_slot(K key) const - { - size_t hash = hashFunc(key); - //ENSURE(max_entries != 0); // otherwise, mask will be incorrect - const size_t mask = max_entries-1; - int stride = 1; // for quadratic probing - for(;;) - { - Entry& e = tbl[hash & mask]; - // empty slot encountered => not found - if(!e.valid) - return e; - // keys are actually equal => found it - if(e.key == key) - return e; - // keep going (quadratic probing) - hash += stride; - stride++; - } - } - - void expand_tbl() - { - // alloc a new table (but don't assign it to unless successful) - Entry* old_tbl = tbl; - tbl = new Entry[max_entries*2]; - if(!tbl) - { - tbl = old_tbl; - throw std::bad_alloc(); - } - - max_entries += max_entries; - // must be set before get_slot - - // newly initialized, nothing to copy - done - if(!old_tbl) - return; - - // re-hash from old table into the new one - for(size_t i = 0; i < max_entries/2u; i++) - { - Entry& e = old_tbl[i]; - if(e.valid) - get_slot(e.key) = e; - } - delete[] old_tbl; - } - - void delete_contents() - { - if(tbl) - { - delete[] tbl; - tbl = 0; - } - } - -public: - - MateiHashTbl() - { - tbl = 0; - num_entries = 0; - max_entries = initial_entries/2; // will be doubled in expand_tbl - //ENSURE(is_pow2(max_entries)); - expand_tbl(); - } - - ~MateiHashTbl() - { - delete_contents(); - } - - void clear() - { - delete_contents(); - num_entries = 0; - // rationale: must not set to 0 because expand_tbl only doubles the size. - // don't keep the previous size because it may have become huge and - // there is no provision for shrinking. - max_entries = initial_entries/2; // will be doubled in expand_tbl - expand_tbl(); - } - - bool contains(const K& key) const - { - return get_slot(key).valid; - } - - T& operator[](const K& key) - { - Entry* slot = &get_slot(key); - if(slot->valid) - { - return slot->value; - } - - // no element exists for this key - insert it into the table - // (this is slightly different from STL::hash_map in that we insert a new element - // on a get for a nonexistent key, but hopefully that's not a problem) - - // if more than 75% full, increase table size and find slot again - if(num_entries*4 >= max_entries*2) - { - expand_tbl(); - slot = &get_slot(key); // find slot again since we expanded - } - - slot->valid = true; - slot->key = key; - num_entries++; - return slot->value; - } - - size_t size() const - { - return num_entries; - } - - // Not an STL iterator, more like a Java one - // Usage: for(HashTable::Iterator it(table); it.valid(); it.advance()) { do stuff to it.key() and it.value() } - class Iterator - { - private: - Entry* pos; - Entry* end; - - public: - Iterator(const MateiHashTbl& ht) - { - pos = ht.tbl; - end = ht.tbl + ht.max_entries; - while(pos < end && !pos->valid) - pos++; - }; - - bool valid() const - { - return pos < end; - } - - void advance() - { - do { - pos++; - } - while(pos < end && !pos->valid); - } - - const K& key() - { - return pos->key; - } - - T& value() - { - return pos->value; - } - }; -}; - - -#endif // #ifndef INCLUDED_ADTS Property changes on: ps/trunk/source/lib/adts.h ___________________________________________________________________ Deleted: svn:eol-style ## -1 +0,0 ## -native \ No newline at end of property Index: ps/trunk/build/premake/premake.lua =================================================================== --- ps/trunk/build/premake/premake.lua (revision 9363) +++ ps/trunk/build/premake/premake.lua (revision 9364) @@ -1,1141 +1,1142 @@ addoption("atlas", "Include Atlas scenario editor packages") addoption("collada", "Include COLLADA packages (requires FCollada library)") addoption("coverage", "Enable code coverage data collection (GCC only)") addoption("aoe3ed", "Include AoE3Ed") addoption("icc", "Use Intel C++ Compiler (Linux only; should use either \"--cc icc\" or --without-pch too, and then set CXX=icpc before calling make)") addoption("outpath", "Location for generated project files") addoption("without-tests", "Disable generation of test projects") addoption("without-pch", "Disable generation and usage of precompiled headers") addoption("with-system-nvtt", "Search standard paths for nvidia-texture-tools library, instead of using bundled copy") addoption("bindir", "Directory for executables (typically '/usr/games'); default is to be relocatable") addoption("datadir", "Directory for data files (typically '/usr/share/games/0ad'); default is ../data/ relative to executable") addoption("libdir", "Directory for libraries (typically '/usr/lib/games/0ad'); default is ./ relative to executable") dofile("functions.lua") dofile("extern_libs.lua") -- detect CPU architecture (simplistic, currently only supports x86 and amd64) arch = "x86" if OS == "windows" then if os.getenv("PROCESSOR_ARCHITECTURE") == "amd64" or os.getenv("PROCESSOR_ARCHITEW6432") == "amd64" then arch = "amd64" end else arch = os.getenv("HOSTTYPE") if arch == "x86_64" then arch = "amd64" else os.execute("gcc -dumpmachine > .gccmachine.tmp") local f = io.open(".gccmachine.tmp", "r") local machine = f:read("*line") f:close() if string.find(machine, "x86_64") == 1 then arch = "amd64" elseif string.find(machine, "i.86") == 1 then arch = "x86" else print("WARNING: Cannot determine architecture from GCC, assuming x86") end end end -- Set up the Project project.name = "pyrogenesis" project.bindir = "../../binaries/system" project.libdir = "../../binaries/system" project.debugdir = "../../binaries/system" if not options["outpath"] then error("You must specify the 'outpath' parameter") end project.path = options["outpath"] project.configs = { "Debug", "Release", "Testing" } if OS == "windows" then project.nasmpath = "../../build/bin/nasm.exe" project.cxxtestpath = "../../build/bin/cxxtestgen.exe" has_broken_pch = false else project.cxxtestpath = "../../build/bin/cxxtestgen.pl" if OS == "linux" and arch == "amd64" then -- Hack for amd64 linux - tell nasm to product 64-bit elf. project.nasmformat = "elf64" elseif OS == "macosx" and arch == "amd64" then project.nasmformat = "macho64" end -- GCC bug (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=10591) - PCH breaks anonymous namespaces -- Fixed in 4.2.0, but we have to disable PCH for earlier versions, else -- it conflicts annoyingly with wx 2.8 headers. -- It's too late to do this test by the time we start compiling the PCH file, so -- do the test in this build script instead (which is kind of ugly - please fix if -- you have a better idea) if not options["icc"] then os.execute("gcc -dumpversion > .gccver.tmp") local f = io.open(".gccver.tmp", "r") major, dot, minor = f:read(1, 1, 1) f:close() major = 0+major -- coerce to number minor = 0+minor has_broken_pch = (major < 4 or (major == 4 and minor < 2)) if has_broken_pch then print("WARNING: Detected GCC <4.2 -- disabling PCH for Atlas (will increase build times)") end end end source_root = "../../../source/" -- default for most projects - overridden by local in others -- Rationale: packages should not have any additional include paths except for -- those required by external libraries. Instead, we should always write the -- full relative path, e.g. #include "maths/Vector3d.h". This avoids confusion -- ("which file is meant?") and avoids enormous include path lists. -- packages: engine static libs, main exe, atlas, atlas frontends, test. -------------------------------------------------------------------------------- -- package helper functions -------------------------------------------------------------------------------- function package_set_target(package_name) -- Note: On Windows, ".exe" is added on the end, on unices the name is used directly package.config["Debug" ].target = package_name.."_dbg" package.config["Testing"].target = package_name.."_test" package.config["Release"].target = package_name local obj_dir_prefix = "obj/"..package_name.."_" package.config["Debug" ].objdir = obj_dir_prefix.."Debug" package.config["Testing"].objdir = obj_dir_prefix.."Test" package.config["Release"].objdir = obj_dir_prefix.."Release" end function package_set_build_flags() package.buildflags = { "with-symbols", "no-edit-and-continue" } if not options["icc"] then -- adds the -Wall compiler flag tinsert(package.buildflags, "extra-warnings") -- this causes far too many warnings/remarks on ICC end -- PremakeWiki says with-symbols and optimize are automatically set for -- Debug and Release builds, respectively. doesn't happen though, so do it manually. package.config["Debug"].defines = { "DEBUG" } package.config["Testing"].buildflags = { "no-runtime-checks" } package.config["Testing"].defines = { "TESTING" } package.config["Release"].buildflags = { "no-runtime-checks", "optimize-speed" } package.config["Release"].defines = { "NDEBUG", "CONFIG_FINAL=1" } -- required for the lowlevel library. must be set from all packages that use it, otherwise it assumes it is -- being used as a DLL (which is currently not the case in 0ad) tinsert(package.defines, "LIB_STATIC_LINK") -- various platform-specific build flags if OS == "windows" then -- use native wchar_t type (not typedef to unsigned short) tinsert(package.buildflags, "native-wchar_t") else -- *nix if options["icc"] then tinsert(package.buildoptions, { "-w1", -- "-Wabi", -- "-Wp64", -- complains about OBJECT_TO_JSVAL which is annoying "-Wpointer-arith", "-Wreturn-type", -- "-Wshadow", "-Wuninitialized", "-Wunknown-pragmas", "-Wunused-function", "-wd1292", -- avoid lots of 'attribute "__nonnull__" ignored' }) tinsert(package.config["Debug"].buildoptions, { "-O0", -- ICC defaults to -O2 }) if OS == "macosx" then tinsert(package.linkoptions, {"-multiply_defined","suppress"}) end else tinsert(package.buildoptions, { -- enable most of the standard warnings "-Wno-switch", -- enumeration value not handled in switch (this is sometimes useful, but results in lots of noise) "-Wno-reorder", -- order of initialization list in constructors (lots of noise) "-Wno-invalid-offsetof", -- offsetof on non-POD types (see comment in renderer/PatchRData.cpp) "-Wextra", "-Wno-missing-field-initializers", -- (this is common in external headers we can't fix) -- add some other useful warnings that need to be enabled explicitly "-Wunused-parameter", "-Wredundant-decls", -- (useful for finding some multiply-included header files) -- "-Wformat=2", -- (useful sometimes, but a bit noisy, so skip it by default) -- "-Wcast-qual", -- (useful for checking const-correctness, but a bit noisy, so skip it by default) "-Wnon-virtual-dtor", -- (sometimes noisy but finds real bugs) "-Wundef", -- (useful for finding macro name typos) -- enable security features (stack checking etc) that shouldn't have -- a significant effect on performance and can catch bugs "-fstack-protector-all", "-D_FORTIFY_SOURCE=2", -- always enable strict aliasing (useful in debug builds because of the warnings) "-fstrict-aliasing", -- do something (?) so that ccache can handle compilation with PCH enabled "-fpch-preprocess", -- enable SSE intrinsics "-msse", -- don't omit frame pointers (for now), because performance will be impacted -- negatively by the way this breaks profilers more than it will be impacted -- positively by the optimisation "-fno-omit-frame-pointer", }) if OS == "linux" then tinsert(package.linkoptions, { "-Wl,--no-undefined", "-Wl,--as-needed", }) end if options["coverage"] then tinsert(package.buildoptions, {"-fprofile-arcs", "-ftest-coverage"}) tinsert(package.links, "gcov") end -- To support intrinsics like __sync_bool_compare_and_swap on x86 -- we need to set -march to something that supports them if arch == "x86" then tinsert(package.buildoptions, "-march=i686") end -- We don't want to require SSE2 everywhere yet, but OS X headers do -- require it (and Intel Macs always have it) so enable it here if OS == "macosx" then tinsert(package.buildoptions, "-msse2") end end tinsert(package.buildoptions, { -- Hide symbols in dynamic shared objects by default, for efficiency and for equivalence with -- Windows - they should be exported explicitly with __attribute__ ((visibility ("default"))) "-fvisibility=hidden", }) -- X11 includes may be installed in one of a gadzillion of three places -- Famous last words: "You can't include too much! ;-)" package.includepaths = { "/usr/X11R6/include/X11", "/usr/X11R6/include", "/usr/include/X11" } package.libpaths = { "/usr/X11R6/lib" } if options["bindir"] then tinsert(package.defines, "INSTALLED_BINDIR=" .. options["bindir"]) end if options["datadir"] then tinsert(package.defines, "INSTALLED_DATADIR=" .. options["datadir"]) end if options["libdir"] then tinsert(package.defines, "INSTALLED_LIBDIR=" .. options["libdir"]) end if OS == "linux" then -- To use our local SpiderMonkey library, it needs to be part of the -- runtime dynamic linker path. Add it with -rpath to make sure it gets found. if options["libdir"] then tinsert(package.linkoptions, {"-Wl,-rpath=" .. options["libdir"]}) else -- Add the executable path: tinsert(package.linkoptions, {"-Wl,-rpath='$$ORIGIN'"}) -- use Makefile escaping of '$' end end end end -- create a package and set the attributes that are common to all packages. function package_create(package_name, target_type) -- Note: don't store in local variable. A global variable needs to -- be set for Premake's use; it is implicitly used in e.g. matchfiles() package = newpackage() package.path = project.path package.language = "c++" package.name = package_name package.kind = target_type package.includepaths = {} package_set_target(package_name) package_set_build_flags() return package end -- extra_params: table including zero or more of the following: -- * no_default_pch: (any type) prevents adding the PCH include dir. -- see setup_static_lib_package() for explanation of this scheme and rationale. -- * extra_files: table of filenames (relative to source_root) to add to project -- * extra_links: table of library names to add to link step function package_add_contents(source_root, rel_source_dirs, rel_include_dirs, extra_params) -- We don't want the VC project to be deeply nested (once for each -- folder in source_root). Therefore, remove the source_root -- directory from the filenames (where those -- names are used by Premake to construct the project tree), but set -- 'trimprefix' (with Premake altered to recognise that) so the project -- will still point to the correct filenames. package.trimprefix = source_root package.files = sourcesfromdirs(source_root, rel_source_dirs) -- Put the project-specific PCH directory at the start of the -- include path, so '#include "precompiled.h"' will look in -- there first if not extra_params["no_default_pch"] then tinsert(package.includepaths, source_root .. "pch/" .. package.name) end -- next is source root dir, for absolute (nonrelative) includes -- (e.g. "lib/precompiled.h") tinsert(package.includepaths, source_root) for i,v in pairs(rel_include_dirs) do tinsert(package.includepaths, source_root .. v) end if extra_params["extra_files"] then for i,v in pairs(extra_params["extra_files"]) do tinsert(package.files, source_root .. v) end end if extra_params["extra_links"] then listconcat(package.links, extra_params["extra_links"]) end end -- Detect and set up PCH for the current package function package_setup_pch(pch_dir, header, source) if OS == "windows" or not options["without-pch"] then package.pchheader = header -- "precompiled.h" package.pchsource = source -- "precompiled.cpp" if pch_dir then tinsert(package.files, { pch_dir..header, pch_dir..source }) end for i,v in pairs(project.configs) do tinsert(package.config[v].defines, "USING_PCH") end end end -------------------------------------------------------------------------------- -- engine static libraries -------------------------------------------------------------------------------- -- the engine is split up into several static libraries. this eases separate -- distribution of those components, reduces dependencies a bit, and can -- also speed up builds. -- more to the point, it is necessary to efficiently support a separate -- test executable that also includes much of the game code. -- names of all static libs created. automatically added to the -- main app project later (see explanation at end of this file) static_lib_names = {} -- set up one of the static libraries into which the main engine code is split. -- extra_params: see package_add_contents(). -- note: rel_source_dirs and rel_include_dirs are relative to global source_root. function setup_static_lib_package (package_name, rel_source_dirs, extern_libs, extra_params) package_create(package_name, "lib") package_add_contents(source_root, rel_source_dirs, {}, extra_params) package_add_extern_libs(extern_libs) if not extra_params["no_default_link"] then tinsert(static_lib_names, package_name) end if OS == "windows" then tinsert(package.buildflags, "no-rtti") end -- Precompiled Headers -- rationale: we need one PCH per static lib, since one global header would -- increase dependencies. To that end, we can either include them as -- "packagedir/precompiled.h", or add "source/PCH/packagedir" to the -- include path and put the PCH there. The latter is better because -- many packages contain several dirs and it's unclear where there the -- PCH should be stored. This way is also a bit easier to use in that -- source files always include "precompiled.h". -- Notes: -- * Visual Assist manages to use the project include path and can -- correctly open these files from the IDE. -- * precompiled.cpp (needed to "Create" the PCH) also goes in -- the abovementioned dir. if not extra_params["no_default_pch"] then pch_dir = source_root.."pch/"..package_name.."/" package_setup_pch(pch_dir, "precompiled.h", "precompiled.cpp") end end -- this is where the source tree is chopped up into static libs. -- can be changed very easily; just copy+paste a new setup_static_lib_package, -- or remove existing ones. static libs are automagically added to -- main_exe link step. function setup_all_libs () -- relative to global source_root. local source_dirs = {} -- names of external libraries used (see libraries_dir comment) local extern_libs = {} source_dirs = { "network", } extern_libs = { "spidermonkey", "enet", "boost", -- dragged in via server->simulation.h->random } setup_static_lib_package("network", source_dirs, extern_libs, {}) source_dirs = { "simulation2", "simulation2/components", "simulation2/helpers", "simulation2/scripting", "simulation2/serialization", "simulation2/system", "simulation2/testcomponents", } extern_libs = { "boost", "opengl", "spidermonkey", } setup_static_lib_package("simulation2", source_dirs, extern_libs, {}) source_dirs = { "scriptinterface", } extern_libs = { "boost", "spidermonkey", "valgrind", } setup_static_lib_package("scriptinterface", source_dirs, extern_libs, {}) source_dirs = { "ps", "ps/scripting", "ps/Network", "ps/GameSetup", "ps/XML", "sound", "scripting", "maths", "maths/scripting", } extern_libs = { "spidermonkey", "sdl", -- key definitions "libxml2", "opengl", "zlib", "boost", "enet", "libcurl", } setup_static_lib_package("engine", source_dirs, extern_libs, {}) source_dirs = { "graphics", "graphics/scripting", "renderer" } extern_libs = { "nvtt", "opengl", "sdl", -- key definitions "spidermonkey", -- for graphics/scripting "boost" } setup_static_lib_package("graphics", source_dirs, extern_libs, {}) source_dirs = { "tools/atlas/GameInterface", "tools/atlas/GameInterface/Handlers" } extern_libs = { "boost", "sdl", -- key definitions "opengl", "spidermonkey" } setup_static_lib_package("atlas", source_dirs, extern_libs, {}) source_dirs = { "gui", "gui/scripting" } if OS == "windows" then -- add JS files to allow VS find-in-solution and VA open-file-in-workspace tinsert(source_dirs, "../binaries/data/mods/public/gui/test") end extern_libs = { "spidermonkey", "sdl", -- key definitions "opengl", "boost" } setup_static_lib_package("gui", source_dirs, extern_libs, {}) source_dirs = { "lib", + "lib/adts", "lib/allocators", "lib/external_libraries", "lib/file", "lib/file/archive", "lib/file/common", "lib/file/io", "lib/file/vfs", "lib/pch", "lib/posix", "lib/res", "lib/res/graphics", "lib/res/sound", "lib/sysdep", "lib/tex" } extern_libs = { "boost", "sdl", "opengl", "libpng", "zlib", "openal", "vorbis", "libjpg", "valgrind", "cxxtest", } -- CPU architecture-specific if arch == "amd64" then tinsert(source_dirs, "lib/sysdep/arch/amd64"); tinsert(source_dirs, "lib/sysdep/arch/x86_x64"); else tinsert(source_dirs, "lib/sysdep/arch/ia32"); tinsert(source_dirs, "lib/sysdep/arch/x86_x64"); end -- OS-specific sysdep_dirs = { linux = { "lib/sysdep/os/linux", "lib/sysdep/os/unix", "lib/sysdep/os/unix/x" }, -- note: RC file must be added to main_exe package. -- note: don't add "lib/sysdep/os/win/aken.cpp" because that must be compiled with the DDK. windows = { "lib/sysdep/os/win", "lib/sysdep/os/win/wposix", "lib/sysdep/os/win/whrt" }, macosx = { "lib/sysdep/os/osx", "lib/sysdep/os/unix" }, } for i,v in pairs(sysdep_dirs[OS]) do tinsert(source_dirs, v); end -- runtime-library-specific if options["target"] == "gnu" then tinsert(source_dirs, "lib/sysdep/rtl/gcc"); else tinsert(source_dirs, "lib/sysdep/rtl/msc"); end setup_static_lib_package("lowlevel", source_dirs, extern_libs, {}) -- CxxTest mock function support extern_libs = { "boost", "cxxtest", } -- 'real' implementations, to be linked against the main executable setup_static_lib_package("mocks_real", {}, extern_libs, { no_default_link = 1, no_default_pch = 1 }) listconcat(package.files, matchfiles(source_root.."mocks/*.h", source_root.."mocks/*_real.cpp")) -- 'test' implementations, to be linked against the test executable setup_static_lib_package("mocks_test", {}, extern_libs, { no_default_link = 1, no_default_pch = 1 }) listconcat(package.files, matchfiles(source_root.."mocks/*.h", source_root.."mocks/*_test.cpp")) end -------------------------------------------------------------------------------- -- main EXE -------------------------------------------------------------------------------- -- used for main EXE as well as test used_extern_libs = { "opengl", "sdl", "libjpg", "libpng", "zlib", "spidermonkey", "libxml2", "openal", "vorbis", "boost", "cxxtest", "comsuppw", "enet", "libcurl", "valgrind", "nvtt", } -- Bundles static libs together with main.cpp and builds game executable. function setup_main_exe () package_create("pyrogenesis", "winexe") -- For VS2005, tell the linker to use the libraries' .obj files instead of -- the .lib, to allow incremental linking. -- (Reduces re-link time from ~20 seconds to ~2 secs) tinsert(package.buildflags, "use-library-dep-inputs") local extra_params = { extra_files = { "main.cpp" }, } package_add_contents(source_root, {}, {}, extra_params) package_add_extern_libs(used_extern_libs) tinsert(package.links, "mocks_real") -- Platform Specifics if OS == "windows" then tinsert(package.files, source_root.."lib/sysdep/os/win/icon.rc") -- from "lowlevel" static lib; must be added here to be linked in tinsert(package.files, source_root.."lib/sysdep/os/win/error_dialog.rc") -- VS2005 generates its own manifest, but earlier ones need us to add it manually if (options["target"] == "vs2002" or options["target"] == "vs2003") then tinsert(package.files, source_root.."lib/sysdep/os/win/manifest.rc") end tinsert(package.buildflags, "no-rtti") -- this seems to be required when using vcbuild but not the IDE (?!) tinsert(package.links, "ws2_32") package.linkoptions = { -- wraps main thread in a __try block(see wseh.cpp). replace with mainCRTStartup if that's undesired. "/ENTRY:wseh_EntryPoint", -- see wstartup.h "/INCLUDE:_wstartup_InitAndRegisterShutdown", -- delay loading of various Windows DLLs (not specific to any of the -- external libraries; those are handled separately) "/DELAYLOAD:ws2_32.dll", -- allow manual unload of delay-loaded DLLs "/DELAY:UNLOAD" } elseif OS == "linux" then -- Libraries tinsert(package.links, { "fam", -- Utilities "rt", -- Dynamic libraries (needed for linking for gold) "dl", }) -- Threading support tinsert(package.buildoptions, "-pthread") tinsert(package.linkoptions, "-pthread") -- For debug_resolve_symbol package.config["Debug"].linkoptions = { "-rdynamic" } package.config["Testing"].linkoptions = { "-rdynamic" } elseif OS == "macosx" then -- Libraries tinsert(package.links, { -- Utilities "pthread" }) end end -------------------------------------------------------------------------------- -- atlas -------------------------------------------------------------------------------- -- setup a typical Atlas component package -- extra_params: as in package_add_contents; also zero or more of the following: -- * pch: (any type) set precompiled.h and .cpp as PCH function setup_atlas_package(package_name, target_type, rel_source_dirs, rel_include_dirs, extern_libs, extra_params) local source_root = "../../../source/tools/atlas/" .. package_name .. "/" package_create(package_name, target_type) -- Don't add the default 'sourceroot/pch/projectname' for finding PCH files extra_params["no_default_pch"] = 1 package_add_contents(source_root, rel_source_dirs, rel_include_dirs, extra_params) package_add_extern_libs(extern_libs) if extra_params["pch"] then package_setup_pch(nil, "precompiled.h", "precompiled.cpp"); end if options["aoe3ed"] then tinsert(package.defines, "USE_AOE3ED") end -- Platform Specifics if OS == "windows" then tinsert(package.defines, "_UNICODE") -- Link to required libraries package.links = { "winmm", "comctl32", "rpcrt4", "delayimp", "ws2_32" } -- required to use WinMain() on Windows, otherwise will default to main() tinsert(package.buildflags, "no-main") if extra_params["extra_links"] then listconcat(package.links, extra_params["extra_links"]) end elseif OS == "linux" then tinsert(package.buildoptions, "-rdynamic") tinsert(package.buildoptions, "-fPIC") tinsert(package.linkoptions, "-fPIC") tinsert(package.linkoptions, "-rdynamic") if extra_params["no_unused_warnings"] then if not options["icc"] then tinsert(package.buildoptions, "-Wno-unused-parameter") end end end end -- build all Atlas component packages function setup_atlas_packages() setup_atlas_package("AtlasObject", "lib", { -- src "" },{ -- include },{ -- extern_libs "libxml2", "wxwidgets" },{ -- extra_params }) setup_atlas_package("AtlasScript", "lib", { -- src "" },{ -- include ".." },{ -- extern_libs "boost", "spidermonkey", "valgrind", "wxwidgets", },{ -- extra_params }) setup_atlas_package("wxJS", "lib", { -- src "", "common", "ext", "gui", "gui/control", "gui/event", "gui/misc", "io", },{ -- include },{ -- extern_libs "spidermonkey", "wxwidgets" },{ -- extra_params pch = (not has_broken_pch), no_unused_warnings = 1, -- wxJS has far too many and we're never going to fix them, so just ignore them }) atlas_src = { "ActorEditor", "ColourTester", "CustomControls/Buttons", "CustomControls/Canvas", "CustomControls/ColourDialog", "CustomControls/DraggableListCtrl", "CustomControls/EditableListCtrl", "CustomControls/FileHistory", "CustomControls/HighResTimer", "CustomControls/NewDialog", "CustomControls/SnapSplitterWindow", "CustomControls/VirtualDirTreeCtrl", "CustomControls/Windows", "ErrorReporter", "General", "General/VideoRecorder", "Misc", "ScenarioEditor", "ScenarioEditor/Sections/Common", "ScenarioEditor/Sections/Cinematic", "ScenarioEditor/Sections/Environment", "ScenarioEditor/Sections/Trigger", "ScenarioEditor/Tools", "ScenarioEditor/Tools/Common", } atlas_extra_links = { "AtlasObject", "AtlasScript", "wxJS", } if options["aoe3ed"] then tinsert(atlas_src, "ArchiveViewer") tinsert(atlas_src, "FileConverter") tinsert(atlas_extra_links, "DatafileIO") tinsert(atlas_extra_links, "xerces-c") end setup_atlas_package("AtlasUI", "dll", atlas_src, { -- include "..", "CustomControls", "Misc" },{ -- extern_libs "boost", "comsuppw", "devil", --"ffmpeg", -- disabled for now because it causes too many build difficulties "libxml2", "sdl", -- key definitions "spidermonkey", "wxwidgets", "x11", "zlib", },{ -- extra_params pch = (not has_broken_pch), extra_links = atlas_extra_links, extra_files = { "Misc/atlas.rc" } }) if options["aoe3ed"] then setup_atlas_package("DatafileIO", "lib", { -- src "", "BAR", "DDT", "SCN", "Stream", "XMB" },{ -- include },{ -- extern_libs "devil", "xerces", "zlib" },{ -- extra_params pch = 1, }) end end -- Atlas 'frontend' tool-launching packages function setup_atlas_frontend_package (package_name) package_create(package_name, "winexe") package_add_extern_libs({ "spidermonkey", }) local source_root = "../../../source/tools/atlas/AtlasFrontends/" package.files = { source_root..package_name..".cpp", source_root..package_name..".rc" } package.trimprefix = source_root package.includepaths = { source_root .. ".." } -- Platform Specifics if OS == "windows" then tinsert(package.defines, "_UNICODE") -- required to use WinMain() on Windows, otherwise will default to main() tinsert(package.buildflags, "no-main") else -- Non-Windows, = Unix if options["aoe3ed"] then tinsert(package.links, "DatafileIO") end tinsert(package.links, "AtlasObject") end tinsert(package.links, "AtlasUI") end function setup_atlas_frontends() setup_atlas_frontend_package("ActorEditor") setup_atlas_frontend_package("ColourTester") if options["aoe3ed"] then setup_atlas_frontend_package("ArchiveViewer") setup_atlas_frontend_package("FileConverter") end end -------------------------------------------------------------------------------- -- collada -------------------------------------------------------------------------------- function setup_collada_package(package_name, target_type, rel_source_dirs, rel_include_dirs, extern_libs, extra_params) package_create(package_name, target_type) -- Don't add the default 'sourceroot/pch/projectname' for finding PCH files extra_params["no_default_pch"] = 1 package_add_contents(source_root, rel_source_dirs, rel_include_dirs, extra_params) package_add_extern_libs(extern_libs) if extra_params["pch"] then package_setup_pch(nil, "precompiled.h", "precompiled.cpp"); end -- Platform Specifics if OS == "windows" then -- required to use WinMain() on Windows, otherwise will default to main() tinsert(package.buildflags, "no-main") if extra_params["extra_links"] then listconcat(package.links, extra_params["extra_links"]) end end if OS == "linux" then tinsert(package.defines, "LINUX"); -- FCollada is not aliasing-safe, so disallow dangerous optimisations -- (TODO: It'd be nice to fix FCollada, but that looks hard) tinsert(package.buildoptions, "-fno-strict-aliasing") tinsert(package.buildoptions, "-rdynamic") tinsert(package.linkoptions, "-rdynamic") elseif OS == "macosx" then -- define MACOS-something? -- On OSX, fcollada uses a few utility functions from coreservices tinsert(package.linkoptions, "-framework CoreServices") end end -- build all Collada component packages function setup_collada_packages() setup_collada_package("Collada", "dll", { -- src "collada" },{ -- include },{ -- extern_libs "fcollada", "dl", "libxml2", },{ -- extra_params pch = 1, }) end -------------------------------------------------------------------------------- -- tests -------------------------------------------------------------------------------- function get_all_test_files(root, src_files, hdr_files) -- note: lua doesn't have any directory handling functions at all, ugh. -- premake's matchrecursive on patterns like *tests*.h doesn't work - -- apparently it applies them to filenames, not the complete path. -- our workaround is to enumerate all files and manually filter out the -- desired */tests/* files. this is a bit slow, but hey. local all_files = matchrecursive(root .. "*.h") for i,v in pairs(all_files) do -- header file in subdirectory test if string.sub(v, -2) == ".h" and string.find(v, "/tests/") then -- don't include sysdep tests on the wrong sys -- don't include Atlas tests unless Atlas is being built if not (string.find(v, "/sysdep/os/win/") and OS ~= "windows") and not (string.find(v, "/tools/atlas/") and not options["atlas"]) then tinsert(hdr_files, v) -- add the corresponding source file immediately, instead of -- waiting for it to appear after cxxtestgen. this avoids -- having to recreate workspace 2x after adding a test. tinsert(src_files, string.sub(v, 1, -3) .. ".cpp") end end end end function setup_tests() local src_files = {} local hdr_files = {} get_all_test_files(source_root, src_files, hdr_files) package_create("test_gen", "cxxtestgen") package.files = hdr_files package.rootfile = source_root .. "test_root.cpp" package.testoptions = "--have-std" package.rootoptions = "--have-std" if OS == "windows" then package.rootoptions = package.rootoptions .. " --gui=PsTestWrapper --runner=Win32ODSPrinter" else package.rootoptions = package.rootoptions .. " --gui=PsTestWrapper --runner=ErrorPrinter" end -- precompiled headers - the header is added to all generated .cpp files -- note that the header isn't actually precompiled here, only #included -- so that the build stage can use it as a precompiled header. include = " --include=precompiled.h" package.rootoptions = package.rootoptions .. include package.testoptions = package.testoptions .. include tinsert(package.buildflags, "no-manifest") package_create("test", "winexe") links = static_lib_names tinsert(links, "test_gen") if options["atlas"] then tinsert(links, "AtlasObject") end extra_params = { extra_files = { "test_root.cpp", "test_setup.cpp" }, extra_links = links, } package_add_contents(source_root, {}, {}, extra_params) -- note: these are not relative to source_root and therefore can't be included via package_add_contents. listconcat(package.files, src_files) package_add_extern_libs(used_extern_libs) tinsert(package.links, "mocks_test") if OS == "windows" then -- from "lowlevel" static lib; must be added here to be linked in tinsert(package.files, source_root.."lib/sysdep/os/win/error_dialog.rc") tinsert(package.buildflags, "no-rtti") -- this seems to be required when using vcbuild but not the IDE (?!) tinsert(package.links, "ws2_32") -- see wstartup.h tinsert(package.linkoptions, "/INCLUDE:_wstartup_InitAndRegisterShutdown") elseif OS == "linux" then tinsert(package.links, { "fam", -- Utilities "rt", -- Dynamic libraries (needed for linking for gold) "dl", }) -- Threading support tinsert(package.buildoptions, "-pthread") tinsert(package.linkoptions, "-pthread") -- For debug_resolve_symbol package.config["Debug"].linkoptions = { "-rdynamic" } package.config["Testing"].linkoptions = { "-rdynamic" } tinsert(package.includepaths, source_root .. "pch/test/") end package_setup_pch( source_root .. "pch/test/", "precompiled.h", "precompiled.cpp"); tinsert(package.buildflags, "use-library-dep-inputs") end -- must come first, so that VC sets it as the default project and therefore -- allows running via F5 without the "where is the EXE" dialog. setup_main_exe() -- save package global variable for later (will be overwritten by setup_all_libs) main_exe_package = package setup_all_libs() -- HACK: add the static libs to the main EXE project. only now (after -- setup_all_libs has run) are the lib names known. cannot move -- setup_main_exe to run after setup_all_libs (see comment above). -- we also don't want to hardcode the names - that would require more -- work when changing the static lib breakdown. listconcat(main_exe_package.links, static_lib_names) if options["atlas"] then setup_atlas_packages() setup_atlas_frontends() end if options["collada"] then setup_collada_packages() end if not options["without-tests"] then setup_tests() end Index: ps/trunk/source/ps/Profile.h =================================================================== --- ps/trunk/source/ps/Profile.h (revision 9363) +++ ps/trunk/source/ps/Profile.h (revision 9364) @@ -1,197 +1,197 @@ /* Copyright (C) 2011 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 2 of the License, or * (at your option) any later version. * * 0 A.D. is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with 0 A.D. If not, see . */ /* * GPG3-style hierarchical profiler */ #ifndef INCLUDED_PROFILE #define INCLUDED_PROFILE #include -#include "lib/adts.h" +#include "lib/adts/ring_buf.h" #include "ps/Singleton.h" #include "ps/ThreadUtil.h" #define PROFILE_AMORTIZE_FRAMES 30 #define PROFILE_AMORTIZE_TURNS 1 class CProfileManager; class CProfileNodeTable; class CStr8; class CStrW; class CProfileNode { friend class CProfileManager; friend class CProfileNodeTable; const char* name; int calls_frame_current; int calls_turn_current; RingBuf calls_per_frame; RingBuf calls_per_turn; double time_frame_current; double time_turn_current; RingBuf time_per_frame; RingBuf time_per_turn; long mallocs_frame_current; long mallocs_turn_current; RingBuf mallocs_per_frame; RingBuf mallocs_per_turn; double start; long start_mallocs; int recursion; CProfileNode* parent; std::vector children; std::vector script_children; CProfileNodeTable* display_table; public: typedef std::vector::iterator profile_iterator; typedef std::vector::const_iterator const_profile_iterator; CProfileNode( const char* name, CProfileNode* parent ); ~CProfileNode(); const char* GetName() const { return name; } double GetFrameCalls() const; double GetFrameTime() const; double GetTurnCalls() const; double GetTurnTime() const; double GetFrameMallocs() const; double GetTurnMallocs() const; const CProfileNode* GetChild( const char* name ) const; const CProfileNode* GetScriptChild( const char* name ) const; const std::vector* GetChildren() const { return( &children ); } const std::vector* GetScriptChildren() const { return( &script_children ); } bool CanExpand(); CProfileNode* GetChild( const char* name ); CProfileNode* GetScriptChild( const char* name ); CProfileNode* GetParent() const { return( parent ); } // Resets timing information for this node and all its children void Reset(); // Resets frame timings for this node and all its children void Frame(); // Resets turn timings for this node and all its children void Turn(); // Enters the node void Call(); // Leaves the node. Returns true if the node has actually been left bool Return(); }; class CProfileManager : public Singleton { CProfileNode* root; CProfileNode* current; bool needs_structural_reset; void PerformStructuralReset(); public: CProfileManager(); ~CProfileManager(); // Begins timing for a named subsection void Start( const char* name ); void StartScript( const char* name ); // Ends timing for the current subsection void Stop(); // Resets all timing information void Reset(); // Resets frame timing information void Frame(); // Resets turn timing information // (Must not be called before Frame) void Turn(); // Resets absolutely everything, at the end of this frame void StructuralReset(); inline const CProfileNode* GetCurrent() { return( current ); } inline const CProfileNode* GetRoot() { return( root ); } }; #define g_Profiler CProfileManager::GetSingleton() class CProfileSample { public: CProfileSample( const char* name ) { if (CProfileManager::IsInitialised()) { // The profiler is only safe to use on the main thread ENSURE(ThreadUtil::IsMainThread()); g_Profiler.Start( name ); } } ~CProfileSample() { if (CProfileManager::IsInitialised()) g_Profiler.Stop(); } }; class CProfileSampleScript { public: CProfileSampleScript( const char* name ) { if (CProfileManager::IsInitialised()) { // The profiler is only safe to use on the main thread, // but scripts get run on other threads too so we need to // conditionally enable the profiler. // (This usually only gets used in debug mode so performance // doesn't matter much.) if (ThreadUtil::IsMainThread()) g_Profiler.StartScript( name ); } } ~CProfileSampleScript() { if (CProfileManager::IsInitialised()) if (ThreadUtil::IsMainThread()) g_Profiler.Stop(); } }; // Put a PROFILE( xyz ) block at the start of all code to be profiled. // Profile blocks last until the end of the containing scope. #define PROFILE( name ) CProfileSample __profile( name ) // Cheat a bit to make things slightly easier on the user #define PROFILE_START( name ) { CProfileSample __profile( name ) #define PROFILE_END( name ) } #endif // INCLUDED_PROFILE Index: ps/trunk/source/lib/adts/bit_buf.h =================================================================== --- ps/trunk/source/lib/adts/bit_buf.h (nonexistent) +++ ps/trunk/source/lib/adts/bit_buf.h (revision 9364) @@ -0,0 +1,64 @@ +/* Copyright (c) 2011 Wildfire Games + * + * 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. + */ + +/* + * FIFO bit queue + */ + +#ifndef INCLUDED_ADTS_BIT_BUF +#define INCLUDED_ADTS_BIT_BUF + +#include "lib/bits.h" + +struct BitBuf +{ + uintptr_t buf; + uintptr_t cur; // bit to be appended (toggled by add()) + size_t len; // |buf| [bits] + + void reset() + { + buf = 0; + cur = 0; + len = 0; + } + + // toggle current bit if desired, and add to buffer (new bit is LSB) + void add(uintptr_t toggle) + { + cur ^= toggle; + buf <<= 1; + buf |= cur; + len++; + } + + // extract LS n bits + size_t extract(uintptr_t n) + { + const uintptr_t bits = buf & bit_mask(n); + buf >>= n; + + return bits; + } +}; + +#endif // #ifndef INCLUDED_ADTS_BIT_BUF Index: ps/trunk/source/lib/adts/cache_adt.h =================================================================== --- ps/trunk/source/lib/adts/cache_adt.h (nonexistent) +++ ps/trunk/source/lib/adts/cache_adt.h (revision 9364) @@ -0,0 +1,753 @@ +/* Copyright (c) 2010 Wildfire Games + * + * 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. + */ + +/* + * Customizable cache data structure. + */ + +#ifndef INCLUDED_CACHE_ADT +#define INCLUDED_CACHE_ADT + +#include + +#include +#include +#include // std::priority_queue + +#if CONFIG_ENABLE_BOOST +# include +# define MAP boost::unordered_map +#else +# define MAP stdext::hash_map +#endif + +/* +Cache for items of variable size and value/"cost". +underlying displacement algorithm is pluggable; default is "Landlord". + +template reference: +Entry provides size, cost, credit and credit_density(). + rationale: + - made a template instead of exposing Cache::Entry because + that would drag a lot of stuff out of Cache. + - calculates its own density since that entails a Divider functor, + which requires storage inside Entry. +Entries is a collection with iterator and begin()/end() and + "static Entry& entry_from_it(iterator)". + rationale: + - STL map has pair as its value_type, so this + function would return it->second. however, we want to support + other container types (where we'd just return *it). +Manager is a template parameterized on typename Key and class Entry. + its interface is as follows: + + // is the cache empty? + bool empty() const; + + // add (key, entry) to cache. + void add(const Key& key, const Entry& entry); + + // if the entry identified by is not in cache, return false; + // otherwise return true and pass back a pointer to it. + bool find(const Key& key, const Entry** pentry) const; + + // remove an entry from cache, which is assumed to exist! + // this makes sense because callers will typically first use find() to + // return info about the entry; this also checks if present. + void remove(const Key& key); + + // mark as just accessed for purpose of cache management. + // it will tend to be kept in cache longer. + void on_access(Entry& entry); + + // caller's intent is to remove the least valuable entry. + // in implementing this, you have the latitude to "shake loose" + // several entries (e.g. because their 'value' is equal). + // they must all be push_back-ed into the list; Cache will dole + // them out one at a time in FIFO order to callers. + // + // rationale: + // - it is necessary for callers to receive a copy of the + // Entry being evicted - e.g. file_cache owns its items and + // they must be passed back to allocator when evicted. + // - e.g. Landlord can potentially see several entries become + // evictable in one call to remove_least_valuable. there are + // several ways to deal with this: + // 1) generator interface: we return one of { empty, nevermind, + // removed, remove-and-call-again }. this greatly complicates + // the call site. + // 2) return immediately after finding an item to evict. + // this changes cache behavior - entries stored at the + // beginning would be charged more often (unfair). + // resuming charging at the next entry doesn't work - this + // would have to be flushed when adding, at which time there + // is no provision for returning any items that may be evicted. + // 3) return list of all entries "shaken loose". this incurs + // frequent mem allocs, which can be alleviated via suballocator. + // note: an intrusive linked-list doesn't make sense because + // entries to be returned need to be copied anyway (they are + // removed from the manager's storage). + void remove_least_valuable(std::list& entry_list) +*/ + + +// +// functors to calculate minimum credit density (MCD) +// + +// MCD is required for the Landlord algorithm's evict logic. +// [Young02] calls it '\delta'. + +// scan over all entries and return MCD. +template float ll_calc_min_credit_density(const Entries& entries) +{ + float min_credit_density = FLT_MAX; + for(typename Entries::const_iterator it = entries.begin(); it != entries.end(); ++it) + { + const float credit_density = Entries::entry_from_it(it).credit_density(); + min_credit_density = std::min(min_credit_density, credit_density); + } + return min_credit_density; +} + +// note: no warning is given that the MCD entry is being removed! +// (reduces overhead in remove_least_valuable) +// these functors must account for that themselves (e.g. by resetting +// their state directly after returning MCD). + +// determine MCD by scanning over all entries. +// tradeoff: O(N) time complexity, but all notify* calls are no-ops. +template +class McdCalc_Naive +{ +public: + void notify_added(const Entry&) const {} + void notify_decreased(const Entry&) const {} + void notify_impending_increase_or_remove(const Entry&) const {} + void notify_increased_or_removed(const Entry&) const {} + float operator()(const Entries& entries) const + { + const float mcd = ll_calc_min_credit_density(entries); + return mcd; + } +}; + +// cache previous MCD and update it incrementally (when possible). +// tradeoff: amortized O(1) time complexity, but notify* calls must +// perform work whenever something in the cache changes. +template +class McdCalc_Cached +{ +public: + McdCalc_Cached() : min_credit_density(FLT_MAX), min_valid(false) {} + + void notify_added(const Entry& entry) + { + // when adding a new item, the minimum credit density can only + // decrease or remain the same; acting as if entry's credit had + // been decreased covers both cases. + notify_decreased(entry); + } + + void notify_decreased(const Entry& entry) + { + min_credit_density = std::min(min_credit_density, entry.credit_density()); + } + + void notify_impending_increase_or_remove(const Entry& entry) + { + // remember if this entry had the smallest density + is_min_entry = feq(min_credit_density, entry.credit_density()); + } + + void notify_increased_or_removed(const Entry& UNUSED(entry)) + { + // .. it did and was increased or removed. we must invalidate + // MCD and recalculate it next time. + if(is_min_entry) + { + min_valid = false; + min_credit_density = -1.0f; + } + } + + float operator()(const Entries& entries) + { + if(min_valid) + { + // the entry that has MCD will be removed anyway by caller; + // we need to invalidate here because they don't call + // notify_increased_or_removed. + min_valid = false; + return min_credit_density; + } + + // this is somewhat counterintuitive. since we're calculating + // MCD directly, why not mark our cached version of it valid + // afterwards? reason is that our caller will remove the entry with + // MCD, so it'll be invalidated anyway. + // instead, our intent is to calculate MCD for the *next time*. + const float ret = ll_calc_min_credit_density(entries); + min_valid = true; + min_credit_density = FLT_MAX; + return ret; + } + +private: + float min_credit_density; + bool min_valid; + + // temporary flag set by notify_impending_increase_or_remove + bool is_min_entry; +}; + + +// +// Landlord cache management policy: see [Young02]. +// + +// in short, each entry has credit initially set to cost. when wanting to +// remove an item, all are charged according to MCD and their size; +// entries are evicted if their credit is exhausted. accessing an entry +// restores "some" of its credit. +template class McdCalc = McdCalc_Cached> +class Landlord +{ +public: + bool empty() const + { + return map.empty(); + } + + void add(const Key& key, const Entry& entry) + { + // adapter for add_ (which returns an iterator) + (void)add_(key, entry); + } + + bool find(const Key& key, const Entry** pentry) const + { + MapCIt it = map.find(key); + if(it == map.end()) + return false; + *pentry = &it->second; + return true; + } + + void remove(const Key& key) + { + MapIt it = map.find(key); + // note: don't complain if not in the cache: this happens after + // writing a file and invalidating its cache entry, which may + // or may not exist. + if(it != map.end()) + remove_(it); + } + + void on_access(Entry& entry) + { + mcd_calc.notify_impending_increase_or_remove(entry); + + // Landlord algorithm calls for credit to be reset to anything + // between its current value and the cost. + const float gain = 0.75f; // restore most credit + entry.credit = gain*entry.cost + (1.0f-gain)*entry.credit; + + mcd_calc.notify_increased_or_removed(entry); + } + + void remove_least_valuable(std::list& entry_list) + { + // we are required to evict at least one entry. one iteration + // ought to suffice, due to definition of min_credit_density and + // tolerance; however, we provide for repeating if necessary. +again: + + // messing with this (e.g. raising if tiny) would result in + // different evictions than Landlord_Lazy, which is unacceptable. + // nor is doing so necessary: if mcd is tiny, so is credit. + const float min_credit_density = mcd_calc(map); + ENSURE(min_credit_density > 0.0f); + + for(MapIt it = map.begin(); it != map.end();) // no ++it + { + Entry& entry = it->second; + + charge(entry, min_credit_density); + if(should_evict(entry)) + { + entry_list.push_back(entry); + + // annoying: we have to increment before erasing + MapIt it_to_remove = it++; + map.erase(it_to_remove); + } + else + { + mcd_calc.notify_decreased(entry); + ++it; + } + } + + if(entry_list.empty()) + goto again; + } + +protected: + class Map : public MAP + { + public: + static Entry& entry_from_it(typename Map::iterator it) { return it->second; } + static const Entry& entry_from_it(typename Map::const_iterator it) { return it->second; } + }; + typedef typename Map::iterator MapIt; + typedef typename Map::const_iterator MapCIt; + Map map; + + // add entry and return iterator pointing to it. + MapIt add_(const Key& key, const Entry& entry) + { + typedef std::pair PairIB; + typename Map::value_type val = std::make_pair(key, entry); + PairIB ret = map.insert(val); + ENSURE(ret.second); // must not already be in map + + mcd_calc.notify_added(entry); + + return ret.first; + } + + // remove entry (given by iterator) directly. + void remove_(MapIt it) + { + const Entry& entry = it->second; + mcd_calc.notify_impending_increase_or_remove(entry); + mcd_calc.notify_increased_or_removed(entry); + map.erase(it); + } + + void charge(Entry& entry, float delta) + { + entry.credit -= delta * entry.size; + + // don't worry about entry.size being 0 - if so, cost + // should also be 0, so credit will already be 0 anyway. + } + + // for each entry, 'charge' it (i.e. reduce credit by) delta * its size. + // delta is typically MCD (see above); however, several such updates + // may be lumped together to save time. Landlord_Lazy does this. + void charge_all(float delta) + { + for(MapIt it = map.begin(); it != map.end(); ++it) + { + Entry& entry = it->second; + entry.credit -= delta * entry.size; + if(!should_evict(entry)) + mcd_calc.notify_decreased(entry); + } + } + + // is entry's credit exhausted? if so, it should be evicted. + bool should_evict(const Entry& entry) + { + // we need a bit of leeway because density calculations may not + // be exact. choose value carefully: must not be high enough to + // trigger false positives. + return entry.credit < 0.0001f; + } + +private: + McdCalc mcd_calc; +}; + +// Cache manger policies. (these are partial specializations of Landlord, +// adapting it to the template params required by Cache) +template class Landlord_Naive : public Landlord {}; +template class Landlord_Cached: public Landlord {}; + +// variant of Landlord that adds a priority queue to directly determine +// which entry to evict. this allows lumping several charge operations +// together and thus reduces iteration over all entries. +// tradeoff: O(logN) removal (instead of N), but additional O(N) storage. +template +class Landlord_Lazy : public Landlord_Naive +{ + typedef typename Landlord_Naive::Map Map; + typedef typename Landlord_Naive::MapIt MapIt; + typedef typename Landlord_Naive::MapCIt MapCIt; + +public: + Landlord_Lazy() { pending_delta = 0.0f; } + + void add(const Key& key, const Entry& entry) + { + // we must apply pending_delta now - otherwise, the existing delta + // would later be applied to this newly added item (incorrect). + commit_pending_delta(); + + MapIt it = Parent::add_(key, entry); + pri_q.push(it); + } + + void remove(const Key& key) + { + Parent::remove(key); + + // reconstruct pri_q from current map. this is slow (N*logN) and + // could definitely be done better, but we don't bother since + // remove is a very rare operation (e.g. invalidating entries). + while(!pri_q.empty()) + pri_q.pop(); + for(MapCIt it = this->map.begin(); it != this->map.end(); ++it) + pri_q.push(it); + } + + void on_access(Entry& entry) + { + Parent::on_access(entry); + + // entry's credit was changed. we now need to reshuffle the + // pri queue to reflect this. + pri_q.ensure_heap_order(); + } + + void remove_least_valuable(std::list& entry_list) + { + MapIt least_valuable_it = pri_q.top(); pri_q.pop(); + Entry& entry = Map::entry_from_it(least_valuable_it); + + entry_list.push_back(entry); + + // add to pending_delta the MCD that would have resulted + // if removing least_valuable_it normally. + // first, calculate actual credit (i.e. apply pending_delta to + // this entry); then add the resulting density to pending_delta. + entry.credit -= pending_delta*entry.size; + const float credit_density = entry.credit_density(); + ENSURE(credit_density > 0.0f); + pending_delta += credit_density; + + Parent::remove_(least_valuable_it); + } + +private: + typedef Landlord_Naive Parent; + + // sort iterators by credit_density of the Entry they reference. + struct CD_greater + { + bool operator()(MapIt it1, MapIt it2) const + { + return Map::entry_from_it(it1).credit_density() > + Map::entry_from_it(it2).credit_density(); + } + }; + // wrapper on top of priority_queue that allows 'heap re-sift' + // (see on_access). + // notes: + // - greater comparator makes pri_q.top() the one with + // LEAST credit_density, which is what we want. + // - deriving from an STL container is a bit dirty, but we need this + // to get at the underlying data (priority_queue interface is not + // very capable). + class PriQ: public std::priority_queue, CD_greater> + { + public: + void ensure_heap_order() + { + // TODO: this is actually N*logN - ouch! that explains high + // CPU cost in profile. this is called after only 1 item has + // changed, so a logN "sift" operation ought to suffice. + // that's not supported by the STL heap functions, so we'd + // need a better implementation. pending.. + std::make_heap(this->c.begin(), this->c.end(), this->comp); + } + }; + PriQ pri_q; + + // delta values that have accumulated over several + // remove_least_valuable() calls. applied during add(). + float pending_delta; + + void commit_pending_delta() + { + if(pending_delta > 0.0f) + { + this->charge_all(pending_delta); + pending_delta = 0.0f; + + // we've changed entry credit, so the heap order *may* have been + // violated; reorder the pri queue. (I don't think so, + // due to definition of delta, but we'll play it safe) + pri_q.ensure_heap_order(); + } + } +}; + + +// +// functor that implements division of first arg by second +// + +// this is used to calculate credit_density(); performance matters +// because this is called for each entry during each remove operation. + +// floating-point division (fairly slow) +class Divider_Naive +{ +public: + Divider_Naive() {} // needed for default CacheEntry ctor + Divider_Naive(float UNUSED(x)) {} + float operator()(float val, float divisor) const + { + return val / divisor; + } +}; + +// caches reciprocal of divisor and multiplies by that. +// tradeoff: only 4 clocks (instead of 20), but 4 bytes extra per entry. +class Divider_Recip +{ + float recip; +public: + Divider_Recip() {} // needed for default CacheEntry ctor + Divider_Recip(float x) { recip = 1.0f / x; } + float operator()(float val, float UNUSED(divisor)) const + { + return val * recip; + } +}; + +// TODO: use SSE/3DNow RCP instruction? not yet, because not all systems +// support it and overhead of detecting this support eats into any gains. + +// initial implementation for testing purposes; quite inefficient. +template +class LRU +{ +public: + bool empty() const + { + return lru.empty(); + } + + void add(const Key& key, const Entry& entry) + { + lru.push_back(KeyAndEntry(key, entry)); + } + + bool find(const Key& key, const Entry** pentry) const + { + CIt it = std::find_if(lru.begin(), lru.end(), KeyEq(key)); + if(it == lru.end()) + return false; + *pentry = &it->entry; + return true; + } + + void remove(const Key& key) + { + std::remove_if(lru.begin(), lru.end(), KeyEq(key)); + } + + void on_access(Entry& entry) + { + for(It it = lru.begin(); it != lru.end(); ++it) + { + if(&entry == &it->entry) + { + add(it->key, it->entry); + lru.erase(it); + return; + } + } + ENSURE(0); // entry not found in list + } + + void remove_least_valuable(std::list& entry_list) + { + entry_list.push_back(lru.front().entry); + lru.pop_front(); + } + +private: + struct KeyAndEntry + { + Key key; + Entry entry; + KeyAndEntry(const Key& key_, const Entry& entry_) + : key(key_), entry(entry_) {} + }; + class KeyEq + { + Key key; + public: + KeyEq(const Key& key_) : key(key_) {} + bool operator()(const KeyAndEntry& ke) const + { + return ke.key == key; + } + }; + + typedef std::list List; + typedef typename List::iterator It; + typedef typename List::const_iterator CIt; + List lru; +}; + + +// this is applicable to all cache management policies and stores all +// required information. a Divider functor is used to implement +// division for credit_density. +template struct CacheEntry +{ + Item item; + size_t size; + size_t cost; + float credit; + + Divider divider; + + // needed for mgr.remove_least_valuable's entry_copy + CacheEntry() + { + } + + CacheEntry(const Item& item_, size_t size_, size_t cost_) + : item(item_), divider((float)size_) + { + size = size_; + cost = cost_; + credit = (float)cost; + + // else divider will fail + ENSURE(size != 0); + } + + float credit_density() const + { + return divider(credit, (float)size); + } +}; + + +// +// Cache +// + +template +< +typename Key, typename Item, +// see documentation above for Manager's interface. +template class Manager = Landlord_Cached, +class Divider = Divider_Naive +> +class Cache +{ +public: + Cache() : mgr() {} + + void add(const Key& key, const Item& item, size_t size, size_t cost) + { + return mgr.add(key, Entry(item, size, cost)); + } + + // remove the entry identified by . expected usage is to check + // if present and determine size via retrieve(), so no need for + // error checking. + // useful for invalidating single cache entries. + void remove(const Key& key) + { + mgr.remove(key); + } + + // if there is no entry for in the cache, return false. + // otherwise, return true and pass back item and (optionally) size. + // + // if refill_credit (default), the cache manager 'rewards' this entry, + // tending to keep it in cache longer. this parameter is not used in + // normal operation - it's only for special cases where we need to + // make an end run around the cache accounting (e.g. for cache simulator). + bool retrieve(const Key& key, Item& item, size_t* psize = 0, bool refill_credit = true) + { + const Entry* entry; + if(!mgr.find(key, &entry)) + return false; + + item = entry->item; + if(psize) + *psize = entry->size; + + if(refill_credit) + mgr.on_access((Entry&)*entry); + + return true; + } + + bool peek(const Key& key, Item& item, size_t* psize = 0) + { + return retrieve(key, item, psize, false); + } + + // toss out the least valuable entry. return false if cache is empty, + // otherwise true and (optionally) pass back its item and size. + bool remove_least_valuable(Item* pItem = 0, size_t* pSize = 0) + { + // as an artefact of the cache eviction policy, several entries + // may be "shaken loose" by one call to remove_least_valuable. + // we cache them in a list to disburden callers (they always get + // exactly one). + if(entries_awaiting_eviction.empty()) + { + if(empty()) + return false; + + mgr.remove_least_valuable(entries_awaiting_eviction); + ENSURE(!entries_awaiting_eviction.empty()); + } + + const Entry& entry = entries_awaiting_eviction.front(); + if(pItem) + *pItem = entry.item; + if(pSize) + *pSize = entry.size; + entries_awaiting_eviction.pop_front(); + + return true; + } + + bool empty() const + { + return mgr.empty(); + } + +private: + typedef CacheEntry Entry; + + // see note in remove_least_valuable(). + std::list entries_awaiting_eviction; + + Manager mgr; +}; + +#endif // #ifndef INCLUDED_CACHE_ADT Property changes on: ps/trunk/source/lib/adts/cache_adt.h ___________________________________________________________________ Added: svn:eol-style ## -0,0 +1 ## +native \ No newline at end of property Index: ps/trunk/source/lib/adts/ring_buf.h =================================================================== --- ps/trunk/source/lib/adts/ring_buf.h (nonexistent) +++ ps/trunk/source/lib/adts/ring_buf.h (revision 9364) @@ -0,0 +1,212 @@ +/* Copyright (c) 2011 Wildfire Games + * + * 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. + */ + +/* + * static array, accessible modulo n + */ + +#ifndef INCLUDED_ADTS_RING_BUF +#define INCLUDED_ADTS_RING_BUF + +template class RingBuf +{ + size_t size_; // # of entries in buffer + size_t head; // index of oldest item + size_t tail; // index of newest item + T data[n]; + +public: + RingBuf() : data() { clear(); } + void clear() { size_ = 0; head = 0; tail = n-1; } + + size_t size() const { return size_; } + bool empty() const { return size_ == 0; } + + const T& operator[](int ofs) const + { + ENSURE(!empty()); + size_t idx = (size_t)(head + ofs); + return data[idx % n]; + } + T& operator[](int ofs) + { + ENSURE(!empty()); + size_t idx = (size_t)(head + ofs); + return data[idx % n]; + } + + T& front() + { + ENSURE(!empty()); + return data[head]; + } + const T& front() const + { + ENSURE(!empty()); + return data[head]; + } + T& back() + { + ENSURE(!empty()); + return data[tail]; + } + const T& back() const + { + ENSURE(!empty()); + return data[tail]; + } + + void push_back(const T& item) + { + if(size_ < n) + size_++; + // do not complain - overwriting old values is legit + // (e.g. sliding window). + else + head = (head + 1) % n; + + tail = (tail + 1) % n; + data[tail] = item; + } + + void pop_front() + { + if(size_ != 0) + { + size_--; + head = (head + 1) % n; + } + else + ENSURE(0); // underflow + } + + class iterator + { + public: + typedef std::random_access_iterator_tag iterator_category; + typedef T value_type; + typedef ptrdiff_t difference_type; + typedef T* pointer; + typedef T& reference; + + iterator() : data(0), pos(0) + {} + iterator(T* data_, size_t pos_) : data(data_), pos(pos_) + {} + T& operator[](int idx) const + { return data[(pos+idx) % n]; } + T& operator*() const + { return data[pos % n]; } + T* operator->() const + { return &**this; } + iterator& operator++() // pre + { ++pos; return (*this); } + iterator operator++(int) // post + { iterator tmp = *this; ++*this; return tmp; } + bool operator==(const iterator& rhs) const + { return data == rhs.data && pos == rhs.pos; } + bool operator!=(const iterator& rhs) const + { return !(*this == rhs); } + bool operator<(const iterator& rhs) const + { return (pos < rhs.pos); } + iterator& operator+=(difference_type ofs) + { pos += ofs; return *this; } + iterator& operator-=(difference_type ofs) + { return (*this += -ofs); } + iterator operator+(difference_type ofs) const + { iterator tmp = *this; return (tmp += ofs); } + iterator operator-(difference_type ofs) const + { iterator tmp = *this; return (tmp -= ofs); } + difference_type operator-(const iterator right) const + { return (difference_type)(pos - right.pos); } + + protected: + T* data; + size_t pos; + // not mod-N so that begin != end when buffer is full. + }; + + class const_iterator + { + public: + typedef std::random_access_iterator_tag iterator_category; + typedef T value_type; + typedef ptrdiff_t difference_type; + typedef const T* pointer; + typedef const T& reference; + + const_iterator() : data(0), pos(0) + {} + const_iterator(const T* data_, size_t pos_) : data(data_), pos(pos_) + {} + const T& operator[](int idx) const + { return data[(pos+idx) % n]; } + const T& operator*() const + { return data[pos % n]; } + const T* operator->() const + { return &**this; } + const_iterator& operator++() // pre + { ++pos; return (*this); } + const_iterator operator++(int) // post + { const_iterator tmp = *this; ++*this; return tmp; } + bool operator==(const const_iterator& rhs) const + { return data == rhs.data && pos == rhs.pos; } + bool operator!=(const const_iterator& rhs) const + { return !(*this == rhs); } + bool operator<(const const_iterator& rhs) const + { return (pos < rhs.pos); } + iterator& operator+=(difference_type ofs) + { pos += ofs; return *this; } + iterator& operator-=(difference_type ofs) + { return (*this += -ofs); } + iterator operator+(difference_type ofs) const + { iterator tmp = *this; return (tmp += ofs); } + iterator operator-(difference_type ofs) const + { iterator tmp = *this; return (tmp -= ofs); } + difference_type operator-(const iterator right) const + { return (difference_type)(pos - right.pos); } + + protected: + const T* data; + size_t pos; + // not mod-N so that begin != end when buffer is full. + }; + + iterator begin() + { + return iterator(data, head); + } + const_iterator begin() const + { + return const_iterator(data, head); + } + iterator end() + { + return iterator(data, head+size_); + } + const_iterator end() const + { + return const_iterator(data, head+size_); + } +}; + +#endif // #ifndef INCLUDED_ADTS_RING_BUF Index: ps/trunk/source/lib/adts/dyn_hash_tbl.h =================================================================== --- ps/trunk/source/lib/adts/dyn_hash_tbl.h (nonexistent) +++ ps/trunk/source/lib/adts/dyn_hash_tbl.h (revision 9364) @@ -0,0 +1,238 @@ +/* Copyright (c) 2011 Wildfire Games + * + * 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. + */ + +/* + * dynamic (grow-able) hash table + */ + +#ifndef INCLUDED_ADTS_DYN_HASH_TBL +#define INCLUDED_ADTS_DYN_HASH_TBL + +#include // strcmp + +#include "lib/fnv_hash.h" + +template class DHT_Traits +{ +public: + static const size_t initial_entries = 16; + size_t hash(Key key) const; + bool equal(Key k1, Key k2) const; + Key get_key(T t) const; +}; + +template<> class DHT_Traits +{ +public: + static const size_t initial_entries = 512; + size_t hash(const char* key) const + { + return (size_t)fnv_lc_hash(key); + } + bool equal(const char* k1, const char* k2) const + { + return !strcmp(k1, k2); + } + const char* get_key(const char* t) const + { + return t; + } +}; + + +// intended for pointer types +template > +class DynHashTbl +{ + T* tbl; + u16 num_entries; + u16 max_entries; // when initialized, = 2**n for faster modulo + Traits tr; + + T& get_slot(Key key) const + { + size_t hash = tr.hash(key); + ENSURE(max_entries != 0); // otherwise, mask will be incorrect + const size_t mask = max_entries-1; + for(;;) + { + T& t = tbl[hash & mask]; + // empty slot encountered => not found + if(!t) + return t; + // keys are actually equal => found it + if(tr.equal(key, tr.get_key(t))) + return t; + // keep going (linear probing) + hash++; + } + } + + void expand_tbl() + { + // alloc a new table (but don't assign it to unless successful) + T* old_tbl = tbl; + tbl = (T*)calloc(max_entries*2, sizeof(T)); + if(!tbl) + { + tbl = old_tbl; + throw std::bad_alloc(); + } + + max_entries *= 2; + // must be set before get_slot + + // newly initialized, nothing to copy - done + if(!old_tbl) + return; + + // re-hash from old table into the new one + for(size_t i = 0; i < max_entries/2u; i++) + { + T t = old_tbl[i]; + if(t) + get_slot(tr.get_key(t)) = t; + } + free(old_tbl); + } + + +public: + + DynHashTbl() + { + tbl = 0; + clear(); + } + + ~DynHashTbl() + { + free(tbl); + } + + void clear() + { + // must remain usable after calling clear, so shrink the table to + // its initial size but don't deallocate it completely + SAFE_FREE(tbl); + num_entries = 0; + // rationale: must not set to 0 because expand_tbl only doubles the size. + // don't keep the previous size when clearing because it may have become + // huge and there is no provision for shrinking. + max_entries = tr.initial_entries/2; // will be doubled in expand_tbl + expand_tbl(); + } + + void insert(const Key key, const T t) + { + // more than 75% full - increase table size. + // do so before determining slot; this will invalidate previous pnodes. + if(num_entries*4 >= max_entries*3) + expand_tbl(); + + T& slot = get_slot(key); + ENSURE(slot == 0); // not already present + slot = t; + num_entries++; + } + + T find(Key key) const + { + return get_slot(key); + } + + size_t size() const + { + return num_entries; + } + + + class iterator + { + public: + typedef std::forward_iterator_tag iterator_category; + typedef T value_type; + typedef ptrdiff_t difference_type; + typedef const T* pointer; + typedef const T& reference; + + iterator() + { + } + iterator(T* pos_, T* end_) : pos(pos_), end(end_) + { + } + T& operator*() const + { + return *pos; + } + iterator& operator++() // pre + { + do + pos++; + while(pos != end && *pos == 0); + return (*this); + } + bool operator==(const iterator& rhs) const + { + return pos == rhs.pos; + } + bool operator<(const iterator& rhs) const + { + return (pos < rhs.pos); + } + + // derived + const T* operator->() const + { + return &**this; + } + bool operator!=(const iterator& rhs) const + { + return !(*this == rhs); + } + iterator operator++(int) // post + { + iterator tmp = *this; ++*this; return tmp; + } + + protected: + T* pos; + T* end; + // only used when incrementing (avoid going beyond end of table) + }; + + iterator begin() const + { + T* pos = tbl; + while(pos != tbl+max_entries && *pos == 0) + pos++; + return iterator(pos, tbl+max_entries); + } + iterator end() const + { + return iterator(tbl+max_entries, 0); + } +}; + + +#endif // #ifndef INCLUDED_ADTS_DYN_HASH_TBL Property changes on: ps/trunk/source/lib/adts/dyn_hash_tbl.h ___________________________________________________________________ Added: svn:eol-style ## -0,0 +1 ## +native \ No newline at end of property Index: ps/trunk/source/lib/tests/test_adts.h =================================================================== --- ps/trunk/source/lib/tests/test_adts.h (revision 9363) +++ ps/trunk/source/lib/tests/test_adts.h (revision 9364) @@ -1,98 +1,98 @@ /* Copyright (c) 2010 Wildfire Games * * 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. */ #include "lib/self_test.h" -#include "lib/adts.h" +#include "lib/adts/ring_buf.h" #include "lib/rand.h" class TestRingbuf : public CxxTest::TestSuite { static const size_t N = 49; // RingBuf capacity static const int S = 100; // number of test items public: void test_insert_remove() { RingBuf buf; for(int i = 1; i < S; i++) { buf.push_back(i); TS_ASSERT_EQUALS(buf.front(), i); buf.pop_front(); } TS_ASSERT(buf.size() == 0 && buf.empty()); } void test_fill_overwrite_old() { RingBuf buf; for(int i = 1; i < S; i++) buf.push_back(i); TS_ASSERT_EQUALS(buf.size(), N); int first = buf.front(); TS_ASSERT_EQUALS(first, (int)(S-1 -N +1)); for(size_t i = 0; i < N; i++) { TS_ASSERT_EQUALS(buf.front(), first); first++; buf.pop_front(); } TS_ASSERT(buf.size() == 0 && buf.empty()); } void test_randomized_insert_remove() { srand(1); RingBuf buf; std::deque deq; for(size_t rep = 0; rep < 1000; rep++) { size_t rnd_op = rand(0, 10); // 70% - insert if(rnd_op >= 3) { int item = rand(); buf.push_back(item); deq.push_back(item); int excess_items = (int)deq.size() - N; if(excess_items > 0) { for(int i = 0; i < excess_items; i++) { deq.pop_front(); } } } // 30% - pop front (only if not empty) else if(!deq.empty()) { buf.pop_front(); deq.pop_front(); } TS_ASSERT_EQUALS(buf.size(), deq.size()); RingBuf::iterator begin = buf.begin(), end = buf.end(); TS_ASSERT(std::equal(begin, end, deq.begin())); } } }; Index: ps/trunk/source/lib/tests/test_cache_adt.h =================================================================== --- ps/trunk/source/lib/tests/test_cache_adt.h (revision 9363) +++ ps/trunk/source/lib/tests/test_cache_adt.h (revision 9364) @@ -1,132 +1,132 @@ /* Copyright (c) 2010 Wildfire Games * * 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. */ #include "lib/self_test.h" -#include "lib/cache_adt.h" +#include "lib/adts/cache_adt.h" #include "lib/rand.h" class TestCache: public CxxTest::TestSuite { public: void test_cache_perf() { Cache c1; Cache c1r; Cache c2; Cache c2r; Cache c3; Cache c3r; #if defined(ENABLE_CACHE_POLICY_BENCHMARK) || 0 // set max priority, to reduce interference while measuring. int old_policy; static sched_param old_param; // (static => 0-init) pthread_getschedparam(pthread_self(), &old_policy, &old_param); static sched_param max_param; max_param.sched_priority = sched_get_priority_max(SCHED_FIFO); pthread_setschedparam(pthread_self(), SCHED_FIFO, &max_param); #define MEASURE(c, desc)\ {\ srand(1);\ int cnt = 1;\ TIMER_BEGIN(desc);\ for(int i = 0; i < 30000; i++)\ {\ /* 70% add (random objects) */\ bool add = rand(1,10) < 7;\ if(add)\ {\ int key = cnt++;\ int val = cnt++;\ size_t size = (size_t)rand(1,100);\ size_t cost = (size_t)rand(1,100);\ c.add(key, val, size, cost);\ }\ else\ {\ size_t size;\ int value;\ c.remove_least_valuable(&value, &size);\ }\ }\ TIMER_END(desc);\ } MEASURE(c1, "naive") MEASURE(c1r, "naiverecip") MEASURE(c2, "cached") MEASURE(c2r, "cachedrecip") MEASURE(c3, "lazy") MEASURE(c3r, "lazyrecip") // restore previous policy and priority. pthread_setschedparam(pthread_self(), old_policy, &old_param); exit(1134); #endif } // ensures all 3 variants of Landlord<> behave the same // [PT: disabled because it's far too slow] void DISABLED_test_cache_policies() { Cache c1; Cache c2; Cache c3; srand(1); int cnt = 1; for(int i = 0; i < 1000; i++) { // 70% add (random objects) bool add = rand(1,10) < 7; if(add) { int key = cnt++; int val = cnt++; size_t size = (size_t)rand(1,100); size_t cost = (size_t)rand(1,100); c1.add(key, val, size, cost); c2.add(key, val, size, cost); c3.add(key, val, size, cost); } // 30% delete - make sure "least valuable" was same for all else { size_t size1, size2, size3; int value1, value2, value3; bool removed1, removed2, removed3; removed1 = c1.remove_least_valuable(&value1, &size1); removed2 = c2.remove_least_valuable(&value2, &size2); removed3 = c3.remove_least_valuable(&value3, &size3); TS_ASSERT_EQUALS(removed1, removed2); TS_ASSERT_EQUALS(removed2, removed3); if (removed1) { TS_ASSERT_EQUALS(size1, size2); TS_ASSERT_EQUALS(value1, value2); TS_ASSERT_EQUALS(size2, size3); TS_ASSERT_EQUALS(value2, value3); } } // else } // for i } }; Index: ps/trunk/source/lib/debug.h =================================================================== --- ps/trunk/source/lib/debug.h (revision 9363) +++ ps/trunk/source/lib/debug.h (revision 9364) @@ -1,555 +1,555 @@ /* Copyright (c) 2010 Wildfire Games * * 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. */ /* * platform-independent debug support code. */ #ifndef INCLUDED_DEBUG #define INCLUDED_DEBUG // this module provides platform-independent debug facilities, useful for // diagnosing and reporting program errors. // - a symbol engine provides access to compiler-generated debug information and // can also give a stack trace including local variables; // - our more powerful assert() replacement gives a stack trace so // that the underlying problem becomes apparent; // - the output routines make for platform-independent logging and // crashlogs with "last-known activity" reporting. #include "lib/lib_errors.h" #include "lib/code_annotation.h" #include "lib/code_generation.h" /** * trigger a breakpoint when reached/"called". * if defined as a macro, the debugger can break directly into the * target function instead of one frame below it as with a conventional * call-based implementation. **/ #if MSC_VERSION # define debug_break __debugbreak // intrinsic "function" #else extern void debug_break(); #endif //----------------------------------------------------------------------------- // output //----------------------------------------------------------------------------- /** * write a formatted string to the debug channel, subject to filtering * (see below). implemented via debug_puts - see performance note there. * * @param fmt Format string and varargs; see printf. **/ LIB_API void debug_printf(const wchar_t* fmt, ...) WPRINTF_ARGS(1); /** * translates and displays the given strings in a dialog. * this is typically only used when debug_DisplayError has failed or * is unavailable because that function is much more capable. * implemented via sys_display_msg; see documentation there. **/ LIB_API void debug_DisplayMessage(const wchar_t* caption, const wchar_t* msg); /// flags to customize debug_DisplayError behavior enum DebugDisplayErrorFlags { /** * disallow the Continue button. used e.g. if an exception is fatal. **/ DE_NO_CONTINUE = 1, /** * enable the Suppress button. set automatically by debug_DisplayError if * it receives a non-NULL suppress pointer. a flag is necessary because * the sys_display_error interface doesn't get that pointer. * rationale for automatic setting: this may prevent someone from * forgetting to specify it, and disabling Suppress despite having * passed a non-NULL pointer doesn't make much sense. **/ DE_ALLOW_SUPPRESS = 2, /** * do not trigger a breakpoint inside debug_DisplayError; caller * will take care of this if ER_BREAK is returned. this is so that the * debugger can jump directly into the offending function. **/ DE_MANUAL_BREAK = 4, /** * display just the given message; do not add any information about the * call stack, do not write crashlogs, etc. */ DE_NO_DEBUG_INFO = 8 }; /** * a bool that is reasonably certain to be set atomically. * we cannot assume support for OpenMP (requires GCC 4.2) or C++0x, * so we'll have to resort to intptr_t, cpu_CAS and COMPILER_FENCE. **/ typedef volatile intptr_t atomic_bool; /** * value for suppress flag once set by debug_DisplayError. * rationale: this value is fairly distinctive and helps when * debugging the symbol engine. * initial value is 0 rather that another constant; this avoids * allocating .rdata space. **/ const atomic_bool DEBUG_SUPPRESS = 0xAB; /** * choices offered by the error dialog that are returned * by debug_DisplayError. **/ enum ErrorReaction { /** * ignore, continue as if nothing happened. * note: value doesn't start at 0 because that is interpreted as a * DialogBoxParam failure. **/ ER_CONTINUE = 1, /** * trigger breakpoint, i.e. enter debugger. * only returned if DE_MANUAL_BREAK was passed; otherwise, * debug_DisplayError will trigger a breakpoint itself. **/ ER_BREAK }; /** * all choices offered by the error dialog. those not defined in * ErrorReaction are acted upon by debug_DisplayError and * never returned to callers. * (this separation avoids enumerator-not-handled warnings) **/ enum ErrorReactionInternal { ERI_CONTINUE = ER_CONTINUE, ERI_BREAK = ER_BREAK, /** * ignore and do not report again. * note: non-persistent; only applicable during this program run. **/ ERI_SUPPRESS, /** * exit the program immediately. **/ ERI_EXIT, /** * special return value for the display_error app hook stub to indicate * that it has done nothing and that the normal sys_display_error * implementation should be called instead. **/ ERI_NOT_IMPLEMENTED }; /** * display an error dialog with a message and stack trace. * * @param description text to show. * @param flags: see DebugDisplayErrorFlags. * @param context, lastFuncToSkip: see debug_DumpStack. * @param file, line, func: location of the error (typically passed as * WIDEN(__FILE__), __LINE__, __func__ from a macro) * @param suppress pointer to a caller-allocated flag that can be used to * suppress this error. if NULL, this functionality is skipped and the * "Suppress" dialog button will be disabled. * note: this flag is read and written exclusively here; caller only * provides the storage. values: see DEBUG_SUPPRESS above. * @return ErrorReaction (user's choice: continue running or stop?) **/ LIB_API ErrorReaction debug_DisplayError(const wchar_t* description, size_t flags, void* context, const wchar_t* lastFuncToSkip, const wchar_t* file, int line, const char* func, atomic_bool* suppress); /** * convenience version, in case the advanced parameters aren't needed. * macro instead of providing overload/default values for C compatibility. **/ #define DEBUG_DISPLAY_ERROR(text) debug_DisplayError(text, 0, 0, L"debug_DisplayError", WIDEN(__FILE__),__LINE__,__func__, 0) // // filtering // /** * debug output is very useful, but "too much of a good thing can kill you". * we don't want to require different LOGn() macros that are enabled * depending on "debug level", because changing that entails lengthy * compiles and it's too coarse-grained. instead, we require all * strings to start with "tag_string|" (exact case and no quotes; * the alphanumeric-only \ identifies output type). * they are then subject to filtering: only if the tag has been * "added" via debug_filter_add is the appendant string displayed. * * this approach is easiest to implement and is fine because we control * all logging code. LIMODS falls from consideration since it's not * portable and too complex. * * notes: * - filter changes only affect subsequent debug_*printf calls; * output that didn't pass the filter is permanently discarded. * - strings not starting with a tag are always displayed. * - debug_filter_* can be called at any time and from the debugger, * but are not reentrant. * * in future, allow output with the given tag to proceed. * no effect if already added. **/ LIB_API void debug_filter_add(const wchar_t* tag); /** * in future, discard output with the given tag. * no effect if not currently added. **/ LIB_API void debug_filter_remove(const wchar_t* tag); /** * clear all filter state; equivalent to debug_filter_remove for * each tag that was debug_filter_add-ed. **/ LIB_API void debug_filter_clear(); /** * indicate if the given text would be printed. * useful for a series of debug_printfs - avoids needing to add a tag to * each of their format strings. **/ LIB_API bool debug_filter_allows(const wchar_t* text); /** * write an error description and all logs into crashlog.txt * (in unicode format). * * @param text description of the error (including stack trace); * typically generated by debug_BuildErrorMessage. * * @return LibError; ERR::REENTERED if reentered via recursion or * multithreading (not allowed since an infinite loop may result). **/ LIB_API LibError debug_WriteCrashlog(const wchar_t* text); //----------------------------------------------------------------------------- // assertions //----------------------------------------------------------------------------- /** * ensure the expression \ evaluates to non-zero. used to validate * invariants in the program during development and thus gives a * very helpful warning if something isn't going as expected. * sprinkle these liberally throughout your code! * * to pass more information to users at runtime, you can write * ENSURE(expression && "descriptive string"). **/ #define ENSURE(expr)\ do\ {\ static atomic_bool suppress__;\ if(!(expr))\ {\ switch(debug_OnAssertionFailure(WIDEN(#expr), &suppress__, WIDEN(__FILE__), __LINE__, __func__))\ {\ case ER_CONTINUE:\ break;\ case ER_BREAK:\ default:\ debug_break();\ break;\ }\ }\ }\ while(0) /** * same as ENSURE in debug mode, does nothing in release mode. * (we don't override the `assert' macro because users may * inadvertently include \ afterwards) * (we do not provide an MFC-style VERIFY macro because the distinction * between ENSURE and VERIFY is unclear. to always run code but only * check for success in debug builds without raising unused-variable warnings, * use ASSERT + UNUSED2.) **/ #define ASSERT(expr) ENSURE(expr) #ifdef NDEBUG # undef ASSERT -# define ASSERT(expr) (void)expr +# define ASSERT(expr) #endif /** * display the error dialog with the given text. this is less error-prone than * ENSURE(0 && "text"). note that "conditional expression is constant" warnings * are disabled anyway. * * if being able to suppress the warning is desirable (e.g. for self-tests), * then use DEBUG_WARN_ERR instead. **/ #define debug_warn(expr) ENSURE(0 && (expr)) /** * display the error dialog with text corresponding to the given error code. * used by CHECK_ERR et al., which wrap function calls and automatically * raise warnings and return to the caller. **/ #define DEBUG_WARN_ERR(err)\ do\ {\ static atomic_bool suppress__;\ switch(debug_OnError(err, &suppress__, WIDEN(__FILE__), __LINE__, __func__))\ {\ case ER_CONTINUE:\ break;\ case ER_BREAK:\ default:\ debug_break();\ break;\ }\ }\ while(0) /** * called when a ENSURE/ASSERT fails; * notifies the user via debug_DisplayError. * * @param assert_expr the expression that failed; typically passed as * \#expr in the assert macro. * @param suppress see debug_DisplayError. * @param file, line source file name and line number of the spot that failed * @param func name of the function containing it * @return ErrorReaction (user's choice: continue running or stop?) **/ LIB_API ErrorReaction debug_OnAssertionFailure(const wchar_t* assert_expr, atomic_bool* suppress, const wchar_t* file, int line, const char* func); /** * called when a DEBUG_WARN_ERR indicates an error occurred; * notifies the user via debug_DisplayError. * * @param err LibError value indicating the error that occurred * @param suppress see debug_DisplayError. * @param file, line source file name and line number of the spot that failed * @param func name of the function containing it * @return ErrorReaction (user's choice: continue running or stop?) **/ LIB_API ErrorReaction debug_OnError(LibError err, atomic_bool* suppress, const wchar_t* file, int line, const char* func); /** * suppress (prevent from showing) the error dialog from subsequent * debug_OnError for the given LibError. * * rationale: for edge cases in some functions, warnings are raised in * addition to returning an error code. self-tests deliberately trigger * these cases and check for the latter but shouldn't cause the former. * we therefore need to squelch them. * * @param err the LibError to skip. * * note: only one concurrent skip request is allowed; call * debug_StopSkippingErrors before the next debug_SkipErrors. */ LIB_API void debug_SkipErrors(LibError err); /** * @return how many errors were skipped since the call to debug_SkipErrors() **/ LIB_API size_t debug_StopSkippingErrors(); //----------------------------------------------------------------------------- // symbol access //----------------------------------------------------------------------------- namespace ERR { const LibError SYM_NO_STACK_FRAMES_FOUND = -100400; const LibError SYM_UNRETRIEVABLE_STATIC = -100401; const LibError SYM_UNRETRIEVABLE = -100402; const LibError SYM_TYPE_INFO_UNAVAILABLE = -100403; const LibError SYM_INTERNAL_ERROR = -100404; const LibError SYM_UNSUPPORTED = -100405; const LibError SYM_CHILD_NOT_FOUND = -100406; // this limit is to prevent infinite recursion. const LibError SYM_NESTING_LIMIT = -100407; // this limit is to prevent large symbols (e.g. arrays or linked lists) // from taking up all available output space. const LibError SYM_SINGLE_SYMBOL_LIMIT = -100408; } namespace INFO { // one of the dump_sym* functions decided not to output anything at // all (e.g. for member functions in UDTs - we don't want those). // therefore, skip any post-symbol formatting (e.g. ) as well. const LibError SYM_SUPPRESS_OUTPUT = +100409; } /** * Maximum number of characters (including trailing \\0) written to * user's buffers by debug_ResolveSymbol. **/ const size_t DBG_SYMBOL_LEN = 1000; const size_t DBG_FILE_LEN = 100; /** * read and return symbol information for the given address. * * NOTE: the PDB implementation is rather slow (~500us). * * @param ptr_of_interest address of symbol (e.g. function, variable) * @param sym_name optional out; size >= DBG_SYMBOL_LEN chars; * receives symbol name returned via debug info. * @param file optional out; size >= DBG_FILE_LEN chars; receives * base name only (no path; see rationale in wdbg_sym) of * source file containing the symbol. * @param line optional out; receives source file line number of symbol. * * note: all of the output parameters are optional; we pass back as much * information as is available and desired. * @return LibError; INFO::OK iff any information was successfully * retrieved and stored. **/ LIB_API LibError debug_ResolveSymbol(void* ptr_of_interest, wchar_t* sym_name, wchar_t* file, int* line); /** * write a complete stack trace (including values of local variables) into * the specified buffer. * * @param buf Target buffer. * @param maxChars Max chars of buffer (should be several thousand). * @param context Platform-specific representation of execution state * (e.g. Win32 CONTEXT). if not NULL, tracing starts there; this is useful * for exceptions. Otherwise, tracing starts from the current call stack. * @param lastFuncToSkip Is used for omitting error-reporting functions like * debug_OnAssertionFailure from the stack trace. It is either 0 (skip nothing) or * a substring of a function's name (this allows platform-independent * matching of stdcall-decorated names). * Rationale: this is safer than specifying a fixed number of frames, * which can be incorrect due to inlining. * @return LibError; ERR::REENTERED if reentered via recursion or * multithreading (not allowed since static data is used). **/ LIB_API LibError debug_DumpStack(wchar_t* buf, size_t maxChars, void* context, const wchar_t* lastFuncToSkip); //----------------------------------------------------------------------------- // helper functions (used by implementation) //----------------------------------------------------------------------------- /** * [system-dependent] write a string to the debug channel. * this can be quite slow (~1 ms)! On Windows, it uses OutputDebugString * (entails context switch), otherwise stdout+fflush (waits for IO). **/ LIB_API void debug_puts(const wchar_t* text); /** * return the caller of a certain function on the call stack. * * this function is useful for recording (partial) stack traces for * memory allocation tracking, etc. * * @param context, lastFuncToSkip - see debug_DumpStack * @return address of the caller **/ LIB_API void* debug_GetCaller(void* context, const wchar_t* lastFuncToSkip); /** * check if a pointer appears to be totally invalid. * * this check is not authoritative (the pointer may be "valid" but incorrect) * but can be used to filter out obviously wrong values in a portable manner. * * @param p pointer * @return 1 if totally bogus, otherwise 0. **/ LIB_API int debug_IsPointerBogus(const void* p); /// does the given pointer appear to point to code? LIB_API bool debug_IsCodePointer(void* p); /// does the given pointer appear to point to the stack? LIB_API bool debug_IsStackPointer(void* p); /** * inform the debugger of the current thread's name. * * (threads are easier to keep apart when they are identified by * name rather than TID.) **/ LIB_API void debug_SetThreadName(const char* name); /** * holds memory for an error message. **/ struct ErrorMessageMem { // rationale: // - error messages with stack traces require a good deal of memory // (hundreds of KB). static buffers of that size are undesirable. // - the heap may be corrupted, so don't use malloc. allocator.h's // page_aligned_malloc (implemented via mmap) should be safe. // - alloca is a bit iffy (the stack may be maxed out), non-portable and // complicates the code because it can't be allocated by a subroutine. // - this method is probably slow, but error messages aren't built often. // if necessary, first try malloc and use mmap if that fails. void* pa_mem; }; /** * free memory from the error message. * * @param emm ErrorMessageMem* **/ LIB_API void debug_FreeErrorMessage(ErrorMessageMem* emm); /** * build a string describing the given error. * * this is a helper function used by debug_DumpStack and is made available * so that the self-test doesn't have to display the error dialog. * * @param description: general description of the problem. * @param fn_only filename (no path) of source file that triggered the error. * @param line, func: exact position of the error. * @param context, lastFuncToSkip: see debug_DumpStack. * @param emm memory for the error message. caller should allocate * stack memory and set alloc_buf*; if not, there will be no * fallback in case heap alloc fails. should be freed via * debug_FreeErrorMessage when no longer needed. **/ LIB_API const wchar_t* debug_BuildErrorMessage(const wchar_t* description, const wchar_t* fn_only, int line, const char* func, void* context, const wchar_t* lastFuncToSkip, ErrorMessageMem* emm); #endif // #ifndef INCLUDED_DEBUG Index: ps/trunk/source/lib/file/vfs/file_cache.cpp =================================================================== --- ps/trunk/source/lib/file/vfs/file_cache.cpp (revision 9363) +++ ps/trunk/source/lib/file/vfs/file_cache.cpp (revision 9364) @@ -1,251 +1,251 @@ /* Copyright (c) 2010 Wildfire Games * * 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. */ /* * cache of file contents (supports zero-copy IO) */ #include "precompiled.h" #include "lib/file/vfs/file_cache.h" #include "lib/external_libraries/suppress_boost_warnings.h" #include "lib/file/common/file_stats.h" -#include "lib/cache_adt.h" // Cache +#include "lib/adts/cache_adt.h" #include "lib/bits.h" // round_up #include "lib/allocators/allocator_checker.h" #include "lib/allocators/shared_ptr.h" #include "lib/allocators/headerless.h" #include "lib/sysdep/os_cpu.h" // os_cpu_PageSize #include "lib/posix/posix_mman.h" // mprotect //----------------------------------------------------------------------------- // allocator /* the biggest worry of a file cache is external fragmentation. there are two basic ways to combat this: 1) 'defragment' periodically - move blocks around to increase size of available 'holes'. 2) prevent fragmentation from occurring at all via deliberate alloc/free policy. file contents are returned directly to the user (zero-copy IO), so only currently unreferenced blocks can be moved. it is believed that this would severely hamper defragmentation; we therefore go with the latter approach. the basic insight is: fragmentation occurs when a block is freed whose neighbors are not free (thus preventing coalescing). this can be prevented by allocating objects of similar lifetimes together. typical workloads (uniform access frequency) already show such behavior: the Landlord cache manager evicts files in an LRU manner, which matches the allocation policy. references: "The Memory Fragmentation Problem - Solved?" (Johnstone and Wilson) "Dynamic Storage Allocation - A Survey and Critical Review" (Johnstone and Wilson) */ // shared_ptrs must own a reference to their allocator to ensure it's extant when // they are freed. it is stored in the shared_ptr deleter. class Allocator; typedef shared_ptr PAllocator; class FileCacheDeleter { public: FileCacheDeleter(size_t size, const PAllocator& allocator) : m_size(size), m_allocator(allocator) { } // (this uses Allocator and must come after its definition) void operator()(u8* mem) const; private: size_t m_size; PAllocator m_allocator; }; // adds statistics and AllocatorChecker to a HeaderlessAllocator class Allocator { public: Allocator(size_t maxSize) : m_allocator(maxSize) { } shared_ptr Allocate(size_t size, const PAllocator& pthis) { const size_t alignedSize = Align(size); u8* mem = (u8*)m_allocator.Allocate(alignedSize); if(!mem) return DummySharedPtr(0); // (prevent FileCacheDeleter from seeing a null pointer) #ifndef NDEBUG m_checker.OnAllocate(mem, alignedSize); #endif stats_buf_alloc(size, alignedSize); return shared_ptr(mem, FileCacheDeleter(size, pthis)); } void Deallocate(u8* mem, size_t size) { const size_t alignedSize = Align(size); // (re)allow writes in case the buffer was made read-only. it would // be nice to unmap the buffer, but this is not possible because // HeaderlessAllocator needs to affix boundary tags. (void)mprotect(mem, size, PROT_READ|PROT_WRITE); #ifndef NDEBUG m_checker.OnDeallocate(mem, alignedSize); #endif m_allocator.Deallocate(mem, alignedSize); stats_buf_free(); } private: HeaderlessAllocator m_allocator; #ifndef NDEBUG AllocatorChecker m_checker; #endif }; void FileCacheDeleter::operator()(u8* mem) const { m_allocator->Deallocate(mem, m_size); } //----------------------------------------------------------------------------- // FileCache::Impl //----------------------------------------------------------------------------- // since users are strongly encouraged to only load/process one file at a // time, there won't be many active references to cache entries. we could // take advantage of this with a separate extant list, but the cache's // hash map should be fast enough and this way is less work than maintaining // (possibly disjunct) cached and extant lists. class FileCache::Impl { public: Impl(size_t maxSize) : m_allocator(new Allocator(maxSize)) { } shared_ptr Reserve(size_t size) { // (should never happen because the VFS ensures size != 0.) ENSURE(size != 0); // (300 iterations have been observed when reserving several MB // of space in a full cache) for(;;) { { shared_ptr data = m_allocator->Allocate(size, m_allocator); if(data) return data; } // remove least valuable entry from cache (if users are holding // references, the contents won't actually be deallocated) { shared_ptr discardedData; size_t discardedSize; bool removed = m_cache.remove_least_valuable(&discardedData, &discardedSize); // only false if cache is empty, which can't be the case because // allocation failed. ENSURE(removed); } } } void Add(const VfsPath& pathname, const shared_ptr& data, size_t size, size_t cost) { // zero-copy cache => all users share the contents => must not // allow changes. this will be reverted when deallocating. (void)mprotect((void*)data.get(), size, PROT_READ); m_cache.add(pathname, data, size, cost); } bool Retrieve(const VfsPath& pathname, shared_ptr& data, size_t& size) { // (note: don't call stats_cache because we don't know the file size // in case of a cache miss; doing so is left to the caller.) stats_buf_ref(); return m_cache.retrieve(pathname, data, &size); } void Remove(const VfsPath& pathname) { m_cache.remove(pathname); // note: we could check if someone is still holding a reference // to the contents, but that currently doesn't matter. } private: typedef Cache > CacheType; CacheType m_cache; PAllocator m_allocator; }; //----------------------------------------------------------------------------- FileCache::FileCache(size_t size) : impl(new Impl(size)) { } shared_ptr FileCache::Reserve(size_t size) { return impl->Reserve(size); } void FileCache::Add(const VfsPath& pathname, const shared_ptr& data, size_t size, size_t cost) { impl->Add(pathname, data, size, cost); } void FileCache::Remove(const VfsPath& pathname) { impl->Remove(pathname); } bool FileCache::Retrieve(const VfsPath& pathname, shared_ptr& data, size_t& size) { return impl->Retrieve(pathname, data, size); } Index: ps/trunk/source/lib/sysdep/os/win/whrt/whrt.cpp =================================================================== --- ps/trunk/source/lib/sysdep/os/win/whrt/whrt.cpp (revision 9363) +++ ps/trunk/source/lib/sysdep/os/win/whrt/whrt.cpp (revision 9364) @@ -1,321 +1,320 @@ /* Copyright (c) 2010 Wildfire Games * * 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. */ /* * Windows High Resolution Timer */ #include "precompiled.h" #include "lib/sysdep/os/win/whrt/whrt.h" #include // _beginthreadex #include "lib/sysdep/cpu.h" #include "lib/sysdep/os/win/win.h" #include "lib/sysdep/os/win/winit.h" #include "lib/sysdep/acpi.h" -//#include "lib/adts.h" #include "lib/bits.h" #include "lib/sysdep/os/win/whrt/counter.h" WINIT_REGISTER_EARLY_INIT2(whrt_Init); // wutil -> whrt -> wtime WINIT_REGISTER_LATE_SHUTDOWN(whrt_Shutdown); namespace ERR { const LibError WHRT_COUNTER_UNSAFE = 140000; } //----------------------------------------------------------------------------- // choose best available safe counter // (moved into a separate function to simplify error handling) static inline LibError ActivateCounter(ICounter* counter) { RETURN_ERR(counter->Activate()); if(!counter->IsSafe()) return ERR::WHRT_COUNTER_UNSAFE; // NOWARN (happens often) return INFO::OK; } /** * @return the newly created and unique instance of the next best counter * that is deemed safe, or 0 if all have already been created. **/ static ICounter* GetNextBestSafeCounter() { for(;;) { static size_t nextCounterId = 0; ICounter* counter = CreateCounter(nextCounterId++); if(!counter) return 0; // tried all, none were safe LibError err = ActivateCounter(counter); if(err == INFO::OK) { debug_printf(L"HRT| using name=%ls freq=%f\n", counter->Name(), counter->NominalFrequency()); return counter; // found a safe counter } else { wchar_t buf[100]; debug_printf(L"HRT| activating %ls failed: %ls\n", counter->Name(), error_description_r(err, buf, ARRAY_SIZE(buf))); DestroyCounter(counter); } } } //----------------------------------------------------------------------------- // counter that drives the timer static ICounter* counter; // (these counter properties are cached for efficiency and convenience:) static double nominalFrequency; static double resolution; static size_t counterBits; static u64 counterMask; static void InitCounter() { // we used to support switching counters at runtime, but that's // unnecessarily complex. it need and should only be done once. ENSURE(counter == 0); counter = GetNextBestSafeCounter(); ENSURE(counter != 0); nominalFrequency = counter->NominalFrequency(); resolution = counter->Resolution(); counterBits = counter->CounterBits(); debug_printf(L"HRT| counter=%ls freq=%g res=%g bits=%d\n", counter->Name(), nominalFrequency, resolution, counterBits); // sanity checks ENSURE(nominalFrequency >= 500.0-DBL_EPSILON); ENSURE(resolution <= 2e-3); ENSURE(8 <= counterBits && counterBits <= 64); counterMask = bit_mask(counterBits); } static void ShutdownCounter() { DestroyCounter(counter); } static inline u64 Counter() { return counter->Counter(); } /** * @return difference [ticks], taking rollover into account. * (time-critical, so it's not called through ICounter.) **/ static inline u64 CounterDelta(u64 oldCounter, u64 newCounter) { return (newCounter - oldCounter) & counterMask; } double whrt_Resolution() { ENSURE(resolution != 0.0); return resolution; } //----------------------------------------------------------------------------- // timer state // we're not going to bother calibrating the counter (i.e. measuring its // current frequency by means of a second timer). rationale: // - all counters except the TSC are stable and run at fixed frequencies; // - it's not clear that any other HRT or the tick count would be useful // as a stable time reference (if it were, we should be using it instead); // - calibration would complicate the code (we'd have to make sure the // secondary counter is safe and can co-exist with the primary). /** * stores all timer state shared between readers and the update thread. * (must be POD because it's used before static ctors run.) **/ struct TimerState { // value of the counter at last update. u64 counter; // total elapsed time [seconds] since first update. // converted from tick deltas with the *then current* frequency // (this enables calibration, which is currently not implemented, // but leaving open the possibility costs nothing) double time; u8 padding[48]; }; // how do we detect when the old TimerState is no longer in use and can be // freed? we use two static instances (avoids dynamic allocation headaches) // and swap between them ('double-buffering'). it is assumed that all // entered critical sections (the latching of TimerState fields) will have // been exited before the next update comes around; if not, TimerState.time // changes, the critical section notices and re-reads the new values. static __declspec(align(64)) TimerState timerStates[2]; // note: exchanging pointers is easier than XORing an index. static volatile TimerState* volatile ts = &timerStates[0]; static volatile TimerState* volatile ts2 = &timerStates[1]; static void UpdateTimerState() { // how can we synchronize readers and the update thread? locks are // preferably avoided since they're dangerous and can be slow. what we // need to ensure is that TimerState doesn't change while another thread is // accessing it. the first step is to linearize the update, i.e. have it // appear to happen in an instant (done by building a new TimerState and // having it go live by switching pointers). all that remains is to make // reads of the state variables consistent, done by latching them all and // retrying if an update came in the middle of this. const u64 counter = Counter(); const u64 deltaTicks = CounterDelta(ts->counter, counter); ts2->counter = counter; ts2->time = ts->time + deltaTicks/nominalFrequency; ts = (volatile TimerState*)InterlockedExchangePointer((volatile PVOID*)&ts2, (PVOID)ts); } double whrt_Time() { retry: // latch timer state (counter and time must be from the same update) const double time = ts->time; COMPILER_FENCE; const u64 counter = ts->counter; // ts changed after reading time. note: don't compare counter because // it _might_ have the same value after two updates. if(time != ts->time) goto retry; const u64 deltaTicks = CounterDelta(counter, Counter()); return (time + deltaTicks/nominalFrequency); } //----------------------------------------------------------------------------- // update thread // note: we used to discipline the HRT timestamp to the system time, so it // was advantageous to trigger updates via WinMM event (thus reducing // instances where we're called in the middle of a scheduler tick). // since that's no longer relevant, we prefer using a thread, because that // avoids the dependency on WinMM and its lengthy startup time. // rationale: (+ and - are reasons for longer and shorter lengths) // + minimize CPU usage // + ensure all threads currently using TimerState return from those // functions before the next interval // - avoid more than 1 counter rollover per interval (InitUpdateThread makes // sure our interval is shorter than the current counter's rollover rate) static const DWORD UPDATE_INTERVAL_MS = 1000; static HANDLE hExitEvent; static HANDLE hUpdateThread; static unsigned __stdcall UpdateThread(void* UNUSED(data)) { debug_SetThreadName("whrt_UpdateThread"); for(;;) { const DWORD ret = WaitForSingleObject(hExitEvent, UPDATE_INTERVAL_MS); // owner terminated or wait failed or exit event signaled - exit thread if(ret != WAIT_TIMEOUT) break; UpdateTimerState(); } return 0; } static inline LibError InitUpdateThread() { // make sure our interval isn't too long // (counterBits can be 64 => Bit() would overflow => calculate period/2) const double period_2 = Bit(counterBits-1) / nominalFrequency; const size_t rolloversPerInterval = size_t(UPDATE_INTERVAL_MS / i64(period_2*2.0*1000.0)); ENSURE(rolloversPerInterval <= 1); hExitEvent = CreateEvent(0, TRUE, FALSE, 0); // manual reset, initially false if(hExitEvent == INVALID_HANDLE_VALUE) WARN_RETURN(ERR::LIMIT); hUpdateThread = (HANDLE)_beginthreadex(0, 0, UpdateThread, 0, 0, 0); if(!hUpdateThread) WARN_RETURN(ERR::LIMIT); return INFO::OK; } static inline void ShutdownUpdateThread() { // signal thread BOOL ok = SetEvent(hExitEvent); WARN_IF_FALSE(ok); // the nice way is to wait for it to exit if(WaitForSingleObject(hUpdateThread, 100) != WAIT_OBJECT_0) TerminateThread(hUpdateThread, 0); // forcibly exit (dangerous) CloseHandle(hExitEvent); CloseHandle(hUpdateThread); } //----------------------------------------------------------------------------- static LibError whrt_Init() { InitCounter(); // latch initial counter value so that timer starts at 0 ts->counter = Counter(); // must come before UpdateTimerState UpdateTimerState(); // must come before InitUpdateThread to avoid race RETURN_ERR(InitUpdateThread()); return INFO::OK; } static LibError whrt_Shutdown() { ShutdownUpdateThread(); ShutdownCounter(); acpi_Shutdown(); return INFO::OK; }