[4256] | 1 | /** @file
|
---|
[8245] | 2 | * IPRT - Abstract Table/Trees.
|
---|
[4256] | 3 | */
|
---|
| 4 |
|
---|
| 5 | /*
|
---|
[98103] | 6 | * Copyright (C) 2006-2023 Oracle and/or its affiliates.
|
---|
[4071] | 7 | *
|
---|
[96407] | 8 | * This file is part of VirtualBox base platform packages, as
|
---|
| 9 | * available from https://www.virtualbox.org.
|
---|
[5999] | 10 | *
|
---|
[96407] | 11 | * This program is free software; you can redistribute it and/or
|
---|
| 12 | * modify it under the terms of the GNU General Public License
|
---|
| 13 | * as published by the Free Software Foundation, in version 3 of the
|
---|
| 14 | * License.
|
---|
| 15 | *
|
---|
| 16 | * This program is distributed in the hope that it will be useful, but
|
---|
| 17 | * WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
| 18 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
---|
| 19 | * General Public License for more details.
|
---|
| 20 | *
|
---|
| 21 | * You should have received a copy of the GNU General Public License
|
---|
| 22 | * along with this program; if not, see <https://www.gnu.org/licenses>.
|
---|
| 23 | *
|
---|
[5999] | 24 | * The contents of this file may alternatively be used under the terms
|
---|
| 25 | * of the Common Development and Distribution License Version 1.0
|
---|
[96407] | 26 | * (CDDL), a copy of it is provided in the "COPYING.CDDL" file included
|
---|
| 27 | * in the VirtualBox distribution, in which case the provisions of the
|
---|
[5999] | 28 | * CDDL are applicable instead of those of the GPL.
|
---|
| 29 | *
|
---|
| 30 | * You may elect to license modified versions of this file under the
|
---|
| 31 | * terms and conditions of either the GPL or the CDDL or both.
|
---|
[96407] | 32 | *
|
---|
| 33 | * SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0
|
---|
[4256] | 34 | */
|
---|
| 35 |
|
---|
[76557] | 36 | #ifndef IPRT_INCLUDED_table_h
|
---|
| 37 | #define IPRT_INCLUDED_table_h
|
---|
[76507] | 38 | #ifndef RT_WITHOUT_PRAGMA_ONCE
|
---|
| 39 | # pragma once
|
---|
| 40 | #endif
|
---|
[4256] | 41 |
|
---|
| 42 | #include <iprt/types.h>
|
---|
| 43 |
|
---|
| 44 | /** @defgroup grp_rt_tab RTTab - Generic Tree and Table Interface.
|
---|
| 45 | * @ingroup grp_rt
|
---|
| 46 | * @{
|
---|
| 47 | */
|
---|
| 48 |
|
---|
[20374] | 49 | RT_C_DECLS_BEGIN
|
---|
[4256] | 50 |
|
---|
| 51 | /** Pointer to an allocator. */
|
---|
| 52 | typedef struct RTTABALLOCATOR *PRTTABALLOCATOR;
|
---|
| 53 |
|
---|
| 54 | /**
|
---|
| 55 | * Allocates memory.
|
---|
| 56 | *
|
---|
| 57 | * @returns Pointer to the allocated memory.
|
---|
| 58 | * @returns NULL on failure. (don't throw!)
|
---|
| 59 | * @param pAllocator The allocator structure.
|
---|
| 60 | * @param cb The number of bytes to allocate. (Never 0.)
|
---|
| 61 | */
|
---|
[85121] | 62 | typedef DECLCALLBACKTYPE(void *, FNRTTABALLOC,(PRTTABALLOCATOR pAllocator, size_t cb));
|
---|
[4256] | 63 | /** Pointer to a FNRTTABALLOC() function. */
|
---|
| 64 | typedef FNRTTABALLOC *PFNRTTABALLOC;
|
---|
| 65 |
|
---|
| 66 | /**
|
---|
| 67 | * Frees memory.
|
---|
| 68 | *
|
---|
| 69 | * @param pAllocator The allocator structure.
|
---|
| 70 | * @param pv The memory to free. (can be NULL)
|
---|
| 71 | */
|
---|
[85121] | 72 | typedef DECLCALLBACKTYPE(void *, FNRTTABFREE,(PRTTABALLOCATOR pAllocator, void *pv));
|
---|
[4256] | 73 | /** Pointer to a FNRTTABFREE() function. */
|
---|
| 74 | typedef FNRTTABFREE *PFNRTTABFREE;
|
---|
| 75 |
|
---|
| 76 | /**
|
---|
| 77 | * The allocator structure.
|
---|
| 78 | * (Hint: use this as like 'base class' for your custom allocators.)
|
---|
| 79 | */
|
---|
| 80 | typedef struct RTTABALLOCATOR
|
---|
| 81 | {
|
---|
| 82 | /** The allocation function. */
|
---|
| 83 | PFNRTTABALLOC pfnAlloc;
|
---|
| 84 | /** The free function. */
|
---|
| 85 | PFNRTTABFREE pfnFree;
|
---|
| 86 | } RTTABALLOCATOR;
|
---|
| 87 |
|
---|
| 88 | /**
|
---|
| 89 | * Gets the default allocator.
|
---|
| 90 | *
|
---|
| 91 | * @returns Pointer to the default allocator.
|
---|
| 92 | */
|
---|
| 93 | RTDECL(RTTABALLOCATOR) RTTabDefaultAllocator(void);
|
---|
| 94 |
|
---|
| 95 |
|
---|
| 96 | /**
|
---|
| 97 | * Compares two table items.
|
---|
| 98 | *
|
---|
| 99 | * @returns 0 if equal
|
---|
| 100 | * @returns <0 if pvItem1 is less than pvItem2 (pvItem2 is then greater than pvItem1).
|
---|
| 101 | * @returns >0 if pvItem1 is less than pvItem2 (pvItem1 is then greater than pvItem2).
|
---|
| 102 | *
|
---|
| 103 | * @param pvItem1 The first item.
|
---|
| 104 | * @param pvItem2 The second item.
|
---|
| 105 | * @param pvUser The user argument.
|
---|
| 106 | */
|
---|
[85121] | 107 | typedef DECLCALLBACKTYPE(int, FNRTTABCOMP,(const void *pvItem1, const void *pvItem2, void *pvUser));
|
---|
[4256] | 108 | /** Pointer to a FNRTTABCOMP() function. */
|
---|
| 109 | typedef FNRTTABCOMP *PFNRTTABCOMP;
|
---|
| 110 |
|
---|
| 111 | /**
|
---|
| 112 | * Duplicates a table item.
|
---|
| 113 | * This is used when duplicating or copying a table.
|
---|
| 114 | *
|
---|
| 115 | * @returns Pointer to the copy.
|
---|
| 116 | * @returns NULL on failure.
|
---|
| 117 | *
|
---|
| 118 | * @param pvItem The item to copy.
|
---|
| 119 | * @param pvUser The user argument.
|
---|
| 120 | */
|
---|
[85121] | 121 | typedef DECLCALLBACKTYPE(void *, FNRTTABDUPLICATE,(const void *pvItem, void *pvUser));
|
---|
[4256] | 122 | /** Pointer to a FNRTTABDUPLICATE() function. */
|
---|
| 123 | typedef FNRTTABDUPLICATE *PFNRTTABDUPLICATE;
|
---|
| 124 |
|
---|
| 125 | /**
|
---|
| 126 | * Callback function for doing something with an item.
|
---|
| 127 | *
|
---|
| 128 | * What exactly we're doing is specific to the context of the call.
|
---|
| 129 | *
|
---|
| 130 | * @param pvItem The item.
|
---|
| 131 | * @param pvUser The user argument.
|
---|
| 132 | */
|
---|
[85121] | 133 | typedef DECLCALLBACKTYPE(void, FNRTTABCALLBACK,(const void *pvItem, void *pvUser));
|
---|
[4256] | 134 | /** Pointer to a FNRTTABCALLBACK() function. */
|
---|
| 135 | typedef FNRTTABCALLBACK *PFNRTTABCALLBACK;
|
---|
| 136 |
|
---|
| 137 |
|
---|
| 138 | /** Pointer to const table operations. */
|
---|
| 139 | typedef const struct RTTABOPS *PCRTTABOPS;
|
---|
| 140 | /** Pointer to a table. */
|
---|
| 141 | typedef struct RTTAB *PRTTAB;
|
---|
| 142 | /** Pointer to a const table. */
|
---|
| 143 | typedef const struct RTTAB *PCRTTAB;
|
---|
| 144 | /** Pointer to a traverser. */
|
---|
| 145 | typedef struct RTTABTRAVERSER *PRTTABTRAVERSER;
|
---|
| 146 | /** Pointer to a const traverser. */
|
---|
| 147 | typedef const struct RTTABTRAVERSER *PCRTTABTRAVERSER;
|
---|
| 148 | /** Pointer to a traverser core. */
|
---|
| 149 | typedef struct RTTABTRAVERSERCORE *PRTTABTRAVERSERCORE;
|
---|
| 150 | /** Pointer to a const traverser core. */
|
---|
| 151 | typedef const struct RTTABTRAVERSERCORE *PCRTTABTRAVERSERCORE;
|
---|
| 152 |
|
---|
| 153 |
|
---|
| 154 | /**
|
---|
| 155 | * Table operations.
|
---|
| 156 | */
|
---|
| 157 | typedef struct RTTABOPS
|
---|
| 158 | {
|
---|
| 159 | /**
|
---|
| 160 | * Create a table.
|
---|
| 161 | *
|
---|
| 162 | * @returns Pointer to the new table.
|
---|
| 163 | * @returns NULL if we're out of memory or some other resource.
|
---|
| 164 | * @param pOps The table operations.
|
---|
| 165 | * @param fCreateFlags The table type specific creation flags.
|
---|
| 166 | * @param pAllocator Custom allocator. Pass NULL for the default allocator.
|
---|
| 167 | * @param pfnComp The comparision function.
|
---|
| 168 | */
|
---|
[85121] | 169 | DECLCALLBACKMEMBER(PRTTAB, pfnCreate,(PCRTTABOPS pOps, unsigned fCreateFlags, PRTTABALLOCATOR pAllocator, PFNRTTABCOMP pfnComp));
|
---|
[4256] | 170 |
|
---|
| 171 | /**
|
---|
| 172 | * Duplicates a table to a table of the same type.
|
---|
| 173 | *
|
---|
| 174 | * @returns Pointer to the new table.
|
---|
| 175 | * @returns NULL if we're out of memory or some other resource.
|
---|
| 176 | * @param pTab The table to duplicate.
|
---|
| 177 | * @param pfnDuplicate Pointer to the item duplication function. If NULL the new table will
|
---|
| 178 | * be referencing the same data as the old one.
|
---|
| 179 | * @param pfnNewCB Callback which is called for all the items in the new table. Optional.
|
---|
| 180 | * @param pAllocator Custom allocator. Pass NULL to use the same allocator as pTab.
|
---|
| 181 | */
|
---|
[85121] | 182 | DECLCALLBACKMEMBER(PRTTAB, pfnDuplicate,(PCRTTAB pTab, PFNRTTABDUPLICATE pfnDuplicate, PFNRTTABCALLBACK pfnNewCB, PRTTABALLOCATOR pAllocator));
|
---|
[4256] | 183 |
|
---|
| 184 | /**
|
---|
| 185 | * Destroys a table.
|
---|
| 186 | *
|
---|
| 187 | * @param pTab The table to destroy.
|
---|
| 188 | */
|
---|
[85121] | 189 | DECLCALLBACKMEMBER(void, pfnDestroy,(PRTTAB pTab));
|
---|
[4256] | 190 |
|
---|
| 191 | /**
|
---|
| 192 | * Inserts an item into the table, if a matching item is encountered
|
---|
| 193 | * the pointer to the pointer to it will be returned.
|
---|
| 194 | *
|
---|
| 195 | * @returns Pointer to the item pointer in the table.
|
---|
| 196 | * This can be used to replace existing items (don't break anything, dude).
|
---|
| 197 | * @returns NULL if we failed to allocate memory for the new node.
|
---|
| 198 | * @param pTab The table.
|
---|
| 199 | * @param pvItem The item which will be inserted if an matching item was not found in the table.
|
---|
| 200 | */
|
---|
[85121] | 201 | DECLCALLBACKMEMBER(void **, pfnProbe,(PRTTAB pTab, void *pvItem));
|
---|
[4256] | 202 |
|
---|
| 203 | /**
|
---|
| 204 | * Inserts an item into the table, fail if a matching item exists.
|
---|
| 205 | *
|
---|
| 206 | * @returns NULL on success and allocation failure.
|
---|
| 207 | * @returns Pointer to the matching item.
|
---|
| 208 | * @param pTab The table.
|
---|
| 209 | * @param pvItem The item which is to be inserted.
|
---|
| 210 | */
|
---|
[85121] | 211 | DECLCALLBACKMEMBER(void *, pfnInsert,(PRTTAB pTab, void *pvItem));
|
---|
[4256] | 212 |
|
---|
| 213 | /**
|
---|
| 214 | * Inserts an item into the table, if a matching item is encountered
|
---|
| 215 | * it will be replaced and returned.
|
---|
| 216 | *
|
---|
| 217 | * @returns NULL if inserted and allocation failure.
|
---|
| 218 | * @returns Pointer to the replaced item.
|
---|
| 219 | * @param pTab The table.
|
---|
| 220 | * @param pvItem The item which is to be inserted.
|
---|
| 221 | */
|
---|
[85121] | 222 | DECLCALLBACKMEMBER(void *, pfnReplace,(PRTTAB pTab, void *pvItem));
|
---|
[4256] | 223 |
|
---|
| 224 | /**
|
---|
| 225 | * Removes an item from the table if found.
|
---|
| 226 | *
|
---|
| 227 | * @returns Pointer to the removed item.
|
---|
| 228 | * @returns NULL if no item matched pvItem.
|
---|
| 229 | * @param pTab The table.
|
---|
| 230 | * @param pvItem The item which is to be inserted.
|
---|
| 231 | */
|
---|
[85121] | 232 | DECLCALLBACKMEMBER(void *, pfnRemove,(PRTTAB pTab, const void *pvItem));
|
---|
[4256] | 233 |
|
---|
| 234 | /**
|
---|
| 235 | * Finds an item in the table.
|
---|
| 236 | *
|
---|
| 237 | * @returns Pointer to the item it found.
|
---|
| 238 | * @returns NULL if no item matched pvItem.
|
---|
| 239 | * @param pTab The table.
|
---|
| 240 | * @param pvItem The item which is to be inserted.
|
---|
| 241 | */
|
---|
[85121] | 242 | DECLCALLBACKMEMBER(void *, pfnFind,(PRTTAB pTab, const void *pvItem));
|
---|
[4256] | 243 |
|
---|
| 244 | /**
|
---|
| 245 | * Initializes a traverser to the NULL item.
|
---|
| 246 | *
|
---|
| 247 | * The NULL item is an imaginary table item before the first and after
|
---|
| 248 | * the last items in the table.
|
---|
| 249 | *
|
---|
| 250 | * @returns Pointer to the traverser positioned at the NULL item.
|
---|
| 251 | * @returns NULL on failure to allocate the traverser.
|
---|
| 252 | *
|
---|
| 253 | * @param pTab The table.
|
---|
| 254 | * @param pTravNew Pointer to a preallocated structure. Optional.
|
---|
| 255 | */
|
---|
[85121] | 256 | DECLCALLBACKMEMBER(PRTTABTRAVERSERCORE, pfnTravInit,(PRTTAB pTab, PRTTABTRAVERSER pTravNew));
|
---|
[4256] | 257 |
|
---|
| 258 | /**
|
---|
| 259 | * Initializes a traverser to the first item in the table.
|
---|
| 260 | *
|
---|
| 261 | * If the table is empty, the traverser will be positioned at the NULL item
|
---|
| 262 | * like with RTTabTravInit().
|
---|
| 263 | *
|
---|
| 264 | * @returns Pointer to the traverser positioned at the first item or NULL item.
|
---|
| 265 | * @returns NULL on failure to allocate the traverser.
|
---|
| 266 | *
|
---|
| 267 | * @param pTab The table.
|
---|
| 268 | * @param pTravNew Pointer to a preallocated structure. Optional.
|
---|
| 269 | */
|
---|
[85121] | 270 | DECLCALLBACKMEMBER(PRTTABTRAVERSERCORE, pfnTravFirst,(PRTTAB pTab, PRTTABTRAVERSER pTravNew));
|
---|
[4256] | 271 |
|
---|
| 272 | /**
|
---|
| 273 | * Initializes a traverser to the last item in the table.
|
---|
| 274 | *
|
---|
| 275 | * If the table is empty, the traverser will be positioned at the NULL item
|
---|
| 276 | * like with RTTabTravInit().
|
---|
| 277 | *
|
---|
| 278 | * @returns Pointer to the traverser positioned at the last item or NULL item.
|
---|
| 279 | * @returns NULL on failure to allocate the traverser.
|
---|
| 280 | *
|
---|
| 281 | * @param pTab The table.
|
---|
| 282 | * @param pTravNew Pointer to a preallocated structure. Optional.
|
---|
| 283 | */
|
---|
[85121] | 284 | DECLCALLBACKMEMBER(PRTTABTRAVERSERCORE, pfnTravLast,(PRTTAB pTab, PRTTABTRAVERSER pTravNew));
|
---|
[4256] | 285 |
|
---|
| 286 | /**
|
---|
| 287 | * Initializes a traverser to an item matching the given one.
|
---|
| 288 | *
|
---|
| 289 | * If the item isn't found, the traverser will be positioned at the NULL item
|
---|
| 290 | * like with RTTabTravInit().
|
---|
| 291 | *
|
---|
| 292 | * @returns Pointer to the traverser positioned at the matching item or NULL item.
|
---|
| 293 | * @returns NULL on failure to allocate the traverser.
|
---|
| 294 | *
|
---|
| 295 | * @param pTab The table.
|
---|
| 296 | * @param pTravNew Pointer to a preallocated structure. Optional.
|
---|
| 297 | * @param pvItem The item to find the match to.
|
---|
| 298 | */
|
---|
[85121] | 299 | DECLCALLBACKMEMBER(PRTTABTRAVERSERCORE, pfnTravFind,(PRTTAB pTab, PRTTABTRAVERSER pTravNew, const void *pvItem));
|
---|
[4256] | 300 |
|
---|
| 301 | /**
|
---|
| 302 | * Initializes a traverser to the inserted item.
|
---|
| 303 | *
|
---|
| 304 | * If there already exists an item in the tree matching pvItem, the traverser
|
---|
| 305 | * is positioned at that item like with RTTabTravFind().
|
---|
| 306 | *
|
---|
| 307 | * If the insert operation failes because of an out of memory condition, the
|
---|
| 308 | * traverser will be positioned at the NULL item like with RTTabTravInit().
|
---|
| 309 | *
|
---|
| 310 | * @returns Pointer to the traverser positioned at the inserted, existing or NULL item.
|
---|
| 311 | * @returns NULL on failure to allocate the traverser.
|
---|
| 312 | *
|
---|
| 313 | * @param pTab The table.
|
---|
| 314 | * @param pTravNew Pointer to a preallocated structure. Optional.
|
---|
| 315 | * @param pvItem The item to be inserted.
|
---|
| 316 | */
|
---|
[85121] | 317 | DECLCALLBACKMEMBER(PRTTABTRAVERSERCORE, pfnTravInsert,(PRTTAB pTab, PRTTABTRAVERSER pTravNew, void *pvItem));
|
---|
[4256] | 318 |
|
---|
| 319 | /**
|
---|
| 320 | * Duplicates a traverser.
|
---|
| 321 | *
|
---|
| 322 | * @returns The pointer to the duplicate.
|
---|
| 323 | * @returns NULL on allocation failure.
|
---|
| 324 | *
|
---|
| 325 | * @param pTrav The traverser to duplicate.
|
---|
| 326 | * @param pTravNew Pointer to a preallocated structure. Optional.
|
---|
| 327 | */
|
---|
[85121] | 328 | DECLCALLBACKMEMBER(PRTTABTRAVERSERCORE, pfnTravDuplicate,(PRTTABTRAVERSERCORE pTrav, PCRTTABTRAVERSER pTravNew));
|
---|
[4256] | 329 |
|
---|
| 330 | /**
|
---|
| 331 | * Frees a traverser.
|
---|
| 332 | *
|
---|
| 333 | * This can safely be called even if the traverser structure
|
---|
| 334 | * wasn't dynamically allocated or the constructor failed.
|
---|
| 335 | *
|
---|
| 336 | * @param pTrav The traverser which is to be free.
|
---|
| 337 | */
|
---|
[85121] | 338 | DECLCALLBACKMEMBER(void, pfnTravFree,(PRTTABTRAVERSERCORE pTrav));
|
---|
[4256] | 339 |
|
---|
| 340 | /**
|
---|
| 341 | * Gets the current item.
|
---|
| 342 | *
|
---|
| 343 | * @returns The current item. (NULL indicates the imaginary NULL item.)
|
---|
| 344 | * @param pTrav The traverser.
|
---|
| 345 | */
|
---|
[85121] | 346 | DECLCALLBACKMEMBER(void *, pfnTravCur,(PCRTTABTRAVERSERCORE pTrav));
|
---|
[4256] | 347 |
|
---|
| 348 | /**
|
---|
| 349 | * Advances to the next item.
|
---|
| 350 | *
|
---|
| 351 | * @returns The new current item. (NULL indicates the imaginary NULL item.)
|
---|
| 352 | * @param pTrav The traverser.
|
---|
| 353 | */
|
---|
[85121] | 354 | DECLCALLBACKMEMBER(void *, pfnTravNext,(PRTTABTRAVERSERCORE pTrav));
|
---|
[4256] | 355 |
|
---|
| 356 | /**
|
---|
| 357 | * Advances to the previous item.
|
---|
| 358 | *
|
---|
| 359 | * @returns The new current item. (NULL indicates the imaginary NULL item.)
|
---|
| 360 | * @param pTrav The traverser.
|
---|
| 361 | */
|
---|
[85121] | 362 | DECLCALLBACKMEMBER(void *, pfnTravPrev,(PRTTABTRAVERSERCORE pTrav));
|
---|
[4256] | 363 |
|
---|
| 364 | /**
|
---|
| 365 | * Replaces the current item.
|
---|
| 366 | *
|
---|
| 367 | * This has the same restrictions as RTTabProbe(), e.g. it's not permitted to
|
---|
| 368 | * break the order of the table.
|
---|
| 369 | *
|
---|
| 370 | * @returns The replaced item.
|
---|
| 371 | * @returns NULL if the current item is the NULL item. The traverser
|
---|
| 372 | * and table remains unchanged.
|
---|
| 373 | * @param pTrav The traverser.
|
---|
| 374 | * @param pvItem The item to be inserted.
|
---|
| 375 | */
|
---|
[85121] | 376 | DECLCALLBACKMEMBER(void *, pfnTravReplace,(PRTTABTRAVERSERCORE pTrav, void *pvItem));
|
---|
[4256] | 377 |
|
---|
| 378 | /** The type of table type. */
|
---|
| 379 | const char *pszType;
|
---|
| 380 | } RTTABOPS;
|
---|
| 381 |
|
---|
| 382 | /**
|
---|
| 383 | * A table.
|
---|
| 384 | */
|
---|
| 385 | typedef struct RTTAB
|
---|
| 386 | {
|
---|
| 387 | /** The table operations. */
|
---|
| 388 | PCRTTABOPS pOps;
|
---|
| 389 | /** The function for comparing table items. */
|
---|
| 390 | PFNRTTABCOMP pfnComp;
|
---|
| 391 | /** The number of items in the table. */
|
---|
| 392 | RTUINT cItems;
|
---|
| 393 | /** The table generation number.
|
---|
| 394 | * This must be updated whenever the table changes. */
|
---|
| 395 | RTUINT idGeneration;
|
---|
| 396 | } RTTAB;
|
---|
| 397 |
|
---|
| 398 |
|
---|
| 399 | /**
|
---|
| 400 | * Create a table.
|
---|
| 401 | *
|
---|
| 402 | * @returns Pointer to the new table.
|
---|
| 403 | * @returns NULL if we're out of memory or some other resource.
|
---|
| 404 | * @param pOps The table operations.
|
---|
| 405 | * @param fCreateFlags The table type specific creation flags.
|
---|
| 406 | * @param pAllocator Custom allocator. Pass NULL for the default allocator.
|
---|
| 407 | * @param pfnComp The comparision function.
|
---|
| 408 | */
|
---|
| 409 | DECLINLINE(PRTTAB) RTTabCreate(PCRTTABOPS pOps, unsigned fCreateFlags, PRTTABALLOCATOR pAllocator, PFNRTTABCOMP pfnComp)
|
---|
| 410 | {
|
---|
| 411 | return pOps->pfnCreate(pOps, fCreateFlags, pAllocator, pfnComp);
|
---|
| 412 | }
|
---|
| 413 |
|
---|
| 414 | /**
|
---|
| 415 | * Duplicates a table to a table of the same type.
|
---|
| 416 | *
|
---|
| 417 | * @returns Pointer to the new table.
|
---|
| 418 | * @returns NULL if we're out of memory or some other resource.
|
---|
| 419 | * @param pTab The table to duplicate.
|
---|
| 420 | * @param pfnDuplicate Pointer to the item duplication function. If NULL the new table will
|
---|
| 421 | * be referencing the same data as the old one.
|
---|
| 422 | * @param pfnNewCB Callback which is called for all the items in the new table. Optional.
|
---|
| 423 | * @param pAllocator Custom allocator. Pass NULL to use the same allocator as pTab.
|
---|
| 424 | */
|
---|
| 425 | DECLINLINE(PRTTAB) RTTabDuplicate(PCRTTAB pTab, PFNRTTABDUPLICATE pfnDuplicate, PFNRTTABCALLBACK pfnNewCB, PRTTABALLOCATOR pAllocator)
|
---|
| 426 | {
|
---|
| 427 | return pTab->pOps->pfnDuplicate(pTab, pfnDuplicate, pfnNewCB, pAllocator);
|
---|
| 428 | }
|
---|
| 429 |
|
---|
| 430 | /**
|
---|
| 431 | * Destroys a table.
|
---|
| 432 | *
|
---|
| 433 | * @param pTab The table to destroy.
|
---|
| 434 | */
|
---|
| 435 | DECLINLINE(void) RTTabDestroy(PRTTAB pTab)
|
---|
| 436 | {
|
---|
[30788] | 437 | pTab->pOps->pfnDestroy(pTab);
|
---|
[4256] | 438 | }
|
---|
| 439 |
|
---|
| 440 | /**
|
---|
| 441 | * Count the item in the table.
|
---|
| 442 | *
|
---|
| 443 | * @returns Number of items in the table.
|
---|
| 444 | * @param pTab The table to count.
|
---|
| 445 | */
|
---|
| 446 | DECLINLINE(RTUINT) RTTabCount(PRTTAB pTab)
|
---|
| 447 | {
|
---|
| 448 | return pTab->cItems;
|
---|
| 449 | }
|
---|
| 450 |
|
---|
| 451 | /**
|
---|
| 452 | * Inserts an item into the table, if a matching item is encountered
|
---|
| 453 | * the pointer to the pointer to it will be returned.
|
---|
| 454 | *
|
---|
| 455 | * @returns Pointer to the item pointer in the table.
|
---|
| 456 | * This can be used to replace existing items (don't break anything, dude).
|
---|
| 457 | * @returns NULL if we failed to allocate memory for the new node.
|
---|
| 458 | * @param pTab The table.
|
---|
| 459 | * @param pvItem The item which will be inserted if an matching item was not found in the table.
|
---|
| 460 | */
|
---|
| 461 | DECLINLINE(void **) RTTabProbe(PRTTAB pTab, void *pvItem)
|
---|
| 462 | {
|
---|
| 463 | return pTab->pOps->pfnProbe(pTab, pvItem);
|
---|
| 464 | }
|
---|
| 465 |
|
---|
| 466 | /**
|
---|
| 467 | * Inserts an item into the table, fail if a matching item exists.
|
---|
| 468 | *
|
---|
| 469 | * @returns NULL on success and allocation failure.
|
---|
| 470 | * @returns Pointer to the matching item.
|
---|
| 471 | * @param pTab The table.
|
---|
| 472 | * @param pvItem The item which is to be inserted.
|
---|
| 473 | */
|
---|
| 474 | DECLINLINE(void *) RTTabInsert(PRTTAB pTab, void *pvItem)
|
---|
| 475 | {
|
---|
| 476 | return pTab->pOps->pfnInsert(pTab, pvItem);
|
---|
| 477 | }
|
---|
| 478 |
|
---|
| 479 | /**
|
---|
| 480 | * Inserts an item into the table, if a matching item is encountered
|
---|
| 481 | * it will be replaced and returned.
|
---|
| 482 | *
|
---|
| 483 | * @returns NULL if inserted and allocation failure.
|
---|
| 484 | * @returns Pointer to the replaced item.
|
---|
| 485 | * @param pTab The table.
|
---|
| 486 | * @param pvItem The item which is to be inserted.
|
---|
| 487 | */
|
---|
| 488 | DECLINLINE(void *) RTTabReplace(PRTTAB pTab, void *pvItem)
|
---|
| 489 | {
|
---|
| 490 | return pTab->pOps->pfnReplace(pTab, pvItem);
|
---|
| 491 | }
|
---|
| 492 |
|
---|
| 493 | /**
|
---|
| 494 | * Removes an item from the table if found.
|
---|
| 495 | *
|
---|
| 496 | * @returns Pointer to the removed item.
|
---|
| 497 | * @returns NULL if no item matched pvItem.
|
---|
| 498 | * @param pTab The table.
|
---|
| 499 | * @param pvItem The item which is to be inserted.
|
---|
| 500 | */
|
---|
| 501 | DECLINLINE(void *) RTTabRemove(PRTTAB pTab, const void *pvItem)
|
---|
| 502 | {
|
---|
| 503 | return pTab->pOps->pfnRemove(pTab, pvItem);
|
---|
| 504 | }
|
---|
| 505 |
|
---|
| 506 | /**
|
---|
| 507 | * Finds an item in the table.
|
---|
| 508 | *
|
---|
| 509 | * @returns Pointer to the item it found.
|
---|
| 510 | * @returns NULL if no item matched pvItem.
|
---|
| 511 | * @param pTab The table.
|
---|
| 512 | * @param pvItem The item to find the match to.
|
---|
| 513 | */
|
---|
| 514 | DECLINLINE(void *) RTTabFind(PRTTAB pTab, const void *pvItem)
|
---|
| 515 | {
|
---|
| 516 | return pTab->pOps->pfnFind(pTab, pvItem);
|
---|
| 517 | }
|
---|
| 518 |
|
---|
| 519 |
|
---|
| 520 | /**
|
---|
| 521 | * Common traverser core.
|
---|
| 522 | */
|
---|
| 523 | typedef struct RTTABTRAVERSERCORE
|
---|
| 524 | {
|
---|
| 525 | /** The table being traversed. */
|
---|
| 526 | PRTTAB pTab;
|
---|
| 527 | /** Indicates that this traverser was allocated. */
|
---|
| 528 | bool fAllocated;
|
---|
| 529 | /** The table generation id this traverser was last updated for.
|
---|
| 530 | * This is used to catch up with table changes. */
|
---|
| 531 | RTUINT idGeneration;
|
---|
| 532 | } RTTABTRAVERSERCORE;
|
---|
| 533 |
|
---|
| 534 | /**
|
---|
| 535 | * Generic traverser structure.
|
---|
| 536 | *
|
---|
| 537 | * Tree implementations will use the tree specific part by mapping
|
---|
| 538 | * this structure onto their own internal traverser structure.
|
---|
| 539 | *
|
---|
| 540 | * @remark It would be better to use alloca() for allocating the structure,
|
---|
| 541 | * OTOH this is simpler for the user.
|
---|
| 542 | */
|
---|
| 543 | typedef struct RTTABTRAVERSER
|
---|
| 544 | {
|
---|
| 545 | /** The common core of the traverser data. */
|
---|
| 546 | RTTABTRAVERSERCORE Core;
|
---|
| 547 | /** The tree specific data. */
|
---|
| 548 | void *apvTreeSpecific[32];
|
---|
| 549 | } RTTABTRAVERSER;
|
---|
| 550 |
|
---|
| 551 |
|
---|
| 552 | /**
|
---|
| 553 | * Initializes a traverser to the NULL item.
|
---|
| 554 | *
|
---|
| 555 | * The NULL item is an imaginary table item before the first and after
|
---|
| 556 | * the last items in the table.
|
---|
| 557 | *
|
---|
| 558 | * @returns Pointer to the traverser positioned at the NULL item.
|
---|
| 559 | * @returns NULL on failure to allocate the traverser.
|
---|
| 560 | *
|
---|
| 561 | * @param pTab The table.
|
---|
| 562 | * @param pTravNew Pointer to a preallocated structure. Optional.
|
---|
| 563 | */
|
---|
| 564 | DECLINLINE(PRTTABTRAVERSERCORE) RTTabTravInit(PRTTAB pTab, PRTTABTRAVERSER pTravNew)
|
---|
| 565 | {
|
---|
| 566 | return pTab->pOps->pfnTravInit(pTab, pTravNew);
|
---|
| 567 | }
|
---|
| 568 |
|
---|
| 569 | /**
|
---|
| 570 | * Initializes a traverser to the first item in the table.
|
---|
| 571 | *
|
---|
| 572 | * If the table is empty, the traverser will be positioned at the NULL item
|
---|
| 573 | * like with RTTabTravInit().
|
---|
| 574 | *
|
---|
| 575 | * @returns Pointer to the traverser positioned at the first item or NULL item.
|
---|
| 576 | * @returns NULL on failure to allocate the traverser.
|
---|
| 577 | *
|
---|
| 578 | * @param pTab The table.
|
---|
| 579 | * @param pTravNew Pointer to a preallocated structure. Optional.
|
---|
| 580 | */
|
---|
| 581 | DECLINLINE(PRTTABTRAVERSERCORE) RTTabTravFirst(PRTTAB pTab, PRTTABTRAVERSER pTravNew)
|
---|
| 582 | {
|
---|
| 583 | return pTab->pOps->pfnTravFirst(pTab, pTravNew);
|
---|
| 584 | }
|
---|
| 585 |
|
---|
| 586 | /**
|
---|
| 587 | * Initializes a traverser to the last item in the table.
|
---|
| 588 | *
|
---|
| 589 | * If the table is empty, the traverser will be positioned at the NULL item
|
---|
| 590 | * like with RTTabTravInit().
|
---|
| 591 | *
|
---|
| 592 | * @returns Pointer to the traverser positioned at the last item or NULL item.
|
---|
| 593 | * @returns NULL on failure to allocate the traverser.
|
---|
| 594 | *
|
---|
| 595 | * @param pTab The table.
|
---|
| 596 | * @param pTravNew Pointer to a preallocated structure. Optional.
|
---|
| 597 | */
|
---|
| 598 | DECLINLINE(PRTTABTRAVERSERCORE) RTTabTravLast(PRTTAB pTab, PRTTABTRAVERSER pTravNew)
|
---|
| 599 | {
|
---|
| 600 | return pTab->pOps->pfnTravLast(pTab, pTravNew);
|
---|
| 601 | }
|
---|
| 602 |
|
---|
| 603 | /**
|
---|
| 604 | * Initializes a traverser to an item matching the given one.
|
---|
| 605 | *
|
---|
| 606 | * If the item isn't found, the traverser will be positioned at the NULL item
|
---|
| 607 | * like with RTTabTravInit().
|
---|
| 608 | *
|
---|
| 609 | * @returns Pointer to the traverser positioned at the matching item or NULL item.
|
---|
| 610 | * @returns NULL on failure to allocate the traverser.
|
---|
| 611 | *
|
---|
| 612 | * @param pTab The table.
|
---|
| 613 | * @param pTravNew Pointer to a preallocated structure. Optional.
|
---|
| 614 | * @param pvItem The item to find the match to.
|
---|
| 615 | */
|
---|
| 616 | DECLINLINE(PRTTABTRAVERSERCORE) RTTabTravFind(PRTTAB pTab, PRTTABTRAVERSER pTravNew, const void *pvItem)
|
---|
| 617 | {
|
---|
| 618 | return pTab->pOps->pfnTravFind(pTab, pTravNew, pvItem);
|
---|
| 619 | }
|
---|
| 620 |
|
---|
| 621 | /**
|
---|
| 622 | * Initializes a traverser to the inserted item.
|
---|
| 623 | *
|
---|
| 624 | * If there already exists an item in the tree matching pvItem, the traverser
|
---|
| 625 | * is positioned at that item like with RTTabTravFind().
|
---|
| 626 | *
|
---|
| 627 | * If the insert operation failes because of an out of memory condition, the
|
---|
| 628 | * traverser will be positioned at the NULL item like with RTTabTravInit().
|
---|
| 629 | *
|
---|
| 630 | * @returns Pointer to the traverser positioned at the inserted, existing or NULL item.
|
---|
| 631 | * @returns NULL on failure to allocate the traverser.
|
---|
| 632 | *
|
---|
| 633 | * @param pTab The table.
|
---|
| 634 | * @param pTravNew Pointer to a preallocated structure. Optional.
|
---|
| 635 | * @param pvItem The item to be inserted.
|
---|
| 636 | */
|
---|
| 637 | DECLINLINE(PRTTABTRAVERSERCORE) RTTabTravInsert(PRTTAB pTab, PRTTABTRAVERSER pTravNew, void *pvItem)
|
---|
| 638 | {
|
---|
| 639 | return pTab->pOps->pfnTravInsert(pTab, pTravNew, pvItem);
|
---|
| 640 | }
|
---|
| 641 |
|
---|
| 642 | /**
|
---|
| 643 | * Duplicates a traverser.
|
---|
| 644 | *
|
---|
| 645 | * @returns The pointer to the duplicate.
|
---|
| 646 | * @returns NULL on allocation failure.
|
---|
| 647 | *
|
---|
| 648 | * @param pTrav The traverser to duplicate.
|
---|
| 649 | * @param pTravNew Pointer to a preallocated structure. Optional.
|
---|
| 650 | */
|
---|
| 651 | DECLINLINE(PRTTABTRAVERSERCORE) RTTabTravDuplicate(PRTTABTRAVERSERCORE pTrav, PCRTTABTRAVERSER pTravNew)
|
---|
| 652 | {
|
---|
| 653 | if (pTrav)
|
---|
| 654 | return pTrav->pTab->pOps->pfnTravDuplicate(pTrav, pTravNew);
|
---|
| 655 | return NULL;
|
---|
| 656 | }
|
---|
| 657 |
|
---|
| 658 | /**
|
---|
| 659 | * Frees a traverser.
|
---|
| 660 | *
|
---|
| 661 | * This can safely be called even if the traverser structure
|
---|
| 662 | * wasn't dynamically allocated or the constructor failed.
|
---|
| 663 | *
|
---|
| 664 | * @param pTrav The traverser which is to be free.
|
---|
| 665 | */
|
---|
| 666 | DECLINLINE(void) RTTabTravFree(PRTTABTRAVERSERCORE pTrav)
|
---|
| 667 | {
|
---|
| 668 | if (pTrav && pTrav->fAllocated)
|
---|
| 669 | pTrav->pTab->pOps->pfnTravFree(pTrav);
|
---|
| 670 | }
|
---|
| 671 |
|
---|
| 672 | /**
|
---|
| 673 | * Gets the current item.
|
---|
| 674 | *
|
---|
| 675 | * @returns The current item. (NULL indicates the imaginary NULL item.)
|
---|
| 676 | * @param pTrav The traverser.
|
---|
| 677 | */
|
---|
| 678 | DECLINLINE(void *) RTTabTravCur(PCRTTABTRAVERSERCORE pTrav)
|
---|
| 679 | {
|
---|
| 680 | return pTrav->pTab->pOps->pfnTravCur(pTrav);
|
---|
| 681 | }
|
---|
| 682 |
|
---|
| 683 | /**
|
---|
| 684 | * Advances to the next item.
|
---|
| 685 | *
|
---|
| 686 | * @returns The new current item. (NULL indicates the imaginary NULL item.)
|
---|
| 687 | * @param pTrav The traverser.
|
---|
| 688 | */
|
---|
| 689 | DECLINLINE(void *) RTTabTravNext(PRTTABTRAVERSERCORE pTrav)
|
---|
| 690 | {
|
---|
| 691 | return pTrav->pTab->pOps->pfnTravNext(pTrav);
|
---|
| 692 | }
|
---|
| 693 |
|
---|
| 694 | /**
|
---|
| 695 | * Advances to the previous item.
|
---|
| 696 | *
|
---|
| 697 | * @returns The new current item. (NULL indicates the imaginary NULL item.)
|
---|
| 698 | * @param pTrav The traverser.
|
---|
| 699 | */
|
---|
| 700 | DECLINLINE(void *) RTTabTravPrev(PRTTABTRAVERSERCORE pTrav)
|
---|
| 701 | {
|
---|
| 702 | return pTrav->pTab->pOps->pfnTravPrev(pTrav);
|
---|
| 703 | }
|
---|
| 704 |
|
---|
| 705 | /**
|
---|
| 706 | * Replaces the current item.
|
---|
| 707 | *
|
---|
| 708 | * This has the same restrictions as RTTabProbe(), e.g. it's not permitted to
|
---|
| 709 | * break the order of the table.
|
---|
| 710 | *
|
---|
| 711 | * @returns The replaced item.
|
---|
| 712 | * @returns NULL if the current item is the NULL item. The traverser
|
---|
| 713 | * and table remains unchanged.
|
---|
| 714 | * @param pTrav The traverser.
|
---|
| 715 | * @param pvItem The item to be inserted.
|
---|
| 716 | */
|
---|
| 717 | DECLINLINE(void *) RTTabTravReplace(PRTTABTRAVERSERCORE pTrav, void *pvItem)
|
---|
| 718 | {
|
---|
| 719 | return pTrav->pTab->pOps->pfnTravReplace(pTrav, pvItem);
|
---|
| 720 | }
|
---|
| 721 |
|
---|
[20374] | 722 | RT_C_DECLS_END
|
---|
[4256] | 723 |
|
---|
| 724 | /** @} */
|
---|
| 725 |
|
---|
[76585] | 726 | #endif /* !IPRT_INCLUDED_table_h */
|
---|