summaryrefslogtreecommitdiff
path: root/Build/source/libs/graphite/engine-2.3.1/src/generic
diff options
context:
space:
mode:
authorPeter Breitenlohner <peb@mppmu.mpg.de>2009-11-10 10:18:38 +0000
committerPeter Breitenlohner <peb@mppmu.mpg.de>2009-11-10 10:18:38 +0000
commit9ab1d67ae5be915e0a7e146123ea577b8b7d85cf (patch)
tree02180daeded681369095ccb9e1f592502d032c90 /Build/source/libs/graphite/engine-2.3.1/src/generic
parentc9e6fa742a274dd314b6e483c65a810f7ed44d1e (diff)
towards TL2010: libs graphite
git-svn-id: svn://tug.org/texlive/trunk@15953 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/libs/graphite/engine-2.3.1/src/generic')
-rw-r--r--Build/source/libs/graphite/engine-2.3.1/src/generic/BinTree.h71
-rw-r--r--Build/source/libs/graphite/engine-2.3.1/src/generic/BinTree_i.cpp225
-rw-r--r--Build/source/libs/graphite/engine-2.3.1/src/generic/Debug.cpp83
-rw-r--r--Build/source/libs/graphite/engine-2.3.1/src/generic/GenericResource.h86
-rw-r--r--Build/source/libs/graphite/engine-2.3.1/src/generic/HashMap.h328
-rw-r--r--Build/source/libs/graphite/engine-2.3.1/src/generic/HashMap_i.cpp561
-rw-r--r--Build/source/libs/graphite/engine-2.3.1/src/generic/Makefile.am8
-rw-r--r--Build/source/libs/graphite/engine-2.3.1/src/generic/Util.cpp261
8 files changed, 1623 insertions, 0 deletions
diff --git a/Build/source/libs/graphite/engine-2.3.1/src/generic/BinTree.h b/Build/source/libs/graphite/engine-2.3.1/src/generic/BinTree.h
new file mode 100644
index 00000000000..a487df03770
--- /dev/null
+++ b/Build/source/libs/graphite/engine-2.3.1/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/engine-2.3.1/src/generic/BinTree_i.cpp b/Build/source/libs/graphite/engine-2.3.1/src/generic/BinTree_i.cpp
new file mode 100644
index 00000000000..5929bf0bab1
--- /dev/null
+++ b/Build/source/libs/graphite/engine-2.3.1/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/engine-2.3.1/src/generic/Debug.cpp b/Build/source/libs/graphite/engine-2.3.1/src/generic/Debug.cpp
new file mode 100644
index 00000000000..d1f2a67e364
--- /dev/null
+++ b/Build/source/libs/graphite/engine-2.3.1/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/engine-2.3.1/src/generic/GenericResource.h b/Build/source/libs/graphite/engine-2.3.1/src/generic/GenericResource.h
new file mode 100644
index 00000000000..119c6317bcd
--- /dev/null
+++ b/Build/source/libs/graphite/engine-2.3.1/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/engine-2.3.1/src/generic/HashMap.h b/Build/source/libs/graphite/engine-2.3.1/src/generic/HashMap.h
new file mode 100644
index 00000000000..dc2de9d0af7
--- /dev/null
+++ b/Build/source/libs/graphite/engine-2.3.1/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/engine-2.3.1/src/generic/HashMap_i.cpp b/Build/source/libs/graphite/engine-2.3.1/src/generic/HashMap_i.cpp
new file mode 100644
index 00000000000..baebe427a4e
--- /dev/null
+++ b/Build/source/libs/graphite/engine-2.3.1/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/engine-2.3.1/src/generic/Makefile.am b/Build/source/libs/graphite/engine-2.3.1/src/generic/Makefile.am
new file mode 100644
index 00000000000..ec60b09be3a
--- /dev/null
+++ b/Build/source/libs/graphite/engine-2.3.1/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/engine-2.3.1/src/generic/Util.cpp b/Build/source/libs/graphite/engine-2.3.1/src/generic/Util.cpp
new file mode 100644
index 00000000000..aabd6563d3e
--- /dev/null
+++ b/Build/source/libs/graphite/engine-2.3.1/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];
+}
+
+}
+