This isn't necessarilly for Smaug (although I may use it with Smaug), but it's been bugging me for a while. I've been designing an object system and the framework for a mud for awhile, and in each case, I realized that I need a way to uniquely identify each object. Initially I wanted to do so by the pointers to each object, since they're pretty unique, but they won't be persistent, since I can't load them from a file and end up with them having the same address. I could give them a long int identifier and randomly generate a number for each, or maybe just assign them sequentially, but the idea of being limited to 4 billion objects or whatever bugs me (presumably for some sort of philosophical reason, 4 billion should be enough for anyone (See also: 64k/640k should be enough for anybody))

Also, I'm pretty ignorant on a lot of the more complex data structures and techniques, since you tend to have to know their names to look them up. (For example, I learned about binary searches digging through Smaug)

Anyway, I've toyed with various ideas, such as randomly generated strings and so on (since you could theoretically have any number of differing strings), but in the case of generating strings or numbers randomly, I could end up generating the same numbers, then having to retry (which seems like a waste of processor time), and if I do them sequentially, I end up with holes when objects are deleted. Tracking those holes seems like a lot of overhead, and trying to fill them randomly seems like it would take many, many attempts.

This has pretty much been a "design decision" that's kept me from working on this particular project for several months (I think I re-downloaded Smaug to have something to do while I thought about it), but I'm pretty much totally out of ideas.

Whatever I end up with, it needs to generate Unique, Persistent IDs and ideally shouldn't waste a lot of processor time or memory in doing so.

I think at one point I decided on doing it sequentially and tracking the number of holes, and if the number of holes was something like 50% of the highest number generated, it'd try to randomly fill a hole, or, failing that, just add another to the top. That seems kind of meh too, and I have a feeling I'm overlooking a much more elegant solution.

Are you talking about uniquely identifying each instance of an object? Because the system already uniquely identifies each master copy by its vnum. .........................
PDNS-Admin | Sandbox | Arthmoor MUD Hosting Services | The Truth About Medievia: A Saga of Code Theft.

"The past was erased, the erasure was forgotten, the lie became truth." -- George Orwell, 1984

Yes. And by "object", I don't mean "object" in the smaug sense. More like "an instance of data"

The simplest way to do this is to just keep an instance counter for each vnum. Increment any time you create a new instance and periodically write that out so it survives reboots. Add a counter to the data structure so the prototype object always has the most recent instance number, when you make a new one increment that. Added bonus, instance 0 of any vnum should be the prototype.

If you want more than 4 billion individual copies of an item, you could always use another data type, such as a 64-bit integer or a string.
.........................

I don't think you really need one per vnum. If you use unsigned 64-bit numbers -- uint64_t -- you have 2^64 possibilities. That's 18,446,744,073,709,551,616. Or, 584,942,417,355.07 objects generated every single second for an entire year. So that should be plenty. If you're really paranoid, do what Quix said and have one counter per object.

Note that 4 billion is still 126.84 objects generated every single second for an entire year, so it's a pretty big number too.

Keeping a map from id to thing, using a std::map for example, is pretty easy and takes care of the "hole tracking" problem. Note that holes are actually a necessary feature of your solution, because you said that an id should be unique "forever" (since it's persistent): so, you can't really recycle ids. If you recycled ids, somebody could have a reference to an object that has suddenly turned into something else. Having holes means that you can know that an object has been truly destroyed, which is a very useful thing to know. .........................
David Haley
Head Coder, Legends of the Darkstone
BabbleMUD Project
http://david.the-haleys.org