Subrata Banik | 20fe24b | 2021-12-09 02:46:38 +0530 | [diff] [blame] | 1 | /** @file |
| 2 | An ordered collection library interface. |
| 3 | |
| 4 | The library class provides a set of APIs to manage an ordered collection of |
| 5 | items. |
| 6 | |
| 7 | Copyright (C) 2014, Red Hat, Inc. |
| 8 | |
| 9 | SPDX-License-Identifier: BSD-2-Clause-Patent |
| 10 | **/ |
| 11 | |
| 12 | #ifndef __ORDERED_COLLECTION_LIB__ |
| 13 | #define __ORDERED_COLLECTION_LIB__ |
| 14 | |
| 15 | #include <Base.h> |
| 16 | |
| 17 | // |
| 18 | // Opaque structure for a collection. |
| 19 | // |
| 20 | typedef struct ORDERED_COLLECTION ORDERED_COLLECTION; |
| 21 | |
| 22 | // |
| 23 | // Opaque structure for collection entries. |
| 24 | // |
| 25 | // Collection entries do not take ownership of the associated user structures, |
| 26 | // they only link them. This makes it easy to link the same user structure into |
| 27 | // several collections. If reference counting is required, the caller is |
| 28 | // responsible for implementing it, as part of the user structure. |
| 29 | // |
| 30 | // A pointer-to-ORDERED_COLLECTION_ENTRY is considered an "iterator". Multiple, |
| 31 | // simultaneous iterations are supported. |
| 32 | // |
| 33 | typedef struct ORDERED_COLLECTION_ENTRY ORDERED_COLLECTION_ENTRY; |
| 34 | |
| 35 | // |
| 36 | // Altering the key field of an in-collection user structure (ie. the portion |
| 37 | // of the user structure that ORDERED_COLLECTION_USER_COMPARE and |
| 38 | // ORDERED_COLLECTION_KEY_COMPARE, below, read) is not allowed in-place. The |
| 39 | // caller is responsible for bracketing the key change with the deletion and |
| 40 | // the reinsertion of the user structure, so that the changed key value is |
| 41 | // reflected in the collection. |
| 42 | // |
| 43 | |
| 44 | /** |
| 45 | Comparator function type for two user structures. |
| 46 | |
| 47 | @param[in] UserStruct1 Pointer to the first user structure. |
| 48 | |
| 49 | @param[in] UserStruct2 Pointer to the second user structure. |
| 50 | |
| 51 | @retval <0 If UserStruct1 compares less than UserStruct2. |
| 52 | |
| 53 | @retval 0 If UserStruct1 compares equal to UserStruct2. |
| 54 | |
| 55 | @retval >0 If UserStruct1 compares greater than UserStruct2. |
| 56 | **/ |
| 57 | typedef |
| 58 | INTN |
| 59 | (EFIAPI *ORDERED_COLLECTION_USER_COMPARE)( |
| 60 | IN CONST VOID *UserStruct1, |
| 61 | IN CONST VOID *UserStruct2 |
| 62 | ); |
| 63 | |
| 64 | /** |
| 65 | Compare a standalone key against a user structure containing an embedded key. |
| 66 | |
| 67 | @param[in] StandaloneKey Pointer to the bare key. |
| 68 | |
| 69 | @param[in] UserStruct Pointer to the user structure with the embedded |
| 70 | key. |
| 71 | |
| 72 | @retval <0 If StandaloneKey compares less than UserStruct's key. |
| 73 | |
| 74 | @retval 0 If StandaloneKey compares equal to UserStruct's key. |
| 75 | |
| 76 | @retval >0 If StandaloneKey compares greater than UserStruct's key. |
| 77 | **/ |
| 78 | typedef |
| 79 | INTN |
| 80 | (EFIAPI *ORDERED_COLLECTION_KEY_COMPARE)( |
| 81 | IN CONST VOID *StandaloneKey, |
| 82 | IN CONST VOID *UserStruct |
| 83 | ); |
| 84 | |
| 85 | |
| 86 | // |
| 87 | // Some functions below are read-only, while others are read-write. If any |
| 88 | // write operation is expected to run concurrently with any other operation on |
| 89 | // the same collection, then the caller is responsible for implementing locking |
| 90 | // for the whole collection. |
| 91 | // |
| 92 | |
| 93 | /** |
| 94 | Retrieve the user structure linked by the specified collection entry. |
| 95 | |
| 96 | Read-only operation. |
| 97 | |
| 98 | @param[in] Entry Pointer to the collection entry whose associated user |
| 99 | structure we want to retrieve. The caller is responsible |
| 100 | for passing a non-NULL argument. |
| 101 | |
| 102 | @return Pointer to user structure linked by Entry. |
| 103 | **/ |
| 104 | VOID * |
| 105 | EFIAPI |
| 106 | OrderedCollectionUserStruct ( |
| 107 | IN CONST ORDERED_COLLECTION_ENTRY *Entry |
| 108 | ); |
| 109 | |
| 110 | |
| 111 | /** |
| 112 | Allocate and initialize the ORDERED_COLLECTION structure. |
| 113 | |
| 114 | @param[in] UserStructCompare This caller-provided function will be used to |
| 115 | order two user structures linked into the |
| 116 | collection, during the insertion procedure. |
| 117 | |
| 118 | @param[in] KeyCompare This caller-provided function will be used to |
| 119 | order the standalone search key against user |
| 120 | structures linked into the collection, during |
| 121 | the lookup procedure. |
| 122 | |
| 123 | @retval NULL If allocation failed. |
| 124 | |
| 125 | @return Pointer to the allocated, initialized ORDERED_COLLECTION |
| 126 | structure, otherwise. |
| 127 | **/ |
| 128 | ORDERED_COLLECTION * |
| 129 | EFIAPI |
| 130 | OrderedCollectionInit ( |
| 131 | IN ORDERED_COLLECTION_USER_COMPARE UserStructCompare, |
| 132 | IN ORDERED_COLLECTION_KEY_COMPARE KeyCompare |
| 133 | ); |
| 134 | |
| 135 | |
| 136 | /** |
| 137 | Check whether the collection is empty (has no entries). |
| 138 | |
| 139 | Read-only operation. |
| 140 | |
| 141 | @param[in] Collection The collection to check for emptiness. |
| 142 | |
| 143 | @retval TRUE The collection is empty. |
| 144 | |
| 145 | @retval FALSE The collection is not empty. |
| 146 | **/ |
| 147 | BOOLEAN |
| 148 | EFIAPI |
| 149 | OrderedCollectionIsEmpty ( |
| 150 | IN CONST ORDERED_COLLECTION *Collection |
| 151 | ); |
| 152 | |
| 153 | |
| 154 | /** |
| 155 | Uninitialize and release an empty ORDERED_COLLECTION structure. |
| 156 | |
| 157 | Read-write operation. |
| 158 | |
| 159 | It is the caller's responsibility to delete all entries from the collection |
| 160 | before calling this function. |
| 161 | |
| 162 | @param[in] Collection The empty collection to uninitialize and release. |
| 163 | **/ |
| 164 | VOID |
| 165 | EFIAPI |
| 166 | OrderedCollectionUninit ( |
| 167 | IN ORDERED_COLLECTION *Collection |
| 168 | ); |
| 169 | |
| 170 | |
| 171 | /** |
| 172 | Look up the collection entry that links the user structure that matches the |
| 173 | specified standalone key. |
| 174 | |
| 175 | Read-only operation. |
| 176 | |
| 177 | @param[in] Collection The collection to search for StandaloneKey. |
| 178 | |
| 179 | @param[in] StandaloneKey The key to locate among the user structures linked |
| 180 | into Collection. StandaloneKey will be passed to |
| 181 | ORDERED_COLLECTION_KEY_COMPARE. |
| 182 | |
| 183 | @retval NULL StandaloneKey could not be found. |
| 184 | |
| 185 | @return The collection entry that links to the user structure matching |
| 186 | StandaloneKey, otherwise. |
| 187 | **/ |
| 188 | ORDERED_COLLECTION_ENTRY * |
| 189 | EFIAPI |
| 190 | OrderedCollectionFind ( |
| 191 | IN CONST ORDERED_COLLECTION *Collection, |
| 192 | IN CONST VOID *StandaloneKey |
| 193 | ); |
| 194 | |
| 195 | |
| 196 | /** |
| 197 | Find the collection entry of the minimum user structure stored in the |
| 198 | collection. |
| 199 | |
| 200 | Read-only operation. |
| 201 | |
| 202 | @param[in] Collection The collection to return the minimum entry of. The |
| 203 | user structure linked by the minimum entry compares |
| 204 | less than all other user structures in the collection. |
| 205 | |
| 206 | @retval NULL If Collection is empty. |
| 207 | |
| 208 | @return The collection entry that links the minimum user structure, |
| 209 | otherwise. |
| 210 | **/ |
| 211 | ORDERED_COLLECTION_ENTRY * |
| 212 | EFIAPI |
| 213 | OrderedCollectionMin ( |
| 214 | IN CONST ORDERED_COLLECTION *Collection |
| 215 | ); |
| 216 | |
| 217 | |
| 218 | /** |
| 219 | Find the collection entry of the maximum user structure stored in the |
| 220 | collection. |
| 221 | |
| 222 | Read-only operation. |
| 223 | |
| 224 | @param[in] Collection The collection to return the maximum entry of. The |
| 225 | user structure linked by the maximum entry compares |
| 226 | greater than all other user structures in the |
| 227 | collection. |
| 228 | |
| 229 | @retval NULL If Collection is empty. |
| 230 | |
| 231 | @return The collection entry that links the maximum user structure, |
| 232 | otherwise. |
| 233 | **/ |
| 234 | ORDERED_COLLECTION_ENTRY * |
| 235 | EFIAPI |
| 236 | OrderedCollectionMax ( |
| 237 | IN CONST ORDERED_COLLECTION *Collection |
| 238 | ); |
| 239 | |
| 240 | |
| 241 | /** |
| 242 | Get the collection entry of the least user structure that is greater than the |
| 243 | one linked by Entry. |
| 244 | |
| 245 | Read-only operation. |
| 246 | |
| 247 | @param[in] Entry The entry to get the successor entry of. |
| 248 | |
| 249 | @retval NULL If Entry is NULL, or Entry is the maximum entry of its |
| 250 | containing collection (ie. Entry has no successor entry). |
| 251 | |
| 252 | @return The collection entry linking the least user structure that is |
| 253 | greater than the one linked by Entry, otherwise. |
| 254 | **/ |
| 255 | ORDERED_COLLECTION_ENTRY * |
| 256 | EFIAPI |
| 257 | OrderedCollectionNext ( |
| 258 | IN CONST ORDERED_COLLECTION_ENTRY *Entry |
| 259 | ); |
| 260 | |
| 261 | |
| 262 | /** |
| 263 | Get the collection entry of the greatest user structure that is less than the |
| 264 | one linked by Entry. |
| 265 | |
| 266 | Read-only operation. |
| 267 | |
| 268 | @param[in] Entry The entry to get the predecessor entry of. |
| 269 | |
| 270 | @retval NULL If Entry is NULL, or Entry is the minimum entry of its |
| 271 | containing collection (ie. Entry has no predecessor entry). |
| 272 | |
| 273 | @return The collection entry linking the greatest user structure that |
| 274 | is less than the one linked by Entry, otherwise. |
| 275 | **/ |
| 276 | ORDERED_COLLECTION_ENTRY * |
| 277 | EFIAPI |
| 278 | OrderedCollectionPrev ( |
| 279 | IN CONST ORDERED_COLLECTION_ENTRY *Entry |
| 280 | ); |
| 281 | |
| 282 | |
| 283 | /** |
| 284 | Insert (link) a user structure into the collection, allocating a new |
| 285 | collection entry. |
| 286 | |
| 287 | Read-write operation. |
| 288 | |
| 289 | @param[in,out] Collection The collection to insert UserStruct into. |
| 290 | |
| 291 | @param[out] Entry The meaning of this optional, output-only |
| 292 | parameter depends on the return value of the |
| 293 | function. |
| 294 | |
| 295 | When insertion is successful (RETURN_SUCCESS), |
| 296 | Entry is set on output to the new collection entry |
| 297 | that now links UserStruct. |
| 298 | |
| 299 | When insertion fails due to lack of memory |
| 300 | (RETURN_OUT_OF_RESOURCES), Entry is not changed. |
| 301 | |
| 302 | When insertion fails due to key collision (ie. |
| 303 | another user structure is already in the |
| 304 | collection that compares equal to UserStruct), |
| 305 | with return value RETURN_ALREADY_STARTED, then |
| 306 | Entry is set on output to the entry that links the |
| 307 | colliding user structure. This enables |
| 308 | "find-or-insert" in one function call, or helps |
| 309 | with later removal of the colliding element. |
| 310 | |
| 311 | @param[in] UserStruct The user structure to link into the collection. |
| 312 | UserStruct is ordered against in-collection user |
| 313 | structures with the |
| 314 | ORDERED_COLLECTION_USER_COMPARE function. |
| 315 | |
| 316 | @retval RETURN_SUCCESS Insertion successful. A new collection entry |
| 317 | has been allocated, linking UserStruct. The |
| 318 | new collection entry is reported back in |
| 319 | Entry (if the caller requested it). |
| 320 | |
| 321 | Existing ORDERED_COLLECTION_ENTRY pointers |
| 322 | into Collection remain valid. For example, |
| 323 | on-going iterations in the caller can |
| 324 | continue with OrderedCollectionNext() / |
| 325 | OrderedCollectionPrev(), and they will |
| 326 | return the new entry at some point if user |
| 327 | structure order dictates it. |
| 328 | |
| 329 | @retval RETURN_OUT_OF_RESOURCES The function failed to allocate memory for |
| 330 | the new collection entry. The collection has |
| 331 | not been changed. Existing |
| 332 | ORDERED_COLLECTION_ENTRY pointers into |
| 333 | Collection remain valid. |
| 334 | |
| 335 | @retval RETURN_ALREADY_STARTED A user structure has been found in the |
| 336 | collection that compares equal to |
| 337 | UserStruct. The entry linking the colliding |
| 338 | user structure is reported back in Entry (if |
| 339 | the caller requested it). The collection has |
| 340 | not been changed. Existing |
| 341 | ORDERED_COLLECTION_ENTRY pointers into |
| 342 | Collection remain valid. |
| 343 | **/ |
| 344 | RETURN_STATUS |
| 345 | EFIAPI |
| 346 | OrderedCollectionInsert ( |
| 347 | IN OUT ORDERED_COLLECTION *Collection, |
| 348 | OUT ORDERED_COLLECTION_ENTRY **Entry OPTIONAL, |
| 349 | IN VOID *UserStruct |
| 350 | ); |
| 351 | |
| 352 | |
| 353 | /** |
| 354 | Delete an entry from the collection, unlinking the associated user structure. |
| 355 | |
| 356 | Read-write operation. |
| 357 | |
| 358 | @param[in,out] Collection The collection to delete Entry from. |
| 359 | |
| 360 | @param[in] Entry The collection entry to delete from Collection. |
| 361 | The caller is responsible for ensuring that Entry |
| 362 | belongs to Collection, and that Entry is non-NULL |
| 363 | and valid. Entry is typically an earlier return |
| 364 | value, or output parameter, of: |
| 365 | |
| 366 | - OrderedCollectionFind(), for deleting an entry |
| 367 | by user structure key, |
| 368 | |
| 369 | - OrderedCollectionMin() / OrderedCollectionMax(), |
| 370 | for deleting the minimum / maximum entry, |
| 371 | |
| 372 | - OrderedCollectionNext() / |
| 373 | OrderedCollectionPrev(), for deleting an entry |
| 374 | found during an iteration, |
| 375 | |
| 376 | - OrderedCollectionInsert() with return value |
| 377 | RETURN_ALREADY_STARTED, for deleting an entry |
| 378 | whose linked user structure caused collision |
| 379 | during insertion. |
| 380 | |
| 381 | Existing ORDERED_COLLECTION_ENTRY pointers (ie. |
| 382 | iterators) *different* from Entry remain valid. |
| 383 | For example: |
| 384 | |
| 385 | - OrderedCollectionNext() / |
| 386 | OrderedCollectionPrev() iterations in the caller |
| 387 | can be continued from Entry, if |
| 388 | OrderedCollectionNext() or |
| 389 | OrderedCollectionPrev() is called on Entry |
| 390 | *before* OrderedCollectionDelete() is. That is, |
| 391 | fetch the successor / predecessor entry first, |
| 392 | then delete Entry. |
| 393 | |
| 394 | - On-going iterations in the caller that would |
| 395 | have otherwise returned Entry at some point, as |
| 396 | dictated by user structure order, will correctly |
| 397 | reflect the absence of Entry after |
| 398 | OrderedCollectionDelete() is called |
| 399 | mid-iteration. |
| 400 | |
| 401 | @param[out] UserStruct If the caller provides this optional output-only |
| 402 | parameter, then on output it is set to the user |
| 403 | structure originally linked by Entry (which is now |
| 404 | freed). |
| 405 | |
| 406 | This is a convenience that may save the caller a |
| 407 | OrderedCollectionUserStruct() invocation before |
| 408 | calling OrderedCollectionDelete(), in order to |
| 409 | retrieve the user structure being unlinked. |
| 410 | **/ |
| 411 | VOID |
| 412 | EFIAPI |
| 413 | OrderedCollectionDelete ( |
| 414 | IN OUT ORDERED_COLLECTION *Collection, |
| 415 | IN ORDERED_COLLECTION_ENTRY *Entry, |
| 416 | OUT VOID **UserStruct OPTIONAL |
| 417 | ); |
| 418 | |
| 419 | #endif |