HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_IndexedHashMapT.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_IndexedHashMap.h ( UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #ifndef __UT_IndexedHashMapT__
12 #define __UT_IndexedHashMapT__
13 
14 #include "UT_String.h"
15 #include "UT_IndexedHashMap.h"
16 
17 /// Convenience class to use strings as keys in the hash map
19 {
20 public:
21  /// This allows a key to be built automatically from a const char *.
22  UT_IndexedHashMapStringKey(const char *key)
23  {
24  // We can use a shallow reference for the key since this is only
25  // constructed when adding/finding items in the map.
26  myString = key;
27  }
29  {
30  // The copy c-tor is called when storing the key in the map. Thus, we
31  // need to harden the string.
32  myString.harden(src.myString);
33  }
34  const char *getString() const { return myString; }
35 
36  uint hash() const { return myString.hash(); }
38  { return strcmp(myString, src.myString) == 0; }
40  { return strcmp(myString, src.myString) < 0; }
42  { return strcmp(myString, src.myString) < 0; }
43 
44 private:
45  UT_String myString;
46 };
47 
48 /// Convenience class for items which just reference their keys. That is, if
49 /// all the information is available on the key, the item class can be a simple
50 /// key container.
51 ///
52 /// The class has a method that allows for deferred creation given the key
53 /// reference.
54 ///
55 /// @note You will likely want to use ut_IndexedHashMapDeferItemAlloc<KEY,ITEM>
56 /// with this class (since the point of this item class is to allow deferred
57 /// allocation).
58 template <typename KEY>
60 {
61 public:
63  : myKey(&k)
64  {
65  }
67  : myKey(i.myKey)
68  {
69  }
71 
74  {
75  myKey = src.myKey;
76  return *this;
77  }
78 
79  const KEY &getKey() const { return *myKey; }
81  { return *myKey < *i.myKey; }
82 private:
83  const KEY *myKey;
84 };
85 
86 /// A typedef for a string item container. This is an item container which
87 /// holds a UT_IndexedHashMapStringKey
90 
91 /// An allocator object which dis-allows deferred allocation of items
93 {
94 public:
95  /// Return NULL (don't allow deferred construction).
98  {
99  UT_ASSERT(0 && "User must define an allocator for deferred allocation");
100  return NULL;
101  }
102 };
103 
104 /// For ITEM objects which support a deferred constructor (for example, the key
105 /// container item), this can be used as a simple deferred allocator.
106 template <typename KEY, typename ITEM>
108 {
109 public:
110  //// Construct an item when it doesn't already exist in the map
113  {
114  return new ITEM(*(static_cast<const KEY *>(key)));
115  }
116 };
117 
118 /// A typedef for an allocator for the string key/item allocation.
120 
121 /// @brief A thread-safe hash map which stores indexed shared items
122 ///
123 /// Each item in the hash map is reference counted. That is, if objects are
124 /// added multiple times, only a single object will be stored in the map.
125 ///
126 /// Removing an item from the hash map (by id or key) will decrement the
127 /// reference count on the item. When no longer referenced, the map will
128 /// automatically delete the item.
129 ///
130 /// As items are added to the map, each is assigned a unique id
131 /// (UT_IndexedHashMapItemId). Items can then be retrieved efficiently from
132 /// the map using the id (UT_IndexedHashMapT::get()).
133 ///
134 /// Many methods on the map are thread-safe, though some are not. The thread
135 /// safety of the methods is described in the comments.
136 ///
137 /// The KEY template parameter needs to have: @code
138 /// KEY(const KEY &src); // The copy constructor
139 /// uint hash() const; // A hash method
140 /// bool isEqual(const KEY &src) const; // A comparison operator
141 /// @endcode
142 /// For sorting, there should be a < operator defined on items.
143 ///
144 /// When adding items to an indexed hash map, only a single item is every
145 /// created for duplicate keys. To optimize addition, items can be created
146 /// only if the item will be added to the map. This is done through the
147 /// DEFER_ALLOC template parameter. With the default argument (which doesn't
148 /// allow deferred allocation), ITEM objects @b must be passed in the add()
149 /// method.
150 template <typename KEY, typename ITEM,
151  typename DEFER_ALLOC=ut_IndexedHashMapDeferNullAlloc>
153 {
154 protected:
155  /// The indexed hash map maintains all operations on internal types. This
156  /// allows the bulk of the code to be shared between template
157  /// instantiations.
159  { return static_cast<KEY *>(key); }
160  SYS_FORCE_INLINE const KEY *castKEY(const InternalKeyT *key) const
161  { return static_cast<const KEY *>(key); }
163  { return static_cast<ITEM *>(item); }
164  SYS_FORCE_INLINE const ITEM *castITEM(const InternalItemT *item) const
165  { return static_cast<const ITEM *>(item); }
166 
167  /// Methods for keys
168  virtual uint hash(const InternalKeyT *key) const
169  { return castKEY(key)->hash(); }
170  virtual bool areKeysEqual(const InternalKeyT *k1,
171  const InternalKeyT *k2) const
172  { return castKEY(k1)->isEqual(*castKEY(k2)); }
173  virtual InternalKeyT *copyKey(const InternalKeyT *key) const
174  { return new KEY(*castKEY(key)); }
175  virtual void deleteKey(InternalKeyT *key) const
176  { delete castKEY(key); }
177 
178  virtual InternalItemT *newItem(const InternalKeyT *key) const
179  {
180  return DEFER_ALLOC::newItem(key);
181  }
182  virtual void deleteItem(InternalItemT *item) const
183  { delete castITEM(item); }
184  virtual bool isItemLessThan(const InternalItemT *a,
185  const InternalItemT *b) const
186  { return *castITEM(a) < *castITEM(b); }
187 
188 public:
189  UT_IndexedHashMapT(bool store_ids=true)
190  : UT_IndexedHashMap(store_ids)
191  {}
193  {
194  clear(); // Clear the map
195  }
196 
197  /// Return approximate memory usage
198  /// NOTE: *Not* including KEY or ITEM storage, even though the destructor
199  /// destroys both the KEY and ITEM objects, because the caller should know
200  /// better what KEY and ITEM are. If they can't vary in size, just
201  /// multiply by entries(); if they can, use begin() to iterate through.
202  int64 getMemoryUsage(bool inclusive) const
203  {
204  int64 mem = inclusive ? sizeof(*this) : 0;
205  mem += UT_IndexedHashMap::getMemoryUsage(false);
206  return mem;
207  }
208 
209  /// Add a new item to the map, returning the item actually stored in the
210  /// map. This may not be the item passed in if the map already contains
211  /// the object.
212  ///
213  /// If the item passed in is NULL, an item will be allocated using the
214  /// deferred allocator (see the DEFER_ALLOC template argument). The
215  /// default allocator does @b not allow for deferred construction and
216  /// requires the item to be passed in.
217  /// @note This is thread-safe
218  ITEM *add(const KEY &key, ITEM *item=NULL,
219  UT_IndexedHashMapItemId *id=NULL)
220  { return castITEM(_add(&key, item, id)); }
221 
222  /// Add reference to an existing item.
223  /// @param id Item index
224  /// @param inc The number of references to add.
225  /// It defaults to 1. If negative, the item may be
226  /// removed in which case it returns 0.
227  /// @note This item is thread-safe provided the item is exists in the map
228  /// @{
230  { return castITEM(_addReference(id, inc)); }
232  { return castITEM(_addReference(id, 1)); }
233  /// @}
234 
235  /// Find an item in the map.
236  /// @note This is thread-safe
237  ITEM *find(const KEY &key) const
238  { return castITEM(_find(&key)); }
239 
240  /// Given a key, find an item's id (or -1 if not found)
241  /// @note This is thread-safe
242  UT_IndexedHashMapItemId findId(const KEY &key) const
243  { return _findId(&key); }
244 
245  /// Find an item and its id. This is more efficient than calling find()
246  /// and findId() separately. Calling find() and findId() is also not
247  /// always thread-safe.
248  /// @note This is thread-safe
249  ITEM *find(const KEY &key, UT_IndexedHashMapItemId &id) const
250  { return castITEM(_findItemAndId(&key, id)); }
251 
252  /// Get the item which has the given id
253  /// @note This is thread-safe
254  ITEM *get(UT_IndexedHashMapItemId id) const
255  { return castITEM(_get(id)); }
256 
257  /// Get the n'th item in the list. This skips over holes and will return
258  /// items for a contiguous list of integers. For example: @code
259  /// for (int i = 0; ; ++i)
260  /// {
261  /// UT_IndexedHashMapItemId id;
262  /// ITEM *item = map.getOrderedItem(i, &id);
263  /// if (!item)
264  /// break;
265  /// }
266  /// @endcode
267  /// The @c UT_IndexedHashMapItemId's returned should be monotonic, but not
268  /// contiguous. If the @c id parameter is non-null, the id for the item
269  /// will be stored there.
270  /// @note This is @b not thread-safe
272  UT_IndexedHashMapItemId *id = NULL) const
273  { return castITEM(_getOrderedItem(index, id)); }
274 
275  /// Get the key associated with the given id
276  /// @note This is thread-safe
277  const KEY *getKey(UT_IndexedHashMapItemId id) const
278  { return castKEY(_getKey(id)); }
279 
280  /// Remove an item from the map. This dereferences the item in the map and
281  /// returns true if the item was deleted from the map. The method will
282  /// return false if the item was shared and is still in the map.
283  /// @note This is thread-safe
284  bool remove(const KEY &key)
285  { return _remove(&key); }
286 
287  /// Remove the item with the given id from the map.
288  /// @note This is thread-safe
290  { return _remove(id); }
291 
292  /// Replace an item at a given id.
293  ///
294  /// The existing item will be deleted from the table and the new item will
295  /// replace it.
296  /// The method will fail if there is currently no item at the given
297  /// location.
298  ///
299  /// The method will return the new id for the item. Usually, this will be
300  /// the same as the existing id, unless the new item already exists in the
301  /// map.
302  ///
303  /// If the item passed in is NULL, a new item will be called using newItem()
304  ///
305  /// @warning If the returned @c id does not match the @c id passed in, it's
306  /// the user's responsibility to update any references to the new id.
307  /// @note This is thread-safe
309  const KEY &key, ITEM *item=NULL)
310  { return _replaceItem(id, &key, item); }
311 
312  /// Replace the object given by the @c old_key with the value given by the
313  /// @c new_key.
314  ///
315  /// The @c old_key will be removed by the map.
316  ///
317  /// If the map stores id's, the @c new_key will be assigned the same id as
318  /// the @c old_key unless the @c new_key already exists in the map.
319  ///
320  /// The @c new_key object will inherit all references of the @c old_key.
321  ///
322  /// This method returns the id of the new item. This will be the same id
323  /// as the old object unless the @c new_key already exists in the map.
324  /// @note This is thread-safe
326  const KEY &new_key)
327  { return _replaceItem(&old_key, &new_key); }
328 
329  /// Extract the items into a list of ids and pointers to items. Items will
330  /// be appended to the lists. The function returns the number of items
331  /// added.
332  /// @note This is @b not thread-safe
335  UT_Array<ITEM *> &items
336  ) const
337  {
338  return _extractItems(ids,
339  reinterpret_cast< UT_Array<InternalItemT *> & >(items));
340  }
343  UT_Array<ITEM *> &items,
344  exint maxitems
345  ) const
346  {
347  return _extractItems(ids,
348  reinterpret_cast< UT_Array<InternalItemT *> & >(items),
349  maxitems);
350  }
351 
352  /// Extract an array of pointers to items.
353  ///
354  /// If there are id's associated with the items, the items will be stored
355  /// at their indexed location. The list of items may contain NULL pointers
356  /// for unused index entries.
357  ///
358  /// If there are no id's, the items will be extracted in arbitrary order
359  /// into a packed array.
360  ///
361  /// The function returns the number of items in the array.
362  /// @note This is @b not thread-safe
364  {
365  return _extractItems(
366  reinterpret_cast< UT_Array<InternalItemT *> & >(items));
367  }
368 
369 
370  /// @{
371  /// Convenience operators
373  { return get(id); }
374  ITEM *operator[](const KEY &k) const
375  { return find(k); }
377  { return get(id); }
378  ITEM *operator()(const KEY &k) const
379  { return find(k); }
380  /// @}
381 
382  /// Replaces the content of this with the content of src.
384  {
385  _replace(src);
386  }
387 };
388 
389 /// A string map
393 
394 #endif
SYS_FORCE_INLINE const KEY * castKEY(const InternalKeyT *key) const
UT_IndexedHashMapItemId replaceItem(const KEY &old_key, const KEY &new_key)
UT_IndexedHashMapItemKeyContainer(const UT_IndexedHashMapItemKeyContainer &i)
UT_IndexedHashMapT(bool store_ids=true)
SYS_FORCE_INLINE KEY * castKEY(InternalKeyT *key) const
InternalItemT * _get(UT_IndexedHashMapItemId id) const
void _replace(const UT_IndexedHashMap &src)
ITEM * find(const KEY &key) const
InternalItemT * _addReference(UT_IndexedHashMapItemId id, int inc)
GLboolean GLboolean GLboolean GLboolean a
Definition: glcorearb.h:1221
UT_IndexedHashMapItemId _replaceItem(UT_IndexedHashMapItemId id, const InternalKeyT *key, InternalItemT *new_item=NULL)
#define UT_API
Definition: UT_API.h:13
ut_IndexedHashMapDeferItemAlloc< UT_IndexedHashMapStringKey, UT_IndexedHashMapStringItem > UT_IndexedHashMapStringAlloc
A typedef for an allocator for the string key/item allocation.
UT_IndexedHashMapItemId replaceItem(UT_IndexedHashMapItemId id, const KEY &key, ITEM *item=NULL)
static UT_IndexedHashMap::InternalItemT * newItem(const UT_IndexedHashMap::InternalKeyT *key)
Return NULL (don't allow deferred construction).
bool operator<(const UT_IndexedHashMapStringKey &src) const
exint extractItems(UT_Array< UT_IndexedHashMapItemId > &ids, UT_Array< ITEM * > &items) const
GLuint * ids
Definition: glcorearb.h:651
png_uint_32 i
Definition: png.h:2877
exint _extractItems(UT_Array< UT_IndexedHashMapItemId > &ids, UT_Array< InternalItemT * > &items, exint maxitems) const
A thread-safe hash map which stores indexed shared items.
UT_IndexedHashMapStringKey(const UT_IndexedHashMapStringKey &src)
GLuint id
Definition: glcorearb.h:654
long long int64
Definition: SYS_Types.h:107
exint extractItems(UT_Array< UT_IndexedHashMapItemId > &ids, UT_Array< ITEM * > &items, exint maxitems) const
ITEM * getOrderedItem(exint index, UT_IndexedHashMapItemId *id=NULL) const
bool _remove(const InternalKeyT *key)
virtual void deleteKey(InternalKeyT *key) const
int64 exint
Definition: SYS_Types.h:116
UT_IndexedHashMapItemKeyContainer & operator=(const UT_IndexedHashMapItemKeyContainer &src)
InternalItemT * _getOrderedItem(exint index, UT_IndexedHashMapItemId *id) const
#define SYS_FORCE_INLINE
Definition: SYS_Inline.h:45
int64 getMemoryUsage(bool inclusive) const
Return approximate memory usage (not including key or item storage)
ITEM * addReference(UT_IndexedHashMapItemId id, int inc)
static UT_IndexedHashMap::InternalItemT * newItem(const UT_IndexedHashMap::InternalKeyT *key)
virtual bool areKeysEqual(const InternalKeyT *k1, const InternalKeyT *k2) const
virtual uint hash(const InternalKeyT *key) const
Methods for keys.
exint _findId(const InternalKeyT *key) const
virtual InternalItemT * newItem(const InternalKeyT *key) const
GLboolean GLboolean GLboolean b
Definition: glcorearb.h:1221
bool operator<(const UT_IndexedHashMapItemKeyContainer &i) const
unsigned int uint
Definition: SYS_Types.h:40
ITEM * operator[](const KEY &k) const
SYS_FORCE_INLINE const ITEM * castITEM(const InternalItemT *item) const
An allocator object which dis-allows deferred allocation of items.
const char * getString() const
Convenience class to use strings as keys in the hash map.
const InternalKeyT * _getKey(UT_IndexedHashMapItemId id) const
ITEM * operator()(const KEY &k) const
virtual bool isItemLessThan(const InternalItemT *a, const InternalItemT *b) const
virtual InternalKeyT * copyKey(const InternalKeyT *key) const
UT_IndexedHashMapStringKey(const char *key)
This allows a key to be built automatically from a const char *.
GLuint index
Definition: glcorearb.h:785
InternalItemT * _add(const InternalKeyT *key, InternalItemT *item=NULL, UT_IndexedHashMapItemId *id=NULL)
void replace(const UT_IndexedHashMapT< KEY, ITEM, DEFER_ALLOC > &src)
Replaces the content of this with the content of src.
SYS_FORCE_INLINE ITEM * castITEM(InternalItemT *item) const
A thread-safe hash map which stores indexed shared items.
UT_IndexedHashMapItemKeyContainer< UT_IndexedHashMapStringKey > UT_IndexedHashMapStringItem
ITEM * operator[](UT_IndexedHashMapItemId id) const
UT_IndexedHashMapT< UT_IndexedHashMapStringKey, UT_IndexedHashMapStringItem, UT_IndexedHashMapStringAlloc > UT_IndexedStringMap
A string map.
ITEM * find(const KEY &key, UT_IndexedHashMapItemId &id) const
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:126
UT_IndexedHashMapItemId findId(const KEY &key) const
ITEM * operator()(UT_IndexedHashMapItemId id) const
virtual void deleteItem(InternalItemT *item) const
InternalItemT * _find(const InternalKeyT *key) const
InternalItemT * _findItemAndId(const InternalKeyT *key, UT_IndexedHashMapItemId &id) const
bool isEqual(const UT_IndexedHashMapStringKey &src) const
int64 getMemoryUsage(bool inclusive) const
int UT_IndexedHashMapItemId
Each item in the shared map is assigned a unique id.
const KEY * getKey(UT_IndexedHashMapItemId id) const
bool isLessThan(const UT_IndexedHashMapStringKey &src) const
exint extractItems(UT_Array< ITEM * > &items) const
ITEM * add(const KEY &key, ITEM *item=NULL, UT_IndexedHashMapItemId *id=NULL)
GLenum src
Definition: glcorearb.h:1792
ITEM * addReference(UT_IndexedHashMapItemId id)