Jump to content
  • Advertisement
Sign in to follow this  
jtrask

Unique ID manager

This topic is 5451 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Language of the evening is C++ (as much as I prefer Python). I've had this problem writing multiplayer games, I'm having it again doing an AI experiment. I need a class where I can request a unique ID (integer), look up (a pointer probably) by ID, free the ID. Since many many many will be connecting, the ID's provided in a 4 byte space will not be enough, so freed ID's need to be recycled. What's a *good* way of doing this? (I have plenty of bad ways. What's the right one?) -j

Share this post


Link to post
Share on other sites
Advertisement
Allocate an empty block of memory and cast it to an integer, the pointer is guaranteed to be unique.

typedef size_t unique_id;

unique_id unique_alloc() {
return unique_id(malloc(0) - (char *) 0);
}

void unique_free(unique_id u) {
free(u + (char *) 0);
}

Share this post


Link to post
Share on other sites
Quote:
Original post by doynax
Allocate an empty block of memory and cast it to an integer, the pointer is guaranteed to be unique.

*** Source Snippet Removed ***

Hey, I never thought of that. Thats a damn neat way to do UIDs.

Share this post


Link to post
Share on other sites
4294967296 = number of unique id's ... thats plenty... of course... if you sustain your server for an indefinite amount of time you may run in to trouble. As for the pointer idea... i dont reccomend that... youd just be using your valuable heap space... depending on how many entities you expect... it might be viable to keep a list of them... considering you are hanging on to the classes anyways so you can do what you might with them. Another idea which needs a little bit of help would be to keep a queue of ID's which have been "decommissioned" (ie destroyed) this of course... means you need to fill the queue to begin with... and when you need a new ID, you just assign it one out of the queue (i dunno that one doesnt sound so good to me)

HOWEVER
BEST IDEA EVAR!:
the best idea i can see... would be... to expand on doynax's idea... simply make the block of memory BE the object... so your not wasting space... whenver you need a new object... you allocate memory for that object somewhere on the heap, and that pointer is the ID, which the clients or whatever will be notified about

hope that helps
-Dan

Share this post


Link to post
Share on other sites
MostA simple and clean way of doing it:


template<class T>
class UidServer {
// holder for fresh UIDs
T baseUid;
// stack containing unused UIDs
std::stack<T> freeUid;
public:
// ctor
UidServer() : baseUid(T(0))
{}
// dtor
~UidServer()
{}

// Allocate a UID
const T Allocate() {
T uid;
if (!freeUid.empty()) {
uid = freeUid.top();
freeUid.pop();
} else {
// --- manage overflows here ---
assert(baseUid + 1 > baseUid);
// -----------------------------
uid = ++baseUid;
}
return uid;
}

// release a UID
void Release(const T uid) {
freeUid.push(uid);
}

// return number of unused UIDs
const size_t Unused() const { return freeUid.size(); }

// return number of used UIDs
const size_t Used() const { return baseUid - Unused(); }
};






You can use a UidServer of any type that provides a prefix ++ operator and a difference operator that accepts a right-hand size_t (so custom bignums classes work as well).

Example: UidServer<unsigned int> uidServerInt;
UidServer<size_t> uidServerSizeT;
UidServer<unsigned long long> uidServer64;

Using Unused() and Used() you can easily detect usage patterns and optimise by pre-allocating some space on the unused stack (to minimise std::stack re-allocations).

This is the cleanest way I can currently think of. Not the best, not the most efficient. But propably the safest and most portable way.

Fell free to comment on this idea,
Pat.

[edit]
Here's a version for paranoids. Duplicate uid releasing is catched in this version. A sorted list of UIDs is used, such that looking for already released UIDs is guaranteed to be O(log n) and the lowest available UID is returned by Allocate().


template<class T>
class UidServer {
// holder for fresh UIDs
T baseUid;
// stack containing unused UIDs
std::list<T> freeUid;
public:
// ctor
UidServer() : baseUid(T(0))
{}
// dtor
~UidServer()
{}

// Allocate a UID
const T Allocate() {
T uid;
if (!freeUid.empty()) {
uid = freeUid.front();
freeUid.pop_front();
} else {
// --- manage overflows here ---
assert(baseUid + 1 > baseUid);
// -----------------------------
uid = ++baseUid;
}
return uid;
}

// release a UID
void Release(const T uid) {
// --- handle invalid calls here ---
assert(uid > T(0) && uid <= baseUid);
// ---------------------------------
if (!freeUid.empty()) {
std::list<T>::iterator pos = std::lower_bound(freeUid.begin(), freeUid.end(), uid);
// --- handle duplicate calls here ---
assert (*pos != uid);
// -----------------------------------

// keep the list sorted for O(log n) duplication test
freeUid.insert(pos, uid);
} else {
freeUid.push_front(uid);
}
}

// return number of unused UIDs
const size_t Unused() const { return freeUid.size(); }

// return number of used UIDs
const size_t Used() const { return baseUid - Unused(); }

};





This second version has is O(1) for Allocate() and O(log n) for Release() - e.g. only 20 iterations for 1M unused UIDs.

[re-edit]Some small semantic corrections to the above code[/re-edit]
[/edit]


[Edited by - darookie on October 14, 2004 6:35:16 PM]

Share this post


Link to post
Share on other sites
Looking at this from another angle, I'll assume the ID->object lookup is the important part, and that you need high uptime (i.e. potentially infinite number of alloc/free).

In that case, what I'd do is generate a "handle", which consists of an index and tag. The index simply gives the position within an expandable array of objects. Tag is an n-bit counter, incremented on each allocation, that distinguishes a handle referring to a certain index from another, previously freed instance. If tag overflows, the handle is no longer guaranteed to be unique, but still works. This won't happen (tm), though, with a 64 bit handle.

Depending on how often IDs are freed vs. allocated, you can go to more or less trouble designing a scheme to return a free index. What I do is simply use the 'last known free index' (set when allocating and freeing); failing that, a linear search. This is the hope that the caller ping/pongs between alloc and free, which is actually often the case.

So, the innovation here is basically make the ID->object lookup part of the ID. What I've described is the core of the resource manager in an RTS. It really gets hammered, but works well :)

Share this post


Link to post
Share on other sites
Right Jan, I missed the look-up part [smile].
I'd rather vote for the most straight-forward solution first.

// look-up is O(log n) for integral ID_TYPEs
std::map<ID_TYPE, BaseObject*> idToObject;

Also very simple to integrate with the UidServer idea.
The 'last-free-index' idea of Jan can be powered up by adding a fixed size free-list in front of the linear search.
The size of the free-list can be empirically determined based on the average alloc/free ratio.

Share this post


Link to post
Share on other sites
Fixed-size freelist determined by alloc/free ratio is a good idea :) It turns out, though, that linear search isn't as bad as expected for my application. I recently discovered to my dismay and amusement that the last-known-index wasn't ever getting set after a free(), due to a silly bug. I never noticed, and the lookup didn't show up in a profile ;)

Right, a map is the simple and easy way. I try to keep heap allocations to an absolute minimum though - they're the bane of my existence. When debugging heap corruption, fire up BoundsChecker in paranoid memory check mode, and try not to cry when initialization takes half an hour because someone's fancy-ass XML loader (which is basically reading flat text data *sigh*) is allocating tens of thousands of nodes.
std::map and vector (which gets bonus points for Dinkumware's new_size=1.5*old allocation strategy!) are pretty bad offenders also.
For heavily-used stuff like this, I'm willing to write suballocators and containers with sane memory allocation footprints ;)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!