Login
User Name:

Password:



Register
Forgot your password?
Vote for Us!
auth_update crash
Dec 23, 2017, 10:15 pm
By Remcon
check_tumble
Dec 18, 2017, 7:21 pm
By Remcon
parse description bug
Dec 15, 2017, 10:08 pm
By Remcon
Couple bugs
Dec 12, 2017, 5:42 pm
By Remcon
Bug in disarm( )
Nov 12, 2017, 6:54 pm
By GatewaySysop
LoP 1.46
Author: Remcon
Submitted by: Remcon
LOP 1.45
Author: Remcon
Submitted by: Remcon
LOP Heroes Edition
Author: Vladaar
Submitted by: Vladaar
Heroes sound extras
Author: Vladaar
Submitted by: Vladaar
6Dragons 4.3
Author: Vladaar
Submitted by: Vladaar
Users Online
CommonCrawl, Yandex, DotBot, Google

Members: 0
Guests: 4
Stats
Files
Topics
Posts
Members
Newest Member
478
3,708
19,242
612
Jacki72H
Today's Birthdays
Evoru (32)
Related Links
» SmaugMuds.org » General » Coding » Unique identifiers
Forum Rules | Mark all | Recent Posts

Unique identifiers
< Newer Topic :: Older Topic >

Pages:<< prev 1 next >>
Post is unread #1 Jul 18, 2009, 9:05 am
Go to the top of the page
Go to the bottom of the page

Tonitrus
Fledgling
GroupMembers
Posts47
JoinedJun 24, 2009

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.
       
Post is unread #2 Jul 18, 2009, 10:40 am
Go to the top of the page
Go to the bottom of the page

Samson
Black Hand
GroupAdministrators
Posts3,639
JoinedJan 1, 2002

Are you talking about uniquely identifying each instance of an object? Because the system already uniquely identifies each master copy by its vnum.
       
Post is unread #3 Jul 18, 2009, 11:16 am
Go to the top of the page
Go to the bottom of the page

Tonitrus
Fledgling
GroupMembers
Posts47
JoinedJun 24, 2009

Samson said:

Are you talking about uniquely identifying each instance of an object?

Yes. And by "object", I don't mean "object" in the smaug sense. More like "an instance of data"
       
Post is unread #4 Jul 18, 2009, 11:12 pm
Go to the top of the page
Go to the bottom of the page

Quixadhal
Conjurer
GroupMembers
Posts398
JoinedMar 8, 2005

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.
       
Post is unread #5 Jul 19, 2009, 1:18 pm
Go to the top of the page
Go to the bottom of the page

David Haley
Sorcerer
GroupMembers
Posts903
JoinedJan 29, 2007

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.
       
Pages:<< prev 1 next >>