diff options
Diffstat (limited to 'Build/source/libs/graphite/src/generic')
-rw-r--r-- | Build/source/libs/graphite/src/generic/BinTree.h | 71 | ||||
-rw-r--r-- | Build/source/libs/graphite/src/generic/BinTree_i.cpp | 225 | ||||
-rw-r--r-- | Build/source/libs/graphite/src/generic/Debug.cpp | 83 | ||||
-rw-r--r-- | Build/source/libs/graphite/src/generic/GenericResource.h | 86 | ||||
-rw-r--r-- | Build/source/libs/graphite/src/generic/HashMap.h | 328 | ||||
-rw-r--r-- | Build/source/libs/graphite/src/generic/HashMap_i.cpp | 561 | ||||
-rw-r--r-- | Build/source/libs/graphite/src/generic/Makefile.am | 8 | ||||
-rw-r--r-- | Build/source/libs/graphite/src/generic/Util.cpp | 261 |
8 files changed, 1623 insertions, 0 deletions
diff --git a/Build/source/libs/graphite/src/generic/BinTree.h b/Build/source/libs/graphite/src/generic/BinTree.h new file mode 100644 index 00000000000..a487df03770 --- /dev/null +++ b/Build/source/libs/graphite/src/generic/BinTree.h @@ -0,0 +1,71 @@ +/*--------------------------------------------------------------------*//*:Ignore this sentence. +Copyright (C) 1999, 2001 SIL International. All rights reserved. + +Distributable under the terms of either the Common Public License or the +GNU Lesser General Public License, as specified in the LICENSING.txt file. + +File: BinTree.h +Responsibility: Darrell Zook +Last reviewed: 9/8/99 + +Description: + This file provides declarations of binary tree class(es). +----------------------------------------------------------------------------------------------*/ +#ifdef _MSC_VER +#pragma once +#endif +#ifndef BINTREE_H_INCLUDED +#define BINTREE_H_INCLUDED + +/*---------------------------------------------------------------------------------------------- + This template class implements a balanced tree, which is a binary tree where the height of + the two children of any node in the tree can only be different by +/- 1 or 0. + + The class of objects to be stored in the tree should be derived from BalTreeBase, because + the constructor of BalTreeBase adds an object to the tree in sorted order without + allocating any memory. + + Classes that derive from BalTreeBase must have a CompareKey member function that compares + a given key with this->key to determine which should be first when sorting the tree. + The declaration of CompareKey should be as follows: + int CompareKey(const Key & key); + and it should return: + <0 if key is less than the key in the current node (this->key) + 0 if key is equal to the key in the current node (this->key) + >0 if key is greater than the key in the current node (this->key) + + CAUTION: Classes that use this template should never be dynamically instantiated (by using + local variables or new/NewObj). This class is meant to be used only for global + instances of a class. The reason for this restriction is that the tree is never + destroyed, so using dynamic instantiations of objects would result in stale pointers + in the tree. + + Hungarian: btb +----------------------------------------------------------------------------------------------*/ + +template<typename Obj, typename Key> class BalTreeBase +{ +protected: + // Pointers to the left and right subtrees. + Obj * m_rgpobj[2]; + + // The difference between the height of the right sub tree and the height of the left + // sub tree. This should be -1, 0, or +1. Insert may temporarily set it to -2 or +2. + short m_dht; + + // Which way we went from this node when inserting the new node. + short m_ipobj; + + // Inserts this in the balanced tree. + BalTreeBase(Obj ** ppobjRoot, const Key & key); + + // Returns a node with the given key from the tree rooted at pobjRoot. + static Obj * Find(Obj * pobjRoot, const Key & key); + +private: + // Inserts a node in the tree rooted at *ppobjRoot, sorting it based on key. + void Insert(Obj ** ppobjRoot, const Key & key); +}; + +#endif // !BINTREE_H_INCLUDED + diff --git a/Build/source/libs/graphite/src/generic/BinTree_i.cpp b/Build/source/libs/graphite/src/generic/BinTree_i.cpp new file mode 100644 index 00000000000..5929bf0bab1 --- /dev/null +++ b/Build/source/libs/graphite/src/generic/BinTree_i.cpp @@ -0,0 +1,225 @@ +/*--------------------------------------------------------------------*//*:Ignore this sentence. +Copyright (C) 1999, 2001 SIL International. All rights reserved. + +Distributable under the terms of either the Common Public License or the +GNU Lesser General Public License, as specified in the LICENSING.txt file. + +File: BinTree_i.cpp +Responsibility: Darrell Zook +Last reviewed: 9/8/99 + +Description: + This file provides implementations of binary tree class(es). + It is used as an #include file in any file which derives from one of the classes. +----------------------------------------------------------------------------------------------*/ +#ifdef _MSC_VER +#pragma once +#endif +#ifndef BINTREE_I_CPP_INCLUDED +#define BINTREE_I_CPP_INCLUDED + +#include "BinTree.h" +////#include <algorithm> +////#include "GrPlatform.h" +#include "GrCommon.h" + + +//using namespace gr; + +/*********************************************************************************************** + BalTreeBase<Obj, Key> methods +***********************************************************************************************/ + +/*---------------------------------------------------------------------------------------------- + Constructor. + This calls Insert to add this node to the tree in the correct (sorted) position. + + Arguments: + [in] ppobjRoot -> The address of the pointer to the root node of the tree. + [in] key -> References the key of the node to insert. +----------------------------------------------------------------------------------------------*/ +template<typename Obj, typename Key> + BalTreeBase<Obj, Key>::BalTreeBase(Obj ** ppobjRoot, const Key & key) +{ + AssertPtr(ppobjRoot); + AssertPtrN(*ppobjRoot); + + m_rgpobj[0] = NULL; + m_rgpobj[1] = NULL; + m_dht = 0; + + Insert(ppobjRoot, key); +} + +/*---------------------------------------------------------------------------------------------- + This method finds a node with the given key within the tree. If the key is not found in + the tree, NULL is returned. + + Arguments: + [in] pobjRoot -> Points to the root node of the tree. + [in] key -> References the key of the node to search for. +----------------------------------------------------------------------------------------------*/ +template<typename Obj, typename Key> + Obj * BalTreeBase<Obj, Key>::Find(Obj * pobjRoot, const Key & key) +{ + AssertPtrN(pobjRoot); + + for (Obj * pobj = pobjRoot; pobj; ) + { + int nT = pobj->CompareKey(key); + if (0 == nT) + return pobj; + pobj = pobj->m_rgpobj[nT > 0]; + } + return NULL; +} + +/*---------------------------------------------------------------------------------------------- + This method inserts a node within the tree, sorting it based on key. It does not allocate + any memory. + + Arguments: + [in] ppobjRoot -> The address of the pointer to the root node of the tree. + [in] key -> References the key of the node to insert into the tree. + Note: "this" is the node that is being inserted into the tree. +----------------------------------------------------------------------------------------------*/ +template<typename Obj, typename Key> + void BalTreeBase<Obj, Key>::Insert(Obj ** ppobjRoot, const Key & key) +{ + AssertPtr(ppobjRoot); + AssertPtrN(*ppobjRoot); + + Assert(m_dht == 0); + Assert(!m_rgpobj[0]); + Assert(!m_rgpobj[1]); + + Obj * pobjThis = static_cast<Obj *>(this); + + // If the tree is empty, set the root of the tree to this and return. + if (!*ppobjRoot) + { + *ppobjRoot = pobjThis; + return; + } + + Obj ** ppobjRebal = ppobjRoot; + Obj * pobjCur; + + // Place this in the tree. Mark each node indicating which branch we took. + // Remember the lowest node with non-zero m_dht in ppobjRebal. If we have to do + // rebalancing, this is where we'll do it. + for (pobjCur = *ppobjRoot; ; ) + { + AssertPtr(pobjCur); + + int nT = pobjCur->CompareKey(key); + Assert(nT != 0); + + // if nT is positive go right, otherwise go left. + pobjCur->m_ipobj = nT > 0; + + Obj ** ppobjNext = &pobjCur->m_rgpobj[pobjCur->m_ipobj]; + if (!*ppobjNext) + { + // Place the node and break. + *ppobjNext = pobjThis; + break; + } + + // Remember this location if m_dht is non-zero. + if ((*ppobjNext)->m_dht != 0) + ppobjRebal = ppobjNext; + + // Move on down. + pobjCur = *ppobjNext; + } + + // Adjust m_dht from *ppobjRebal to pobjThis. + for (pobjCur = *ppobjRebal; pobjCur != pobjThis; ) + { + AssertPtr(pobjCur); + Assert((unsigned int)pobjCur->m_ipobj < (unsigned int)2); + + // Recall that ppobjRebal is the lowest node on the path which has non-zero m_dht. + Assert(pobjCur->m_dht == 0 || pobjCur == *ppobjRebal); + + // If we went left (m_ipobj == 0) we need to subtract one. If we went right + // (m_ipobj == 1) we need to add one. + pobjCur->m_dht = (short)(pobjCur->m_dht + (pobjCur->m_ipobj << 1) - 1); + pobjCur = pobjCur->m_rgpobj[pobjCur->m_ipobj]; + } + + if ((unsigned int)((*ppobjRebal)->m_dht + 1) <= (unsigned int)2) + { + // No need to rebalance since the new m_dht for *ppobjRebal is within -1 to 1. + return; + } + + // We need to rebalance. + Obj * pobjRebal = *ppobjRebal; + Assert(pobjRebal->m_dht == -2 || pobjRebal->m_dht == 2); + + // Get the direction from pobjRebal and the next lower node. + int ipobj = pobjRebal->m_ipobj; + Obj * pobjChd = pobjRebal->m_rgpobj[ipobj]; + + if (pobjChd->m_ipobj == ipobj) + { + // We branched the same way at pobjRebal and pobjChd. + // Do a single rotation: make pobjChd the parent of pobjRebal. + Assert(pobjChd->m_dht << 1 == pobjRebal->m_dht); + pobjRebal->m_rgpobj[ipobj] = pobjChd->m_rgpobj[1 - ipobj]; + pobjChd->m_rgpobj[1 - ipobj] = pobjRebal; + *ppobjRebal = pobjChd; + + // Fix the m_dht values. + pobjChd->m_dht = 0; + pobjRebal->m_dht = 0; + return; + } + + // We branched opposite ways at pobjRebal and pobjChd. + // Do a double rotation. + Assert(pobjChd->m_ipobj == 1 - ipobj); + pobjCur = pobjChd->m_rgpobj[1 - ipobj]; + AssertPtr(pobjCur); + + // Let (A own[ipobj] B) mean that A->m_rgpobj[ipobj] == B. + // Currently, (pobjRebal own[ipobj] pobjChd) and (pobjChd own[1 - ipobj] pobjCur). + // Make (pobjCur own[ipobj] pobjChd) and (pobjCur own[1 - ipobj] pobjRebal). + + // Rotate pobjChd and pobjCur. + Assert(pobjCur == pobjChd->m_rgpobj[1 - ipobj]); + pobjChd->m_rgpobj[1 - ipobj] = pobjCur->m_rgpobj[ipobj]; + pobjCur->m_rgpobj[ipobj] = pobjChd; + + // Rotate pobjRebal and pobjCur. + Assert(pobjRebal->m_rgpobj[ipobj] == pobjChd); + pobjRebal->m_rgpobj[ipobj] = pobjCur->m_rgpobj[1 - ipobj]; + pobjCur->m_rgpobj[1 - ipobj] = pobjRebal; + + // Fix *ppobjRebal. + *ppobjRebal = pobjCur; + + // Fix the m_dht values. Note that we don't compare with pobjRebal->m_dht since it + // currently has absolute value 2. + Assert(pobjChd->m_dht); + if (pobjCur->m_dht == pobjChd->m_dht) + { + pobjRebal->m_dht = 0; + pobjChd->m_dht = (short)-pobjChd->m_dht; + } + else if (pobjCur->m_dht == -pobjChd->m_dht) + { + pobjRebal->m_dht = pobjChd->m_dht; + pobjChd->m_dht = 0; + } + else + { + pobjRebal->m_dht = 0; + pobjChd->m_dht = 0; + } + pobjCur->m_dht = 0; +} + +#endif // !BINTREE_I_CPP_INCLUDED diff --git a/Build/source/libs/graphite/src/generic/Debug.cpp b/Build/source/libs/graphite/src/generic/Debug.cpp new file mode 100644 index 00000000000..d1f2a67e364 --- /dev/null +++ b/Build/source/libs/graphite/src/generic/Debug.cpp @@ -0,0 +1,83 @@ +/*--------------------------------------------------------------------*//*:Ignore this sentence. +Copyright (C) 1999, 2001 SIL International. All rights reserved. + +Distributable under the terms of either the Common Public License or the +GNU Lesser General Public License, as specified in the LICENSING.txt file. + +File: Debug.cpp +Responsibility: Darrell Zook +Last reviewed: Not yet. + +Description: + This file provides the standard debug error functions. +----------------------------------------------------------------------------------------------*/ + +#ifdef _WIN32 +#include <windows.h> +#endif +//#include "common.h" +//#include "Main.h" +#include "GrDebug.h" +#ifdef _MSC_VER +#pragma hdrstop +#endif +#undef THIS_FILE +DEFINE_THIS_FILE + +//#include "ModuleEntry.h" +#include <stdio.h> +#ifdef _MSC_VER +#include <crtdbg.h> +#endif + + +#if 0 +//#ifdef DEBUG + +extern HMODULE Win32DllGetModuleHandle(); + +void WINAPI AssertProcLocal(const char * pszExp, const char * pszFile, int nLine, + bool fCritical) +{ + AssertProc(pszExp, pszFile, nLine, fCritical, Win32DllGetModuleHandle()); +} + +void WINAPI WarnProcLocal(const char * pszExp, const char * pszFile, int nLine, + bool fCritical) +{ + WarnProc(pszExp, pszFile, nLine, fCritical, Win32DllGetModuleHandle()); +} + +void WINAPI WarnHrProc(HRESULT hr, const char * pszFile, int nLine, bool fCritical) +{ + char szBuffer[MAX_PATH + 25]; + sprintf(szBuffer, "HRESULT[0x%08x]--", hr); + int cch = lstrlen(szBuffer); + FormatMessage(FORMAT_MESSAGE_FROM_SYSTEM, NULL, hr, 0, szBuffer + cch, + sizeof(szBuffer) - cch, NULL); + szBuffer[max(lstrlen(szBuffer) - 2, 0)] = 0; + WarnProcLocal(szBuffer, pszFile, nLine, fCritical); +} + + +OLECHAR * DebugWatch::WatchNV() +{ + // JT: we need this, otherwise if dealing with a deleted object or null pointer + // we may try to call a virtual function where there is no valid VTABLE pointer. + // In the debugger we can't be sure of not dereferencing a bad pointer. + if (!::_CrtIsValidPointer(this, isizeof(this), TRUE )) + return L"A very bad object pointer"; + // We could also be referencing memory that is trashed (e.g., the object has + // been deleted, or deleted and replaced by something else). + if (!dynamic_cast<DebugWatch *>(this)) + return L"A bad object pointer"; + return Watch(); +} + +void DebugWatch::Output (char *fmt, ...) // LIMITED to 10 pointer-sized arguments +{ + struct args { void * pv[10]; }; + _CrtDbgReport (_CRT_WARN, NULL, NULL, __FILE__, fmt, *(args*)(&fmt+1)); +} + +#endif // DEBUG diff --git a/Build/source/libs/graphite/src/generic/GenericResource.h b/Build/source/libs/graphite/src/generic/GenericResource.h new file mode 100644 index 00000000000..119c6317bcd --- /dev/null +++ b/Build/source/libs/graphite/src/generic/GenericResource.h @@ -0,0 +1,86 @@ +/*--------------------------------------------------------------------*//*:Ignore this sentence. +Copyright (C) 1999, 2001 SIL International. All rights reserved. + +Distributable under the terms of either the Common Public License or the +GNU Lesser General Public License, as specified in the LICENSING.txt file. + +File: GenericResource.h +Responsibility: John Thomson +Last reviewed: + + Resources needed by certain generic components (but must be created in app's or AppCore's + resource file). +----------------------------------------------------------------------------------------------*/ +#ifdef _MSC_VER +#pragma once +#endif +#ifndef GenericResource_H +#define GenericResource_H 1 +// Create suitable resources for these if your app uses StackDumper. +// For example +// STRINGTABLE DISCARDABLE +// BEGIN +// "A programming error (%s) has been detected in module %s.\n Please report this to the developers", kstidInternalError +// "Out of memory. To attempt Save, close other apps and click OK. To quit without saving click Cancel", kstidOutOfMemory +// END + + +// Date qualifier string IDs: +#define kstidDateQualBefore 24200 +#define kstidDateQualOn 24201 +#define kstidDateQualAbout 24202 +#define kstidDateQualAfter 24203 +#define kstidDateQualAbt 24204 +#define kstidDateQualBC 24205 +#define kstidDateQualAD 24206 +#define kstidDateBlank 24207 +#define kstidDateBlankM 24208 +#define kstidDateBlankD 24209 + + +#define kstidInternalError 25900 +#define khcidHelpOutOfMemory 25901 +#define khcidNoHelpAvailable 25902 // default help module when there is no specific one. +#define kstidOutOfMemory 25903 +#define kstidUndoFrame 25904 +#define kstidRedoFrame 25905 + +#define kstidFileErrUnknown 25920 +#define kstidFileErrNotFound 25921 +#define kstidFileErrPathNotFound 25922 +#define kstidFileErrTooManyFiles 25923 +#define kstidFileErrAccDenied 25924 +#define kstidFileErrBadHandle 25925 +#define kstidFileErrBadDrive 25926 +#define kstidFileErrWriteProtect 25927 +#define kstidFileErrBadUnit 25928 +#define kstidFileErrNotReady 25929 +#define kstidFileErrSeek 25930 +#define kstidFileErrNotDosDisk 25931 +#define kstidFileErrBadSector 25932 +#define kstidFileErrWriteFault 25933 +#define kstidFileErrReadFault 25934 +#define kstidFileErrGeneral 25935 +#define kstidFileErrSharing 25936 +#define kstidFileErrLock 25937 +#define kstidFileErrEof 25938 +#define kstidFileErrHandleDiskFull 25939 +#define kstidFileErrBadNetPath 25940 +#define kstidFileErrNetworkBusy 25941 +#define kstidFileErrNoDevice 25942 +#define kstidFileErrNoNetAccess 25943 +#define kstidFileErrBadDevice 25944 +#define kstidFileErrBadNetName 25945 +#define kstidFileErrExists 25946 +#define kstidFileErrCantMake 25947 +#define kstidFileErrBadPassword 25948 +#define kstidFileErrNetWriteFault 25949 +#define kstidFileErrDriveLocked 25950 +#define kstidFileErrOpenFailed 25951 +#define kstidFileErrBufOverflow 25952 +#define kstidFileErrDiskFull 25953 +#define kstidFileErrBadName 25954 +#define kstidFileErrNoVolLabel 25955 +#define kstidFileErrAlreadyExists 25956 + +#endif // !GenericResource_H diff --git a/Build/source/libs/graphite/src/generic/HashMap.h b/Build/source/libs/graphite/src/generic/HashMap.h new file mode 100644 index 00000000000..dc2de9d0af7 --- /dev/null +++ b/Build/source/libs/graphite/src/generic/HashMap.h @@ -0,0 +1,328 @@ +/*--------------------------------------------------------------------*//*:Ignore this sentence. +Copyright (C) 2001 SIL International. All rights reserved. + +Distributable under the terms of either the Common Public License or the +GNU Lesser General Public License, as specified in the LICENSING.txt file. + +File: HashMap.h +Responsibility: Steve McConnel +Last reviewed: Not yet. + +Description: + This provides a set of template collection classes to replace std::map. Their primary + reason to exist is to allow explicit checking for internal memory allocation failures. +----------------------------------------------------------------------------------------------*/ +#pragma once +#ifndef HASHMAP_H_INCLUDED +#define HASHMAP_H_INCLUDED +//:End Ignore + +/*---------------------------------------------------------------------------------------------- + Functor class for computing a hash value from an arbitrary object. + + Hungarian: hsho +----------------------------------------------------------------------------------------------*/ +class HashObj +{ +public: + int operator () (void * pKey, int cbKey); +}; + +/*---------------------------------------------------------------------------------------------- + Functor class for comparing two arbitrary objects (of the same class) for equality. + + Hungarian: eqlo +----------------------------------------------------------------------------------------------*/ +class EqlObj +{ +public: + bool operator () (void * pKey1, void * pKey2, int cbKey); +}; + +/*---------------------------------------------------------------------------------------------- + Hash map template collection class whose keys are objects of an arbitrary class. + + Hungarian: hm[K][T] +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H = HashObj, class Eq = EqlObj> class HashMap +{ +public: + //:> Member classes + + /*------------------------------------------------------------------------------------------ + This is the basic data structure for storing one key-value pair in a hash map. In + order to handle hash collisions, this structure is a member of a linked list. + Hungarian: hsnd + ------------------------------------------------------------------------------------------*/ + class HashNode + { + public: + //:> Constructors/destructors/etc. + + HashNode(void) + : m_key(K()), m_value(T()), m_nHash(0), m_ihsndNext(0) + { + } + HashNode(K & key, T & value, int nHash, int ihsndNext = -1) + : m_key(key), m_value(value), m_nHash(nHash), m_ihsndNext(ihsndNext) + { + } + ~HashNode() + { + } + + //:> Member variable access + + void PutKey(K & key) + { + m_key = key; + } + K & GetKey() + { + return m_key; + } + void PutValue(T & value) + { + m_value = value; + } + T & GetValue() + { + return m_value; + } + void PutHash(int nHash) + { + m_nHash = nHash; + } + int GetHash() + { + return m_nHash; + } + void PutNext(int ihsndNext) + { + m_ihsndNext = ihsndNext; + } + int GetNext() + { + return m_ihsndNext; + } + + /*-------------------------------------------------------------------------------------- + Check whether the given HashNode is being used. + --------------------------------------------------------------------------------------*/ + bool InUse() + { + return m_ihsndNext >= -1; + } + + protected: + //:> Member variables + + K m_key; + T m_value; + int m_nHash; + int m_ihsndNext; // -1 means end of list, -(ihsnd + 3) for free list members + }; + + /*------------------------------------------------------------------------------------------ + This provides an iterator for stepping through all HashNodes stored in the hash map. + This is useful primarily for saving the contents of a hash map to a file. + + Hungarian: ithm[K][T] + ------------------------------------------------------------------------------------------*/ + class iterator + { + public: + // Constructors/destructors/etc. + + iterator() : m_phmParent(NULL), m_ihsnd(0) + { + } + iterator(HashMap<K,T,H,Eq> * phm, int ihsnd) : m_phmParent(phm), m_ihsnd(ihsnd) + { + } + iterator(const iterator & v) : m_phmParent(v.m_phmParent), m_ihsnd(v.m_ihsnd) + { + } + ~iterator() + { + } + + // Other public methods + + iterator & operator = (const iterator & ithm) + { + m_phmParent = ithm.m_phmParent; + m_ihsnd = ithm.m_ihsnd; + return *this; + } + T & operator * (void) + { + Assert(m_phmParent); + Assert(m_phmParent->m_prghsnd); + Assert(m_ihsnd < m_phmParent->m_ihsndLim); + return m_phmParent->m_prghsnd[m_ihsnd].GetValue(); + } + HashNode * operator -> (void) + { + Assert(m_phmParent); + Assert(m_phmParent->m_prghsnd); + Assert(m_ihsnd < m_phmParent->m_ihsndLim); + return &m_phmParent->m_prghsnd[m_ihsnd]; + } + iterator & operator ++ (void) + { + Assert(m_phmParent); + ++m_ihsnd; + // make sure that this new HashNode is actually in use + while (m_ihsnd < m_phmParent->m_ihsndLim) + { + if (m_phmParent->m_prghsnd[m_ihsnd].InUse()) + return *this; + // skip to the next one and check it + ++m_ihsnd; + } + if (m_ihsnd > m_phmParent->m_ihsndLim) + m_ihsnd = m_phmParent->m_ihsndLim; + return *this; + } + bool operator == (const iterator & ithm) + { + return (m_phmParent == ithm.m_phmParent) && (m_ihsnd == ithm.m_ihsnd); + } + bool operator != (const iterator & ithm) + { + return (m_phmParent != ithm.m_phmParent) || (m_ihsnd != ithm.m_ihsnd); + } + T & GetValue(void) + { + Assert(m_phmParent); + Assert(m_phmParent->m_prghsnd); + Assert(m_ihsnd < m_phmParent->m_ihsndLim); + Assert(m_phmParent->m_prghsnd[m_ihsnd].InUse()); + return m_phmParent->m_prghsnd[m_ihsnd].GetValue(); + } + K & GetKey(void) + { + Assert(m_phmParent); + Assert(m_phmParent->m_prghsnd); + Assert(m_ihsnd < m_phmParent->m_ihsndLim); + Assert(m_phmParent->m_prghsnd[m_ihsnd].InUse()); + return m_phmParent->m_prghsnd[m_ihsnd].GetKey(); + } + int GetHash() + { + Assert(m_phmParent); + Assert(m_phmParent->m_prghsnd); + Assert(m_ihsnd < m_phmParent->m_ihsndLim); + Assert(m_phmParent->m_prghsnd[m_ihsnd].InUse()); + return m_phmParent->m_prghsnd[m_ihsnd].GetHash(); + } + int GetIndex() + { + Assert(m_phmParent); + Assert(m_phmParent->m_prghsnd); + Assert(m_ihsnd < m_phmParent->m_ihsndLim); + Assert(m_phmParent->m_prghsnd[m_ihsnd].InUse()); + return m_ihsnd; + } + + protected: + //:> Member variables + + HashMap<K,T,H,Eq> * m_phmParent; + int m_ihsnd; + }; + friend class iterator; + + //:> Constructors/destructors/etc. + + HashMap(); + ~HashMap(); + HashMap(HashMap<K,T,H,Eq> & hm); + + //:> Other public methods + + iterator Begin(); + iterator End(); + void Insert(K & key, T & value, bool fOverwrite = false, int * pihsndOut = NULL); + bool Retrieve(K & key, T * pvalueRet); + bool Delete(K & key); + void Clear(); + void CopyTo(HashMap<K,T,H,Eq> & hmKT); + void CopyTo(HashMap<K,T,H,Eq> * phmKT); + + bool GetIndex(K & key, int * pihsndRet); + bool IndexKey(int ihsnd, K * pkeyRet); + bool IndexValue(int ihsnd, T * pvalueRet); + + int Size(); + + /*------------------------------------------------------------------------------------------ + The assignment operator allows an entire hashmap to be assigned as the value of another + hashmap. It throws an error if it runs out of memory. + + @return a reference to this hashmap. (That is how the assignment operator is defined!) + + @param hm is a reference to the other hashmap. + ------------------------------------------------------------------------------------------*/ + HashMap<K,T,H,Eq> & operator = (HashMap<K,T,H,Eq> & hm) + { + hm.CopyTo(this); + return *this; + } + + //:Ignore +#ifdef DEBUG + int _BucketCount(); + int _EmptyBuckets(); + int _BucketsUsed(); + int _FullestBucket(); + bool AssertValid() + { + AssertPtrN(m_prgihsndBuckets); + Assert(m_prgihsndBuckets || !m_cBuckets); + Assert(!m_prgihsndBuckets || m_cBuckets); + AssertArray(m_prgihsndBuckets, m_cBuckets); + AssertPtrN(m_prghsnd); + Assert(m_prghsnd || !m_ihsndMax); + Assert(!m_prghsnd || m_ihsndMax); + AssertArray(m_prghsnd, m_ihsndMax); + Assert(0 <= m_ihsndLim && m_ihsndLim <= m_ihsndMax); + Assert(-1 <= FreeListIdx(m_ihsndFirstFree)); + Assert(FreeListIdx(m_ihsndFirstFree) < m_ihsndLim); + return true; + } +#endif + //:End Ignore + +protected: + //:> Member variables + + int * m_prgihsndBuckets; + int m_cBuckets; + HashNode * m_prghsnd; + int m_ihsndLim; + int m_ihsndMax; + int m_ihsndFirstFree; // stores -(ihsnd + 3) + + //:> Protected methods + //:Ignore + + /*------------------------------------------------------------------------------------------ + Map between real index and "free list" index. Note that this mapping is bidirectional. + ------------------------------------------------------------------------------------------*/ + int FreeListIdx(int ihsnd) + { + return -(ihsnd + 3); + } + //:End Ignore +}; + + +// Local Variables: +// mode:C++ +// c-file-style:"cellar" +// tab-width:4 +// End: + +#endif /*HASHMAP_H_INCLUDED*/ diff --git a/Build/source/libs/graphite/src/generic/HashMap_i.cpp b/Build/source/libs/graphite/src/generic/HashMap_i.cpp new file mode 100644 index 00000000000..baebe427a4e --- /dev/null +++ b/Build/source/libs/graphite/src/generic/HashMap_i.cpp @@ -0,0 +1,561 @@ +/*--------------------------------------------------------------------*//*:Ignore this sentence. +Copyright (C) 2001 SIL International. All rights reserved. + +Distributable under the terms of either the Common Public License or the +GNU Lesser General Public License, as specified in the LICENSING.txt file. + +File: HashMap_i.cpp +Responsibility: Steve McConnel +Last reviewed: Not yet. + +Description: + This file provides the implementations of methods for the HashMap template collection + classes. It is used as an #include file in any file which explicitly instantiates any + particular type of HashMap<K,T>, HashMapStrUni<T>, or HashMapChars<T>. +----------------------------------------------------------------------------------------------*/ +#pragma once +#ifndef HASHMAP_I_C_INCLUDED +#define HASHMAP_I_C_INCLUDED + +#include "HashMap.h" +////#include <algorithm> +////#include "GrPlatform.h" +#include "GrCommon.h" + +/*********************************************************************************************** + Methods +***********************************************************************************************/ +//:End Ignore + +/*---------------------------------------------------------------------------------------------- + Constructor. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + HashMap<K,T,H,Eq>::HashMap() +{ + m_prgihsndBuckets = NULL; + m_cBuckets = 0; + m_prghsnd = NULL; + m_ihsndLim = 0; + m_ihsndMax = 0; + m_ihsndFirstFree = FreeListIdx(-1); +} + +/*---------------------------------------------------------------------------------------------- + Copy constructor. It throws an error if it runs out of memory. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + HashMap<K,T,H,Eq>::HashMap(HashMap<K,T,H,Eq> & hm) +{ + m_prgihsndBuckets = NULL; + m_cBuckets= 0; + m_prghsnd = NULL; + m_ihsndLim = 0; + m_ihsndMax = 0; + m_ihsndFirstFree = FreeListIdx(-1); + hm.CopyTo(this); +} + +/*---------------------------------------------------------------------------------------------- + Destructor. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + HashMap<K,T,H,Eq>::~HashMap() +{ + Clear(); +} + +/*---------------------------------------------------------------------------------------------- + Return an iterator that references the first key and value stored in the HashMap. + If the hash map is empty, Begin returns the same value as End. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + typename HashMap<K,T,H,Eq>::iterator HashMap<K,T,H,Eq>::Begin() +{ + AssertObj(this); + int ihsnd; + for (ihsnd = 0; ihsnd < m_ihsndLim; ++ihsnd) + { + if (m_prghsnd[ihsnd].InUse()) + { + iterator ithm(this, ihsnd); + return ithm; + } + } + return End(); +} + +/*---------------------------------------------------------------------------------------------- + Return an iterator that marks the end of the set of keys and values stored in the HashMap. + If the HashMap is empty, End returns the same value as Begin. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + typename HashMap<K,T,H,Eq>::iterator HashMap<K,T,H,Eq>::End() +{ + AssertObj(this); + iterator ithm(this, m_ihsndLim); + return ithm; +} + +/*---------------------------------------------------------------------------------------------- + Add one key and value to the HashMap. Insert potentially invalidates existing iterators + for this HashMap. An exception is thrown if there are any errors. + + @param key Reference to the key object. An internal copy is made of this object. + @param value Reference to the object associated with the key. An internal copy is + made of this object. + @param fOverwrite Optional flag (defaults to false) to allow a value already associated + with this key to be replaced by this value. + @param pihsndOut Optional pointer to an integer for returning the internal index where the + key-value pair is stored. + + @exception E_INVALIDARG if fOverwrite is not true and the key already is stored with a value + in this HashMap. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + void HashMap<K,T,H,Eq>::Insert(K & key, T & value, bool fOverwrite, int * pihsndOut) +{ + AssertObj(this); + // Check for initial allocation of memory. + if (!m_cBuckets) + { + int cBuckets = GetPrimeNear(10); + m_prgihsndBuckets = (int *)malloc(cBuckets * isizeof(int)); + if (!m_prgihsndBuckets) + ThrowHr(WarnHr(E_OUTOFMEMORY)); + std::fill_n(m_prgihsndBuckets, cBuckets, -1); + m_cBuckets = cBuckets; + } + if (!m_ihsndMax) + { + int iMax = 32; + m_prghsnd = (HashNode *)malloc(iMax * isizeof(HashNode)); + if (!m_prghsnd) + ThrowHr(WarnHr(E_OUTOFMEMORY)); + std::fill_n(m_prghsnd, iMax, 0); + m_ihsndLim = 0; + m_ihsndMax = iMax; + m_ihsndFirstFree = FreeListIdx(-1); + } + // Check whether this key is already used. + // If it is, store the value if overwriting is allowed, otherwise return an error value. + H hasher; + Eq equal; + int ihsnd; + int nHash = hasher(&key, isizeof(K)); + int ie = (unsigned)nHash % m_cBuckets; + for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext()) + { + if ((nHash == m_prghsnd[ihsnd].GetHash()) && + equal(&key, &m_prghsnd[ihsnd].GetKey(), isizeof(K))) + { + if (fOverwrite) + { + m_prghsnd[ihsnd].PutValue(value); + if (pihsndOut) + *pihsndOut = ihsnd; + AssertObj(this); + return; + } + else + { + ThrowHr(WarnHr(E_INVALIDARG)); + } + } + } + // Check whether to increase the number of buckets to redistribute the wealth. + // Calculate the average depth of hash collection chains. + // If greater than or equal to two, increase the number of buckets. + int chsndFree = 0; + int i; + for (i = m_ihsndFirstFree; i != FreeListIdx(-1); i = m_prghsnd[FreeListIdx(i)].GetNext()) + ++chsndFree; + int chsndAvgDepth = (m_ihsndLim - chsndFree) / m_cBuckets; + if (chsndAvgDepth > 2) + { + int cNewBuckets = GetPrimeNear(4 * m_cBuckets); + if (cNewBuckets && cNewBuckets > m_cBuckets) + { + int * pNewBuckets = (int *)realloc(m_prgihsndBuckets, cNewBuckets * isizeof(int)); + if (pNewBuckets) + { + std::fill_n(pNewBuckets, cNewBuckets, -1); + m_cBuckets = cNewBuckets; + m_prgihsndBuckets = pNewBuckets; + for (ihsnd = 0; ihsnd < m_ihsndLim; ++ihsnd) + { + if (m_prghsnd[ihsnd].InUse()) + { + ie = (unsigned)m_prghsnd[ihsnd].GetHash() % m_cBuckets; + m_prghsnd[ihsnd].PutNext(m_prgihsndBuckets[ie]); + m_prgihsndBuckets[ie] = ihsnd; + } + } + // Recompute the new entry's slot so that it can be stored properly. + ie = (unsigned)nHash % m_cBuckets; + } + } + } + if (m_ihsndLim < m_ihsndMax) + { + ihsnd = m_ihsndLim; + ++m_ihsndLim; + } + else if (m_ihsndFirstFree != FreeListIdx(-1)) + { + ihsnd = FreeListIdx(m_ihsndFirstFree); + m_ihsndFirstFree = m_prghsnd[ihsnd].GetNext(); + } + else + { + int iNewMax = (!m_ihsndMax) ? 32 : 2 * m_ihsndMax; + HashNode * pNewNodes = (HashNode *)realloc(m_prghsnd, iNewMax * isizeof(HashNode)); + if (!pNewNodes && iNewMax > 32) + { + iNewMax = m_ihsndMax + (m_ihsndMax / 2); + pNewNodes = (HashNode *)realloc(m_prghsnd, iNewMax * isizeof(HashNode)); + if (!pNewNodes) + ThrowHr(WarnHr(E_OUTOFMEMORY)); + } + m_prghsnd = pNewNodes; + m_ihsndMax = iNewMax; + Assert(m_ihsndLim < m_ihsndMax); + ihsnd = m_ihsndLim; + ++m_ihsndLim; + } + // Call constructor on previously allocated memory. + new((void *)&m_prghsnd[ihsnd]) HashNode(key, value, nHash, m_prgihsndBuckets[ie]); + m_prgihsndBuckets[ie] = ihsnd; + if (pihsndOut) + *pihsndOut = ihsnd; + AssertObj(this); +} + +/*---------------------------------------------------------------------------------------------- + Search the HashMap for the given key, and return true if the key is found or false if the + key is not found. If the key is found and the given pointer is not NULL, copy the + associated value to that memory location. + + @param key Reference to a key object. + @param pvalueRet Pointer to an empty object for storing a copy of the value associated with + the key, if one exists. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + bool HashMap<K,T,H,Eq>::Retrieve(K & key, T * pvalueRet) +{ + AssertObj(this); + if (!m_prgihsndBuckets) + return false; + H hasher; + Eq equal; + int nHash = hasher(&key, isizeof(K)); + int ie = (unsigned)nHash % m_cBuckets; + int ihsnd; + for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext()) + { + if ((nHash == m_prghsnd[ihsnd].GetHash()) && + equal(&key, &m_prghsnd[ihsnd].GetKey(), isizeof(K))) + { + if (pvalueRet) + *pvalueRet = m_prghsnd[ihsnd].GetValue(); + return true; + } + } + return false; +} + +/*---------------------------------------------------------------------------------------------- + Remove the element with the given key from the stored HashMap. This potentially + invalidates existing iterators for this HashMap. If the key is not found in the + HashMap, then nothing is deleted. + + @param key Reference to a key object. + + @return True if the key is found, and something is actually deleted; otherwise, false. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + bool HashMap<K,T,H,Eq>::Delete(K & key) +{ + AssertObj(this); + if (!m_prgihsndBuckets) + return false; + H hasher; + Eq equal; + int nHash = hasher(&key, isizeof(K)); + int ie = (unsigned)nHash % m_cBuckets; + int ihsnd; + int ihsndPrev = -1; + for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext()) + { + if ((nHash == m_prghsnd[ihsnd].GetHash()) && + equal(&key, &m_prghsnd[ihsnd].GetKey(), isizeof(K))) + { + if (ihsndPrev == -1) + m_prgihsndBuckets[ie] = m_prghsnd[ihsnd].GetNext(); + else + m_prghsnd[ihsndPrev].PutNext(m_prghsnd[ihsnd].GetNext()); + m_prghsnd[ihsnd].~HashNode(); // Ensure member destructors are called. + memset(&m_prghsnd[ihsnd], 0, isizeof(HashNode)); + m_prghsnd[ihsnd].PutNext(m_ihsndFirstFree); + m_ihsndFirstFree = FreeListIdx(ihsnd); + AssertObj(this); + return true; + } + ihsndPrev = ihsnd; + } + return false; +} + +/*---------------------------------------------------------------------------------------------- + Free all the memory used by the HashMap. When done, only the minimum amount of + bookkeeping memory is still taking up space, and any internal pointers all been set + to NULL. The appropriate destructor is called for all key and value objects stored + in the HashMap before the memory space is freed. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + void HashMap<K,T,H,Eq>::Clear() +{ + AssertObj(this); + if (!m_prgihsndBuckets) + return; + int ihsnd; + for (ihsnd = 0; ihsnd < m_ihsndLim; ++ihsnd) + { + if (m_prghsnd[ihsnd].InUse()) + m_prghsnd[ihsnd].~HashNode(); // Ensure member destructors are called. + } + free(m_prgihsndBuckets); + free(m_prghsnd); + m_prgihsndBuckets = NULL; + m_cBuckets = 0; + m_prghsnd = NULL; + m_ihsndLim = 0; + m_ihsndMax = 0; + m_ihsndFirstFree = FreeListIdx(-1); + AssertObj(this); +} + +/*---------------------------------------------------------------------------------------------- + Copy the content of one HashMap to another. An exception is thrown if there are any errors. + + @param hmKT Reference to the other HashMap. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + void HashMap<K,T,H,Eq>::CopyTo(HashMap<K,T,H,Eq> & hmKT) +{ + AssertObj(this); + AssertObj(&hmKT); + hmKT.Clear(); + iterator itmm; + for (itmm = Begin(); itmm != End(); ++itmm) + hmKT.Insert(itmm->GetKey(), itmm->GetValue()); +} + +/*---------------------------------------------------------------------------------------------- + Copy the content of one HashMap to another. An exception is thrown if there are any errors. + + @param phmKT Pointer to the other HashMap. + + @exception E_POINTER if phmKT is NULL. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + void HashMap<K,T,H,Eq>::CopyTo(HashMap<K,T,H,Eq> * phmKT) +{ + if (!phmKT) + ThrowHr(WarnHr(E_POINTER)); + CopyTo(*phmKT); +} + +/*---------------------------------------------------------------------------------------------- + If the given key is found in the HashMap, return true, and if the provided index pointer + is not NULL, also store the internal index value in the indicated memory location. + If the given key is NOT found in the HashMap, return false and ignore the provided index + pointer. + + @param key Reference to a key object. + @param pihsndRet Pointer to an integer for returning the internal index where the + key-value pair is stored. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + bool HashMap<K,T,H,Eq>::GetIndex(K & key, int * pihsndRet) +{ + AssertObj(this); + if (!m_prgihsndBuckets) + return false; + H hasher; + Eq equal; + int nHash = hasher(&key, isizeof(K)); + int ie = (unsigned)nHash % m_cBuckets; + int ihsnd; + for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext()) + { + if ((nHash == m_prghsnd[ihsnd].GetHash()) && + equal(&key, &m_prghsnd[ihsnd].GetKey(), isizeof(K))) + { + if (pihsndRet) + *pihsndRet = ihsnd; + return true; + } + } + return false; +} + +/*---------------------------------------------------------------------------------------------- + If the given internal HashMap index is valid, return true, and if the provided pointer to a + key object is not NULL, also copy the indexed key to the indicated memory location. + If the given internal index is NOT valid, return false, and ignore the provided key + object pointer. + + @param ihsnd Internal index value returned earlier by GetIndex or Insert. + @param pkeyRet Pointer to an empty key object for storing a copy of the key found at the + indexed location. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + bool HashMap<K,T,H,Eq>::IndexKey(int ihsnd, K * pkeyRet) +{ + AssertObj(this); + if ((ihsnd < 0) || (ihsnd >= m_ihsndLim)) + return false; + if (m_prghsnd[ihsnd].InUse()) + { + if (pkeyRet) + *pkeyRet = m_prghsnd[ihsnd].GetKey(); + return true; + } + else + { + return false; + } +} + +/*---------------------------------------------------------------------------------------------- + If the given internal HashMap index is valid, return true, and if the provided pointer to an + object is not NULL, also copy the indexed value to the indicated memory location. + If the given internal index is NOT valid, return false, and ignore the provided + object pointer. + + @param ihsnd Internal index value returned earlier by GetIndex or Insert. + @param pvalueRet Pointer to an empty object for storing a copy of the value found at the + indexed location. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + bool HashMap<K,T,H,Eq>::IndexValue(int ihsnd, T * pvalueRet) +{ + AssertObj(this); + if (ihsnd < 0 || ihsnd >= m_ihsndLim) + return false; + if (m_prghsnd[ihsnd].InUse()) + { + if (pvalueRet) + *pvalueRet = m_prghsnd[ihsnd].GetValue(); + return true; + } + else + { + return false; + } +} + +/*---------------------------------------------------------------------------------------------- + Return the number of items (key-value pairs) stored in the HashMap. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + int HashMap<K,T,H,Eq>::Size() +{ + AssertObj(this); + if (!m_prgihsndBuckets) + return 0; + int chsndFree = 0; + int ihsnd; + for (ihsnd = m_ihsndFirstFree; + ihsnd != FreeListIdx(-1); + ihsnd = m_prghsnd[FreeListIdx(ihsnd)].GetNext()) + { + ++chsndFree; + } + return m_ihsndLim - chsndFree; +} + +//:Ignore +#ifdef DEBUG +/*---------------------------------------------------------------------------------------------- + Return the number of buckets (hash slots) currently allocated for the hash map. This is + useful only for debugging the hash map mechanism itself. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + int HashMap<K,T,H,Eq>::_BucketCount() +{ + AssertObj(this); + return m_cBuckets; +} + +/*---------------------------------------------------------------------------------------------- + Return the number of buckets (hash slots) that do not point to a list of HashNode objects. + This is useful only for debugging the hash map mechanism itself. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + int HashMap<K,T,H,Eq>::_EmptyBuckets() +{ + AssertObj(this); + int ceUnused = 0; + int ie; + for (ie = 0; ie < m_cBuckets; ++ie) + { + if (m_prgihsndBuckets[ie] == -1) + ++ceUnused; + } + return ceUnused; +} + +/*---------------------------------------------------------------------------------------------- + Return the number of buckets (hash slots) that currently point to a list of HashNode + objects in the hash map. This is useful only for debugging the hash map mechanism itself. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + int HashMap<K,T,H,Eq>::_BucketsUsed() +{ + AssertObj(this); + int ceUsed = 0; + int ie; + for (ie = 0; ie < m_cBuckets; ++ie) + { + if (m_prgihsndBuckets[ie] != -1) + ++ceUsed; + } + return ceUsed; +} + +/*---------------------------------------------------------------------------------------------- + Return the length of the longest list of HashNode objects stored in any bucket (hash slot) + of the hash map. This is useful only for debugging the hash map mechanism itself. +----------------------------------------------------------------------------------------------*/ +template<class K, class T, class H, class Eq> + int HashMap<K,T,H,Eq>::_FullestBucket() +{ + AssertObj(this); + int chsndMax = 0; + int chsnd; + int ie; + int ihsnd; + for (ie = 0; ie < m_cBuckets; ++ie) + { + chsnd = 0; + for (ihsnd = m_prgihsndBuckets[ie]; ihsnd != -1; ihsnd = m_prghsnd[ihsnd].GetNext()) + ++chsnd; + if (chsndMax < chsnd) + chsndMax = chsnd; + } + return chsndMax; +} +#endif +//:End Ignore + + + +// Local Variables: +// mode:C++ +// c-file-style:"cellar" +// tab-width:4 +// End: + +#endif /*HASHMAP_I_C_INCLUDED*/ diff --git a/Build/source/libs/graphite/src/generic/Makefile.am b/Build/source/libs/graphite/src/generic/Makefile.am new file mode 100644 index 00000000000..ec60b09be3a --- /dev/null +++ b/Build/source/libs/graphite/src/generic/Makefile.am @@ -0,0 +1,8 @@ +genericdir = $(top_srcdir)/src/generic + +libgraphite_la_SOURCES += $(genericdir)/Debug.cpp +libgraphite_la_SOURCES += $(genericdir)/Util.cpp + +EXTRA_DIST += $(genericdir)/*.h +EXTRA_DIST += $(genericdir)/BinTree_i.cpp +EXTRA_DIST += $(genericdir)/HashMap_i.cpp diff --git a/Build/source/libs/graphite/src/generic/Util.cpp b/Build/source/libs/graphite/src/generic/Util.cpp new file mode 100644 index 00000000000..aabd6563d3e --- /dev/null +++ b/Build/source/libs/graphite/src/generic/Util.cpp @@ -0,0 +1,261 @@ + +#include "GrCommon.h" +#include "GrDebug.h" + + +namespace gr +{ + +/*---------------------------------------------------------------------------------------------- + Swap two blocks of size cb starting at pv1 and pv2. Doesn't handle overlapping blocks. +----------------------------------------------------------------------------------------------*/ +void SwapBytes(void * pv1, void * pv2, int cb) +{ + Assert((byte *)pv1 + cb <= (byte *)pv2 || (byte *)pv2 + cb <= (byte *)pv1); + AssertPtrSize(pv1, cb); + AssertPtrSize(pv2, cb); + +#ifdef NO_ASM + + byte *pb1 = (byte *)pv1; + byte *pb2 = (byte *)pv2; + byte b; + + while (--cb >= 0) + { + b = *pb1; + *pb1++ = *pb2; + *pb2++ = b; + } + +#else // !NO_ASM + + __asm + { + // edi -> memory to swap, first pointer + // esi -> memory to swap, second pointer + + mov edi,pv1 + mov esi,pv2 + + mov ecx,cb + shr ecx,2 + jz LBytes + +LIntLoop: + mov eax,[edi] + mov ebx,[esi] + mov [edi],ebx + mov [esi],eax + + add edi,4 + add esi,4 + dec ecx + jnz LIntLoop; + +LBytes: + mov ecx,cb + and ecx,3 + jz LDone + +LByteLoop: + mov al,[edi] + mov bl,[esi] + mov [edi],bl + mov [esi],al + inc edi + inc esi + dec ecx + jnz LByteLoop + +LDone: + } + +#endif //!NO_ASM +} + +/*---------------------------------------------------------------------------------------------- + Fills a block of memory with the given short value. +----------------------------------------------------------------------------------------------*/ +void FillShorts(void * pv, short sn, int csn) +{ + AssertPtrSize(pv, csn * isizeof(short)); + +#ifdef NO_ASM + + short * psn = (short *)pv; + short * psnLim = psn + csn; + + while (psn < psnLim) + *psn++ = sn; + +#else // !NO_ASM + + __asm + { + // Setup the registers for using REP STOS instruction to set memory. + // NOTE: Alignment does not effect the speed of STOS. + // + // edi -> memory to set + // eax = value to store in destination + // direction flag is clear for auto-increment + + mov edi,pv + mov ax,sn + mov ecx,csn + + mov edx,ecx + and edx,1 + jz LInts + + // set 1 short + stosw + +LInts: + shr ecx,1 + jz LDone + + mov ebx,eax + shl eax,16 + mov ax,bx + + rep stosd +LDone: + } + +#endif //!NO_ASM +} + +/*********************************************************************************************** + Integer utilities. +***********************************************************************************************/ + +/* + * table of powers of 2, and largest prime smaller than each power of 2 + * n 2**n prime diff + * --- ---------- ---------- ---- + * 2: 4 3 ( -1) + * 3: 8 7 ( -1) + * 4: 16 13 ( -3) + * 5: 32 31 ( -1) + * 6: 64 61 ( -3) + * 7: 128 127 ( -1) + * 8: 256 251 ( -5) + * 9: 512 509 ( -3) + * 10: 1024 1021 ( -3) + * 11: 2048 2039 ( -9) + * 12: 4096 4093 ( -3) + * 13: 8192 8191 ( -1) + * 14: 16384 16381 ( -3) + * 15: 32768 32749 (-19) + * 16: 65536 65521 (-15) + * 17: 131072 131071 ( -1) + * 18: 262144 262139 ( -5) + * 19: 524288 524287 ( -1) + * 20: 1048576 1048573 ( -3) + * 21: 2097152 2097143 ( -9) + * 22: 4194304 4194301 ( -3) + * 23: 8388608 8388593 (-15) + * 24: 16777216 16777213 ( -3) + * 25: 33554432 33554393 (-39) + * 26: 67108864 67108859 ( -5) + * 27: 134217728 134217689 (-39) + * 28: 268435456 268435399 (-57) + * 29: 536870912 536870909 ( -3) + * 30: 1073741824 1073741789 (-35) + * 31: 2147483648 2147483647 ( -1) + * 32: 4294967296 4294967291 ( -5) + */ +const static unsigned int g_rguPrimes[] = { + 3, 7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071, + 262139, 524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393, 67108859, + 134217689, 268435399, 536870909, 1073741789, 2147483647, 4294967291U +}; + + +/*---------------------------------------------------------------------------------------------- + Returns the prime in g_rguPrimes that is closest to u. +----------------------------------------------------------------------------------------------*/ +unsigned int GetPrimeNear(unsigned int u) +{ + int cu = isizeof(g_rguPrimes) / isizeof(unsigned int); + int iuMin; + int iuLim; + int iu; + + for (iuMin = 0, iuLim = cu; iuMin < iuLim; ) + { + iu = (iuMin + iuLim) / 2; + if (u > g_rguPrimes[iu]) + iuMin = iu + 1; + else + iuLim = iu; + } + Assert(iuMin == cu || iuMin < cu && u <= g_rguPrimes[iuMin]); + Assert(iuMin == 0 || iuMin > 0 && u > g_rguPrimes[iuMin - 1]); + + if (!iuMin) + return g_rguPrimes[0]; + if (iuMin == cu) + return g_rguPrimes[cu - 1]; + if (g_rguPrimes[iuMin] - u < u - g_rguPrimes[iuMin - 1]) + return g_rguPrimes[iuMin]; + return g_rguPrimes[iuMin - 1]; +} + + +/*---------------------------------------------------------------------------------------------- + Returns the prime in g_rguPrimes that is larger than u or is the largest in the list. +----------------------------------------------------------------------------------------------*/ +unsigned int GetLargerPrime(unsigned int u) +{ + int cu = isizeof(g_rguPrimes) / isizeof(unsigned int); + int iuMin; + int iuLim; + int iu; + + for (iuMin = 0, iuLim = cu; iuMin < iuLim; ) + { + iu = (iuMin + iuLim) / 2; + if (u >= g_rguPrimes[iu]) + iuMin = iu + 1; + else + iuLim = iu; + } + Assert(iuMin == cu || iuMin < cu && u < g_rguPrimes[iuMin]); + Assert(iuMin == 0 || iuMin > 0 && u >= g_rguPrimes[iuMin - 1]); + + if (iuMin == cu) + return g_rguPrimes[cu - 1]; + return g_rguPrimes[iuMin]; +} + + +/*---------------------------------------------------------------------------------------------- + Returns the prime in g_rguPrimes that is smaller than u or is the smallest in the list. +----------------------------------------------------------------------------------------------*/ +unsigned int GetSmallerPrime(unsigned int u) +{ + int cu = isizeof(g_rguPrimes) / isizeof(unsigned int); + int iuMin; + int iuLim; + int iu; + + for (iuMin = 0, iuLim = cu; iuMin < iuLim; ) + { + iu = (iuMin + iuLim) / 2; + if (u > g_rguPrimes[iu]) + iuMin = iu + 1; + else + iuLim = iu; + } + Assert(iuMin == cu || iuMin < cu && u <= g_rguPrimes[iuMin]); + Assert(iuMin == 0 || iuMin > 0 && u > g_rguPrimes[iuMin - 1]); + + if (!iuMin) + return g_rguPrimes[0]; + return g_rguPrimes[iuMin - 1]; +} + +} + |