VirtualBox

source: vbox/trunk/src/VBox/Runtime/common/misc/handletable.cpp@ 10788

Last change on this file since 10788 was 10788, checked in by vboxsync, 16 years ago

IPRT: Implemented the context variant of the handle table.

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 23.9 KB
Line 
1/* $Id: handletable.cpp 10788 2008-07-21 16:44:33Z vboxsync $ */
2/** @file
3 * IPRT - Handle Tables.
4 */
5
6/*
7 * Copyright (C) 2008 Sun Microsystems, Inc.
8 *
9 * This file is part of VirtualBox Open Source Edition (OSE), as
10 * available from http://www.virtualbox.org. This file is free software;
11 * you can redistribute it and/or modify it under the terms of the GNU
12 * General Public License (GPL) as published by the Free Software
13 * Foundation, in version 2 as it comes in the "COPYING" file of the
14 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
15 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
16 *
17 * The contents of this file may alternatively be used under the terms
18 * of the Common Development and Distribution License Version 1.0
19 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
20 * VirtualBox OSE distribution, in which case the provisions of the
21 * CDDL are applicable instead of those of the GPL.
22 *
23 * You may elect to license modified versions of this file under the
24 * terms and conditions of either the GPL or the CDDL or both.
25 *
26 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
27 * Clara, CA 95054 USA or visit http://www.sun.com if you need
28 * additional information or have any questions.
29 */
30
31/*******************************************************************************
32* Header Files *
33*******************************************************************************/
34#include <iprt/handletable.h>
35#include <iprt/mem.h>
36#include <iprt/spinlock.h>
37#include <iprt/err.h>
38#include <iprt/assert.h>
39#include <iprt/param.h>
40#include <iprt/string.h>
41#include <iprt/asm.h>
42#include "internal/magics.h"
43
44
45/*******************************************************************************
46* Defined Constants And Macros *
47*******************************************************************************/
48/** The number of entries in the 2nd level lookup table. */
49#define RTHT_LEVEL2_ENTRIES 2048
50
51/** The number of (max) 1st level entries requiring dynamic allocation of the
52 * 1st level table. If the max number is below this threshold, the 1st level
53 * table will be allocated as part of the handle table structure. */
54#define RTHT_LEVEL1_DYN_ALLOC_THRESHOLD 256
55
56/** Checks whether a object pointer is really a free entry or not. */
57#define RTHT_IS_FREE(pvObj) ( ((uintptr_t)(pvObj) & 3) == 3 )
58
59/** Sets RTHTENTRYFREE::iNext. */
60#define RTHT_SET_FREE_IDX(pFree, idx) \
61 do { \
62 (pFree)->iNext = ((uintptr_t)((uint32_t)(idx)) << 2) | 3U; \
63 } while (0)
64
65/** Gets the index part of RTHTENTRYFREE::iNext. */
66#define RTHT_GET_FREE_IDX(pFree) ( (uint32_t)((pFree)->iNext >> 2) )
67
68/** @def NIL_RTHT_INDEX
69 * The NIL handle index for use in the free list. (The difference between
70 * 32-bit and 64-bit hosts here comes down to the shifting performed for
71 * RTHTENTRYFREE::iNext.) */
72#if ARCH_BITS == 32
73# define NIL_RTHT_INDEX ( UINT32_C(0x3fffffff) )
74#elif ARCH_BITS >= 34
75# define NIL_RTHT_INDEX ( UINT32_C(0xffffffff) )
76#else
77# error "Missing or unsupported ARCH_BITS."
78#endif
79
80
81/*******************************************************************************
82* Structures and Typedefs *
83*******************************************************************************/
84
85/**
86 * Handle table entry, simple variant.
87 */
88typedef struct RTHTENTRY
89{
90 /** The object. */
91 void *pvObj;
92} RTHTENTRY;
93/** Pointer to a handle table entry, simple variant. */
94typedef RTHTENTRY *PRTHTENTRY;
95
96
97/**
98 * Handle table entry, context variant.
99 */
100typedef struct RTHTENTRYCTX
101{
102 /** The object. */
103 void *pvObj;
104 /** The context. */
105 void *pvCtx;
106} RTHTENTRYCTX;
107/** Pointer to a handle table entry, context variant. */
108typedef RTHTENTRYCTX *PRTHTENTRYCTX;
109
110
111/**
112 * Free handle table entry, shared by all variants.
113 */
114typedef struct RTHTENTRYFREE
115{
116 /** The index of the next handle, special format.
117 * In order to distinguish free and used handle table entries we exploit
118 * the heap alignment and use the lower two bits to do this. Used entries
119 * will have these bits set to 0, while free entries will have tem set
120 * to 3. Use the RTHT_GET_FREE_IDX and RTHT_SET_FREE_IDX macros to access
121 * this field. */
122 uintptr_t iNext;
123} RTHTENTRYFREE;
124/** Pointer to a free handle table entry. */
125typedef RTHTENTRYFREE *PRTHTENTRYFREE;
126
127AssertCompile(sizeof(RTHTENTRYFREE) <= sizeof(RTHTENTRY));
128AssertCompile(sizeof(RTHTENTRYFREE) <= sizeof(RTHTENTRYCTX));
129AssertCompileMemberOffset(RTHTENTRYFREE, iNext, 0);
130AssertCompileMemberOffset(RTHTENTRY, pvObj, 0);
131AssertCompileMemberOffset(RTHTENTRYCTX, pvObj, 0);
132
133
134/**
135 * Internal handle table structure.
136 */
137typedef struct RTHANDLETABLEINT
138{
139 /** Magic value (RTHANDLETABLE_MAGIC). */
140 uint32_t u32Magic;
141 /** The handle table flags specified to RTHandleTableCreateEx. */
142 uint32_t fFlags;
143 /** The base handle value (i.e. the first handle). */
144 uint32_t uBase;
145 /** The current number of handle table entries. */
146 uint32_t cCur;
147 /** The spinlock handle (NIL if RTHANDLETABLE_FLAGS_LOCKED wasn't used). */
148 RTSPINLOCK hSpinlock;
149 /** The level one lookup table. */
150 void **papvLevel1;
151 /** The retainer callback. Can be NULL. */
152 PFNRTHANDLETABLERETAIN pfnRetain;
153 /** The user argument to the retainer. */
154 void *pvRetainUser;
155 /** The max number of handles. */
156 uint32_t cMax;
157 /** The number of handles currently allocated. (for optimizing destruction) */
158 uint32_t cCurAllocated;
159 /** The current number of 1st level entries. */
160 uint32_t cLevel1;
161 /** Head of the list of free handle entires (index). */
162 uint32_t iFreeHead;
163 /** Tail of the list of free handle entires (index). */
164 uint32_t iFreeTail;
165} RTHANDLETABLEINT;
166/** Pointer to an handle table structure. */
167typedef RTHANDLETABLEINT *PRTHANDLETABLEINT;
168
169
170/**
171 * Looks up a simple index.
172 *
173 * @returns Pointer to the handle table entry on success, NULL on failure.
174 * @param pThis The handle table structure.
175 * @param i The index to look up.
176 */
177DECLINLINE(PRTHTENTRY) rtHandleTableLookupSimpleIdx(PRTHANDLETABLEINT pThis, uint32_t i)
178{
179 if (i < pThis->cCur)
180 {
181 PRTHTENTRY paTable = (PRTHTENTRY)pThis->papvLevel1[i / RTHT_LEVEL2_ENTRIES];
182 if (paTable)
183 return &paTable[i % RTHT_LEVEL2_ENTRIES];
184 }
185 return NULL;
186}
187
188
189/**
190 * Looks up a simple handle.
191 *
192 * @returns Pointer to the handle table entry on success, NULL on failure.
193 * @param pThis The handle table structure.
194 * @param h The handle to look up.
195 */
196DECLINLINE(PRTHTENTRY) rtHandleTableLookupSimple(PRTHANDLETABLEINT pThis, uint32_t h)
197{
198 return rtHandleTableLookupSimpleIdx(pThis, h - pThis->uBase);
199}
200
201
202/**
203 * Looks up a context index.
204 *
205 * @returns Pointer to the handle table entry on success, NULL on failure.
206 * @param pThis The handle table structure.
207 * @param i The index to look up.
208 */
209DECLINLINE(PRTHTENTRYCTX) rtHandleTableLookupWithCtxIdx(PRTHANDLETABLEINT pThis, uint32_t i)
210{
211 if (i < pThis->cCur)
212 {
213 PRTHTENTRYCTX paTable = (PRTHTENTRYCTX)pThis->papvLevel1[i / RTHT_LEVEL2_ENTRIES];
214 if (paTable)
215 return &paTable[i % RTHT_LEVEL2_ENTRIES];
216 }
217 return NULL;
218}
219
220
221/**
222 * Looks up a context handle.
223 *
224 * @returns Pointer to the handle table entry on success, NULL on failure.
225 * @param pThis The handle table structure.
226 * @param h The handle to look up.
227 */
228DECLINLINE(PRTHTENTRYCTX) rtHandleTableLookupWithCtx(PRTHANDLETABLEINT pThis, uint32_t h)
229{
230 return rtHandleTableLookupWithCtxIdx(pThis, h - pThis->uBase);
231}
232
233
234/**
235 * Locks the handle table.
236 *
237 * @param pThis The handle table structure.
238 * @param pTmp The spinlock temp variable.
239 */
240DECLINLINE(void) rtHandleTableLock(PRTHANDLETABLEINT pThis, PRTSPINLOCKTMP pTmp)
241{
242 if (pThis->hSpinlock != NIL_RTSPINLOCK)
243 {
244 RTSPINLOCKTMP const Tmp = RTSPINLOCKTMP_INITIALIZER;
245 *pTmp = Tmp;
246 RTSpinlockAcquire(pThis->hSpinlock, pTmp);
247 }
248}
249
250
251/**
252 * Locks the handle table.
253 *
254 * @param pThis The handle table structure.
255 * @param pTmp The spinlock temp variable.
256 */
257DECLINLINE(void) rtHandleTableUnlock(PRTHANDLETABLEINT pThis, PRTSPINLOCKTMP pTmp)
258{
259 if (pThis->hSpinlock != NIL_RTSPINLOCK)
260 RTSpinlockRelease(pThis->hSpinlock, pTmp);
261}
262
263
264RTDECL(int) RTHandleTableCreateEx(PRTHANDLETABLE phHandleTable, uint32_t fFlags, uint32_t uBase, uint32_t cMax,
265 PFNRTHANDLETABLERETAIN pfnRetain, void *pvUser)
266{
267 /*
268 * Validate input.
269 */
270 AssertPtrReturn(phHandleTable, VERR_INVALID_POINTER);
271 *phHandleTable = NIL_RTHANDLETABLE;
272 AssertPtrNullReturn(pfnRetain, VERR_INVALID_POINTER);
273 AssertReturn(!(fFlags & ~RTHANDLETABLE_FLAGS_MASK), VERR_INVALID_PARAMETER);
274 AssertReturn(cMax > 0, VERR_INVALID_PARAMETER);
275 AssertReturn(UINT32_MAX - cMax >= uBase, VERR_INVALID_PARAMETER);
276
277 /*
278 * Adjust the cMax value so it is a multiple of the 2nd level tables.
279 */
280 if (cMax >= UINT32_MAX - RTHT_LEVEL2_ENTRIES)
281 cMax = UINT32_MAX - RTHT_LEVEL2_ENTRIES + 1;
282 cMax = ((cMax + RTHT_LEVEL2_ENTRIES - 1) / RTHT_LEVEL2_ENTRIES) * RTHT_LEVEL2_ENTRIES;
283
284 uint32_t const cLevel1 = cMax / RTHT_LEVEL2_ENTRIES;
285 Assert(cLevel1 * RTHT_LEVEL2_ENTRIES == cMax);
286
287 /*
288 * Allocate the structure, include the 1st level lookup table
289 * if it's below the threshold size.
290 */
291 size_t cb = sizeof(RTHANDLETABLEINT);
292 if (cLevel1 < RTHT_LEVEL1_DYN_ALLOC_THRESHOLD)
293 cb = RT_ALIGN(cb, sizeof(void *)) + cLevel1 * sizeof(void *);
294 PRTHANDLETABLEINT pThis = (PRTHANDLETABLEINT)RTMemAllocZ(cb);
295 if (!pThis)
296 return VERR_NO_MEMORY;
297
298 /*
299 * Initialize it.
300 */
301 pThis->u32Magic = RTHANDLETABLE_MAGIC;
302 pThis->fFlags = fFlags;
303 pThis->uBase = uBase;
304 pThis->cCur = 0;
305 pThis->hSpinlock = NIL_RTSPINLOCK;
306 if (cLevel1 < RTHT_LEVEL1_DYN_ALLOC_THRESHOLD)
307 pThis->papvLevel1 = (void **)((uint8_t *)pThis + RT_ALIGN(sizeof(*pThis), sizeof(void *)));
308 else
309 pThis->papvLevel1 = NULL;
310 pThis->pfnRetain = pfnRetain;
311 pThis->pvRetainUser = pvUser;
312 pThis->cMax = cMax;
313 pThis->cCurAllocated = 0;
314 pThis->cLevel1 = cLevel1 < RTHT_LEVEL1_DYN_ALLOC_THRESHOLD ? cLevel1 : 0;
315 pThis->iFreeHead = NIL_RTHT_INDEX;
316 pThis->iFreeTail = NIL_RTHT_INDEX;
317 if (fFlags & RTHANDLETABLE_FLAGS_LOCKED)
318 {
319 int rc = RTSpinlockCreate(&pThis->hSpinlock);
320 if (RT_FAILURE(rc))
321 {
322 RTMemFree(pThis);
323 return rc;
324 }
325 }
326
327 *phHandleTable = pThis;
328 return VINF_SUCCESS;
329}
330
331
332RTDECL(int) RTHandleTableCreate(PRTHANDLETABLE phHandleTable)
333{
334 return RTHandleTableCreateEx(phHandleTable, RTHANDLETABLE_FLAGS_LOCKED, 1, 65534, NULL, NULL);
335}
336
337
338RTDECL(int) RTHandleTableDestroy(RTHANDLETABLE hHandleTable, PFNRTHANDLETABLEDELETE pfnDelete, void *pvUser)
339{
340 /*
341 * Validate input, quitely ignore the NIL handle.
342 */
343 if (hHandleTable == NIL_RTHANDLETABLE)
344 return VINF_SUCCESS;
345 PRTHANDLETABLEINT pThis = (PRTHANDLETABLEINT)hHandleTable;
346 AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
347 AssertReturn(pThis->u32Magic == RTHANDLETABLE_MAGIC, VERR_INVALID_HANDLE);
348 AssertPtrNullReturn(pfnDelete, VERR_INVALID_POINTER);
349
350 /*
351 * Mark the thing as invalid / deleted.
352 * Then kill the lock.
353 */
354 RTSPINLOCKTMP Tmp;
355 rtHandleTableLock(pThis, &Tmp);
356 ASMAtomicWriteU32(&pThis->u32Magic, ~RTHANDLETABLE_MAGIC);
357 rtHandleTableUnlock(pThis, &Tmp);
358
359 if (pThis->hSpinlock != NIL_RTSPINLOCK)
360 {
361 rtHandleTableLock(pThis, &Tmp);
362 rtHandleTableUnlock(pThis, &Tmp);
363
364 RTSpinlockDestroy(pThis->hSpinlock);
365 pThis->hSpinlock = NIL_RTSPINLOCK;
366 }
367
368 if (pfnDelete)
369 {
370 /*
371 * Walk all the tables looking for used handles.
372 */
373 uint32_t cLeft = pThis->cCurAllocated;
374 if (pThis->fFlags & RTHANDLETABLE_FLAGS_CONTEXT)
375 {
376 for (uint32_t i1 = 0; cLeft > 0 && i1 < pThis->cLevel1; i1++)
377 {
378 PRTHTENTRYCTX paTable = (PRTHTENTRYCTX)pThis->papvLevel1[i1];
379 if (paTable)
380 for (uint32_t i = 0; i < RTHT_LEVEL2_ENTRIES; i++)
381 if (!RTHT_IS_FREE(paTable[i].pvObj))
382 {
383 pfnDelete(hHandleTable, pThis->uBase + i + i1 * RTHT_LEVEL2_ENTRIES,
384 paTable[i].pvObj, paTable[i].pvCtx, pvUser);
385 Assert(cLeft > 0);
386 cLeft--;
387 }
388 }
389 }
390 else
391 {
392 for (uint32_t i1 = 0; cLeft > 0 && i1 < pThis->cLevel1; i1++)
393 {
394 PRTHTENTRY paTable = (PRTHTENTRY)pThis->papvLevel1[i1];
395 if (paTable)
396 for (uint32_t i = 0; i < RTHT_LEVEL2_ENTRIES; i++)
397 if (!RTHT_IS_FREE(paTable[i].pvObj))
398 {
399 pfnDelete(hHandleTable, pThis->uBase + i + i1 * RTHT_LEVEL2_ENTRIES,
400 paTable[i].pvObj, NULL, pvUser);
401 Assert(cLeft > 0);
402 cLeft--;
403 }
404 }
405 }
406 Assert(!cLeft);
407 }
408
409 /*
410 * Free the memory.
411 */
412 for (uint32_t i1 = 0; i1 < pThis->cLevel1; i1++)
413 if (pThis->papvLevel1[i1])
414 {
415 RTMemFree(pThis->papvLevel1[i1]);
416 pThis->papvLevel1[i1] = NULL;
417 }
418
419 if (pThis->cMax / RTHT_LEVEL2_ENTRIES >= RTHT_LEVEL1_DYN_ALLOC_THRESHOLD)
420 RTMemFree(pThis->papvLevel1);
421
422 RTMemFree(pThis);
423
424 return VINF_SUCCESS;
425}
426
427
428/**
429 * Allocates a handle from the handle table.
430 *
431 * @returns IPRT status code, almost any.
432 * @retval VINF_SUCCESS on success.
433 * @retval VERR_NO_MEMORY if we failed to extend the handle table.
434 * @retval VERR_NO_MORE_HANDLES if we're out of handles.
435 *
436 * @param hHandleTable The handle to the handle table.
437 * @param pvObj The object to associate with the new handle.
438 * @param ph Where to return the handle on success.
439 *
440 * @remarks Do not call this if RTHANDLETABLE_FLAGS_CONTEXT was used during creation.
441 */
442RTDECL(int) RTHandleTableAlloc(RTHANDLETABLE hHandleTable, void *pvObj, uint32_t *ph);
443
444/**
445 * Looks up a handle.
446 *
447 * @returns The object pointer on success. NULL on failure.
448 *
449 * @param hHandleTable The handle to the handle table.
450 * @param h The handle to lookup.
451 *
452 * @remarks Do not call this if RTHANDLETABLE_FLAGS_CONTEXT was used during creation.
453 */
454RTDECL(void *) RTHandleTableLookup(RTHANDLETABLE hHandleTable, uint32_t h);
455
456/**
457 * Looks up and frees a handle.
458 *
459 * @returns The object pointer on success. NULL on failure.
460 *
461 * @param hHandleTable The handle to the handle table.
462 * @param h The handle to lookup.
463 *
464 * @remarks Do not call this if RTHANDLETABLE_FLAGS_CONTEXT was used during creation.
465 */
466RTDECL(void *) RTHandleTableFree(RTHANDLETABLE hHandleTable, uint32_t h);
467
468
469RTDECL(int) RTHandleTableAllocWithCtx(RTHANDLETABLE hHandleTable, void *pvObj, void *pvCtx, uint32_t *ph)
470{
471 /* validate the input */
472 PRTHANDLETABLEINT pThis = (PRTHANDLETABLEINT)hHandleTable;
473 AssertPtrReturn(pThis, VERR_INVALID_HANDLE);
474 AssertReturn(pThis->u32Magic == RTHANDLETABLE_MAGIC, VERR_INVALID_HANDLE);
475 AssertReturn(pThis->fFlags & RTHANDLETABLE_FLAGS_CONTEXT, VERR_INVALID_FUNCTION);
476 AssertReturn(!RTHT_IS_FREE(pvObj), VERR_INVALID_PARAMETER);
477 AssertPtrReturn(ph, VERR_INVALID_POINTER);
478 *ph = pThis->uBase - 1;
479
480 /*
481 * Allocation loop.
482 */
483 RTSPINLOCKTMP Tmp;
484 rtHandleTableLock(pThis, &Tmp);
485
486 int rc;
487 do
488 {
489 /*
490 * Try grab a free entry from the head of the free list.
491 */
492 uint32_t i = pThis->iFreeHead;
493 if (i != NIL_RTHT_INDEX)
494 {
495 PRTHTENTRYFREE pFree = (PRTHTENTRYFREE)rtHandleTableLookupWithCtxIdx(pThis, i);
496 Assert(pFree);
497 if (i == pThis->iFreeTail)
498 pThis->iFreeTail = pThis->iFreeHead = NIL_RTHT_INDEX;
499 else
500 pThis->iFreeHead = RTHT_GET_FREE_IDX(pFree);
501 pThis->cCurAllocated++;
502 Assert(pThis->cCurAllocated <= pThis->cCur);
503
504 /*
505 * Setup the entry and return.
506 */
507 PRTHTENTRYCTX pEntry = (PRTHTENTRYCTX)pFree;
508 pEntry->pvObj = pvObj;
509 pEntry->pvCtx = pvCtx;
510 *ph = i + pThis->uBase;
511 rc = VINF_SUCCESS;
512 }
513 /*
514 * Must expand the handle table, unless it's full.
515 */
516 else if (pThis->cCur >= pThis->cMax)
517 {
518 rc = VERR_NO_MORE_HANDLES;
519 Assert(pThis->cCur == pThis->cCurAllocated);
520 }
521 else
522 {
523 /*
524 * Do we have to expand the 1st level table too?
525 */
526 uint32_t const iLevel1 = pThis->cCur / RTHT_LEVEL2_ENTRIES;
527 uint32_t cLevel1 = iLevel1 >= pThis->cLevel1
528 ? pThis->cLevel1 + PAGE_SIZE / sizeof(void *)
529 : 0;
530 if (cLevel1 > pThis->cMax / RTHT_LEVEL2_ENTRIES)
531 cLevel1 = pThis->cMax / RTHT_LEVEL2_ENTRIES;
532 Assert(!cLevel1 || pThis->cMax / RTHT_LEVEL2_ENTRIES >= RTHT_LEVEL1_DYN_ALLOC_THRESHOLD);
533
534 /* leave the lock (never do fancy stuff from behind a spinlock). */
535 rtHandleTableUnlock(pThis, &Tmp);
536
537 /*
538 * Do the allocation(s).
539 */
540 rc = VERR_TRY_AGAIN;
541 void **papvLevel1 = NULL;
542 if (cLevel1)
543 {
544 papvLevel1 = (void **)RTMemAlloc(sizeof(void *) * cLevel1);
545 if (!papvLevel1)
546 return VERR_NO_MEMORY;
547 }
548
549 PRTHTENTRYCTX paTable = (PRTHTENTRYCTX)RTMemAlloc(sizeof(*paTable) * RTHT_LEVEL2_ENTRIES);
550 if (!paTable)
551 {
552 RTMemFree(papvLevel1);
553 return VERR_NO_MEMORY;
554 }
555
556 /* re-enter the lock. */
557 rtHandleTableLock(pThis, &Tmp);
558
559 /*
560 * Insert the new bits, but be a bit careful as someone might have
561 * raced us expanding the table.
562 */
563 /* deal with the 1st level lookup expansion first */
564 if (cLevel1)
565 {
566 Assert(papvLevel1);
567 if (cLevel1 > pThis->cLevel1)
568 {
569 /* Replace the 1st level table. */
570 memcpy(papvLevel1, pThis->papvLevel1, sizeof(void *) * pThis->cLevel1);
571 memset(&papvLevel1[pThis->cLevel1], 0, sizeof(void *) * (cLevel1 - pThis->cLevel1));
572 pThis->cLevel1 = cLevel1;
573 void **papvTmp = pThis->papvLevel1;
574 pThis->papvLevel1 = papvLevel1;
575 papvLevel1 = papvTmp;
576 }
577
578 /* free the obsolete one (outside the lock of course) */
579 rtHandleTableUnlock(pThis, &Tmp);
580 RTMemFree(papvLevel1);
581 rtHandleTableLock(pThis, &Tmp);
582 }
583
584 /* insert the table we allocated */
585 if (pThis->cCur < pThis->cMax)
586 {
587 uint32_t iLevel1New = pThis->cCur / RTHT_LEVEL2_ENTRIES;
588 pThis->papvLevel1[iLevel1New] = paTable;
589
590 /* link all entries into a free list. */
591 Assert(!(pThis->cCur % RTHT_LEVEL2_ENTRIES));
592 for (uint32_t i = 0; i < RTHT_LEVEL2_ENTRIES - 1; i++)
593 {
594 RTHT_SET_FREE_IDX((PRTHTENTRYFREE)&paTable[i], i + 1 + pThis->cCur);
595 paTable[i].pvCtx = (void *)~(uintptr_t)7;
596 }
597 RTHT_SET_FREE_IDX((PRTHTENTRYFREE)&paTable[RTHT_LEVEL2_ENTRIES - 1], NIL_RTHT_INDEX);
598 paTable[RTHT_LEVEL2_ENTRIES - 1].pvCtx = (void *)~(uintptr_t)7;
599
600 /* join the free list with the other. */
601 if (pThis->iFreeTail == NIL_RTHT_INDEX)
602 pThis->iFreeHead = pThis->cCur;
603 else
604 {
605 PRTHTENTRYFREE pPrev = (PRTHTENTRYFREE)rtHandleTableLookupWithCtxIdx(pThis, pThis->iFreeTail);
606 Assert(pPrev);
607 RTHT_SET_FREE_IDX(pPrev, pThis->cCur);
608 }
609 pThis->iFreeTail = pThis->cCur + RTHT_LEVEL2_ENTRIES - 1;
610
611 pThis->cCur += RTHT_LEVEL2_ENTRIES;
612 }
613 else
614 {
615 /* free the table (raced someone, and we lost). */
616 rtHandleTableUnlock(pThis, &Tmp);
617 RTMemFree(paTable);
618 rtHandleTableLock(pThis, &Tmp);
619 }
620
621 rc = VERR_TRY_AGAIN;
622 }
623 } while (rc == VERR_TRY_AGAIN);
624
625 rtHandleTableUnlock(pThis, &Tmp);
626
627 return rc;
628}
629
630
631RTDECL(void *) RTHandleTableLookupWithCtx(RTHANDLETABLE hHandleTable, uint32_t h, void *pvCtx)
632{
633 /* validate the input */
634 PRTHANDLETABLEINT pThis = (PRTHANDLETABLEINT)hHandleTable;
635 AssertPtrReturn(pThis, NULL);
636 AssertReturn(pThis->u32Magic == RTHANDLETABLE_MAGIC, NULL);
637 AssertReturn(pThis->fFlags & RTHANDLETABLE_FLAGS_CONTEXT, NULL);
638
639 void *pvObj = NULL;
640
641 /* acquire the lock */
642 RTSPINLOCKTMP Tmp;
643 rtHandleTableLock(pThis, &Tmp);
644
645 /*
646 * Perform the lookup and retaining.
647 */
648 PRTHTENTRYCTX pEntry = rtHandleTableLookupWithCtx(pThis, h);
649 if (pEntry && pEntry->pvCtx == pvCtx)
650 {
651 pvObj = pEntry->pvObj;
652 if (!RTHT_IS_FREE(pvObj))
653 {
654 if (pThis->pfnRetain)
655 {
656 int rc = pThis->pfnRetain(hHandleTable, pEntry->pvObj, pvCtx, pThis->pvRetainUser);
657 if (RT_FAILURE(rc))
658 pvObj = NULL;
659 }
660 }
661 else
662 pvObj = NULL;
663 }
664
665 /* release the lock */
666 rtHandleTableUnlock(pThis, &Tmp);
667 return pvObj;
668}
669
670
671RTDECL(void *) RTHandleTableFreeWithCtx(RTHANDLETABLE hHandleTable, uint32_t h, void *pvCtx)
672{
673 /* validate the input */
674 PRTHANDLETABLEINT pThis = (PRTHANDLETABLEINT)hHandleTable;
675 AssertPtrReturn(pThis, NULL);
676 AssertReturn(pThis->u32Magic == RTHANDLETABLE_MAGIC, NULL);
677 AssertReturn(pThis->fFlags & RTHANDLETABLE_FLAGS_CONTEXT, NULL);
678
679 void *pvObj = NULL;
680
681 /* acquire the lock */
682 RTSPINLOCKTMP Tmp;
683 rtHandleTableLock(pThis, &Tmp);
684
685 /*
686 * Perform the lookup and retaining.
687 */
688 PRTHTENTRYCTX pEntry = rtHandleTableLookupWithCtx(pThis, h);
689 if (pEntry && pEntry->pvCtx == pvCtx)
690 {
691 pvObj = pEntry->pvObj;
692 if (!RTHT_IS_FREE(pvObj))
693 {
694 if (pThis->pfnRetain)
695 {
696 int rc = pThis->pfnRetain(hHandleTable, pEntry->pvObj, pvCtx, pThis->pvRetainUser);
697 if (RT_FAILURE(rc))
698 pvObj = NULL;
699 }
700
701 /*
702 * Link it into the free list.
703 */
704 if (pvObj)
705 {
706 pEntry->pvCtx = (void *)~(uintptr_t)7;
707
708 PRTHTENTRYFREE pFree = (PRTHTENTRYFREE)pEntry;
709 RTHT_SET_FREE_IDX(pFree, NIL_RTHT_INDEX);
710
711 uint32_t const i = h - pThis->uBase;
712 if (pThis->iFreeTail == NIL_RTHT_INDEX)
713 pThis->iFreeHead = pThis->iFreeTail = i;
714 else
715 {
716 PRTHTENTRYFREE pPrev = (PRTHTENTRYFREE)rtHandleTableLookupWithCtxIdx(pThis, pThis->iFreeTail);
717 Assert(pPrev);
718 RTHT_SET_FREE_IDX(pPrev, i);
719 pThis->iFreeTail = i;
720 }
721
722 Assert(pThis->cCurAllocated > 0);
723 pThis->cCurAllocated--;
724 }
725 }
726 else
727 pvObj = NULL;
728 }
729
730 /* release the lock */
731 rtHandleTableUnlock(pThis, &Tmp);
732 return pvObj;
733}
734
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette