Data Structures Library
<i>This post was originally made by <b>danij</b> on the dengDevs blog. It was posted under the categories: Engine, Games, jDoom, jHeretic, jHexen, Mac OS X, Unix/Linux, Windows.</i>
As you know I'm currently working on commonizing the multiplayer object respawn implementation. I have the need for a standard Queue data structure to implement this so I figured it would be a good idea to encapsulate the functionality into a reusable object-like implementation.
I'm quite happy to write this simple data structure. It should be done in such a way that both the engine and the plugins can use this code, like a library.
Where under the new directory structure should this code reside?
As you know I'm currently working on commonizing the multiplayer object respawn implementation. I have the need for a standard Queue data structure to implement this so I figured it would be a good idea to encapsulate the functionality into a reusable object-like implementation.
I'm quite happy to write this simple data structure. It should be done in such a way that both the engine and the plugins can use this code, like a library.
Where under the new directory structure should this code reside?
Comments
Creating a real shared library would make sense if it will in the future contain more functionality than just the queue data structure. For example, it might make sense to create a shared library out of plugins/common, so that the game libs don't have to include a separate copy of the common code.
We might add a "libs" directory into the root, for Doomsday-specific libraries usable by the engine and the plugins. "libs" would then contain only libraries developed and maintained by the Doomsday team (as opposed to "external"). The difference between libs and plugins is their public interface: a lib provides an API specific to the lib's functionality, while a plugin's API is strictly defined by Doomsday.
If we had a libs subdirectory and plugins/common was made into a library, it would be moved to libs/common.
Perhaps we should just create a "libs/common/" shared library now and put your queue routines there? Then we could start thinking about moving common game-related routines there as well (unless they can be moved to the engine).
Thoughts?
Yes I would be expanding the library to include other kinds of data structures for our own (Doomsday) use to include such common structures as List, Stack, Linked Lists, m-way Trees etc. Basically any type of data structure we are already using in Doomsday and/or the games plus various, common search and sorting algorithms.
The only benefit of me writing such a thing is that it would be in C and not C++ (where we would probably be better off using STL) and which could be linked with both the engine and the games. I already have some of these structures built for my SCUDD project (which is also a C app looking to move to C++ in the distant future) so the code could be reused.
What I would like to do is to replace all instances of (common) hard wired data structures, search and sort algorithms in the Doomsday + games source and replace them with these "objects". The benefits of this are obvious.
I'm not sure a completely generic set of data structures would serve us best. For example we should be able to specify what kind of storage is used (eg heap, zone (zblock, level static etc)).
I think a "libs/common/" shared library would be useful anyway, though, I'm unsure how much is likely to end up in there in the long term.