← Back to branch summary

~ubuntu-branches/ubuntu/raring/virtualbox-ose/raring

« back to all changes in this revision

Viewing changes to src/VBox/Main/include/vector.h

  • Committer: Bazaar Package Importer
  • Author(s): Felix Geyer
  • Date: 2011-01-30 23:27:25 UTC
  • mfrom: (0.3.12 upstream)
  • Revision ID: james.westby@ubuntu.com-20110130232725-2ouajjd2ggdet0zd
Tags: 4.0.2-dfsg-1ubuntu1
* Merge from Debian unstable, remaining changes:
  - Add Apport hook.
    - debian/virtualbox-ose.files/source_virtualbox-ose.py
    - debian/virtualbox-ose.install
  - Drop *-source packages.
* Drop ubuntu-01-fix-build-gcc45.patch, fixed upstream.
* Drop ubuntu-02-as-needed.patch, added to the Debian package.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/VBox/Main/include/vector.h
 
1
/** @file
 
2
 * STL-inspired vector implementation in C
 
3
 * @note  functions in this file are inline to prevent warnings about
 
4
 *        unused static functions.  I assume that in this day and age a
 
5
 *        compiler makes its own decisions about whether to actually
 
6
 *        inline a function.
 
7
 * @note  as this header is included in rdesktop-vrdp, we do not include other
 
8
 *        required header files here (to wit assert.h, err.h, mem.h and
 
9
 *        types.h).  These must be included first.  If this moves to iprt, we
 
10
 *        should write a wrapper around it doing that.
 
11
 * @todo  can we do more of the type checking at compile time somehow?
 
12
 */
 
13
 
 
14
/*
 
15
 * Copyright (C) 2008-2010 Oracle Corporation
 
16
 *
 
17
 * This file is part of VirtualBox Open Source Edition (OSE), as
 
18
 * available from http://www.virtualbox.org. This file is free software;
 
19
 * you can redistribute it and/or modify it under the terms of the GNU
 
20
 * General Public License (GPL) as published by the Free Software
 
21
 * Foundation, in version 2 as it comes in the "COPYING" file of the
 
22
 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
 
23
 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
 
24
 */
 
25
 
 
26
#ifndef MAIN_VECTOR_H
 
27
# define MAIN_VECTOR_H
 
28
 
 
29
/*******************************************************************************
 
30
*   Header Files                                                               *
 
31
*******************************************************************************/
 
32
 
 
33
#include <stdlib.h>
 
34
 
 
35
/*******************************************************************************
 
36
*   Helper macros and definitions                                              *
 
37
*******************************************************************************/
 
38
 
 
39
/** The unit by which the vector capacity is increased */
 
40
#define VECTOR_ALLOC_UNIT 16
 
41
 
 
42
/** Calculate a hash of a string of tokens for sanity type checking */
 
43
#define VECTOR_TOKEN_HASH(token) \
 
44
    ((unsigned) \
 
45
     (  VECTOR_TOKEN_HASH4(token, 0) \
 
46
      ^ VECTOR_TOKEN_HASH4(token, 4) \
 
47
      ^ VECTOR_TOKEN_HASH4(token, 8) \
 
48
      ^ VECTOR_TOKEN_HASH4(token, 12)))
 
49
 
 
50
/** Helper macro for @a VECTOR_TOKEN_HASH */
 
51
#define VECTOR_TOKEN_HASH_VALUE(token, place, mul) \
 
52
    (sizeof(#token) > place ? #token[place] * mul : 0)
 
53
 
 
54
/** Helper macro for @a VECTOR_TOKEN_HASH */
 
55
#define VECTOR_TOKEN_HASH4(token, place) \
 
56
      VECTOR_TOKEN_HASH_VALUE(token, place,     0x1) \
 
57
    ^ VECTOR_TOKEN_HASH_VALUE(token, place + 1, 0x100) \
 
58
    ^ VECTOR_TOKEN_HASH_VALUE(token, place + 2, 0x10000) \
 
59
    ^ VECTOR_TOKEN_HASH_VALUE(token, place + 3, 0x1000000)
 
60
 
 
61
/** Generic vector structure, used by @a VECTOR_OBJ and @a VECTOR_PTR */
 
62
#define VECTOR_STRUCT \
 
63
{ \
 
64
    /** The number of elements in the vector */ \
 
65
    size_t mcElements; \
 
66
    /** The current capacity of the vector */ \
 
67
    size_t mcCapacity; \
 
68
    /** The size of an element */ \
 
69
    size_t mcbElement; \
 
70
    /** Hash value of the element type */ \
 
71
    unsigned muTypeHash; \
 
72
    /** The elements themselves */ \
 
73
    void *mpvaElements; \
 
74
    /** Destructor for elements - takes a pointer to an element. */ \
 
75
    void (*mpfnCleanup)(void *); \
 
76
}
 
77
 
 
78
/*** Structure definitions ***/
 
79
 
 
80
/** A vector of values or objects */
 
81
typedef struct VECTOR_OBJ VECTOR_STRUCT VECTOR_OBJ;
 
82
 
 
83
/** A vector of pointer values.  (A handy special case.) */
 
84
typedef struct VECTOR_PTR VECTOR_STRUCT VECTOR_PTR;
 
85
 
 
86
/** Convenience macro for annotating the type of the vector.  Unfortunately the
 
87
 * type name is only cosmetic. */
 
88
/** @todo can we do something useful with the type? */
 
89
#define VECTOR_OBJ(type) VECTOR_OBJ
 
90
 
 
91
/** Convenience macro for annotating the type of the vector.  Unfortunately the
 
92
 * type name is only cosmetic. */
 
93
#define VECTOR_PTR(type) VECTOR_PTR
 
94
 
 
95
/*** Private helper functions and macros ***/
 
96
 
 
97
#define VEC_GET_ELEMENT_OBJ(pvaElements, cbElement, cElement) \
 
98
    ((void *)((char *)(pvaElements) + (cElement) * (cbElement)))
 
99
 
 
100
#define VEC_GET_ELEMENT_PTR(pvaElements, cElement) \
 
101
    (*(void **)VEC_GET_ELEMENT_OBJ(pvaElements, sizeof(void *), cElement))
 
102
 
 
103
/** Default cleanup function that does nothing. */
 
104
DECLINLINE(void) vecNoCleanup(void *pvElement)
 
105
{
 
106
    (void) pvElement;
 
107
}
 
108
 
 
109
/** Expand an existing vector, implementation */
 
110
DECLINLINE(int) vecExpand(size_t *pcCapacity, void **ppvaElements,
 
111
                            size_t cbElement)
 
112
{
 
113
    size_t cOldCap, cNewCap;
 
114
    void *pRealloc;
 
115
 
 
116
    cOldCap = *pcCapacity;
 
117
    cNewCap = cOldCap + VECTOR_ALLOC_UNIT;
 
118
    pRealloc = RTMemRealloc(*ppvaElements, cNewCap * cbElement);
 
119
    if (!pRealloc)
 
120
        return VERR_NO_MEMORY;
 
121
    *pcCapacity = cNewCap;
 
122
    *ppvaElements = pRealloc;
 
123
    return VINF_SUCCESS;
 
124
}
 
125
 
 
126
/** Expand an existing vector */
 
127
#define VEC_EXPAND(pvec) vecExpand(&(pvec)->mcCapacity, &(pvec)->mpvaElements, \
 
128
                                   (pvec)->mcbElement)
 
129
 
 
130
/** Reset a vector, cleaning up all its elements. */
 
131
DECLINLINE(void) vecClearObj(VECTOR_OBJ *pvec)
 
132
{
 
133
    unsigned i;
 
134
 
 
135
    for (i = 0; i < pvec->mcElements; ++i)
 
136
        pvec->mpfnCleanup(VEC_GET_ELEMENT_OBJ(pvec->mpvaElements,
 
137
                                              pvec->mcbElement, i));
 
138
    pvec->mcElements = 0;
 
139
}
 
140
 
 
141
/** Reset a pointer vector, cleaning up all its elements. */
 
142
DECLINLINE(void) vecClearPtr(VECTOR_PTR *pvec)
 
143
{
 
144
    unsigned i;
 
145
 
 
146
    for (i = 0; i < pvec->mcElements; ++i)
 
147
        pvec->mpfnCleanup(VEC_GET_ELEMENT_PTR(pvec->mpvaElements, i));
 
148
    pvec->mcElements = 0;
 
149
}
 
150
 
 
151
/** Clean up a vector */
 
152
DECLINLINE(void) vecCleanupObj(VECTOR_OBJ *pvec)
 
153
{
 
154
    vecClearObj(pvec);
 
155
    RTMemFree(pvec->mpvaElements);
 
156
    pvec->mpvaElements = NULL;
 
157
}
 
158
 
 
159
/** Clean up a pointer vector */
 
160
DECLINLINE(void) vecCleanupPtr(VECTOR_PTR *pvec)
 
161
{
 
162
    vecClearPtr(pvec);
 
163
    RTMemFree(pvec->mpvaElements);
 
164
    pvec->mpvaElements = NULL;
 
165
}
 
166
 
 
167
/** Initialise a vector structure, implementation */
 
168
#define VEC_INIT(pvec, cbElement, uTypeHash, pfnCleanup) \
 
169
    pvec->mcElements = pvec->mcCapacity = 0; \
 
170
    pvec->mcbElement = cbElement; \
 
171
    pvec->muTypeHash = uTypeHash; \
 
172
    pvec->mpfnCleanup = pfnCleanup ? pfnCleanup : vecNoCleanup; \
 
173
    pvec->mpvaElements = NULL;
 
174
 
 
175
/** Initialise a vector. */
 
176
DECLINLINE(void) vecInitObj(VECTOR_OBJ *pvec, size_t cbElement,
 
177
                            unsigned uTypeHash, void (*pfnCleanup)(void *))
 
178
{
 
179
    VEC_INIT(pvec, cbElement, uTypeHash, pfnCleanup)
 
180
}
 
181
 
 
182
/** Initialise a pointer vector. */
 
183
DECLINLINE(void) vecInitPtr(VECTOR_PTR *pvec, size_t cbElement,
 
184
                            unsigned uTypeHash, void (*pfnCleanup)(void *))
 
185
{
 
186
    VEC_INIT(pvec, cbElement, uTypeHash, pfnCleanup)
 
187
}
 
188
 
 
189
/** Add an element onto the end of a vector */
 
190
DECLINLINE(int) vecPushBackObj(VECTOR_OBJ *pvec, unsigned uTypeHash,
 
191
                                 void *pvElement)
 
192
{
 
193
    int rc2;
 
194
    AssertReturn(pvec->muTypeHash == uTypeHash, VERR_INVALID_PARAMETER);
 
195
    if (   pvec->mcElements == pvec->mcCapacity
 
196
        && RT_FAILURE((rc2 = VEC_EXPAND(pvec))))
 
197
        return rc2;
 
198
    memcpy(VEC_GET_ELEMENT_OBJ(pvec->mpvaElements, pvec->mcbElement,
 
199
                               pvec->mcElements), pvElement, pvec->mcbElement);
 
200
    ++pvec->mcElements;
 
201
    return VINF_SUCCESS;
 
202
}
 
203
 
 
204
/** Add a pointer onto the end of a pointer vector */
 
205
DECLINLINE(int) vecPushBackPtr(VECTOR_PTR *pvec, unsigned uTypeHash,
 
206
                                 void *pv)
 
207
{
 
208
    int rc2;
 
209
    AssertReturn(pvec->muTypeHash == uTypeHash, VERR_INVALID_PARAMETER);
 
210
    if (   pvec->mcElements == pvec->mcCapacity
 
211
        && RT_FAILURE((rc2 = VEC_EXPAND(pvec))))
 
212
        return rc2;
 
213
    VEC_GET_ELEMENT_PTR(pvec->mpvaElements, pvec->mcElements) = pv;
 
214
    ++pvec->mcElements;
 
215
    return VINF_SUCCESS;
 
216
}
 
217
 
 
218
/*******************************************************************************
 
219
*   Public interface macros                                                    *
 
220
*******************************************************************************/
 
221
 
 
222
/**
 
223
 * Initialise a vector structure.  Always succeeds.
 
224
 * @param   pvec        pointer to an uninitialised vector structure
 
225
 * @param   type        the type of the objects in the vector.  As this is
 
226
 *                      hashed by the preprocessor use of space etc is
 
227
 *                      important.
 
228
 * @param   pfnCleanup  cleanup function (void (*pfn)(void *)) that is called
 
229
 *                      on a pointer to a vector element when that element is
 
230
 *                      dropped
 
231
 */
 
232
#define VEC_INIT_OBJ(pvec, type, pfnCleanup) \
 
233
    vecInitObj(pvec, sizeof(type), VECTOR_TOKEN_HASH(type), \
 
234
               (void (*)(void*)) pfnCleanup)
 
235
 
 
236
/**
 
237
 * Initialise a vector-of-pointers structure.  Always succeeds.
 
238
 * @param   pvec        pointer to an uninitialised vector structure
 
239
 * @param   type        the type of the pointers in the vector, including the
 
240
 *                      final "*".  As this is hashed by the preprocessor use
 
241
 *                      of space etc is important.
 
242
 * @param   pfnCleanup  cleanup function (void (*pfn)(void *)) that is called
 
243
 *                      directly on a vector element when that element is
 
244
 *                      dropped
 
245
 */
 
246
#define VEC_INIT_PTR(pvec, type, pfnCleanup) \
 
247
    vecInitPtr(pvec, sizeof(type), VECTOR_TOKEN_HASH(type), \
 
248
               (void (*)(void*)) pfnCleanup)
 
249
 
 
250
/**
 
251
 * Clean up a vector.
 
252
 * @param pvec  pointer to the vector to clean up.  The clean up function
 
253
 *              specified at initialisation (if any) is called for each element
 
254
 *              in the vector.  After clean up, the vector structure is invalid
 
255
 *              until it is re-initialised
 
256
 */
 
257
#define VEC_CLEANUP_OBJ vecCleanupObj
 
258
 
 
259
/**
 
260
 * Clean up a vector-of-pointers.
 
261
 * @param pvec  pointer to the vector to clean up.  The clean up function
 
262
 *              specified at initialisation (if any) is called for each element
 
263
 *              in the vector.  After clean up, the vector structure is invalid
 
264
 *              until it is re-initialised
 
265
 */
 
266
#define VEC_CLEANUP_PTR vecCleanupPtr
 
267
 
 
268
/**
 
269
 * Reinitialises a vector structure to empty.
 
270
 * @param  pvec  pointer to the vector to re-initialise.  The clean up function
 
271
 *               specified at initialisation (if any) is called for each element
 
272
 *               in the vector.
 
273
 */
 
274
#define VEC_CLEAR_OBJ vecClearObj
 
275
 
 
276
/**
 
277
 * Reinitialises a vector-of-pointers structure to empty.
 
278
 * @param  pvec  pointer to the vector to re-initialise.  The clean up function
 
279
 *               specified at initialisation (if any) is called for each element
 
280
 *               in the vector.
 
281
 */
 
282
#define VEC_CLEAR_PTR vecClearPtr
 
283
 
 
284
/**
 
285
 * Adds an element to the back of a vector.  The element will be byte-copied
 
286
 * and become owned by the vector, to be cleaned up by the vector's clean-up
 
287
 * routine when the element is dropped.
 
288
 * @returns iprt status code (VINF_SUCCESS or VERR_NO_MEMORY)
 
289
 * @returns VERR_INVALID_PARAMETER if the type does not match the type given
 
290
 *          when the vector was initialised (asserted)
 
291
 * @param pvec       pointer to the vector on to which the element should be
 
292
 *                   added
 
293
 * @param type       the type of the vector as specified at initialisation.
 
294
 *                   Spacing etc is important.
 
295
 * @param pvElement  void pointer to the element to be added
 
296
 */
 
297
#define VEC_PUSH_BACK_OBJ(pvec, type, pvElement) \
 
298
    vecPushBackObj(pvec, VECTOR_TOKEN_HASH(type), \
 
299
                   (pvElement) + ((pvElement) - (type *)(pvElement)))
 
300
 
 
301
/**
 
302
 * Adds a pointer to the back of a vector-of-pointers.  The pointer will become
 
303
 * owned by the vector, to be cleaned up by the vector's clean-up routine when
 
304
 * it is dropped.
 
305
 * @returns iprt status code (VINF_SUCCESS or VERR_NO_MEMORY)
 
306
 * @returns VERR_INVALID_PARAMETER if the type does not match the type given
 
307
 *          when the vector was initialised (asserted)
 
308
 * @param pvec       pointer to the vector on to which the element should be
 
309
 *                   added
 
310
 * @param type       the type of the vector as specified at initialisation.
 
311
 *                   Spacing etc is important.
 
312
 * @param pvElement  the pointer to be added, typecast to pointer-to-void
 
313
 */
 
314
#define VEC_PUSH_BACK_PTR(pvec, type, pvElement) \
 
315
    vecPushBackPtr(pvec, VECTOR_TOKEN_HASH(type), \
 
316
                   (pvElement) + ((pvElement) - (type)(pvElement)))
 
317
 
 
318
/**
 
319
 * Returns the count of elements in a vector.
 
320
 * @param  pvec  pointer to the vector.
 
321
 */
 
322
#define VEC_SIZE_OBJ(pvec) (pvec)->mcElements
 
323
 
 
324
/**
 
325
 * Returns the count of elements in a vector-of-pointers.
 
326
 * @param  pvec  pointer to the vector.
 
327
 */
 
328
#define VEC_SIZE_PTR VEC_SIZE_OBJ
 
329
 
 
330
/**
 
331
 * Iterates over the vector elements from first to last and execute the
 
332
 * following instruction or block on each iteration with @a pIterator set to
 
333
 * point to the current element (that is, a pointer to the pointer element for
 
334
 * a vector-of-pointers).  Use in the same way as a "for" statement.
 
335
 * @param pvec       pointer to the vector to be iterated over
 
336
 * @param type       the type of the vector, must match the type specified at
 
337
 *                   vector initialisation (including whitespace etc)
 
338
 * @todo  can we assert the correctness of the type in some way?
 
339
 * @param pIterator  a pointer to @a type which will be set to point to the
 
340
 *                   current vector element on each iteration
 
341
 */
 
342
#define VEC_FOR_EACH(pvec, type, pIterator) \
 
343
    for (pIterator = (type *) (pvec)->mpvaElements; \
 
344
            (pvec)->muTypeHash == VECTOR_TOKEN_HASH(type) \
 
345
         && pIterator < (type *) (pvec)->mpvaElements + (pvec)->mcElements; \
 
346
         ++pIterator)
 
347
 
 
348
#endif /* MAIN_VECTOR_H */