gwnavruntime/kernel/SF_StringHash.h Source File

SF_StringHash.h
Go to the documentation of this file.
1 /*
2 * Copyright 2015 Autodesk, Inc. All rights reserved.
3 * Use of this software is subject to the terms of the Autodesk license agreement and any attachments or Appendices thereto provided at the time of installation or download,
4 * or which otherwise accompanies this software in either electronic or hard copy form, or which is signed by you and accepted by Autodesk.
5 */
6 
7 /**************************************************************************
8 
9 PublicHeader: None
10 Filename : KY_StringHash.h
11 Content : String hash table used when optional case-insensitive
12  lookup is required.
13 Created :
14 Authors :
15 
16 **************************************************************************/
17 
18 #ifndef INC_KY_Kernel_StringHash_H
19 #define INC_KY_Kernel_StringHash_H
20 
23 
24 namespace Kaim {
25 
26 // *** StringHash
27 
28 // This is a custom string hash table that supports case-insensitive
29 // searches through special functions such as GetCaseInsensitive, etc.
30 // This class is used for Flash labels, exports and other case-insensitive tables.
31 
32 template<class U, class Allocator = AllocatorGH<U> >
33 class StringHash : public Hash<String, U, String::NoCaseHashFunctor, Allocator>
34 {
35 public:
36  typedef U ValueType;
37  typedef StringHash<U, Allocator> SelfType;
38  typedef Hash<String, U, String::NoCaseHashFunctor, Allocator> BaseType;
39 
40 public:
41 
42  void operator = (const SelfType& src) { BaseType::operator = (src); }
43 
44  bool GetCaseInsensitive(const String& key, U* pvalue) const
45  {
46  String::NoCaseKey ikey(key);
47  return BaseType::GetAlt(ikey, pvalue);
48  }
49  // Pointer-returning get variety.
50  const U* GetCaseInsensitive(const String& key) const
51  {
52  String::NoCaseKey ikey(key);
53  return BaseType::GetAlt(ikey);
54  }
55  U* GetCaseInsensitive(const String& key)
56  {
57  String::NoCaseKey ikey(key);
58  return BaseType::GetAlt(ikey);
59  }
60 
61 
62  typedef typename BaseType::Iterator base_iterator;
63 
64  base_iterator FindCaseInsensitive(const String& key)
65  {
66  String::NoCaseKey ikey(key);
67  return BaseType::FindAlt(ikey);
68  }
69 
70  // Set just uses a find and assigns value if found. The key is not modified;
71  // this behavior is identical to Flash string variable assignment.
72  void SetCaseInsensitive(const String& key, const U& value)
73  {
74  base_iterator it = FindCaseInsensitive(key);
75  if (it != BaseType::End())
76  {
77  it->Second = value;
78  }
79  else
80  {
81  BaseType::Add(key, value);
82  }
83  }
84 };
85 
86 
87 // Global version that assigns the id.
88 template<class U, int SID = Stat_Default_Mem>
89 class StringHash_sid : public StringHash<U, AllocatorGH<U, SID> >
90 {
91  typedef StringHash_sid<U, SID> SelfType;
92  typedef StringHash<U, AllocatorGH<U, SID> > BaseType;
93 public:
94 
95  void operator = (const SelfType& src) { BaseType::operator = (src); }
96 };
97 
98 
99 
100 
101 // ***** StringHashLH: Structure heap local String Hash table
102 
103 // This hash table must live locally within a heap-allocated structure
104 // and is also allocates its string from the local heap by using StringLcl.
105 //
106 // This hash table needs to have custom implementation, since all strings
107 // are passed by String reference, so the locally stored value is not the same.
108 
109 
110 template<class U, class HashF>
111 struct StringLH_HashNode
112 {
113  StringLH First;
114  U Second;
115 
116  // NodeRef is used to allow passing of elements into ghash_set
117  // without using a temporary object.
118  struct NodeRef
119  {
120  const String* pFirst;
121  const U* pSecond;
122 
123  NodeRef(const String& f, const U& s) : pFirst(&f), pSecond(&s) { }
124  NodeRef(const NodeRef& src) : pFirst(src.pFirst), pSecond(src.pSecond) { }
125 
126  // Enable computation of ghash_node_hashf.
127  inline UPInt GetHash() const { return HashF()(*pFirst); }
128  // Necessary conversion to allow ghash_node::operator == to work.
129  operator const String& () const { return *pFirst; }
130  };
131 
132  // Note: No default constructor is necessary.
133  StringLH_HashNode(const StringLH_HashNode& src) : First(src.First), Second(src.Second) { }
134  StringLH_HashNode(const NodeRef& src) : First(*src.pFirst), Second(*src.pSecond) { }
135  void operator = (const NodeRef& src) { First = *src.pFirst; Second = *src.pSecond; }
136 
137 #ifdef KY_CC_RENESAS
138  bool operator == (const NodeRef& src) const { return (First == *src.pFirst); }
139 #endif
140 
141  template<class K>
142  bool operator == (const K& src) const { return (First == src); }
143 
144  template<class K>
145  static UPInt KY_STDCALL CalcHash(const K& data) { return HashF()(data); }
146  inline UPInt GetHash() const { return HashF()(First); }
147 
148  // Hash functors used with this node. A separate functor is used for alternative
149  // key lookup so that it does not need to access the '.First' element.
150  struct NodeHashF
151  {
152  template<class K>
153  UPInt operator()(const K& data) const { return data.GetHash(); }
154  };
155  struct NodeAltHashF
156  {
157  template<class K>
158  UPInt operator()(const K& data) const { return StringLH_HashNode<U,HashF>::CalcHash(data); }
159  };
160 };
161 
162 
163 #undef new
164 
165 template<class U, int SID = Stat_Default_Mem,
166  class HashF = String::NoCaseHashFunctor,
167  class HashNode = StringLH_HashNode<U,HashF>,
168  class Entry = HashsetCachedNodeEntry<HashNode, typename HashNode::NodeHashF> >
169 class StringHashLH
170 {
171 public:
172  KY_MEMORY_REDEFINE_NEW(StringHashLH, SID)
173 
174  typedef AllocatorLH<U, SID> Allocator;
175 
176  // Types used for hash_set.
177  typedef U ValueType;
178  typedef StringHashLH<U, SID, HashF, HashNode, Entry> SelfType;
179  typedef typename HashNode::NodeHashF HashNodeF;
180  typedef HashSet<HashNode, HashNodeF,
181  typename HashNode::NodeAltHashF,
182  Allocator, Entry > Container;
183 
184  // Actual hash table itself, implemented as hash_set.
185  Container mHash;
186 
187 public:
188 
189  StringHashLH() { }
190  StringHashLH(int sizeHint) : mHash(sizeHint) { }
191  StringHashLH(const SelfType& src) : mHash(src.mHash) { }
192  ~StringHashLH() { }
193 
194  void operator = (const SelfType& src) { mHash = src.mHash; }
195 
196  // Remove all entries from the Hash table.
197  inline void Clear() { mHash.Clear(); }
198  // Returns true if the mHash is empty.
199  inline bool IsEmpty() const { return mHash.IsEmpty(); }
200 
201  // Access (set).
202  inline void Set(const String& key, const U& value)
203  {
204  typename HashNode::NodeRef e(key, value);
205  mHash.Set(e);
206  }
207  inline void Add(const String& key, const U& value)
208  {
209  typename HashNode::NodeRef e(key, value);
210  mHash.Add(e);
211  }
212 
213  // Removes an element by clearing its Entry.
214  inline void Remove(const String& key)
215  {
216  mHash.RemoveAlt(key);
217  }
218  template<class K>
219  inline void RemoveAlt(const K& key)
220  {
221  mHash.RemoveAlt(key);
222  }
223 
224  // Retrieve the value under the given key.
225  // - If there's no value under the key, then return false and leave *pvalue alone.
226  // - If there is a value, return true, and set *Pvalue to the Entry's value.
227  // - If value == NULL, return true or false according to the presence of the key.
228  bool Get(const String& key, U* pvalue) const
229  {
230  const HashNode* p = mHash.GetAlt(key);
231  if (p)
232  {
233  if (pvalue)
234  *pvalue = p->Second;
235  return true;
236  }
237  return false;
238  }
239 
240  template<class K>
241  bool GetAlt(const K& key, U* pvalue) const
242  {
243  const HashNode* p = mHash.GetAlt(key);
244  if (p)
245  {
246  if (pvalue)
247  *pvalue = p->Second;
248  return true;
249  }
250  return false;
251  }
252 
253  // Retrieve the pointer to a value under the given key.
254  // - If there's no value under the key, then return NULL.
255  // - If there is a value, return the pointer.
256  inline U* Get(const String& key)
257  {
258  HashNode* p = mHash.GetAlt(key);
259  return p ? &p->Second : 0;
260  }
261  inline const U* Get(const String& key) const
262  {
263  const HashNode* p = mHash.GetAlt(key);
264  return p ? &p->Second : 0;
265  }
266 
267  template<class K>
268  inline U* GetAlt(const K& key)
269  {
270  HashNode* p = mHash.GetAlt(key);
271  return p ? &p->Second : 0;
272  }
273  template<class K>
274  inline const U* GetAlt(const K& key) const
275  {
276  const HashNode* p = mHash.GetAlt(key);
277  return p ? &p->Second : 0;
278  }
279 
280  // Sizing methods - delegate to Hash.
281  inline UPInt GetSize() const { return mHash.GetSize(); }
282  inline void Resize(UPInt n) { mHash.Resize(n); }
283  inline void SetSapacity(UPInt newSize) { mHash.RemoveAlt(newSize); }
284 
285  // Iterator API, like STL.
286  typedef typename Container::ConstIterator ConstIterator;
287  typedef typename Container::Iterator Iterator;
288 
289  inline Iterator Begin() { return mHash.Begin(); }
290  inline Iterator End() { return mHash.End(); }
291  inline ConstIterator Begin() const { return mHash.Begin(); }
292  inline ConstIterator End() const { return mHash.End(); }
293 
294  Iterator Find(const String& key) { return mHash.FindAlt(key); }
295  ConstIterator Find(const String& key) const { return mHash.FindAlt(key); }
296 
297  template<class K>
298  Iterator FindAlt(const K& key) { return mHash.FindAlt(key); }
299  template<class K>
300  ConstIterator FindAlt(const K& key) const { return mHash.FindAlt(key); }
301 
302 
303  // **** Case-Insensitive Lookup
304 
305  bool GetCaseInsensitive(const String& key, U* pvalue) const
306  {
307  String::NoCaseKey ikey(key);
308  return GetAlt(ikey, pvalue);
309  }
310  // Pointer-returning get variety.
311  const U* GetCaseInsensitive(const String& key) const
312  {
313  String::NoCaseKey ikey(key);
314  return GetAlt(ikey);
315  }
316  U* GetCaseInsensitive(const String& key)
317  {
318  String::NoCaseKey ikey(key);
319  return GetAlt(ikey);
320  }
321 
322 
323  // typedef typename BaseType::Iterator base_iterator;
324 
325  Iterator FindCaseInsensitive(const String& key)
326  {
327  String::NoCaseKey ikey(key);
328  return FindAlt(ikey);
329  }
330 
331  // Set just uses a find and assigns value if found. The key is not modified;
332  // this behavior is identical to Flash string variable assignment.
333  void SetCaseInsensitive(const String& key, const U& value)
334  {
335  Iterator it = FindCaseInsensitive(key);
336  if (it != End())
337  {
338  it->Second = value;
339  }
340  else
341  {
342  Add(key, value);
343  }
344  }
345 
346 };
347 
348 } // Scaleform
349 
350 // Redefine operator 'new' if necessary.
351 #if defined(KY_DEFINE_NEW)
352 #define new KY_DEFINE_NEW
353 #endif
354 
355 #endif
Definition: gamekitcrowddispersion.h:20