Laszlo, The incomplete types between lib class .h and lib instance is not something we done anywhere else. I prefer the lib class .h file to be able to stand on its own. Meaning it can be included by a module, but if not lib instance is linked to the module, the module should still be able to compile.
The allocation of the root node issue could be handled in a similar way to the CryproPkg lib classes where there is a lib API to get the size of the opaque struct. The caller calls the size function. Does the allocation, and then is able to use that allocated buffer for all other lib APIs. This may be a way to get to VOID * for both ROOT and NODE opaque types. I was also thinking that the use of Red Black algorithm is an implementation choice. Does it make more sense to change the name of the lib class to be more generic (no references to red black), and one of many possible lib instances uses the read black algorithm? Thanks, Mike -----Original Message----- From: Laszlo Ersek [mailto:ler...@redhat.com] Sent: Monday, August 04, 2014 7:17 AM To: edk2-devel@lists.sourceforge.net Subject: Re: [edk2] [PATCH 1/2] MdePkg: introduce RbTreeLib On 08/03/14 21:17, Kinney, Michael D wrote: > If the library is type BASE, then why do you need UefiBaseTypes.h? > For libs of type BASE, the return status codes should be RETURN_* > instead of EFI_*. That may reduce the dependency on > UefiBaseTypes.h. Ah, good point! And indeed I think the sole reason for UefiBaseTypes.h was EFI_STATUS. Now that you say it it's obvious that a base type module shouldn't be tied to Uefi*. > I also recommend changing name of RB_TREE to RED_BLACK_TREE and in > other places where abbreviation "Rb" is used, expand to "RedBlack" Alright, will do. Do you also want me to replace Rb with RedBlack in file and directory names as well? > I am also curious. The type RB_TREE_ROOT and RB_TREE_NODE. Could > these be defined as VOID * in the public library class .h file and > hide the internal implementation of the structures inside the lib > implementation itself. RB_TREE_NODE is already hidden. The header file introduces the two type names "struct RB_TREE_NODE" and plain "RB_TREE_NODE" (via the typedef) as the same incomplete type, via this single line: typedef struct RB_TREE_NODE RB_TREE_NODE; This doesn't expose any internals, but it allows the use of pointers to it (pointers to incomplete types are allowed) while preserving strict type checking. Ie. the client code can use RB_TREE_NODE* and rely on the compiler to catch unintended or invalid casts, but the client will still have no clue of the internals. RB_TREE is different. I must make that non-opaque (ie. a complete type) because I want callers to be able to allocate it without wrapper functions, globally or locally: RB_TREE mModuleTree; SomeFunc ( ... ) { RB_TREE Tree; } I think this is a good thing to allow. The unit tester in the 2nd patch relies on this. (RB_TREE_NODE has no such use.) > It looks like you have defined functions for > the consumer of the lib to access their data and perform all > operations without the consumer requiring access to fields of these > structs. Are there any consumer use cases that require access to the > fields of these structs? None for RB_TREE_NODE as explained above -- I agree that hiding internals is preferable. For RB_TREE, there are two consumer use cases. (1) The RB_TREE structure exposes the iterator (ie. RB_TREE_NODE*) to the root of the tree, in the RB_TREE.Root field. This is useful for repeatedly deleting the root node in a tight loop, in order to tear down a tree completely, without introducing any local variable iterators (node pointers). It allows you to grab *some* valid iterator into the tree and then delete it, returning the thus-far associated user structure. Please see the TearDown() function in the second patch. (BTW no, I don't think that TearDown() should be a library function.) Of course I could easily provide a small function called RbTreeRoot (or RedBlackTreeRoot()) for this use. (2) The more important use case that requires the client to see the complete type is the size -- the allocation of static and auto storage duration variables that I mentioned above. I could write a library function that allocates RB_TREE itself with AllocatePool() and returns that dynamic instance, but I disagree with such a user restriction. I can see that the statically or locally allocated RB_TREE instance needs to be initialized with RbTreeInit() anyway (so the initialization function call is not saved), but I'd like to enable clients to allocate RB_TREE on the stack, or globally, or to place it in another structure (ie. not a pointer to RB_TREE, but RB_TREE itself). If you think this is not important, I won't insist; for RB_TREE I can just as well say typedef struct RB_TREE RB_TREE; in the header file, introducing the incomplete type, and then both opacity and type safety will be ensured. The price (which is a step back in my eyes) would be that RbTreeInit() wouldn't take an externally allocated structure to initialize, but it would do the allocation itself, dynamically. (And RbTreeUninit() would release RB_TREE itself too.) In one sentence, the main use case for the transparency of RB_TREE is that I'd like to allow callers to allocate the RB_TREE structure themselves. 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
