Fast Unit Mapper
Posted: 05 Jan 2006, 19:11
Code: Select all
#ifndef GLOBALUNITMAPPER
#define GLOBALUNITMAPPER
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
/**
* GlobalUnitMapper.h
*
* a complete unit mapping function to store unit data.
* this is technically a double linked hash map, higly optimized
* for the special case of univocal and continuos limited key
*
* here key refers to the game unitID. it is assumed that never a
* player will have more than 5000 units. If the limit needs to be
* expanded, edit the MAX_UNIT definition that follow
*
* the iterator is sorted by insertion order
*
* it is alghoritmically the fastest implementation possible;
* table of comparision:
*
* GlobalUnitMapper:
* insertion O(1), deletion O(1), retrieval O(1)
*
* HashMap:
* insertion O(1), deletion O(1), retrieval O(1) but those
* include "real hashing" costs not need here as keys are know
* in number and structure.
*
* Map:
* insertion O(log(n)), deletion O(log(n)), retrieval O(log(n))
*
* released under the terms of BSD license. copyright by cain.
*/
#include "IAICallback.h"
#include <string>
#include "UnitDef.h"
//modify those to use custom structures.
//having my class called unitWrapper, I use #define UNIT_DEFINITION unitWrapper *
#define UNIT_DEFINITION const UnitDef *
//this is the placeholder put on the map on empty spot
//getting a non-existant unit will return this
#define INVALID_UNIT_DEFINITION NULL
//here put the "constructor"
#define UNIT_DEFINITION_GENERATOR(x) cb->GetUnitDef(x)
#define STRING_LOGGER(x) cb->SendTextMsg(x,0)
//uncomment this to disable the logging (improves performance)
// #define STRING_LOGGER(X)
#define MAX_UNIT 5000
//note that the add, get and remove functions are NOT synchronized
//if you have a multithreaded concurrent access, you need to define
//your custom synchronization mutex.
//if you do modify this code, adding for example access mutex,
//send the modified version back to me so I can clean it up and
//mantain a unified distribution.
typedef struct {
int unitID;
UNIT_DEFINITION unitdef;
} unitMap;
typedef struct {
int prev;
int next;
} doubleLink;
class GlobalUnitMapper
{
private:
IAICallback *cb;
unitMap units[MAX_UNIT];
doubleLink links[MAX_UNIT];
int tailPos;
int headPos;
int size;
public:
GlobalUnitMapper(IAICallback *cb) {
this->cb=cb;
for (int i=0;i<MAX_UNIT;i++) {
units[i].unitID=-1;
units[i].unitdef=INVALID_UNIT_DEFINITION;
links[i].next=-1;
links[i].prev=-1;
}
tailPos=-1;
headPos=-1;
size=0;
}
~GlobalUnitMapper(void){
}
int getSize() {
return size;
}
void addUnit(int unitID) {
int position=getUnitPosition(unitID,false);
if (units[position].unitID==-1) {
++size;
} else {
STRING_LOGGER("unit was already here");
}
units[position].unitID=unitID;
units[position].unitdef=UNIT_DEFINITION_GENERATOR(unitID);
if(headPos==-1) headPos=position;
if (tailPos!=-1) links[tailPos].next=position;
links[position].next=-1;
links[position].prev=tailPos;
tailPos=position;
}
UNIT_DEFINITION getUnit(int unitID) {
int position=getUnitPosition(unitID,true);
if (units[position].unitID==-1) {
STRING_LOGGER("Unit not Found");
}
return units[position].unitdef;
}
UNIT_DEFINITION removeUnit(int unitID) {
int position=getUnitPosition(unitID,true);
UNIT_DEFINITION r=units[position].unitdef;
if (units[position].unitID!=-1) --size;
else {
STRING_LOGGER("Removing non existant unit");
}
if (units[(position+1)%MAX_UNIT].unitID==-1) {
units[position].unitID=-1;
}else {
units[position].unitID=-1;
}
units[position].unitdef=INVALID_UNIT_DEFINITION;
int prev=links[position].prev;
int next=links[position].next;
if (prev==-1) {
if (next==-1) { //was the only one
tailPos=-1;
headPos=-1;
} else { //was the head
links[next].prev=-1;
headPos=next;
}
} else {
if (next==-1) { //was the tail
links[prev].next=-1;
tailPos=prev;
} else { //in the middle
links[next].prev=prev;
links[prev].next=next;
}
}
return r;
}
/**
* fast iteator usage:
* unit_iterator ui=map.getIterator()
* while (ui.hasNext()) {
* unitMap m=ui.next();
* int unitID=m.unitID;
* UNIT_DEFINITION def=m.unitdef;
* //blah blah
* }
*/
class unit_iterator {
protected:
int current;
doubleLink *links;
unitMap *units;
unit_iterator() {
current=-1;
}
public:
unit_iterator(unitMap *units,doubleLink *links,int headPos) {
this->units=units;
this->links=links;
current=headPos;
}
/**
* true if there is another element avaiable
*/
bool hasNext() {
if (current==-1)return false;
return true;
};
/**
* return the current element and increment the counter
*/
unitMap &next() {
unitMap &p=units[current];
current=links[current].next;
return p;
};
};
class thread_safe_unit_iterator : public unit_iterator {
public:
thread_safe_unit_iterator(unitMap *units,doubleLink *links,int headPos):unit_iterator() {
memcpy(this->units,units,sizeof(unitMap)*(MAX_UNIT));
memcpy(this->links,links,sizeof(links)*(MAX_UNIT));
current=headPos;
}
};
/**
* Returns a fast unit iterator
* fast iteator usage:
* unit_iterator ui=map.getIterator()
* while (ui.hasNext()) {
* unitMap m=ui.next();
* int unitID=m.unitID;
* UNIT_DEFINITION def=m.unitdef;
* //blah blah
* }
*
* If the map is modified during the existance of
* the iterator, undefined behaviour may occour.
*/
unit_iterator &getIterator() {
return (*new unit_iterator(units,links,headPos));
};
/**
* thread safe version of the iterator.
* same usage, but allows modification of the map.
* the unit returned are the ones that were present
* at the moment of the function call.
*
* note that while the iterator IS thread safe, the
* iteration constructor (this function) it is NOT.
*
* while the iteration speed is the same of the other,
* the constructor present a little overhead for the
* replicating of the info.
*/
unit_iterator &getTSIterator() {
return (*new thread_safe_unit_iterator(units,links,headPos));
};
private:
int getUnitPosition(int unitID,bool consiterTombstoneFull){
int position=(unitID)%MAX_UNIT;
while(units[position].unitID!=unitID) {
if (units[position].unitID==-1) return position;
if (!consiterTombstoneFull) if(units[position].unitID==-2) return position;
++position;
if (position==MAX_UNIT) {position=0;}
};
return position;
}
};
#endif
