tSparseArray.h

Classes:

class
SparseArray::Node
Detailed Description

  1
  2//-----------------------------------------------------------------------------
  3// Copyright (c) 2012 GarageGames, LLC
  4//
  5// Permission is hereby granted, free of charge, to any person obtaining a copy
  6// of this software and associated documentation files (the "Software"), to
  7// deal in the Software without restriction, including without limitation the
  8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  9// sell copies of the Software, and to permit persons to whom the Software is
 10// furnished to do so, subject to the following conditions:
 11//
 12// The above copyright notice and this permission notice shall be included in
 13// all copies or substantial portions of the Software.
 14//
 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 21// IN THE SOFTWARE.
 22//-----------------------------------------------------------------------------
 23
 24#ifndef _TSPARSEARRAY_H_
 25#define _TSPARSEARRAY_H_
 26
 27//Includes
 28#ifndef _PLATFORM_H_
 29#include "platform/platform.h"
 30#endif
 31#ifndef _PLATFORMASSERT_H_
 32#include "platform/platformAssert.h"
 33#endif
 34
 35template <class T>
 36class SparseArray
 37{
 38  protected:
 39   struct Node {
 40      T*    pObject;
 41      U32   key;
 42
 43      Node* next;
 44   };
 45
 46  protected:
 47   U32   mModulus;
 48   Node* mSentryTables;
 49
 50public:
 51   SparseArray(const U32 modulusSize = 64);
 52   ~SparseArray();
 53
 54   void insert(T* pObject, U32 key);
 55   T*   remove(U32 key);
 56   T*   retreive(U32 key);
 57
 58   void clearTables();           // Note: _deletes_ the objects!
 59};
 60
 61template <class T>
 62inline SparseArray<T>::SparseArray(const U32 modulusSize)
 63{
 64   AssertFatal(modulusSize > 0, "Error, modulus must be > 0");
 65
 66   mModulus      = modulusSize;
 67   mSentryTables = new Node[mModulus];
 68   for (U32 i = 0; i < mModulus; i++)
 69      mSentryTables[i].next = NULL;
 70}
 71
 72template <class T>
 73inline SparseArray<T>::~SparseArray()
 74{
 75   clearTables();
 76}
 77
 78template <class T>
 79inline void SparseArray<T>::clearTables()
 80{
 81   for (U32 i = 0; i < mModulus; i++) {
 82      Node* pProbe = mSentryTables[i].next;
 83      while (pProbe != NULL) {
 84         Node* pNext = pProbe->next;
 85         delete pProbe->pObject;
 86         delete pProbe;
 87         pProbe = pNext;
 88      }
 89   }
 90   delete [] mSentryTables;
 91   mSentryTables = NULL;
 92   mModulus = 0;
 93}
 94
 95template <class T>
 96inline void SparseArray<T>::insert(T* pObject, U32 key)
 97{
 98   U32 insert = key % mModulus;
 99   Node* pNew = new Node;
100   pNew->pObject = pObject;
101   pNew->key     = key;
102   pNew->next    = mSentryTables[insert].next;
103   mSentryTables[insert].next = pNew;
104
105#ifdef TORQUE_DEBUG
106   Node* probe = pNew->next;
107   while (probe != NULL) {
108      AssertFatal(probe->key != key, "error, duplicate keys in sparse array!");
109      probe = probe->next;
110   }
111#endif
112}
113
114template <class T>
115inline T* SparseArray<T>::remove(U32 key)
116{
117   U32 sentryID  = key % mModulus;
118   Node* probe = &mSentryTables[sentryID];
119   while (probe->next != NULL) {
120      if (probe->next->key == key) {
121         Node* nextProbe = probe->next;
122         T* pReturn   = nextProbe->pObject;
123         probe->next  = nextProbe->next;
124         delete nextProbe;
125         return pReturn;
126      }
127      probe = probe->next;
128   }
129
130   // [tom, 8/19/2006] This assert is also utterly, utterly useless
131   // AssertFatal(false, "Key didn't exist in the array!");
132   return NULL;
133}
134
135template <class T>
136inline T* SparseArray<T>::retreive(U32 key)
137{
138   U32 retrieve = key % mModulus;
139   Node* probe  = &mSentryTables[retrieve];
140   while (probe->next != NULL) {
141      if (probe->next->key == key) {
142         return probe->next->pObject;
143      }
144      probe = probe->next;
145   }
146
147   // [tom, 11/16/2005] This assert is utterly, utterly useless
148   // AssertFatal(false, "Key didn't exist in the array!");
149   return NULL;
150}
151
152#endif //_TSPARSEARRAY_H_
153
154