1 /* -*- mode: C++; tab-width: 4; c-basic-offset: 4; -*- */
2
3 /* AbiSource Program Utilities
4 * Copyright (C) 1998-2000 AbiSource, Inc.
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 * 02110-1301 USA.
20 */
21
22 #ifndef UTVECTOR_H
23 #define UTVECTOR_H
24
25 /* pre-emptive dismissal; ut_types.h is needed by just about everything,
26 * so even if it's commented out in-file that's still a lot of work for
27 * the preprocessor to do...
28 */
29 #ifndef UT_TYPES_H
30 #include "ut_types.h"
31 #endif
32 #include "ut_assert.h"
33 #include "ut_debugmsg.h"
34 // ----------------------------------------------------------------
35
36 #define UT_VECTOR_CLEANUP(d, v, r) \
37 do { int utv_max = v.getItemCount(); \
38 for (int utv=utv_max-1; utv>=0; utv--) \
39 { \
40 d utv_p = (d) v.getNthItem(utv); \
41 UT_ASSERT_HARMLESS(utv_p); \
42 if (utv_p) \
43 r (utv_p); \
44 } \
45 } while (0)
46
47 #define UT_VECTOR_SPARSECLEANUP(d, v, r) \
48 do { int utv_max = v.getItemCount(); \
49 for (int utv=utv_max-1; utv>=0; utv--) \
50 { \
51 d utv_p = (d) v.getNthItem(utv); \
52 if (utv_p) \
53 r (utv_p); \
54 } \
55 } while (0)
56
57 #define UT_VECTOR_PURGEALL(d, v) UT_VECTOR_CLEANUP(d, v, delete)
58 #define UT_VECTOR_FREEALL(d, v) UT_VECTOR_CLEANUP(d, v, g_free)
59 #define UT_VECTOR_SPARSEPURGEALL(d, v) UT_VECTOR_SPARSECLEANUP(d, v, delete)
60 #define UT_VECTOR_SPARSEFREEALL(d, v) UT_VECTOR_SPARSECLEANUP(d, v, g_free)
61
62 /* don't call this macro unless you are in Obj-C++ */
63 /* release any non nil objective-C object of the array */
64 #define UT_VECTOR_RELEASE(v) \
65 { \
66 int utv_max = v.getItemCount(); \
67 for (int utv=utv_max-1; utv>=0; utv--) \
68 { \
69 id utv_p = (id) v.getNthItem(utv); \
70 [utv_p release]; \
71 } \
72 }
73
74
75 template <class T> class UT_GenericVector
76 {
77 public:
78 typedef int (*compar_fn_t) (const void *, const void *);
79
80 // Real-life tests shown that vast majority of our vectors contain less than 4 items
81 // and virtually all contains less than 32 elements; I have adjusted the initial
82 // values accordingly. Where vectors are known to be larger, bigger values should be
83 // passed to the constructor, and, if approprite, pre-allocation forced
84 UT_GenericVector(UT_sint32 sizehint = 32, UT_sint32 baseincr = 4, bool bPrealloc = false);
85 UT_GenericVector(const UT_GenericVector<T>&);
86 UT_GenericVector<T>& operator=(const UT_GenericVector<T>&);
87 virtual ~UT_GenericVector();
88
89 UT_sint32 addItem(const T);
push_back(const T item)90 inline UT_sint32 push_back(const T item) { return addItem(item); }
91 bool pop_back();
back()92 inline const T back() const { return getLastItem(); }
93
94 UT_sint32 addItem(const T p, UT_sint32 * pIndex);
95
96 /* FIXME -- this function assumes that it is possible to do
97 * static_cast<T>(0)
98 */
getNthItem(UT_sint32 n)99 inline T getNthItem(UT_sint32 n) const
100 {
101 UT_ASSERT_HARMLESS(m_pEntries);
102 UT_ASSERT_HARMLESS(m_iCount > 0);
103 UT_ASSERT_HARMLESS(n<m_iCount);
104
105 if(n >= m_iCount || !m_pEntries) {
106 return 0;
107 }
108 return m_pEntries[n];
109 }
110
111 const T operator[](UT_sint32 i) const;
112 UT_sint32 setNthItem(UT_sint32 ndx, T pNew, T * ppOld);
113 const T getFirstItem() const;
114 const T getLastItem() const;
getItemCount()115 inline UT_sint32 getItemCount() const { return m_iCount; }
116 UT_sint32 findItem(T) const;
117
118 UT_sint32 insertItemAt(T, UT_sint32 ndx);
119 UT_sint32 addItemSorted(const T p, int (*compar)(const void *, const void *));
120 void deleteNthItem(UT_sint32 n);
121 void clear();
122 void qsort(int (*compar)(const void *, const void *));
123 UT_sint32 binarysearch(const void* key, int (*compar)(const void *, const void *)) const;
124
125 bool copy(const UT_GenericVector<T> *pVec);
size()126 inline UT_sint32 size() const { return getItemCount(); }
127
128 private:
129 UT_sint32 grow(UT_sint32);
130 UT_sint32 binarysearchForSlot(const void* key, compar_fn_t compar) const;
131
132 T* m_pEntries;
133 UT_sint32 m_iCount;
134 UT_sint32 m_iSpace;
135 UT_sint32 m_iCutoffDouble;
136 UT_sint32 m_iPostCutoffIncrement;
137 };
138
139 // TODO Rob: try to export like this once plugin loading is fixed:
140 // template class ABI_EXPORT UT_GenericVector<void const *>;
141 class ABI_EXPORT UT_Vector : public UT_GenericVector<void const *> {
142 public:
143 UT_Vector(UT_sint32 sizehint = 32, UT_sint32 baseincr = 4, bool bPrealloc = false)
144 : UT_GenericVector<void const *>(sizehint, baseincr, bPrealloc)
145 {}
146 };
147
148 // TODO Rob: try to export like this once plugin loading is fixed:
149 // template class ABI_EXPORT UT_GenericVector<UT_sint32>;
150 class ABI_EXPORT UT_NumberVector : public UT_GenericVector<UT_sint32> {
151 public:
152 UT_NumberVector(UT_sint32 sizehint = 32, UT_sint32 baseincr = 4, bool bPrealloc = false)
153 : UT_GenericVector<UT_sint32>(sizehint, baseincr, bPrealloc)
154 {}
155 };
156
157 #include <stdlib.h>
158 #include <string.h>
159
160 /*!
161 sizehint: expected size of the vector
162
163 baseincr: the amount by which the internal storage will grow once the sizehint has
164 been reached (until then, the size gets doubled)
165
166 bPrealoc: if true, we immediately allocate storage of at least sizehint (otherwise the
167 space will be allocated when first item is inserted to baseincr)
168 */
169 template <class T>
UT_GenericVector(UT_sint32 sizehint,UT_sint32 baseincr,bool bPrealoc)170 UT_GenericVector<T>::UT_GenericVector(UT_sint32 sizehint, UT_sint32 baseincr, bool bPrealoc)
171 : m_pEntries(NULL), m_iCount(0), m_iSpace(0),
172 m_iCutoffDouble(sizehint), m_iPostCutoffIncrement(baseincr)
173 {
174 if(bPrealoc)
175 grow(sizehint);
176 }
177
178 template <class T>
UT_GenericVector(const UT_GenericVector<T> & utv)179 UT_GenericVector<T>::UT_GenericVector(const UT_GenericVector<T>& utv)
180 : m_pEntries(NULL), m_iCount(0), m_iSpace(0),
181 m_iCutoffDouble(utv.m_iCutoffDouble),
182 m_iPostCutoffIncrement(utv.m_iPostCutoffIncrement)
183 {
184 copy(&utv);
185 }
186
187 template <class T>
188 UT_GenericVector<T>& UT_GenericVector<T>::operator=(const UT_GenericVector<T>& utv)
189 {
190 if(this != &utv)
191 {
192 m_iCutoffDouble = utv.m_iCutoffDouble;
193 m_iPostCutoffIncrement = utv.m_iPostCutoffIncrement;
194 copy(&utv);
195 }
196 return *this;
197 }
198
199 template <class T>
clear()200 void UT_GenericVector<T>::clear()
201 {
202 if(m_iCount > m_iCutoffDouble)
203 {
204 xxx_UT_DEBUGMSG(("Vector contained %d entries, allocated %d slots\n", m_iCount, m_iSpace));
205 }
206
207 m_iCount = 0;
208 memset(m_pEntries, 0, m_iSpace * sizeof(T));
209 }
210
211
212 template <class T>
~UT_GenericVector()213 UT_GenericVector<T>::~UT_GenericVector()
214 {
215 if(m_iCount > m_iCutoffDouble)
216 {
217 xxx_UT_DEBUGMSG(("Vector contained %d entries, allocated %d slots\n", m_iCount, m_iSpace));
218 }
219
220 FREEP(m_pEntries);
221 }
222
223 /*
224 This function is called everytime we want to insert a new element but don't have
225 enough space. In this case we grow the array to be _at least_ ndx size.
226 */
227 template <class T>
grow(UT_sint32 ndx)228 UT_sint32 UT_GenericVector<T>::grow(UT_sint32 ndx)
229 {
230 UT_sint32 new_iSpace;
231 if(!m_iSpace) {
232 new_iSpace = m_iPostCutoffIncrement;
233 }
234 else if (m_iSpace < m_iCutoffDouble) {
235 xxx_UT_DEBUGMSG(("Vector growing (%d -> %d\n", m_iSpace, ndx));
236 new_iSpace = m_iSpace * 2;
237 }
238 else {
239 new_iSpace = m_iSpace + m_iPostCutoffIncrement;
240 }
241
242 if (new_iSpace < ndx)
243 {
244 new_iSpace = ndx;
245 }
246
247 T * new_pEntries = static_cast<T *>(g_try_realloc(m_pEntries, new_iSpace * sizeof(T)));
248 if (!new_pEntries) {
249 return -1;
250 }
251 //Is this required? We always check Count first anyways.
252 // TMN: Unfortunately it is, since the class GR_CharWidths
253 // uses UT_GenericVector<T> as a sparse array!
254 memset(&new_pEntries[m_iSpace], 0, (new_iSpace - m_iSpace) * sizeof(T));
255 m_iSpace = new_iSpace;
256 m_pEntries = new_pEntries;
257
258 return 0;
259 }
260
261 template <class T>
insertItemAt(const T p,UT_sint32 ndx)262 UT_sint32 UT_GenericVector<T>::insertItemAt(const T p, UT_sint32 ndx)
263 {
264 if (ndx > m_iCount + 1)
265 return -1;
266
267 if ((m_iCount+1) > m_iSpace)
268 {
269 UT_sint32 err = grow(0);
270 if (err)
271 {
272 return err;
273 }
274 }
275
276 // bump the elements -> thataway up to the ndxth position
277 memmove(&m_pEntries[ndx+1], &m_pEntries[ndx], (m_iCount - ndx) * sizeof(T));
278
279 m_pEntries[ndx] = (T)p;
280 ++m_iCount;
281
282 return 0;
283 }
284
285 template <class T>
addItem(const T p,UT_sint32 * pIndex)286 UT_sint32 UT_GenericVector<T>::addItem(const T p, UT_sint32 * pIndex)
287 {
288 UT_sint32 err = addItem(p);
289 if (!err && pIndex)
290 *pIndex = m_iCount-1;
291 return err;
292 }
293
294 template <class T>
addItem(const T p)295 UT_sint32 UT_GenericVector<T>::addItem(const T p)
296 {
297 if ((m_iCount+1) > m_iSpace)
298 {
299 UT_sint32 err = grow(0);
300 if (err)
301 {
302 return err;
303 }
304 }
305
306 m_pEntries[m_iCount++] = (T)p; /*** bad, cast away const so we can build again ***/
307
308 return 0;
309 }
310
311 template <class T>
addItemSorted(const T p,int (* compar)(const void *,const void *))312 UT_sint32 UT_GenericVector<T>::addItemSorted(const T p, int (*compar)(const void *, const void *))
313 {
314 if (!m_iCount) {
315 return addItem(p);
316 }
317
318 return insertItemAt( p, binarysearchForSlot((static_cast<void*>(const_cast<T*>(&p))), compar));
319 }
320
321 /** It returns true if there were no errors, false elsewhere */
322 template <class T>
pop_back()323 bool UT_GenericVector<T>::pop_back()
324 {
325 if (m_iCount > 0)
326 {
327 --m_iCount;
328 return true;
329 }
330 else
331 return false;
332 }
333
334 template <class T>
setNthItem(UT_sint32 ndx,T pNew,T * ppOld)335 UT_sint32 UT_GenericVector<T>::setNthItem(UT_sint32 ndx, T pNew, T* ppOld)
336 {
337 const UT_sint32 old_iSpace = m_iSpace;
338
339 if (ndx >= m_iSpace)
340 {
341 const UT_sint32 err = grow(ndx+1);
342 if (err)
343 {
344 return err;
345 }
346 }
347
348 if (ppOld)
349 {
350 *ppOld = (ndx < old_iSpace) ? m_pEntries[ndx] : 0;
351 }
352
353 m_pEntries[ndx] = pNew;
354 if (ndx >= m_iCount)
355 {
356 m_iCount = ndx + 1;
357 }
358
359 return 0;
360 }
361
362 template <class T>
getLastItem()363 const T UT_GenericVector<T>::getLastItem() const
364 {
365 UT_ASSERT_HARMLESS(m_iCount > 0);
366
367 return m_pEntries[m_iCount-1];
368 }
369
370 template <class T>
getFirstItem()371 const T UT_GenericVector<T>::getFirstItem() const
372 {
373 UT_ASSERT_HARMLESS(m_iCount > 0);
374 UT_ASSERT_HARMLESS(m_pEntries);
375
376 return m_pEntries[0];
377 }
378
379 template <class T>
deleteNthItem(UT_sint32 n)380 void UT_GenericVector<T>::deleteNthItem(UT_sint32 n)
381 {
382 UT_ASSERT_HARMLESS(n < m_iCount);
383 UT_ASSERT_HARMLESS(m_iCount > 0);
384
385 memmove(&m_pEntries[n], &m_pEntries[n+1], (m_iCount - (n + 1)) * sizeof(T));
386
387 m_pEntries[m_iCount-1] = 0;
388 m_iCount--;
389
390 return;
391 }
392
393 template <class T>
findItem(T p)394 UT_sint32 UT_GenericVector<T>::findItem(T p) const
395 {
396 for (UT_sint32 i=0; i<m_iCount; i++)
397 {
398 if (m_pEntries[i] == p)
399 {
400 return i;
401 }
402 }
403
404 return -1;
405 }
406
407 template <class T>
qsort(int (* compar)(const void *,const void *))408 void UT_GenericVector<T>::qsort(int (*compar)(const void *, const void *))
409 {
410 ::qsort(m_pEntries, m_iCount, sizeof(T), compar);
411 }
412
413 // this binary search finds the earliest element (lowest index)
414 // in the vector which matches the key
415 // based on code from Tim Bray's 'On the Goodness of Binary Search'
416 // http://tbray.org/ongoing/When/200x/2003/03/22/Binary
417
418 template <class T>
binarysearch(const void * key,compar_fn_t compar)419 UT_sint32 UT_GenericVector<T>::binarysearch(const void* key, compar_fn_t compar) const
420 {
421 UT_sint32 slot = binarysearchForSlot(key, compar);
422
423 if ((slot == m_iCount) || (0 != (*compar)(key, &m_pEntries[slot])))
424 return -1;
425 else
426 return slot;
427 }
428
429 template <class T>
binarysearchForSlot(const void * key,compar_fn_t compar)430 UT_sint32 UT_GenericVector<T>::binarysearchForSlot(const void* key, compar_fn_t compar) const
431 {
432 UT_sint32 high = m_iCount;
433 UT_sint32 low = -1;
434 UT_sint32 probe;
435
436 while (high - low > 1)
437 {
438 int res;
439 probe = (high + low) / 2;
440 res = (*compar)(key, &m_pEntries[probe]);
441 if (0 < res)
442 low = probe;
443 else
444 high = probe;
445 }
446
447 return high;
448 }
449
450 template <class T>
copy(const UT_GenericVector<T> * pVec)451 bool UT_GenericVector<T>::copy(const UT_GenericVector<T> *pVec)
452 {
453 clear();
454
455 for (UT_sint32 i=0; i < pVec->m_iCount; i++)
456 {
457 UT_sint32 err;
458
459 err = addItem(pVec->m_pEntries[i]);
460 if(err == -1)
461 return (err ? true : false);
462 }
463
464 return 0;
465 }
466
467 template <class T>
468 const T UT_GenericVector<T>::operator[](UT_sint32 i) const
469 {
470 return this->getNthItem(i);
471 }
472
473
474 #endif /* UTVECTOR_H */
475