Mercurial > hg > openttd
changeset 5633:a9c31d5be476 draft
(svn r8092) -Codechange: header files with miscellaneous template classes (smart pointers, blob, array, hashtable, etc.) moved from src/yapf to src/misc as they can now be used anywhere.
| author | KUDr <KUDr@openttd.org> |
|---|---|
| date | Sat, 13 Jan 2007 13:33:36 +0000 |
| parents | a80a0873f4b0 |
| children | 395bfe9e1f77 |
| files | src/helpers.cpp src/misc/array.hpp src/misc/autocopyptr.hpp src/misc/binaryheap.hpp src/misc/blob.hpp src/misc/countedptr.hpp src/misc/crc32.hpp src/misc/fixedsizearray.hpp src/misc/hashtable.hpp src/yapf/array.hpp src/yapf/autocopyptr.hpp src/yapf/binaryheap.hpp src/yapf/blob.hpp src/yapf/countedptr.hpp src/yapf/crc32.hpp src/yapf/fixedsizearray.hpp src/yapf/hashtable.hpp src/yapf/nodelist.hpp src/yapf/yapf.hpp src/yapf/yapf_base.hpp |
| diffstat | 20 files changed, 1237 insertions(+), 1237 deletions(-) [+] |
line wrap: on
line diff
--- a/src/helpers.cpp +++ b/src/helpers.cpp @@ -5,7 +5,7 @@ #include "engine.h" #include <new> -#include "yapf/blob.hpp" +#include "misc/blob.hpp" /* Engine list manipulators - current implementation is only C wrapper around CBlobT<EngineID> (see yapf/blob.hpp) */
new file mode 100644 --- /dev/null +++ b/src/misc/array.hpp @@ -0,0 +1,71 @@ +/* $Id$ */ + +#ifndef ARRAY_HPP +#define ARRAY_HPP + +#include "fixedsizearray.hpp" + +/** Flexible array with size limit. Implemented as fixed size + * array of fixed size arrays */ +template <class Titem_, int Tblock_size_ = 1024, int Tnum_blocks_ = Tblock_size_> +class CArrayT { +public: + typedef Titem_ Titem; ///< Titem is now visible from outside + typedef CFixedSizeArrayT<Titem_, Tblock_size_> CSubArray; ///< inner array + typedef CFixedSizeArrayT<CSubArray, Tnum_blocks_> CSuperArray; ///< outer array + +protected: + CSuperArray m_a; ///< array of arrays of items + +public: + static const int Tblock_size = Tblock_size_; ///< block size is now visible from outside + static const int Tnum_blocks = Tnum_blocks_; ///< number of blocks is now visible from outside + static const int Tcapacity = Tblock_size * Tnum_blocks; ///< total max number of items + + /** implicit constructor */ + FORCEINLINE CArrayT() { } + /** Clear (destroy) all items */ + FORCEINLINE void Clear() {m_a.Clear();} + /** Return actual number of items */ + FORCEINLINE int Size() const + { + int super_size = m_a.Size(); + if (super_size == 0) return 0; + int sub_size = m_a[super_size - 1].Size(); + return (super_size - 1) * Tblock_size + sub_size; + } + /** return true if array is empty */ + FORCEINLINE bool IsEmpty() { return m_a.IsEmpty(); } + /** return true if array is full */ + FORCEINLINE bool IsFull() { return m_a.IsFull() && m_a[Tnum_blocks - 1].IsFull(); } + /** return first sub-array with free space for new item */ + FORCEINLINE CSubArray& FirstFreeSubArray() + { + int super_size = m_a.Size(); + if (super_size > 0) { + CSubArray& sa = m_a[super_size - 1]; + if (!sa.IsFull()) return sa; + } + return m_a.Add(); + } + /** allocate but not construct new item */ + FORCEINLINE Titem_& AddNC() { return FirstFreeSubArray().AddNC(); } + /** allocate and construct new item */ + FORCEINLINE Titem_& Add() { return FirstFreeSubArray().Add(); } + /** indexed access (non-const) */ + FORCEINLINE Titem& operator [] (int idx) + { + CSubArray& sa = m_a[idx / Tblock_size]; + Titem& item = sa [idx % Tblock_size]; + return item; + } + /** indexed access (const) */ + FORCEINLINE const Titem& operator [] (int idx) const + { + CSubArray& sa = m_a[idx / Tblock_size]; + Titem& item = sa [idx % Tblock_size]; + return item; + } +}; + +#endif /* ARRAY_HPP */
new file mode 100644 --- /dev/null +++ b/src/misc/autocopyptr.hpp @@ -0,0 +1,83 @@ +/* $Id$ */ + +#ifndef AUTOCOPYPTR_HPP +#define AUTOCOPYPTR_HPP + +#if 0 // reenable when needed +/** CAutoCopyPtrT - kind of CoW (Copy on Write) pointer. + * It is non-invasive smart pointer (reference counter is held outside + * of Tdata). + * When copied, its new copy shares the same underlaying structure Tdata. + * When dereferenced, its behavior depends on 2 factors: + * - whether the data is shared (used by more than one pointer) + * - type of access (read/write) + * When shared pointer is dereferenced for write, new clone of Tdata + * is made first. + * Can't be used for polymorphic data types (interfaces). + */ +template <class Tdata_> +class CAutoCopyPtrT { +protected: + typedef Tdata_ Tdata; + + struct CItem { + int m_ref_cnt; ///< reference counter + Tdata m_data; ///< custom data itself + + FORCEINLINE CItem() : m_ref_cnt(1) {}; + FORCEINLINE CItem(const Tdata& data) : m_ref_cnt(1), m_data(data) {}; + FORCEINLINE CItem(const CItem& src) : m_ref_cnt(1), m_data(src.m_data) {}; + }; + + mutable CItem* m_pI; ///< points to the ref-counted data + +public: + FORCEINLINE CAutoCopyPtrT() : m_pI(NULL) {}; + FORCEINLINE CAutoCopyPtrT(const Tdata& data) : m_pI(new CItem(data)) {}; + FORCEINLINE CAutoCopyPtrT(const CAutoCopyPtrT& src) : m_pI(src.m_pI) {if (m_pI != NULL) m_pI->m_ref_cnt++;} + FORCEINLINE ~CAutoCopyPtrT() {if (m_pI == NULL || (--m_pI->m_ref_cnt) > 0) return; delete m_pI; m_pI = NULL;} + + /** data accessor (read only) */ + FORCEINLINE const Tdata& GetDataRO() const {if (m_pI == NULL) m_pI = new CItem(); return m_pI->m_data;} + /** data accessor (read / write) */ + FORCEINLINE Tdata& GetDataRW() {CloneIfShared(); if (m_pI == NULL) m_pI = new CItem(); return m_pI->m_data;} + + /** clone data if it is shared */ + FORCEINLINE void CloneIfShared() + { + if (m_pI != NULL && m_pI->m_ref_cnt > 1) { + // we share data item with somebody, clone it to become an exclusive owner + CItem* pNewI = new CItem(*m_pI); + m_pI->m_ref_cnt--; + m_pI = pNewI; + } + } + + /** assign pointer from the other one (maintaining ref counts) */ + FORCEINLINE void Assign(const CAutoCopyPtrT& src) + { + if (m_pI == src.m_pI) return; + if (m_pI != NULL && (--m_pI->m_ref_cnt) <= 0) delete m_pI; + m_pI = src.m_pI; + if (m_pI != NULL) m_pI->m_ref_cnt++; + } + + /** dereference operator (read only) */ + FORCEINLINE const Tdata* operator -> () const {return &GetDataRO();} + /** dereference operator (read / write) */ + FORCEINLINE Tdata* operator -> () {return &GetDataRW();} + + /** assignment operator */ + FORCEINLINE CAutoCopyPtrT& operator = (const CAutoCopyPtrT& src) {Assign(src); return *this;} + + /** forwarding 'lower then' operator to the underlaying items */ + FORCEINLINE bool operator < (const CAutoCopyPtrT& other) const + { + assert(m_pI != NULL); + assert(other.m_pI != NULL); + return (m_pI->m_data) < (other.m_pI->m_data); + } +}; + +#endif /* 0 */ +#endif /* AUTOCOPYPTR_HPP */
new file mode 100644 --- /dev/null +++ b/src/misc/binaryheap.hpp @@ -0,0 +1,225 @@ +/* $Id$ */ + +#ifndef BINARYHEAP_HPP +#define BINARYHEAP_HPP + +//void* operator new (size_t size, void* p) {return p;} +#if defined(_MSC_VER) && (_MSC_VER >= 1400) +//void operator delete (void* p, void* p2) {} +#endif + + +/** + * Binary Heap as C++ template. + * + * For information about Binary Heap algotithm, + * see: http://www.policyalmanac.org/games/binaryHeaps.htm + * + * Implementation specific notes: + * + * 1) It allocates space for item pointers (array). Items are allocated elsewhere. + * + * 2) ItemPtr [0] is never used. Total array size is max_items + 1, because we + * use indices 1..max_items instead of zero based C indexing. + * + * 3) Item of the binary heap should support these public members: + * - 'lower-then' operator '<' - used for comparing items before moving + * + */ + +template <class Titem_> +class CBinaryHeapT { +public: + typedef Titem_ *ItemPtr; +private: + int m_size; ///< Number of items in the heap + int m_max_size; ///< Maximum number of items the heap can hold + ItemPtr* m_items; ///< The heap item pointers + +public: + explicit CBinaryHeapT(int max_items = 102400) + : m_size(0) + , m_max_size(max_items) + { + m_items = new ItemPtr[max_items + 1]; + } + + ~CBinaryHeapT() + { + Clear(); + delete [] m_items; + m_items = NULL; + } + +public: + /** Return the number of items stored in the priority queue. + * @return number of items in the queue */ + FORCEINLINE int Size() const {return m_size;}; + + /** Test if the priority queue is empty. + * @return true if empty */ + FORCEINLINE bool IsEmpty() const {return (m_size == 0);}; + + /** Test if the priority queue is full. + * @return true if full. */ + FORCEINLINE bool IsFull() const {return (m_size >= m_max_size);}; + + /** Find the smallest item in the priority queue. + * Return the smallest item, or throw assert if empty. */ + FORCEINLINE Titem_& GetHead() {assert(!IsEmpty()); return *m_items[1];} + + /** Insert new item into the priority queue, maintaining heap order. + * @return false if the queue is full. */ + bool Push(Titem_& new_item); + + /** Remove and return the smallest item from the priority queue. */ + FORCEINLINE Titem_& PopHead() {Titem_& ret = GetHead(); RemoveHead(); return ret;}; + + /** Remove the smallest item from the priority queue. */ + void RemoveHead(); + + /** Remove item specified by index */ + void RemoveByIdx(int idx); + + /** return index of the item that matches (using &item1 == &item2) the given item. */ + int FindLinear(const Titem_& item) const; + + /** Make the priority queue empty. + * All remaining items will remain untouched. */ + void Clear() {m_size = 0;}; + + /** verifies the heap consistency (added during first YAPF debug phase) */ + void CheckConsistency(); +}; + + +template <class Titem_> +FORCEINLINE bool CBinaryHeapT<Titem_>::Push(Titem_& new_item) +{ + if (IsFull()) return false; + + // make place for new item + int gap = ++m_size; + // Heapify up + for (int parent = gap / 2; (parent > 0) && (new_item < *m_items[parent]); gap = parent, parent /= 2) + m_items[gap] = m_items[parent]; + m_items[gap] = &new_item; + CheckConsistency(); + return true; +} + +template <class Titem_> +FORCEINLINE void CBinaryHeapT<Titem_>::RemoveHead() +{ + assert(!IsEmpty()); + + // at index 1 we have a gap now + int gap = 1; + + // Heapify down: + // last item becomes a candidate for the head. Call it new_item. + Titem_& new_item = *m_items[m_size--]; + + // now we must maintain relation between parent and its children: + // parent <= any child + // from head down to the tail + int child = 2; // first child is at [parent * 2] + + // while children are valid + while (child <= m_size) { + // choose the smaller child + if (child < m_size && *m_items[child + 1] < *m_items[child]) + child++; + // is it smaller than our parent? + if (!(*m_items[child] < new_item)) { + // the smaller child is still bigger or same as parent => we are done + break; + } + // if smaller child is smaller than parent, it will become new parent + m_items[gap] = m_items[child]; + gap = child; + // where do we have our new children? + child = gap * 2; + } + // move last item to the proper place + if (m_size > 0) m_items[gap] = &new_item; + CheckConsistency(); +} + +template <class Titem_> +inline void CBinaryHeapT<Titem_>::RemoveByIdx(int idx) +{ + // at position idx we have a gap now + int gap = idx; + Titem_& last = *m_items[m_size]; + if (idx < m_size) { + assert(idx >= 1); + m_size--; + // and the candidate item for fixing this gap is our last item 'last' + // Move gap / last item up: + while (gap > 1) + { + // compare [gap] with its parent + int parent = gap / 2; + if (last < *m_items[parent]) { + m_items[gap] = m_items[parent]; + gap = parent; + } else { + // we don't need to continue upstairs + break; + } + } + + // Heapify (move gap) down: + while (true) { + // where we do have our children? + int child = gap * 2; // first child is at [parent * 2] + if (child > m_size) break; + // choose the smaller child + if (child < m_size && *m_items[child + 1] < *m_items[child]) + child++; + // is it smaller than our parent? + if (!(*m_items[child] < last)) { + // the smaller child is still bigger or same as parent => we are done + break; + } + // if smaller child is smaller than parent, it will become new parent + m_items[gap] = m_items[child]; + gap = child; + } + // move parent to the proper place + if (m_size > 0) m_items[gap] = &last; + } + else { + assert(idx == m_size); + m_size--; + } + CheckConsistency(); +} + +template <class Titem_> +inline int CBinaryHeapT<Titem_>::FindLinear(const Titem_& item) const +{ + if (IsEmpty()) return 0; + for (ItemPtr *ppI = m_items + 1, *ppLast = ppI + m_size; ppI <= ppLast; ppI++) { + if (*ppI == &item) { + return ppI - m_items; + } + } + return 0; +} + +template <class Titem_> +FORCEINLINE void CBinaryHeapT<Titem_>::CheckConsistency() +{ + // enable it if you suspect binary heap doesn't work well +#if 0 + for (int child = 2; child <= m_size; child++) { + int parent = child / 2; + assert(!(m_items[child] < m_items[parent])); + } +#endif +} + + +#endif /* BINARYHEAP_HPP */
new file mode 100644 --- /dev/null +++ b/src/misc/blob.hpp @@ -0,0 +1,342 @@ +/* $Id$ */ + +#ifndef BLOB_HPP +#define BLOB_HPP + +/** Type-safe version of memcpy(). + * @param d destination buffer + * @param s source buffer + * @param num_items number of items to be copied (!not number of bytes!) */ +template <class Titem_> +FORCEINLINE void MemCpyT(Titem_* d, const Titem_* s, int num_items = 1) +{ + memcpy(d, s, num_items * sizeof(Titem_)); +} + + +/** Base class for simple binary blobs. + * Item is byte. + * The word 'simple' means: + * - no configurable allocator type (always made from heap) + * - no smart deallocation - deallocation must be called from the same + * module (DLL) where the blob was allocated + * - no configurable allocation policy (how big blocks should be allocated) + * - no extra ownership policy (i.e. 'copy on write') when blob is copied + * - no thread synchronization at all + * + * Internal member layout: + * 1. The only class member is pointer to the first item (see union ptr_u). + * 2. Allocated block contains the blob header (see CHdr) followed by the raw byte data. + * Always, when it allocates memory the allocated size is: + * sizeof(CHdr) + <data capacity> + * 3. Two 'virtual' members (m_size and m_max_size) are stored in the CHdr at beginning + * of the alloated block. + * 4. The pointer (in ptr_u) points behind the header (to the first data byte). + * When memory block is allocated, the sizeof(CHdr) it added to it. + * 5. Benefits of this layout: + * - items are accessed in the simplest possible way - just dereferencing the pointer, + * which is good for performance (assuming that data are accessed most often). + * - sizeof(blob) is the same as the size of any other pointer + * 6. Drawbacks of this layout: + * - the fact, that pointer to the alocated block is adjusted by sizeof(CHdr) before + * it is stored can lead to several confusions: + * - it is not common pattern so the implementation code is bit harder to read + * - valgrind can generate warning that allocated block is lost (not accessible) + * */ +class CBlobBaseSimple { +protected: + /** header of the allocated memory block */ + struct CHdr { + int m_size; ///< actual blob size in bytes + int m_max_size; ///< maximum (allocated) size in bytes + }; + + /** type used as class member */ + union { + int8 *m_pData; ///< pointer to the first byte of data + CHdr *m_pHdr_1; ///< pointer just after the CHdr holding m_size and m_max_size + } ptr_u; + +public: + static const int Ttail_reserve = 4; ///< four extra bytes will be always allocated and zeroed at the end + + /** default constructor - initializes empty blob */ + FORCEINLINE CBlobBaseSimple() { InitEmpty(); } + /** copy constructor */ + FORCEINLINE CBlobBaseSimple(const CBlobBaseSimple& src) + { + InitEmpty(); + AppendRaw(src); + } + /** destructor */ + FORCEINLINE ~CBlobBaseSimple() { Free(); } +protected: + /** initialize the empty blob by setting the ptr_u.m_pHdr_1 pointer to the static CHdr with + * both m_size and m_max_size containing zero */ + FORCEINLINE void InitEmpty() { static CHdr hdrEmpty[] = {{0, 0}, {0, 0}}; ptr_u.m_pHdr_1 = &hdrEmpty[1]; } + /** initialize blob by attaching it to the given header followed by data */ + FORCEINLINE void Init(CHdr* hdr) { ptr_u.m_pHdr_1 = &hdr[1]; } + /** blob header accessor - use it rather than using the pointer arithmetics directly - non-const version */ + FORCEINLINE CHdr& Hdr() { return ptr_u.m_pHdr_1[-1]; } + /** blob header accessor - use it rather than using the pointer arithmetics directly - const version */ + FORCEINLINE const CHdr& Hdr() const { return ptr_u.m_pHdr_1[-1]; } + /** return reference to the actual blob size - used when the size needs to be modified */ + FORCEINLINE int& RawSizeRef() { return Hdr().m_size; }; + +public: + /** return true if blob doesn't contain valid data */ + FORCEINLINE bool IsEmpty() const { return RawSize() == 0; } + /** return the number of valid data bytes in the blob */ + FORCEINLINE int RawSize() const { return Hdr().m_size; }; + /** return the current blob capacity in bytes */ + FORCEINLINE int MaxRawSize() const { return Hdr().m_max_size; }; + /** return pointer to the first byte of data - non-const version */ + FORCEINLINE int8* RawData() { return ptr_u.m_pData; } + /** return pointer to the first byte of data - const version */ + FORCEINLINE const int8* RawData() const { return ptr_u.m_pData; } +#if 0 // reenable when needed + /** return the 32 bit CRC of valid data in the blob */ + FORCEINLINE uint32 Crc32() const {return CCrc32::Calc(RawData(), RawSize());} +#endif //0 + /** invalidate blob's data - doesn't free buffer */ + FORCEINLINE void Clear() { RawSizeRef() = 0; } + /** free the blob's memory */ + FORCEINLINE void Free() { if (MaxRawSize() > 0) {RawFree(&Hdr()); InitEmpty();} } + /** copy data from another blob - replaces any existing blob's data */ + FORCEINLINE void CopyFrom(const CBlobBaseSimple& src) { Clear(); AppendRaw(src); } + /** overtake ownership of data buffer from the source blob - source blob will become empty */ + FORCEINLINE void MoveFrom(CBlobBaseSimple& src) { Free(); ptr_u.m_pData = src.ptr_u.m_pData; src.InitEmpty(); } + /** swap buffers (with data) between two blobs (this and source blob) */ + FORCEINLINE void Swap(CBlobBaseSimple& src) { int8 *tmp = ptr_u.m_pData; ptr_u.m_pData = src.ptr_u.m_pData; src.ptr_u.m_pData = tmp; } + + /** append new bytes at the end of existing data bytes - reallocates if necessary */ + FORCEINLINE void AppendRaw(int8 *p, int num_bytes) + { + assert(p != NULL); + if (num_bytes > 0) { + memcpy(GrowRawSize(num_bytes), p, num_bytes); + } else { + assert(num_bytes >= 0); + } + } + + /** append bytes from given source blob to the end of existing data bytes - reallocates if necessary */ + FORCEINLINE void AppendRaw(const CBlobBaseSimple& src) + { + if (!src.IsEmpty()) + memcpy(GrowRawSize(src.RawSize()), src.RawData(), src.RawSize()); + } + + /** Reallocate if there is no free space for num_bytes bytes. + * @return pointer to the new data to be added */ + FORCEINLINE int8* MakeRawFreeSpace(int num_bytes) + { + assert(num_bytes >= 0); + int new_size = RawSize() + num_bytes; + if (new_size > MaxRawSize()) SmartAlloc(new_size); + FixTail(); + return ptr_u.m_pData + RawSize(); + } + + /** Increase RawSize() by num_bytes. + * @return pointer to the new data added */ + FORCEINLINE int8* GrowRawSize(int num_bytes) + { + int8* pNewData = MakeRawFreeSpace(num_bytes); + RawSizeRef() += num_bytes; + return pNewData; + } + + /** Decrease RawSize() by num_bytes. */ + FORCEINLINE void ReduceRawSize(int num_bytes) + { + if (MaxRawSize() > 0 && num_bytes > 0) { + assert(num_bytes <= RawSize()); + if (num_bytes < RawSize()) RawSizeRef() -= num_bytes; + else RawSizeRef() = 0; + } + } + /** reallocate blob data if needed */ + void SmartAlloc(int new_size) + { + int old_max_size = MaxRawSize(); + if (old_max_size >= new_size) return; + // calculate minimum block size we need to allocate + int min_alloc_size = sizeof(CHdr) + new_size + Ttail_reserve; + // ask allocation policy for some reasonable block size + int alloc_size = AllocPolicy(min_alloc_size); + // allocate new block + CHdr* pNewHdr = RawAlloc(alloc_size); + // setup header + pNewHdr->m_size = RawSize(); + pNewHdr->m_max_size = alloc_size - (sizeof(CHdr) + Ttail_reserve); + // copy existing data + if (RawSize() > 0) + memcpy(pNewHdr + 1, ptr_u.m_pData, pNewHdr->m_size); + // replace our block with new one + CHdr* pOldHdr = &Hdr(); + Init(pNewHdr); + if (old_max_size > 0) + RawFree(pOldHdr); + } + /** simple allocation policy - can be optimized later */ + FORCEINLINE static int AllocPolicy(int min_alloc) + { + if (min_alloc < (1 << 9)) { + if (min_alloc < (1 << 5)) return (1 << 5); + return (min_alloc < (1 << 7)) ? (1 << 7) : (1 << 9); + } + if (min_alloc < (1 << 15)) { + if (min_alloc < (1 << 11)) return (1 << 11); + return (min_alloc < (1 << 13)) ? (1 << 13) : (1 << 15); + } + if (min_alloc < (1 << 20)) { + if (min_alloc < (1 << 17)) return (1 << 17); + return (min_alloc < (1 << 19)) ? (1 << 19) : (1 << 20); + } + min_alloc = (min_alloc | ((1 << 20) - 1)) + 1; + return min_alloc; + } + + /** all allocation should happen here */ + static FORCEINLINE CHdr* RawAlloc(int num_bytes) { return (CHdr*)malloc(num_bytes); } + /** all deallocations should happen here */ + static FORCEINLINE void RawFree(CHdr* p) { free(p); } + /** fixing the four bytes at the end of blob data - useful when blob is used to hold string */ + FORCEINLINE void FixTail() + { + if (MaxRawSize() > 0) { + int8 *p = &ptr_u.m_pData[RawSize()]; + for (int i = 0; i < Ttail_reserve; i++) p[i] = 0; + } + } +}; + +/** Blob - simple dynamic Titem_ array. Titem_ (template argument) is a placeholder for any type. + * Titem_ can be any integral type, pointer, or structure. Using Blob instead of just plain C array + * simplifies the resource management in several ways: + * 1. When adding new item(s) it automatically grows capacity if needed. + * 2. When variable of type Blob comes out of scope it automatically frees the data buffer. + * 3. Takes care about the actual data size (number of used items). + * 4. Dynamically constructs only used items (as opposite of static array which constructs all items) */ +template <class Titem_, class Tbase_ = CBlobBaseSimple> +class CBlobT : public CBlobBaseSimple { + // make template arguments public: +public: + typedef Titem_ Titem; + typedef Tbase_ Tbase; + + static const int Titem_size = sizeof(Titem); + + /** Default constructor - makes new Blob ready to accept any data */ + FORCEINLINE CBlobT() : Tbase() {} + /** Copy constructor - make new blob to become copy of the original (source) blob */ + FORCEINLINE CBlobT(const Tbase& src) : Tbase(src) {assert((RawSize() % Titem_size) == 0);} + /** Destructor - ensures that allocated memory (if any) is freed */ + FORCEINLINE ~CBlobT() { Free(); } + /** Check the validity of item index (only in debug mode) */ + FORCEINLINE void CheckIdx(int idx) { assert(idx >= 0); assert(idx < Size()); } + /** Return pointer to the first data item - non-const version */ + FORCEINLINE Titem* Data() { return (Titem*)RawData(); } + /** Return pointer to the first data item - const version */ + FORCEINLINE const Titem* Data() const { return (const Titem*)RawData(); } + /** Return pointer to the idx-th data item - non-const version */ + FORCEINLINE Titem* Data(int idx) { CheckIdx(idx); return (Data() + idx); } + /** Return pointer to the idx-th data item - const version */ + FORCEINLINE const Titem* Data(int idx) const { CheckIdx(idx); return (Data() + idx); } + /** Return number of items in the Blob */ + FORCEINLINE int Size() const { return (RawSize() / Titem_size); } + /** Free the memory occupied by Blob destroying all items */ + FORCEINLINE void Free() + { + assert((RawSize() % Titem_size) == 0); + int old_size = Size(); + if (old_size > 0) { + // destroy removed items; + Titem* pI_last_to_destroy = Data(0); + for (Titem* pI = Data(old_size - 1); pI >= pI_last_to_destroy; pI--) pI->~Titem_(); + } + Tbase::Free(); + } + /** Grow number of data items in Blob by given number - doesn't construct items */ + FORCEINLINE Titem* GrowSizeNC(int num_items) { return (Titem*)GrowRawSize(num_items * Titem_size); } + /** Grow number of data items in Blob by given number - constructs new items (using Titem_'s default constructor) */ + FORCEINLINE Titem* GrowSizeC(int num_items) + { + Titem* pI = GrowSizeNC(num_items); + for (int i = num_items; i > 0; i--, pI++) new (pI) Titem(); + } + /** Destroy given number of items and reduce the Blob's data size */ + FORCEINLINE void ReduceSize(int num_items) + { + assert((RawSize() % Titem_size) == 0); + int old_size = Size(); + assert(num_items <= old_size); + int new_size = (num_items <= old_size) ? (old_size - num_items) : 0; + // destroy removed items; + Titem* pI_last_to_destroy = Data(new_size); + for (Titem* pI = Data(old_size - 1); pI >= pI_last_to_destroy; pI--) pI->~Titem(); + // remove them + ReduceRawSize(num_items * Titem_size); + } + /** Append one data item at the end (calls Titem_'s default constructor) */ + FORCEINLINE Titem* AppendNew() + { + Titem& dst = *GrowSizeNC(1); // Grow size by one item + Titem* pNewItem = new (&dst) Titem(); // construct the new item by calling in-place new operator + return pNewItem; + } + /** Append the copy of given item at the end of Blob (using copy constructor) */ + FORCEINLINE Titem* Append(const Titem& src) + { + Titem& dst = *GrowSizeNC(1); // Grow size by one item + Titem* pNewItem = new (&dst) Titem(src); // construct the new item by calling in-place new operator with copy ctor() + return pNewItem; + } + /** Add given items (ptr + number of items) at the end of blob */ + FORCEINLINE Titem* Append(const Titem* pSrc, int num_items) + { + Titem* pDst = GrowSizeNC(num_items); + Titem* pDstOrg = pDst; + Titem* pDstEnd = pDst + num_items; + while (pDst < pDstEnd) new (pDst++) Titem(*(pSrc++)); + return pDstOrg; + } + /** Remove item with the given index by replacing it by the last item and reducing the size by one */ + FORCEINLINE void RemoveBySwap(int idx) + { + CheckIdx(idx); + // destroy removed item + Titem* pRemoved = Data(idx); + RemoveBySwap(pRemoved); + } + /** Remove item given by pointer replacing it by the last item and reducing the size by one */ + FORCEINLINE void RemoveBySwap(Titem* pItem) + { + Titem* pLast = Data(Size() - 1); + assert(pItem >= Data() && pItem <= pLast); + // move last item to its new place + if (pItem != pLast) { + pItem->~Titem_(); + new (pItem) Titem_(*pLast); + } + // destroy the last item + pLast->~Titem_(); + // and reduce the raw blob size + ReduceRawSize(Titem_size); + } + /** Ensures that given number of items can be added to the end of Blob. Returns pointer to the + * first free (unused) item */ + FORCEINLINE Titem* MakeFreeSpace(int num_items) { return (Titem*)MakeRawFreeSpace(num_items * Titem_size); } +}; + +// simple string implementation +struct CStrA : public CBlobT<char> +{ + typedef CBlobT<char> base; + CStrA(const char* str = NULL) {Append(str);} + FORCEINLINE CStrA(const CBlobBaseSimple& src) : base(src) {} + void Append(const char* str) {if (str != NULL && str[0] != '\0') base::Append(str, (int)strlen(str));} +}; + +#endif /* BLOB_HPP */
new file mode 100644 --- /dev/null +++ b/src/misc/countedptr.hpp @@ -0,0 +1,100 @@ +/* $Id$ */ + +#ifndef COUNTEDPTR_HPP +#define COUNTEDPTR_HPP + +#if 0 // reenable when needed +/** @file CCountedPtr - smart pointer implementation */ + +/** CCountedPtr - simple reference counting smart pointer. + * + * One of the standard ways how to maintain object's lifetime. + * + * See http://ootips.org/yonat/4dev/smart-pointers.html for more + * general info about smart pointers. + * + * This class implements ref-counted pointer for objects/interfaces that + * support AddRef() and Release() methods. + */ +template <class Tcls_> +class CCountedPtr { + /** redefine the template argument to make it visible for derived classes */ +public: + typedef Tcls_ Tcls; + +protected: + /** here we hold our pointer to the target */ + Tcls* m_pT; + +public: + /** default (NULL) construct or construct from a raw pointer */ + FORCEINLINE CCountedPtr(Tcls* pObj = NULL) : m_pT(pObj) {AddRef();}; + + /** copy constructor (invoked also when initializing from another smart ptr) */ + FORCEINLINE CCountedPtr(const CCountedPtr& src) : m_pT(src.m_pT) {AddRef();}; + + /** destructor releasing the reference */ + FORCEINLINE ~CCountedPtr() {Release();}; + +protected: + /** add one ref to the underlaying object */ + FORCEINLINE void AddRef() {if (m_pT != NULL) m_pT->AddRef();} + +public: + /** release smart pointer (and decrement ref count) if not null */ + FORCEINLINE void Release() {if (m_pT != NULL) {m_pT->Release(); m_pT = NULL;}} + + /** dereference of smart pointer - const way */ + FORCEINLINE const Tcls* operator -> () const {assert(m_pT != NULL); return m_pT;}; + + /** dereference of smart pointer - non const way */ + FORCEINLINE Tcls* operator -> () {assert(m_pT != NULL); return m_pT;}; + + /** raw pointer casting operator - const way */ + FORCEINLINE operator const Tcls*() const {assert(m_pT == NULL); return m_pT;} + + /** raw pointer casting operator - non-const way */ + FORCEINLINE operator Tcls*() {assert(m_pT == NULL); return m_pT;} + + /** operator & to support output arguments */ + FORCEINLINE Tcls** operator &() {assert(m_pT == NULL); return &m_pT;} + + /** assignment operator from raw ptr */ + FORCEINLINE CCountedPtr& operator = (Tcls* pT) {Assign(pT); return *this;} + + /** assignment operator from another smart ptr */ + FORCEINLINE CCountedPtr& operator = (CCountedPtr& src) {Assign(src.m_pT); return *this;} + + /** assignment operator helper */ + FORCEINLINE void Assign(Tcls* pT); + + /** one way how to test for NULL value */ + FORCEINLINE bool IsNull() const {return m_pT == NULL;} + + /** another way how to test for NULL value */ + FORCEINLINE bool operator == (const CCountedPtr& sp) const {return m_pT == sp.m_pT;} + + /** yet another way how to test for NULL value */ + FORCEINLINE bool operator != (const CCountedPtr& sp) const {return m_pT != sp.m_pT;} + + /** assign pointer w/o incrementing ref count */ + FORCEINLINE void Attach(Tcls* pT) {Release(); m_pT = pT;} + + /** detach pointer w/o decrementing ref count */ + FORCEINLINE Tcls* Detach() {Tcls* pT = m_pT; m_pT = NULL; return pT;} +}; + +template <class Tcls_> +FORCEINLINE void CCountedPtr<Tcls_>::Assign(Tcls* pT) +{ + // if they are the same, we do nothing + if (pT != m_pT) { + if (pT) pT->AddRef(); // AddRef new pointer if any + Tcls* pTold = m_pT; // save original ptr + m_pT = pT; // update m_pT to new value + if (pTold) pTold->Release(); // release old ptr if any + } +} + +#endif /* 0 */ +#endif /* COUNTEDPTR_HPP */
new file mode 100644 --- /dev/null +++ b/src/misc/crc32.hpp @@ -0,0 +1,65 @@ +/* $Id$ */ + +#ifndef CRC32_HPP +#define CRC32_HPP + +#if 0 // reenable when needed +struct CCrc32 +{ + static uint32 Calc(const void *pBuffer, int nCount) + { + uint32 crc = 0xffffffff; + const uint32* pTable = CrcTable(); + + uint8* begin = (uint8*)pBuffer; + uint8* end = begin + nCount; + for(uint8* cur = begin; cur < end; cur++) + crc = (crc >> 8) ^ pTable[cur[0] ^ (uint8)(crc & 0xff)]; + crc ^= 0xffffffff; + + return crc; + } + + static const uint32* CrcTable() + { + static const uint32 Table[256] = + { + 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, + 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, + 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, + 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5, + 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, + 0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, + 0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F, + 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, + 0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433, + 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01, + 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, + 0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65, + 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, + 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, + 0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F, + 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, + 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, + 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, + 0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7, + 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, + 0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B, + 0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79, + 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, + 0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D, + 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713, + 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, + 0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777, + 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, + 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, + 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9, + 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF, + 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D + }; + return Table; + } +}; +#endif // 0 + +#endif /* CRC32_HPP */
new file mode 100644 --- /dev/null +++ b/src/misc/fixedsizearray.hpp @@ -0,0 +1,99 @@ +/* $Id$ */ + +#ifndef FIXEDSIZEARRAY_HPP +#define FIXEDSIZEARRAY_HPP + + +/** fixed size array + * Upon construction it preallocates fixed size block of memory + * for all items, but doesn't construct them. Item's construction + * is delayed. */ +template <class Titem_, int Tcapacity_> +struct CFixedSizeArrayT { + /** the only member of fixed size array is pointer to the block + * of C array of items. Header can be found on the offset -sizeof(CHdr). */ + Titem_ *m_items; + + /** header for fixed size array */ + struct CHdr + { + int m_num_items; ///< number of items in the array + int m_ref_cnt; ///< block reference counter (used by copy constructor and by destructor) + }; + + // make types and constants visible from outside + typedef Titem_ Titem; // type of array item + + static const int Tcapacity = Tcapacity_; // the array capacity (maximum size) + static const int TitemSize = sizeof(Titem_); // size of item + static const int ThdrSize = sizeof(CHdr); // size of header + + /** Default constructor. Preallocate space for items and header, then initialize header. */ + CFixedSizeArrayT() + { + // allocate block for header + items (don't construct items) + m_items = (Titem*)(((int8*)malloc(ThdrSize + Tcapacity * sizeof(Titem))) + ThdrSize); + SizeRef() = 0; // initial number of items + RefCnt() = 1; // initial reference counter + } + + /** Copy constructor. Preallocate space for items and header, then initialize header. */ + CFixedSizeArrayT(const CFixedSizeArrayT<Titem_, Tcapacity_>& src) + { + // share block (header + items) with the source array + m_items = src.m_items; + RefCnt()++; // now we share block with the source + } + + /** destroy remaining items and free the memory block */ + ~CFixedSizeArrayT() + { + // release one reference to the shared block + if ((--RefCnt()) > 0) return; // and return if there is still some owner + + Clear(); + // free the memory block occupied by items + free(((int8*)m_items) - ThdrSize); + m_items = NULL; + } + + /** Clear (destroy) all items */ + FORCEINLINE void Clear() + { + // walk through all allocated items backward and destroy them + for (Titem* pItem = &m_items[Size() - 1]; pItem >= m_items; pItem--) { + pItem->~Titem_(); + } + // number of items become zero + SizeRef() = 0; + } + +protected: + /** return reference to the array header (non-const) */ + FORCEINLINE CHdr& Hdr() { return *(CHdr*)(((int8*)m_items) - ThdrSize); } + /** return reference to the array header (const) */ + FORCEINLINE const CHdr& Hdr() const { return *(CHdr*)(((int8*)m_items) - ThdrSize); } + /** return reference to the block reference counter */ + FORCEINLINE int& RefCnt() { return Hdr().m_ref_cnt; } + /** return reference to number of used items */ + FORCEINLINE int& SizeRef() { return Hdr().m_num_items; } +public: + /** return number of used items */ + FORCEINLINE int Size() const { return Hdr().m_num_items; } + /** return true if array is full */ + FORCEINLINE bool IsFull() const { return Size() >= Tcapacity; }; + /** return true if array is empty */ + FORCEINLINE bool IsEmpty() const { return Size() <= 0; }; + /** index validation */ + FORCEINLINE void CheckIdx(int idx) const { assert(idx >= 0); assert(idx < Size()); } + /** add (allocate), but don't construct item */ + FORCEINLINE Titem& AddNC() { assert(!IsFull()); return m_items[SizeRef()++]; } + /** add and construct item using default constructor */ + FORCEINLINE Titem& Add() { Titem& item = AddNC(); new(&item)Titem; return item; } + /** return item by index (non-const version) */ + FORCEINLINE Titem& operator [] (int idx) { CheckIdx(idx); return m_items[idx]; } + /** return item by index (const version) */ + FORCEINLINE const Titem& operator [] (int idx) const { CheckIdx(idx); return m_items[idx]; } +}; + +#endif /* FIXEDSIZEARRAY_HPP */
new file mode 100644 --- /dev/null +++ b/src/misc/hashtable.hpp @@ -0,0 +1,240 @@ +/* $Id$ */ + +#ifndef HASHTABLE_HPP +#define HASHTABLE_HPP + +template <class Titem_> +struct CHashTableSlotT +{ + typedef typename Titem_::Key Key; // make Titem_::Key a property of HashTable + + Titem_* m_pFirst; + + CHashTableSlotT() : m_pFirst(NULL) {} + + /** hash table slot helper - clears the slot by simple forgetting its items */ + FORCEINLINE void Clear() {m_pFirst = NULL;} + + /** hash table slot helper - linear search for item with given key through the given blob - const version */ + FORCEINLINE const Titem_* Find(const Key& key) const + { + for (const Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) { + if (pItem->GetKey() == key) { + // we have found the item, return it + return pItem; + } + } + return NULL; + } + + /** hash table slot helper - linear search for item with given key through the given blob - non-const version */ + FORCEINLINE Titem_* Find(const Key& key) + { + for (Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) { + if (pItem->GetKey() == key) { + // we have found the item, return it + return pItem; + } + } + return NULL; + } + + /** hash table slot helper - add new item to the slot */ + FORCEINLINE void Attach(Titem_& new_item) + { + assert(new_item.GetHashNext() == NULL); + new_item.SetHashNext(m_pFirst); + m_pFirst = &new_item; + } + + /** hash table slot helper - remove item from a slot */ + FORCEINLINE bool Detach(Titem_& item_to_remove) + { + if (m_pFirst == &item_to_remove) { + m_pFirst = item_to_remove.GetHashNext(); + item_to_remove.SetHashNext(NULL); + return true; + } + Titem_* pItem = m_pFirst; + while (true) { + if (pItem == NULL) { + return false; + } + Titem_* pNextItem = pItem->GetHashNext(); + if (pNextItem == &item_to_remove) break; + pItem = pNextItem; + } + pItem->SetHashNext(item_to_remove.GetHashNext()); + item_to_remove.SetHashNext(NULL); + return true; + } + + /** hash table slot helper - remove and return item from a slot */ + FORCEINLINE Titem_* Detach(const Key& key) + { + // do we have any items? + if (m_pFirst == NULL) { + return NULL; + } + // is it our first item? + if (m_pFirst->GetKey() == key) { + Titem_& ret_item = *m_pFirst; + m_pFirst = m_pFirst->GetHashNext(); + ret_item.SetHashNext(NULL); + return &ret_item; + } + // find it in the following items + Titem_* pPrev = m_pFirst; + for (Titem_* pItem = m_pFirst->GetHashNext(); pItem != NULL; pPrev = pItem, pItem = pItem->GetHashNext()) { + if (pItem->GetKey() == key) { + // we have found the item, unlink and return it + pPrev->SetHashNext(pItem->GetHashNext()); + pItem->SetHashNext(NULL); + return pItem; + } + } + return NULL; + } +}; + +/** @class CHashTableT<Titem, Thash_bits> - simple hash table + * of pointers allocated elsewhere. + * + * Supports: Add/Find/Remove of Titems. + * + * Your Titem must meet some extra requirements to be CHashTableT + * compliant: + * - its constructor/destructor (if any) must be public + * - if the copying of item requires an extra resource management, + * you must define also copy constructor + * - must support nested type (struct, class or typedef) Titem::Key + * that defines the type of key class for that item + * - must support public method: + * const Key& GetKey() const; // return the item's key object + * + * In addition, the Titem::Key class must support: + * - public method that calculates key's hash: + * int CalcHash() const; + * - public 'equality' operator to compare the key with another one + * bool operator == (const Key& other) const; + */ +template <class Titem_, int Thash_bits_> +class CHashTableT { +public: + typedef Titem_ Titem; // make Titem_ visible from outside of class + typedef typename Titem_::Key Tkey; // make Titem_::Key a property of HashTable + static const int Thash_bits = Thash_bits_; // publish num of hash bits + static const int Tcapacity = 1 << Thash_bits; // and num of slots 2^bits + +protected: + /** each slot contains pointer to the first item in the list, + * Titem contains pointer to the next item - GetHashNext(), SetHashNext() */ + typedef CHashTableSlotT<Titem_> Slot; + + Slot* m_slots; // here we store our data (array of blobs) + int m_num_items; // item counter + +public: + // default constructor + FORCEINLINE CHashTableT() + { + // construct all slots + m_slots = new Slot[Tcapacity]; + m_num_items = 0; + } + + ~CHashTableT() {delete [] m_slots; m_num_items = 0; m_slots = NULL;} + +protected: + /** static helper - return hash for the given key modulo number of slots */ + FORCEINLINE static int CalcHash(const Tkey& key) + { + int32 hash = key.CalcHash(); + if ((8 * Thash_bits) < 32) hash ^= hash >> (min(8 * Thash_bits, 31)); + if ((4 * Thash_bits) < 32) hash ^= hash >> (min(4 * Thash_bits, 31)); + if ((2 * Thash_bits) < 32) hash ^= hash >> (min(2 * Thash_bits, 31)); + if ((1 * Thash_bits) < 32) hash ^= hash >> (min(1 * Thash_bits, 31)); + hash &= (1 << Thash_bits) - 1; + return hash; + } + + /** static helper - return hash for the given item modulo number of slots */ + FORCEINLINE static int CalcHash(const Titem_& item) {return CalcHash(item.GetKey());} + +public: + /** item count */ + FORCEINLINE int Count() const {return m_num_items;} + + /** simple clear - forget all items - used by CSegmentCostCacheT.Flush() */ + FORCEINLINE void Clear() const {for (int i = 0; i < Tcapacity; i++) m_slots[i].Clear();} + + /** const item search */ + const Titem_* Find(const Tkey& key) const + { + int hash = CalcHash(key); + const Slot& slot = m_slots[hash]; + const Titem_* item = slot.Find(key); + return item; + } + + /** non-const item search */ + Titem_* Find(const Tkey& key) + { + int hash = CalcHash(key); + Slot& slot = m_slots[hash]; + Titem_* item = slot.Find(key); + return item; + } + + /** non-const item search & optional removal (if found) */ + Titem_* TryPop(const Tkey& key) + { + int hash = CalcHash(key); + Slot& slot = m_slots[hash]; + Titem_* item = slot.Detach(key); + if (item != NULL) { + m_num_items--; + } + return item; + } + + /** non-const item search & removal */ + Titem_& Pop(const Tkey& key) + { + Titem_* item = TryPop(key); + assert(item != NULL); + return *item; + } + + /** non-const item search & optional removal (if found) */ + bool TryPop(Titem_& item) + { + const Tkey& key = item.GetKey(); + int hash = CalcHash(key); + Slot& slot = m_slots[hash]; + bool ret = slot.Detach(item); + if (ret) { + m_num_items--; + } + return ret; + } + + /** non-const item search & removal */ + void Pop(Titem_& item) + { + bool ret = TryPop(item); + assert(ret); + } + + /** add one item - copy it from the given item */ + void Push(Titem_& new_item) + { + int hash = CalcHash(new_item); + Slot& slot = m_slots[hash]; + assert(slot.Find(new_item.GetKey()) == NULL); + slot.Attach(new_item); + m_num_items++; + } +}; + +#endif /* HASHTABLE_HPP */
deleted file mode 100644 --- a/src/yapf/array.hpp +++ /dev/null @@ -1,71 +0,0 @@ -/* $Id$ */ - -#ifndef ARRAY_HPP -#define ARRAY_HPP - -#include "fixedsizearray.hpp" - -/** Flexible array with size limit. Implemented as fixed size - * array of fixed size arrays */ -template <class Titem_, int Tblock_size_ = 1024, int Tnum_blocks_ = Tblock_size_> -class CArrayT { -public: - typedef Titem_ Titem; ///< Titem is now visible from outside - typedef CFixedSizeArrayT<Titem_, Tblock_size_> CSubArray; ///< inner array - typedef CFixedSizeArrayT<CSubArray, Tnum_blocks_> CSuperArray; ///< outer array - -protected: - CSuperArray m_a; ///< array of arrays of items - -public: - static const int Tblock_size = Tblock_size_; ///< block size is now visible from outside - static const int Tnum_blocks = Tnum_blocks_; ///< number of blocks is now visible from outside - static const int Tcapacity = Tblock_size * Tnum_blocks; ///< total max number of items - - /** implicit constructor */ - FORCEINLINE CArrayT() { } - /** Clear (destroy) all items */ - FORCEINLINE void Clear() {m_a.Clear();} - /** Return actual number of items */ - FORCEINLINE int Size() const - { - int super_size = m_a.Size(); - if (super_size == 0) return 0; - int sub_size = m_a[super_size - 1].Size(); - return (super_size - 1) * Tblock_size + sub_size; - } - /** return true if array is empty */ - FORCEINLINE bool IsEmpty() { return m_a.IsEmpty(); } - /** return true if array is full */ - FORCEINLINE bool IsFull() { return m_a.IsFull() && m_a[Tnum_blocks - 1].IsFull(); } - /** return first sub-array with free space for new item */ - FORCEINLINE CSubArray& FirstFreeSubArray() - { - int super_size = m_a.Size(); - if (super_size > 0) { - CSubArray& sa = m_a[super_size - 1]; - if (!sa.IsFull()) return sa; - } - return m_a.Add(); - } - /** allocate but not construct new item */ - FORCEINLINE Titem_& AddNC() { return FirstFreeSubArray().AddNC(); } - /** allocate and construct new item */ - FORCEINLINE Titem_& Add() { return FirstFreeSubArray().Add(); } - /** indexed access (non-const) */ - FORCEINLINE Titem& operator [] (int idx) - { - CSubArray& sa = m_a[idx / Tblock_size]; - Titem& item = sa [idx % Tblock_size]; - return item; - } - /** indexed access (const) */ - FORCEINLINE const Titem& operator [] (int idx) const - { - CSubArray& sa = m_a[idx / Tblock_size]; - Titem& item = sa [idx % Tblock_size]; - return item; - } -}; - -#endif /* ARRAY_HPP */
deleted file mode 100644 --- a/src/yapf/autocopyptr.hpp +++ /dev/null @@ -1,83 +0,0 @@ -/* $Id$ */ - -#ifndef AUTOCOPYPTR_HPP -#define AUTOCOPYPTR_HPP - -#if 0 // reenable when needed -/** CAutoCopyPtrT - kind of CoW (Copy on Write) pointer. - * It is non-invasive smart pointer (reference counter is held outside - * of Tdata). - * When copied, its new copy shares the same underlaying structure Tdata. - * When dereferenced, its behavior depends on 2 factors: - * - whether the data is shared (used by more than one pointer) - * - type of access (read/write) - * When shared pointer is dereferenced for write, new clone of Tdata - * is made first. - * Can't be used for polymorphic data types (interfaces). - */ -template <class Tdata_> -class CAutoCopyPtrT { -protected: - typedef Tdata_ Tdata; - - struct CItem { - int m_ref_cnt; ///< reference counter - Tdata m_data; ///< custom data itself - - FORCEINLINE CItem() : m_ref_cnt(1) {}; - FORCEINLINE CItem(const Tdata& data) : m_ref_cnt(1), m_data(data) {}; - FORCEINLINE CItem(const CItem& src) : m_ref_cnt(1), m_data(src.m_data) {}; - }; - - mutable CItem* m_pI; ///< points to the ref-counted data - -public: - FORCEINLINE CAutoCopyPtrT() : m_pI(NULL) {}; - FORCEINLINE CAutoCopyPtrT(const Tdata& data) : m_pI(new CItem(data)) {}; - FORCEINLINE CAutoCopyPtrT(const CAutoCopyPtrT& src) : m_pI(src.m_pI) {if (m_pI != NULL) m_pI->m_ref_cnt++;} - FORCEINLINE ~CAutoCopyPtrT() {if (m_pI == NULL || (--m_pI->m_ref_cnt) > 0) return; delete m_pI; m_pI = NULL;} - - /** data accessor (read only) */ - FORCEINLINE const Tdata& GetDataRO() const {if (m_pI == NULL) m_pI = new CItem(); return m_pI->m_data;} - /** data accessor (read / write) */ - FORCEINLINE Tdata& GetDataRW() {CloneIfShared(); if (m_pI == NULL) m_pI = new CItem(); return m_pI->m_data;} - - /** clone data if it is shared */ - FORCEINLINE void CloneIfShared() - { - if (m_pI != NULL && m_pI->m_ref_cnt > 1) { - // we share data item with somebody, clone it to become an exclusive owner - CItem* pNewI = new CItem(*m_pI); - m_pI->m_ref_cnt--; - m_pI = pNewI; - } - } - - /** assign pointer from the other one (maintaining ref counts) */ - FORCEINLINE void Assign(const CAutoCopyPtrT& src) - { - if (m_pI == src.m_pI) return; - if (m_pI != NULL && (--m_pI->m_ref_cnt) <= 0) delete m_pI; - m_pI = src.m_pI; - if (m_pI != NULL) m_pI->m_ref_cnt++; - } - - /** dereference operator (read only) */ - FORCEINLINE const Tdata* operator -> () const {return &GetDataRO();} - /** dereference operator (read / write) */ - FORCEINLINE Tdata* operator -> () {return &GetDataRW();} - - /** assignment operator */ - FORCEINLINE CAutoCopyPtrT& operator = (const CAutoCopyPtrT& src) {Assign(src); return *this;} - - /** forwarding 'lower then' operator to the underlaying items */ - FORCEINLINE bool operator < (const CAutoCopyPtrT& other) const - { - assert(m_pI != NULL); - assert(other.m_pI != NULL); - return (m_pI->m_data) < (other.m_pI->m_data); - } -}; - -#endif /* 0 */ -#endif /* AUTOCOPYPTR_HPP */
deleted file mode 100644 --- a/src/yapf/binaryheap.hpp +++ /dev/null @@ -1,225 +0,0 @@ -/* $Id$ */ - -#ifndef BINARYHEAP_HPP -#define BINARYHEAP_HPP - -//void* operator new (size_t size, void* p) {return p;} -#if defined(_MSC_VER) && (_MSC_VER >= 1400) -//void operator delete (void* p, void* p2) {} -#endif - - -/** - * Binary Heap as C++ template. - * - * For information about Binary Heap algotithm, - * see: http://www.policyalmanac.org/games/binaryHeaps.htm - * - * Implementation specific notes: - * - * 1) It allocates space for item pointers (array). Items are allocated elsewhere. - * - * 2) ItemPtr [0] is never used. Total array size is max_items + 1, because we - * use indices 1..max_items instead of zero based C indexing. - * - * 3) Item of the binary heap should support these public members: - * - 'lower-then' operator '<' - used for comparing items before moving - * - */ - -template <class Titem_> -class CBinaryHeapT { -public: - typedef Titem_ *ItemPtr; -private: - int m_size; ///< Number of items in the heap - int m_max_size; ///< Maximum number of items the heap can hold - ItemPtr* m_items; ///< The heap item pointers - -public: - explicit CBinaryHeapT(int max_items = 102400) - : m_size(0) - , m_max_size(max_items) - { - m_items = new ItemPtr[max_items + 1]; - } - - ~CBinaryHeapT() - { - Clear(); - delete [] m_items; - m_items = NULL; - } - -public: - /** Return the number of items stored in the priority queue. - * @return number of items in the queue */ - FORCEINLINE int Size() const {return m_size;}; - - /** Test if the priority queue is empty. - * @return true if empty */ - FORCEINLINE bool IsEmpty() const {return (m_size == 0);}; - - /** Test if the priority queue is full. - * @return true if full. */ - FORCEINLINE bool IsFull() const {return (m_size >= m_max_size);}; - - /** Find the smallest item in the priority queue. - * Return the smallest item, or throw assert if empty. */ - FORCEINLINE Titem_& GetHead() {assert(!IsEmpty()); return *m_items[1];} - - /** Insert new item into the priority queue, maintaining heap order. - * @return false if the queue is full. */ - bool Push(Titem_& new_item); - - /** Remove and return the smallest item from the priority queue. */ - FORCEINLINE Titem_& PopHead() {Titem_& ret = GetHead(); RemoveHead(); return ret;}; - - /** Remove the smallest item from the priority queue. */ - void RemoveHead(); - - /** Remove item specified by index */ - void RemoveByIdx(int idx); - - /** return index of the item that matches (using &item1 == &item2) the given item. */ - int FindLinear(const Titem_& item) const; - - /** Make the priority queue empty. - * All remaining items will remain untouched. */ - void Clear() {m_size = 0;}; - - /** verifies the heap consistency (added during first YAPF debug phase) */ - void CheckConsistency(); -}; - - -template <class Titem_> -FORCEINLINE bool CBinaryHeapT<Titem_>::Push(Titem_& new_item) -{ - if (IsFull()) return false; - - // make place for new item - int gap = ++m_size; - // Heapify up - for (int parent = gap / 2; (parent > 0) && (new_item < *m_items[parent]); gap = parent, parent /= 2) - m_items[gap] = m_items[parent]; - m_items[gap] = &new_item; - CheckConsistency(); - return true; -} - -template <class Titem_> -FORCEINLINE void CBinaryHeapT<Titem_>::RemoveHead() -{ - assert(!IsEmpty()); - - // at index 1 we have a gap now - int gap = 1; - - // Heapify down: - // last item becomes a candidate for the head. Call it new_item. - Titem_& new_item = *m_items[m_size--]; - - // now we must maintain relation between parent and its children: - // parent <= any child - // from head down to the tail - int child = 2; // first child is at [parent * 2] - - // while children are valid - while (child <= m_size) { - // choose the smaller child - if (child < m_size && *m_items[child + 1] < *m_items[child]) - child++; - // is it smaller than our parent? - if (!(*m_items[child] < new_item)) { - // the smaller child is still bigger or same as parent => we are done - break; - } - // if smaller child is smaller than parent, it will become new parent - m_items[gap] = m_items[child]; - gap = child; - // where do we have our new children? - child = gap * 2; - } - // move last item to the proper place - if (m_size > 0) m_items[gap] = &new_item; - CheckConsistency(); -} - -template <class Titem_> -inline void CBinaryHeapT<Titem_>::RemoveByIdx(int idx) -{ - // at position idx we have a gap now - int gap = idx; - Titem_& last = *m_items[m_size]; - if (idx < m_size) { - assert(idx >= 1); - m_size--; - // and the candidate item for fixing this gap is our last item 'last' - // Move gap / last item up: - while (gap > 1) - { - // compare [gap] with its parent - int parent = gap / 2; - if (last < *m_items[parent]) { - m_items[gap] = m_items[parent]; - gap = parent; - } else { - // we don't need to continue upstairs - break; - } - } - - // Heapify (move gap) down: - while (true) { - // where we do have our children? - int child = gap * 2; // first child is at [parent * 2] - if (child > m_size) break; - // choose the smaller child - if (child < m_size && *m_items[child + 1] < *m_items[child]) - child++; - // is it smaller than our parent? - if (!(*m_items[child] < last)) { - // the smaller child is still bigger or same as parent => we are done - break; - } - // if smaller child is smaller than parent, it will become new parent - m_items[gap] = m_items[child]; - gap = child; - } - // move parent to the proper place - if (m_size > 0) m_items[gap] = &last; - } - else { - assert(idx == m_size); - m_size--; - } - CheckConsistency(); -} - -template <class Titem_> -inline int CBinaryHeapT<Titem_>::FindLinear(const Titem_& item) const -{ - if (IsEmpty()) return 0; - for (ItemPtr *ppI = m_items + 1, *ppLast = ppI + m_size; ppI <= ppLast; ppI++) { - if (*ppI == &item) { - return ppI - m_items; - } - } - return 0; -} - -template <class Titem_> -FORCEINLINE void CBinaryHeapT<Titem_>::CheckConsistency() -{ - // enable it if you suspect binary heap doesn't work well -#if 0 - for (int child = 2; child <= m_size; child++) { - int parent = child / 2; - assert(!(m_items[child] < m_items[parent])); - } -#endif -} - - -#endif /* BINARYHEAP_HPP */
deleted file mode 100644 --- a/src/yapf/blob.hpp +++ /dev/null @@ -1,342 +0,0 @@ -/* $Id$ */ - -#ifndef BLOB_HPP -#define BLOB_HPP - -/** Type-safe version of memcpy(). - * @param d destination buffer - * @param s source buffer - * @param num_items number of items to be copied (!not number of bytes!) */ -template <class Titem_> -FORCEINLINE void MemCpyT(Titem_* d, const Titem_* s, int num_items = 1) -{ - memcpy(d, s, num_items * sizeof(Titem_)); -} - - -/** Base class for simple binary blobs. - * Item is byte. - * The word 'simple' means: - * - no configurable allocator type (always made from heap) - * - no smart deallocation - deallocation must be called from the same - * module (DLL) where the blob was allocated - * - no configurable allocation policy (how big blocks should be allocated) - * - no extra ownership policy (i.e. 'copy on write') when blob is copied - * - no thread synchronization at all - * - * Internal member layout: - * 1. The only class member is pointer to the first item (see union ptr_u). - * 2. Allocated block contains the blob header (see CHdr) followed by the raw byte data. - * Always, when it allocates memory the allocated size is: - * sizeof(CHdr) + <data capacity> - * 3. Two 'virtual' members (m_size and m_max_size) are stored in the CHdr at beginning - * of the alloated block. - * 4. The pointer (in ptr_u) points behind the header (to the first data byte). - * When memory block is allocated, the sizeof(CHdr) it added to it. - * 5. Benefits of this layout: - * - items are accessed in the simplest possible way - just dereferencing the pointer, - * which is good for performance (assuming that data are accessed most often). - * - sizeof(blob) is the same as the size of any other pointer - * 6. Drawbacks of this layout: - * - the fact, that pointer to the alocated block is adjusted by sizeof(CHdr) before - * it is stored can lead to several confusions: - * - it is not common pattern so the implementation code is bit harder to read - * - valgrind can generate warning that allocated block is lost (not accessible) - * */ -class CBlobBaseSimple { -protected: - /** header of the allocated memory block */ - struct CHdr { - int m_size; ///< actual blob size in bytes - int m_max_size; ///< maximum (allocated) size in bytes - }; - - /** type used as class member */ - union { - int8 *m_pData; ///< pointer to the first byte of data - CHdr *m_pHdr_1; ///< pointer just after the CHdr holding m_size and m_max_size - } ptr_u; - -public: - static const int Ttail_reserve = 4; ///< four extra bytes will be always allocated and zeroed at the end - - /** default constructor - initializes empty blob */ - FORCEINLINE CBlobBaseSimple() { InitEmpty(); } - /** copy constructor */ - FORCEINLINE CBlobBaseSimple(const CBlobBaseSimple& src) - { - InitEmpty(); - AppendRaw(src); - } - /** destructor */ - FORCEINLINE ~CBlobBaseSimple() { Free(); } -protected: - /** initialize the empty blob by setting the ptr_u.m_pHdr_1 pointer to the static CHdr with - * both m_size and m_max_size containing zero */ - FORCEINLINE void InitEmpty() { static CHdr hdrEmpty[] = {{0, 0}, {0, 0}}; ptr_u.m_pHdr_1 = &hdrEmpty[1]; } - /** initialize blob by attaching it to the given header followed by data */ - FORCEINLINE void Init(CHdr* hdr) { ptr_u.m_pHdr_1 = &hdr[1]; } - /** blob header accessor - use it rather than using the pointer arithmetics directly - non-const version */ - FORCEINLINE CHdr& Hdr() { return ptr_u.m_pHdr_1[-1]; } - /** blob header accessor - use it rather than using the pointer arithmetics directly - const version */ - FORCEINLINE const CHdr& Hdr() const { return ptr_u.m_pHdr_1[-1]; } - /** return reference to the actual blob size - used when the size needs to be modified */ - FORCEINLINE int& RawSizeRef() { return Hdr().m_size; }; - -public: - /** return true if blob doesn't contain valid data */ - FORCEINLINE bool IsEmpty() const { return RawSize() == 0; } - /** return the number of valid data bytes in the blob */ - FORCEINLINE int RawSize() const { return Hdr().m_size; }; - /** return the current blob capacity in bytes */ - FORCEINLINE int MaxRawSize() const { return Hdr().m_max_size; }; - /** return pointer to the first byte of data - non-const version */ - FORCEINLINE int8* RawData() { return ptr_u.m_pData; } - /** return pointer to the first byte of data - const version */ - FORCEINLINE const int8* RawData() const { return ptr_u.m_pData; } -#if 0 // reenable when needed - /** return the 32 bit CRC of valid data in the blob */ - FORCEINLINE uint32 Crc32() const {return CCrc32::Calc(RawData(), RawSize());} -#endif //0 - /** invalidate blob's data - doesn't free buffer */ - FORCEINLINE void Clear() { RawSizeRef() = 0; } - /** free the blob's memory */ - FORCEINLINE void Free() { if (MaxRawSize() > 0) {RawFree(&Hdr()); InitEmpty();} } - /** copy data from another blob - replaces any existing blob's data */ - FORCEINLINE void CopyFrom(const CBlobBaseSimple& src) { Clear(); AppendRaw(src); } - /** overtake ownership of data buffer from the source blob - source blob will become empty */ - FORCEINLINE void MoveFrom(CBlobBaseSimple& src) { Free(); ptr_u.m_pData = src.ptr_u.m_pData; src.InitEmpty(); } - /** swap buffers (with data) between two blobs (this and source blob) */ - FORCEINLINE void Swap(CBlobBaseSimple& src) { int8 *tmp = ptr_u.m_pData; ptr_u.m_pData = src.ptr_u.m_pData; src.ptr_u.m_pData = tmp; } - - /** append new bytes at the end of existing data bytes - reallocates if necessary */ - FORCEINLINE void AppendRaw(int8 *p, int num_bytes) - { - assert(p != NULL); - if (num_bytes > 0) { - memcpy(GrowRawSize(num_bytes), p, num_bytes); - } else { - assert(num_bytes >= 0); - } - } - - /** append bytes from given source blob to the end of existing data bytes - reallocates if necessary */ - FORCEINLINE void AppendRaw(const CBlobBaseSimple& src) - { - if (!src.IsEmpty()) - memcpy(GrowRawSize(src.RawSize()), src.RawData(), src.RawSize()); - } - - /** Reallocate if there is no free space for num_bytes bytes. - * @return pointer to the new data to be added */ - FORCEINLINE int8* MakeRawFreeSpace(int num_bytes) - { - assert(num_bytes >= 0); - int new_size = RawSize() + num_bytes; - if (new_size > MaxRawSize()) SmartAlloc(new_size); - FixTail(); - return ptr_u.m_pData + RawSize(); - } - - /** Increase RawSize() by num_bytes. - * @return pointer to the new data added */ - FORCEINLINE int8* GrowRawSize(int num_bytes) - { - int8* pNewData = MakeRawFreeSpace(num_bytes); - RawSizeRef() += num_bytes; - return pNewData; - } - - /** Decrease RawSize() by num_bytes. */ - FORCEINLINE void ReduceRawSize(int num_bytes) - { - if (MaxRawSize() > 0 && num_bytes > 0) { - assert(num_bytes <= RawSize()); - if (num_bytes < RawSize()) RawSizeRef() -= num_bytes; - else RawSizeRef() = 0; - } - } - /** reallocate blob data if needed */ - void SmartAlloc(int new_size) - { - int old_max_size = MaxRawSize(); - if (old_max_size >= new_size) return; - // calculate minimum block size we need to allocate - int min_alloc_size = sizeof(CHdr) + new_size + Ttail_reserve; - // ask allocation policy for some reasonable block size - int alloc_size = AllocPolicy(min_alloc_size); - // allocate new block - CHdr* pNewHdr = RawAlloc(alloc_size); - // setup header - pNewHdr->m_size = RawSize(); - pNewHdr->m_max_size = alloc_size - (sizeof(CHdr) + Ttail_reserve); - // copy existing data - if (RawSize() > 0) - memcpy(pNewHdr + 1, ptr_u.m_pData, pNewHdr->m_size); - // replace our block with new one - CHdr* pOldHdr = &Hdr(); - Init(pNewHdr); - if (old_max_size > 0) - RawFree(pOldHdr); - } - /** simple allocation policy - can be optimized later */ - FORCEINLINE static int AllocPolicy(int min_alloc) - { - if (min_alloc < (1 << 9)) { - if (min_alloc < (1 << 5)) return (1 << 5); - return (min_alloc < (1 << 7)) ? (1 << 7) : (1 << 9); - } - if (min_alloc < (1 << 15)) { - if (min_alloc < (1 << 11)) return (1 << 11); - return (min_alloc < (1 << 13)) ? (1 << 13) : (1 << 15); - } - if (min_alloc < (1 << 20)) { - if (min_alloc < (1 << 17)) return (1 << 17); - return (min_alloc < (1 << 19)) ? (1 << 19) : (1 << 20); - } - min_alloc = (min_alloc | ((1 << 20) - 1)) + 1; - return min_alloc; - } - - /** all allocation should happen here */ - static FORCEINLINE CHdr* RawAlloc(int num_bytes) { return (CHdr*)malloc(num_bytes); } - /** all deallocations should happen here */ - static FORCEINLINE void RawFree(CHdr* p) { free(p); } - /** fixing the four bytes at the end of blob data - useful when blob is used to hold string */ - FORCEINLINE void FixTail() - { - if (MaxRawSize() > 0) { - int8 *p = &ptr_u.m_pData[RawSize()]; - for (int i = 0; i < Ttail_reserve; i++) p[i] = 0; - } - } -}; - -/** Blob - simple dynamic Titem_ array. Titem_ (template argument) is a placeholder for any type. - * Titem_ can be any integral type, pointer, or structure. Using Blob instead of just plain C array - * simplifies the resource management in several ways: - * 1. When adding new item(s) it automatically grows capacity if needed. - * 2. When variable of type Blob comes out of scope it automatically frees the data buffer. - * 3. Takes care about the actual data size (number of used items). - * 4. Dynamically constructs only used items (as opposite of static array which constructs all items) */ -template <class Titem_, class Tbase_ = CBlobBaseSimple> -class CBlobT : public CBlobBaseSimple { - // make template arguments public: -public: - typedef Titem_ Titem; - typedef Tbase_ Tbase; - - static const int Titem_size = sizeof(Titem); - - /** Default constructor - makes new Blob ready to accept any data */ - FORCEINLINE CBlobT() : Tbase() {} - /** Copy constructor - make new blob to become copy of the original (source) blob */ - FORCEINLINE CBlobT(const Tbase& src) : Tbase(src) {assert((RawSize() % Titem_size) == 0);} - /** Destructor - ensures that allocated memory (if any) is freed */ - FORCEINLINE ~CBlobT() { Free(); } - /** Check the validity of item index (only in debug mode) */ - FORCEINLINE void CheckIdx(int idx) { assert(idx >= 0); assert(idx < Size()); } - /** Return pointer to the first data item - non-const version */ - FORCEINLINE Titem* Data() { return (Titem*)RawData(); } - /** Return pointer to the first data item - const version */ - FORCEINLINE const Titem* Data() const { return (const Titem*)RawData(); } - /** Return pointer to the idx-th data item - non-const version */ - FORCEINLINE Titem* Data(int idx) { CheckIdx(idx); return (Data() + idx); } - /** Return pointer to the idx-th data item - const version */ - FORCEINLINE const Titem* Data(int idx) const { CheckIdx(idx); return (Data() + idx); } - /** Return number of items in the Blob */ - FORCEINLINE int Size() const { return (RawSize() / Titem_size); } - /** Free the memory occupied by Blob destroying all items */ - FORCEINLINE void Free() - { - assert((RawSize() % Titem_size) == 0); - int old_size = Size(); - if (old_size > 0) { - // destroy removed items; - Titem* pI_last_to_destroy = Data(0); - for (Titem* pI = Data(old_size - 1); pI >= pI_last_to_destroy; pI--) pI->~Titem_(); - } - Tbase::Free(); - } - /** Grow number of data items in Blob by given number - doesn't construct items */ - FORCEINLINE Titem* GrowSizeNC(int num_items) { return (Titem*)GrowRawSize(num_items * Titem_size); } - /** Grow number of data items in Blob by given number - constructs new items (using Titem_'s default constructor) */ - FORCEINLINE Titem* GrowSizeC(int num_items) - { - Titem* pI = GrowSizeNC(num_items); - for (int i = num_items; i > 0; i--, pI++) new (pI) Titem(); - } - /** Destroy given number of items and reduce the Blob's data size */ - FORCEINLINE void ReduceSize(int num_items) - { - assert((RawSize() % Titem_size) == 0); - int old_size = Size(); - assert(num_items <= old_size); - int new_size = (num_items <= old_size) ? (old_size - num_items) : 0; - // destroy removed items; - Titem* pI_last_to_destroy = Data(new_size); - for (Titem* pI = Data(old_size - 1); pI >= pI_last_to_destroy; pI--) pI->~Titem(); - // remove them - ReduceRawSize(num_items * Titem_size); - } - /** Append one data item at the end (calls Titem_'s default constructor) */ - FORCEINLINE Titem* AppendNew() - { - Titem& dst = *GrowSizeNC(1); // Grow size by one item - Titem* pNewItem = new (&dst) Titem(); // construct the new item by calling in-place new operator - return pNewItem; - } - /** Append the copy of given item at the end of Blob (using copy constructor) */ - FORCEINLINE Titem* Append(const Titem& src) - { - Titem& dst = *GrowSizeNC(1); // Grow size by one item - Titem* pNewItem = new (&dst) Titem(src); // construct the new item by calling in-place new operator with copy ctor() - return pNewItem; - } - /** Add given items (ptr + number of items) at the end of blob */ - FORCEINLINE Titem* Append(const Titem* pSrc, int num_items) - { - Titem* pDst = GrowSizeNC(num_items); - Titem* pDstOrg = pDst; - Titem* pDstEnd = pDst + num_items; - while (pDst < pDstEnd) new (pDst++) Titem(*(pSrc++)); - return pDstOrg; - } - /** Remove item with the given index by replacing it by the last item and reducing the size by one */ - FORCEINLINE void RemoveBySwap(int idx) - { - CheckIdx(idx); - // destroy removed item - Titem* pRemoved = Data(idx); - RemoveBySwap(pRemoved); - } - /** Remove item given by pointer replacing it by the last item and reducing the size by one */ - FORCEINLINE void RemoveBySwap(Titem* pItem) - { - Titem* pLast = Data(Size() - 1); - assert(pItem >= Data() && pItem <= pLast); - // move last item to its new place - if (pItem != pLast) { - pItem->~Titem_(); - new (pItem) Titem_(*pLast); - } - // destroy the last item - pLast->~Titem_(); - // and reduce the raw blob size - ReduceRawSize(Titem_size); - } - /** Ensures that given number of items can be added to the end of Blob. Returns pointer to the - * first free (unused) item */ - FORCEINLINE Titem* MakeFreeSpace(int num_items) { return (Titem*)MakeRawFreeSpace(num_items * Titem_size); } -}; - -// simple string implementation -struct CStrA : public CBlobT<char> -{ - typedef CBlobT<char> base; - CStrA(const char* str = NULL) {Append(str);} - FORCEINLINE CStrA(const CBlobBaseSimple& src) : base(src) {} - void Append(const char* str) {if (str != NULL && str[0] != '\0') base::Append(str, (int)strlen(str));} -}; - -#endif /* BLOB_HPP */
deleted file mode 100644 --- a/src/yapf/countedptr.hpp +++ /dev/null @@ -1,100 +0,0 @@ -/* $Id$ */ - -#ifndef COUNTEDPTR_HPP -#define COUNTEDPTR_HPP - -#if 0 // reenable when needed -/** @file CCountedPtr - smart pointer implementation */ - -/** CCountedPtr - simple reference counting smart pointer. - * - * One of the standard ways how to maintain object's lifetime. - * - * See http://ootips.org/yonat/4dev/smart-pointers.html for more - * general info about smart pointers. - * - * This class implements ref-counted pointer for objects/interfaces that - * support AddRef() and Release() methods. - */ -template <class Tcls_> -class CCountedPtr { - /** redefine the template argument to make it visible for derived classes */ -public: - typedef Tcls_ Tcls; - -protected: - /** here we hold our pointer to the target */ - Tcls* m_pT; - -public: - /** default (NULL) construct or construct from a raw pointer */ - FORCEINLINE CCountedPtr(Tcls* pObj = NULL) : m_pT(pObj) {AddRef();}; - - /** copy constructor (invoked also when initializing from another smart ptr) */ - FORCEINLINE CCountedPtr(const CCountedPtr& src) : m_pT(src.m_pT) {AddRef();}; - - /** destructor releasing the reference */ - FORCEINLINE ~CCountedPtr() {Release();}; - -protected: - /** add one ref to the underlaying object */ - FORCEINLINE void AddRef() {if (m_pT != NULL) m_pT->AddRef();} - -public: - /** release smart pointer (and decrement ref count) if not null */ - FORCEINLINE void Release() {if (m_pT != NULL) {m_pT->Release(); m_pT = NULL;}} - - /** dereference of smart pointer - const way */ - FORCEINLINE const Tcls* operator -> () const {assert(m_pT != NULL); return m_pT;}; - - /** dereference of smart pointer - non const way */ - FORCEINLINE Tcls* operator -> () {assert(m_pT != NULL); return m_pT;}; - - /** raw pointer casting operator - const way */ - FORCEINLINE operator const Tcls*() const {assert(m_pT == NULL); return m_pT;} - - /** raw pointer casting operator - non-const way */ - FORCEINLINE operator Tcls*() {assert(m_pT == NULL); return m_pT;} - - /** operator & to support output arguments */ - FORCEINLINE Tcls** operator &() {assert(m_pT == NULL); return &m_pT;} - - /** assignment operator from raw ptr */ - FORCEINLINE CCountedPtr& operator = (Tcls* pT) {Assign(pT); return *this;} - - /** assignment operator from another smart ptr */ - FORCEINLINE CCountedPtr& operator = (CCountedPtr& src) {Assign(src.m_pT); return *this;} - - /** assignment operator helper */ - FORCEINLINE void Assign(Tcls* pT); - - /** one way how to test for NULL value */ - FORCEINLINE bool IsNull() const {return m_pT == NULL;} - - /** another way how to test for NULL value */ - FORCEINLINE bool operator == (const CCountedPtr& sp) const {return m_pT == sp.m_pT;} - - /** yet another way how to test for NULL value */ - FORCEINLINE bool operator != (const CCountedPtr& sp) const {return m_pT != sp.m_pT;} - - /** assign pointer w/o incrementing ref count */ - FORCEINLINE void Attach(Tcls* pT) {Release(); m_pT = pT;} - - /** detach pointer w/o decrementing ref count */ - FORCEINLINE Tcls* Detach() {Tcls* pT = m_pT; m_pT = NULL; return pT;} -}; - -template <class Tcls_> -FORCEINLINE void CCountedPtr<Tcls_>::Assign(Tcls* pT) -{ - // if they are the same, we do nothing - if (pT != m_pT) { - if (pT) pT->AddRef(); // AddRef new pointer if any - Tcls* pTold = m_pT; // save original ptr - m_pT = pT; // update m_pT to new value - if (pTold) pTold->Release(); // release old ptr if any - } -} - -#endif /* 0 */ -#endif /* COUNTEDPTR_HPP */
deleted file mode 100644 --- a/src/yapf/crc32.hpp +++ /dev/null @@ -1,65 +0,0 @@ -/* $Id$ */ - -#ifndef CRC32_HPP -#define CRC32_HPP - -#if 0 // reenable when needed -struct CCrc32 -{ - static uint32 Calc(const void *pBuffer, int nCount) - { - uint32 crc = 0xffffffff; - const uint32* pTable = CrcTable(); - - uint8* begin = (uint8*)pBuffer; - uint8* end = begin + nCount; - for(uint8* cur = begin; cur < end; cur++) - crc = (crc >> 8) ^ pTable[cur[0] ^ (uint8)(crc & 0xff)]; - crc ^= 0xffffffff; - - return crc; - } - - static const uint32* CrcTable() - { - static const uint32 Table[256] = - { - 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, - 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, - 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, - 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5, - 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, - 0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, - 0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F, - 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, - 0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433, - 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01, - 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, - 0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65, - 0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, - 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, - 0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F, - 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, - 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, - 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, - 0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7, - 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, - 0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B, - 0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79, - 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, - 0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D, - 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713, - 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, - 0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777, - 0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, - 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, - 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9, - 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF, - 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D - }; - return Table; - } -}; -#endif // 0 - -#endif /* CRC32_HPP */
deleted file mode 100644 --- a/src/yapf/fixedsizearray.hpp +++ /dev/null @@ -1,99 +0,0 @@ -/* $Id$ */ - -#ifndef FIXEDSIZEARRAY_HPP -#define FIXEDSIZEARRAY_HPP - - -/** fixed size array - * Upon construction it preallocates fixed size block of memory - * for all items, but doesn't construct them. Item's construction - * is delayed. */ -template <class Titem_, int Tcapacity_> -struct CFixedSizeArrayT { - /** the only member of fixed size array is pointer to the block - * of C array of items. Header can be found on the offset -sizeof(CHdr). */ - Titem_ *m_items; - - /** header for fixed size array */ - struct CHdr - { - int m_num_items; ///< number of items in the array - int m_ref_cnt; ///< block reference counter (used by copy constructor and by destructor) - }; - - // make types and constants visible from outside - typedef Titem_ Titem; // type of array item - - static const int Tcapacity = Tcapacity_; // the array capacity (maximum size) - static const int TitemSize = sizeof(Titem_); // size of item - static const int ThdrSize = sizeof(CHdr); // size of header - - /** Default constructor. Preallocate space for items and header, then initialize header. */ - CFixedSizeArrayT() - { - // allocate block for header + items (don't construct items) - m_items = (Titem*)(((int8*)malloc(ThdrSize + Tcapacity * sizeof(Titem))) + ThdrSize); - SizeRef() = 0; // initial number of items - RefCnt() = 1; // initial reference counter - } - - /** Copy constructor. Preallocate space for items and header, then initialize header. */ - CFixedSizeArrayT(const CFixedSizeArrayT<Titem_, Tcapacity_>& src) - { - // share block (header + items) with the source array - m_items = src.m_items; - RefCnt()++; // now we share block with the source - } - - /** destroy remaining items and free the memory block */ - ~CFixedSizeArrayT() - { - // release one reference to the shared block - if ((--RefCnt()) > 0) return; // and return if there is still some owner - - Clear(); - // free the memory block occupied by items - free(((int8*)m_items) - ThdrSize); - m_items = NULL; - } - - /** Clear (destroy) all items */ - FORCEINLINE void Clear() - { - // walk through all allocated items backward and destroy them - for (Titem* pItem = &m_items[Size() - 1]; pItem >= m_items; pItem--) { - pItem->~Titem_(); - } - // number of items become zero - SizeRef() = 0; - } - -protected: - /** return reference to the array header (non-const) */ - FORCEINLINE CHdr& Hdr() { return *(CHdr*)(((int8*)m_items) - ThdrSize); } - /** return reference to the array header (const) */ - FORCEINLINE const CHdr& Hdr() const { return *(CHdr*)(((int8*)m_items) - ThdrSize); } - /** return reference to the block reference counter */ - FORCEINLINE int& RefCnt() { return Hdr().m_ref_cnt; } - /** return reference to number of used items */ - FORCEINLINE int& SizeRef() { return Hdr().m_num_items; } -public: - /** return number of used items */ - FORCEINLINE int Size() const { return Hdr().m_num_items; } - /** return true if array is full */ - FORCEINLINE bool IsFull() const { return Size() >= Tcapacity; }; - /** return true if array is empty */ - FORCEINLINE bool IsEmpty() const { return Size() <= 0; }; - /** index validation */ - FORCEINLINE void CheckIdx(int idx) const { assert(idx >= 0); assert(idx < Size()); } - /** add (allocate), but don't construct item */ - FORCEINLINE Titem& AddNC() { assert(!IsFull()); return m_items[SizeRef()++]; } - /** add and construct item using default constructor */ - FORCEINLINE Titem& Add() { Titem& item = AddNC(); new(&item)Titem; return item; } - /** return item by index (non-const version) */ - FORCEINLINE Titem& operator [] (int idx) { CheckIdx(idx); return m_items[idx]; } - /** return item by index (const version) */ - FORCEINLINE const Titem& operator [] (int idx) const { CheckIdx(idx); return m_items[idx]; } -}; - -#endif /* FIXEDSIZEARRAY_HPP */
deleted file mode 100644 --- a/src/yapf/hashtable.hpp +++ /dev/null @@ -1,240 +0,0 @@ -/* $Id$ */ - -#ifndef HASHTABLE_HPP -#define HASHTABLE_HPP - -template <class Titem_> -struct CHashTableSlotT -{ - typedef typename Titem_::Key Key; // make Titem_::Key a property of HashTable - - Titem_* m_pFirst; - - CHashTableSlotT() : m_pFirst(NULL) {} - - /** hash table slot helper - clears the slot by simple forgetting its items */ - FORCEINLINE void Clear() {m_pFirst = NULL;} - - /** hash table slot helper - linear search for item with given key through the given blob - const version */ - FORCEINLINE const Titem_* Find(const Key& key) const - { - for (const Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) { - if (pItem->GetKey() == key) { - // we have found the item, return it - return pItem; - } - } - return NULL; - } - - /** hash table slot helper - linear search for item with given key through the given blob - non-const version */ - FORCEINLINE Titem_* Find(const Key& key) - { - for (Titem_* pItem = m_pFirst; pItem != NULL; pItem = pItem->GetHashNext()) { - if (pItem->GetKey() == key) { - // we have found the item, return it - return pItem; - } - } - return NULL; - } - - /** hash table slot helper - add new item to the slot */ - FORCEINLINE void Attach(Titem_& new_item) - { - assert(new_item.GetHashNext() == NULL); - new_item.SetHashNext(m_pFirst); - m_pFirst = &new_item; - } - - /** hash table slot helper - remove item from a slot */ - FORCEINLINE bool Detach(Titem_& item_to_remove) - { - if (m_pFirst == &item_to_remove) { - m_pFirst = item_to_remove.GetHashNext(); - item_to_remove.SetHashNext(NULL); - return true; - } - Titem_* pItem = m_pFirst; - while (true) { - if (pItem == NULL) { - return false; - } - Titem_* pNextItem = pItem->GetHashNext(); - if (pNextItem == &item_to_remove) break; - pItem = pNextItem; - } - pItem->SetHashNext(item_to_remove.GetHashNext()); - item_to_remove.SetHashNext(NULL); - return true; - } - - /** hash table slot helper - remove and return item from a slot */ - FORCEINLINE Titem_* Detach(const Key& key) - { - // do we have any items? - if (m_pFirst == NULL) { - return NULL; - } - // is it our first item? - if (m_pFirst->GetKey() == key) { - Titem_& ret_item = *m_pFirst; - m_pFirst = m_pFirst->GetHashNext(); - ret_item.SetHashNext(NULL); - return &ret_item; - } - // find it in the following items - Titem_* pPrev = m_pFirst; - for (Titem_* pItem = m_pFirst->GetHashNext(); pItem != NULL; pPrev = pItem, pItem = pItem->GetHashNext()) { - if (pItem->GetKey() == key) { - // we have found the item, unlink and return it - pPrev->SetHashNext(pItem->GetHashNext()); - pItem->SetHashNext(NULL); - return pItem; - } - } - return NULL; - } -}; - -/** @class CHashTableT<Titem, Thash_bits> - simple hash table - * of pointers allocated elsewhere. - * - * Supports: Add/Find/Remove of Titems. - * - * Your Titem must meet some extra requirements to be CHashTableT - * compliant: - * - its constructor/destructor (if any) must be public - * - if the copying of item requires an extra resource management, - * you must define also copy constructor - * - must support nested type (struct, class or typedef) Titem::Key - * that defines the type of key class for that item - * - must support public method: - * const Key& GetKey() const; // return the item's key object - * - * In addition, the Titem::Key class must support: - * - public method that calculates key's hash: - * int CalcHash() const; - * - public 'equality' operator to compare the key with another one - * bool operator == (const Key& other) const; - */ -template <class Titem_, int Thash_bits_> -class CHashTableT { -public: - typedef Titem_ Titem; // make Titem_ visible from outside of class - typedef typename Titem_::Key Tkey; // make Titem_::Key a property of HashTable - static const int Thash_bits = Thash_bits_; // publish num of hash bits - static const int Tcapacity = 1 << Thash_bits; // and num of slots 2^bits - -protected: - /** each slot contains pointer to the first item in the list, - * Titem contains pointer to the next item - GetHashNext(), SetHashNext() */ - typedef CHashTableSlotT<Titem_> Slot; - - Slot* m_slots; // here we store our data (array of blobs) - int m_num_items; // item counter - -public: - // default constructor - FORCEINLINE CHashTableT() - { - // construct all slots - m_slots = new Slot[Tcapacity]; - m_num_items = 0; - } - - ~CHashTableT() {delete [] m_slots; m_num_items = 0; m_slots = NULL;} - -protected: - /** static helper - return hash for the given key modulo number of slots */ - FORCEINLINE static int CalcHash(const Tkey& key) - { - int32 hash = key.CalcHash(); - if ((8 * Thash_bits) < 32) hash ^= hash >> (min(8 * Thash_bits, 31)); - if ((4 * Thash_bits) < 32) hash ^= hash >> (min(4 * Thash_bits, 31)); - if ((2 * Thash_bits) < 32) hash ^= hash >> (min(2 * Thash_bits, 31)); - if ((1 * Thash_bits) < 32) hash ^= hash >> (min(1 * Thash_bits, 31)); - hash &= (1 << Thash_bits) - 1; - return hash; - } - - /** static helper - return hash for the given item modulo number of slots */ - FORCEINLINE static int CalcHash(const Titem_& item) {return CalcHash(item.GetKey());} - -public: - /** item count */ - FORCEINLINE int Count() const {return m_num_items;} - - /** simple clear - forget all items - used by CSegmentCostCacheT.Flush() */ - FORCEINLINE void Clear() const {for (int i = 0; i < Tcapacity; i++) m_slots[i].Clear();} - - /** const item search */ - const Titem_* Find(const Tkey& key) const - { - int hash = CalcHash(key); - const Slot& slot = m_slots[hash]; - const Titem_* item = slot.Find(key); - return item; - } - - /** non-const item search */ - Titem_* Find(const Tkey& key) - { - int hash = CalcHash(key); - Slot& slot = m_slots[hash]; - Titem_* item = slot.Find(key); - return item; - } - - /** non-const item search & optional removal (if found) */ - Titem_* TryPop(const Tkey& key) - { - int hash = CalcHash(key); - Slot& slot = m_slots[hash]; - Titem_* item = slot.Detach(key); - if (item != NULL) { - m_num_items--; - } - return item; - } - - /** non-const item search & removal */ - Titem_& Pop(const Tkey& key) - { - Titem_* item = TryPop(key); - assert(item != NULL); - return *item; - } - - /** non-const item search & optional removal (if found) */ - bool TryPop(Titem_& item) - { - const Tkey& key = item.GetKey(); - int hash = CalcHash(key); - Slot& slot = m_slots[hash]; - bool ret = slot.Detach(item); - if (ret) { - m_num_items--; - } - return ret; - } - - /** non-const item search & removal */ - void Pop(Titem_& item) - { - bool ret = TryPop(item); - assert(ret); - } - - /** add one item - copy it from the given item */ - void Push(Titem_& new_item) - { - int hash = CalcHash(new_item); - Slot& slot = m_slots[hash]; - assert(slot.Find(new_item.GetKey()) == NULL); - slot.Attach(new_item); - m_num_items++; - } -}; - -#endif /* HASHTABLE_HPP */
--- a/src/yapf/nodelist.hpp +++ b/src/yapf/nodelist.hpp @@ -3,9 +3,9 @@ #ifndef NODELIST_HPP #define NODELIST_HPP -#include "array.hpp" -#include "hashtable.hpp" -#include "binaryheap.hpp" +#include "../misc/array.hpp" +#include "../misc/hashtable.hpp" +#include "../misc/binaryheap.hpp" /** Hash table based node list multi-container class. * Implements open list, closed list and priority queue for A-star
--- a/src/yapf/yapf.hpp +++ b/src/yapf/yapf.hpp @@ -71,12 +71,12 @@ //#undef FORCEINLINE //#define FORCEINLINE inline -#include "crc32.hpp" -#include "blob.hpp" -#include "fixedsizearray.hpp" -#include "array.hpp" -#include "hashtable.hpp" -#include "binaryheap.hpp" +#include "../misc/crc32.hpp" +#include "../misc/blob.hpp" +#include "../misc/fixedsizearray.hpp" +#include "../misc/array.hpp" +#include "../misc/hashtable.hpp" +#include "../misc/binaryheap.hpp" #include "nodelist.hpp" #include "yapf_base.hpp" #include "yapf_node.hpp"