Laszlo, I do not have any specific issues with the undefined behavior of these APIs, and I agree with the limited utility of checking for NULL. I just wanted to make sure the style difference between this lib class and other lib classes in the MdePkg was on purpose.
I did misunderstand the behavior of Delete(). Your explanation helped, and I agree no changes are required. Not sure I see the value in the Validate() API. I can see it could be useful as an internal API during the development of an OrderedCollection library instance. What is the use case from a consumer of the OrderedCollection lib class perspective? Thanks, Mike -----Original Message----- From: Laszlo Ersek [mailto:ler...@redhat.com] Sent: Tuesday, August 05, 2014 3:11 PM To: edk2-devel@lists.sourceforge.net Subject: Re: [edk2] [PATCH v2 1/3] MdePkg: introduce OrderedCollectionLib library class On 08/05/14 23:16, Kinney, Michael D wrote: > Lazlo, > > These updates look really good. Just a few minor comments on the lib class: > > 1) UserStruct()/IsEmpty()/Min()/Max()/Next()/Prev()/Validate(): What > is the required behavior if an invalid pointer is passed in? The behavior is undefined. This mimics the C standard, which says 4. Conformance 2 If a ''shall'' or ''shall not'' requirement that appears outside of a constraint is violated, the behavior is undefined. Undefined behavior is otherwise indicated in this International Standard by the words ''undefined behavior'' or by the omission of any explicit definition of behavior. There is no difference in emphasis among these three; they all describe ''behavior that is undefined''. Thus, undefined behavior by the omission of any explicit definition of behavior. > Many of > the other MdePkg lib APIs will ASSERT() for NULL, which is really > only useful for debug builds. The library instance in the second patch doesn't even ASSERT() for NULL, in general; and the library class makes no such requirement. There's no way to detect if a pointer is valid or invalid. If a pointer is invalid, just *evaluating* it, for example, in order to compare it against NULL (that is, not *dereferencing* it) is undefined behavior. void *p; p = malloc(10); if (p != NULL) { free(p); if (p != NULL) { // <------ undefined behavior /* ... */ } } If the caller doesn't track its pointers carefully, there's nothing the callee can do. Checking for NULL might catch a minuscule subset. > 2) UnInit(): Should this API return an error status if the collection > is not empty? I don't see why. The specification clearly states the caller's responsibility. If the caller can't bother to ensure that, why would the caller bother to check the error? > What is the required behavior if an invalid pointer is > passed in? It is undefined. > Many of the other MdePkg lib APIs will ASSERT() for NULL, > which is really only useful for debug builds. You can't catch pointer errors in a non-managed environment. > 3) Insert()/Delete(): Should Collection be an a CONST [in]? Absolutely not. > Does the > caller need to consider the case there the Collection structure is > re-allocated to a new buffer location or the contents are modified? Yes, the contents can be modified. In the red-black tree library instance, a pointer to the root node of the tree is stored in the Collection, and that can change during rebalancing on insert/delete. > 4) Delete(): Should this API have a return code. Maybe SUCCESS for > deleted, and NOT_FOUND of the entry is not in the collection. This is incorrect. The Delete() API does not take a key to look up, and then to delete the associated node. The API of the library is iterator-centric. The example / tester application in the third patch demonstrates this, for example in the CmdDelete() function. If the caller wants to unlink a user structure with a specific key, the caller has to find associated node first, with the Find() API. If that node exists, then the iterator (not the key!) needs to be passed to the Delete() API. (This emphasis on iterators makes the library more flexible. For example, you can use the iterator (ie. pointer-to-Entry) returned by the Find() API to start a forward iteration from that point on.) Given the nature of the Delete() API -- ie. it takes a valid iterator, that is, a valid pointer to an ORDERED_COLLECTION_ENTRY), rather than a key -- there is no way to check for the callee to see if the pointer (the iterator) is valid. Consider the example of trying to unlinking the same-keyed user structure twice in succession, from the same tree: - On the first Find() call, assume a user structure is found with the requested key. An iterator is returned. (== A pointer is returned to the Entry that links the user structure with the requested key.) - The iterator is passed to Delete(), and the pointed-to entry is unlinked and released. The Delete() documentation clearly states, Existing ORDERED_COLLECTION_ENTRY pointers (ie. iterators) *different* from Entry remain valid. (The address of the user structure originally linked by that entry is reported back.) - Now, if the caller at this point tries to look up the key *again*, with the Find() API, Find() will return NULL. Hence the correct caller will know that no entry exists that links a user structure with a matching key. - If, instead, the caller just passes in the *same* iterator to Delete() again, you get undefined behavior. This is precisely the same as calling FreePool() twice in succession on the same pointer. The same way FreePool() -- or free() in standard C -- can't tell you if your pointer is stale, Delete() can't tell you if your pointer-to-Entry is stale. I'd like to emphasize the iterator-centricity of the Delete() interface (and the rest of the API). For example, - looking up key "2", - taking its successor with OrderedCollectionNext(), - then passing *that* iterator to Delete() is completely valid (assuming of course that the original Find() and the subsequent Next() suceed). > 5) Validate(): Should this API have a return code. Maybe SUCCESS if > the ordered collection is consistent. Some other error code if it is > inconsistent. I disagree. If you have an inconsistent data structure, in particular a red-black tree, then you possibly have stale / chaotic pointers in it. There's nothing to do. The Validate() function works by simply not triggering undefined behavior before returning (if it returns at all). The red-black tree implementation uses ASSERT()s exclusively for this reason, for checking validity. > Do you intend this to be able to do repair operations if the > collection is not ordered correctly and return a status that it was > repaired? No. Consider the example of duplicated keys. How do you recover from conflicting keys (which appear as a traversal disorder in Validate())? Which user structure do you evict? How do you return it to the client code? You can't. If basic invariants are violated, the world has ended. Thanks, Laszlo ------------------------------------------------------------------------------ Infragistics Professional Build stunning WinForms apps today! Reboot your WinForms applications with our WinForms controls. Build a bridge from your legacy apps to the future. http://pubads.g.doubleclick.net/gampad/clk?id=153845071&iu=/4140/ostg.clktrk _______________________________________________ edk2-devel mailing list edk2-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/edk2-devel ------------------------------------------------------------------------------ Infragistics Professional Build stunning WinForms apps today! Reboot your WinForms applications with our WinForms controls. Build a bridge from your legacy apps to the future. http://pubads.g.doubleclick.net/gampad/clk?id=153845071&iu=/4140/ostg.clktrk _______________________________________________ edk2-devel mailing list edk2-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/edk2-devel
