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