1 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
3 * Contains a simple container class.
5 * \author Pierre Terdiman
6 * \date February, 5, 2000
8 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
10 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
12 #ifndef ICECONTAINER_H
13 #define ICECONTAINER_H
15 // #define CONTAINER_STATS // #### doesn't work with micro-threads!
24 FIND_FORCE_DWORD = 0x7fffffff
27 class ICECORE_API Container : public Allocateable
28 #ifdef CONTAINER_STATS
33 // Constructor / Destructor
35 Container(const Container& object);
36 Container(udword size, float growth_factor);
39 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
41 * Initializes the container so that it uses an external memory buffer. The container doesn't own the memory, resizing is disabled.
42 * \param max_entries [in] max number of entries in the container
43 * \param entries [in] external memory buffer
45 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
46 void InitSharedBuffers(udword max_entries, udword* entries);
48 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
50 * A O(1) method to add a value in the container. The container is automatically resized if needed.
51 * The method is inline, not the resize. The call overhead happens on resizes only, which is not a problem since the resizing operation
52 * costs a lot more than the call overhead...
54 * \param entry [in] a udword to store in the container
55 * \see Add(float entry)
57 * \see Contains(udword entry)
58 * \return Self-Reference
60 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
61 inline_ Container& Add(udword entry)
64 if(mCurNbEntries==mMaxNbEntries) Resize();
67 mEntries[mCurNbEntries++] = entry;
71 inline_ Container& Add(const udword* entries, udword nb)
76 if(mCurNbEntries+nb>mMaxNbEntries) Resize(nb);
79 CopyMemory(&mEntries[mCurNbEntries], entries, nb*sizeof(udword));
85 inline_ Container& Add(const Container& container)
87 return Add(container.GetEntries(), container.GetNbEntries());
90 inline_ udword* Reserve(udword nb)
93 if(mCurNbEntries+nb>mMaxNbEntries) Resize(nb);
95 // We expect the user to fill reserved memory with 'nb' udwords
96 udword* Reserved = &mEntries[mCurNbEntries];
98 // Meanwhile, we do as if it had been filled
101 // This is mainly used to avoid the copy when possible
105 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
107 * A O(1) method to add a value in the container. The container is automatically resized if needed.
108 * The method is inline, not the resize. The call overhead happens on resizes only, which is not a problem since the resizing operation
109 * costs a lot more than the call overhead...
111 * \param entry [in] a float to store in the container
112 * \see Add(udword entry)
114 * \see Contains(udword entry)
115 * \return Self-Reference
117 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
118 inline_ Container& Add(float entry)
121 if(mCurNbEntries==mMaxNbEntries) Resize();
124 mEntries[mCurNbEntries++] = IR(entry);
128 inline_ Container& Add(const float* entries, udword nb)
131 if(mCurNbEntries+nb>mMaxNbEntries) Resize(nb);
134 CopyMemory(&mEntries[mCurNbEntries], entries, nb*sizeof(float));
139 //! Add unique [slow]
140 inline_ Container& AddUnique(udword entry)
142 if(!Contains(entry)) Add(entry);
146 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
148 * Clears the container. All stored values are deleted, and it frees used ram.
150 * \return Self-Reference
152 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
155 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
157 * Resets the container. Stored values are discarded but the buffer is kept so that further calls don't need resizing again.
158 * That's a kind of temporal coherence.
161 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
164 // Avoid the write if possible
166 if(mCurNbEntries) mCurNbEntries = 0;
169 // HANDLE WITH CARE - I hope you know what you're doing
170 inline_ void ForceSize(udword size)
172 mCurNbEntries = size;
175 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
177 * Sets the initial size of the container. If it already contains something, it's discarded.
178 * \param nb [in] Number of entries
179 * \return true if success
181 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
182 bool SetSize(udword nb);
184 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
186 * Refits the container and get rid of unused bytes.
187 * \return true if success
189 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
194 // Checks whether the container already contains a given value.
195 bool Contains(udword entry, udword* location=null) const;
196 // Deletes an entry - doesn't preserve insertion order.
197 bool Delete(udword entry);
198 // Deletes an entry - does preserve insertion order.
199 bool DeleteKeepingOrder(udword entry);
200 //! Deletes the very last entry.
201 inline_ void DeleteLastEntry() { if(mCurNbEntries) mCurNbEntries--; }
202 //! Deletes the entry whose index is given
203 inline_ void DeleteIndex(udword index) { mEntries[index] = mEntries[--mCurNbEntries]; }
206 Container& FindNext(udword& entry, FindMode find_mode=FIND_CLAMP);
207 Container& FindPrev(udword& entry, FindMode find_mode=FIND_CLAMP);
209 inline_ udword GetNbEntries() const { return mCurNbEntries; } //!< Returns the current number of entries.
210 inline_ udword GetMaxNbEntries() const { return mMaxNbEntries; } //!< Returns max number of entries before resizing.
211 inline_ udword GetEntry(udword i) const { return mEntries[i]; } //!< Returns ith entry.
212 inline_ udword* GetEntries() const { return mEntries; } //!< Returns the list of entries.
214 inline_ udword GetFirst() const { return mEntries[0]; }
215 inline_ udword GetLast() const { return mEntries[mCurNbEntries-1]; }
218 float GetGrowthFactor() const; //!< Returns the growth factor
219 void SetGrowthFactor(float growth); //!< Sets the growth factor
220 inline_ bool IsFull() const { return mCurNbEntries==mMaxNbEntries; } //!< Checks the container is full
221 inline_ BOOL IsNotEmpty() const { return mCurNbEntries; } //!< Checks the container is empty
223 //! Read-access as an array
224 inline_ udword operator[](udword i) const { ASSERT(i>=0 && i<mCurNbEntries); return mEntries[i]; }
225 //! Write-access as an array
226 inline_ udword& operator[](udword i) { ASSERT(i>=0 && i<mCurNbEntries); return mEntries[i]; }
229 udword GetUsedRam() const;
231 //! Operator for "Container A = Container B"
232 void operator = (const Container& object);
234 #ifdef CONTAINER_STATS
235 static udword GetNbContainers() { return mNbContainers; }
236 static udword GetTotalBytes() { return mUsedRam; }
237 static LinkedList& GetContainers() { return mContainers; }
240 static udword mNbContainers; //!< Number of containers around
241 static udword mUsedRam; //!< Amount of bytes used by containers in the system
242 static LinkedList mContainers;
246 bool Resize(udword needed=1);
248 udword mMaxNbEntries; //!< Maximum possible number of entries
249 udword mCurNbEntries; //!< Current number of entries
250 udword* mEntries; //!< List of entries
251 float mGrowthFactor; //!< Resize: new number of entries = old number * mGrowthFactor
254 #endif // ICECONTAINER_H