Data Structures With Indexes
Update: This tutorial is about static data structures. For dynamic type safe storage in SourcePawn see my
Object Library.
Basics
We often need to store data in a structured manner. A way to get a simple data structure is using arrays and enums. That way we can sort of get small value objects (structs). Have a look at the following code:
PHP Code:
// Data structure definition. Elements can be tagged. Arrays and strings
// can also be used.
enum MyDataStruct
{
Data_SomeVar,
bool:Data_SomeBool,
Float:Data_SomeFloat,
String:Data_SomeString[32]
}
// Maximum number of objects to store. Not all indexes has to be used.
const MAX_OBJECTS = 20;
// Data. Note the use of MyDataStruct in the last dimension.
new MyObjects[MAx_OBJECTS][MyDataStruct];
// Number of objects.
new ObjectCount = 0;
TestCase()
{
// Creating a test object.
MyObjects[ObjectCount][Data_SomeVar] = 5;
MyObjects[ObjectCount][Data_SomeBool] = true;
MyObjects[ObjectCount][Data_SomeFloat] = 3.14159265;
strcopy(MyObjects[ObjectCount][Data_SomeString], 32, "Test string.");
// After each insertion the counter should be updated.
ObjectCount++;
new var = MyObjects[0][Data_SomeVar];
new bool:boolVar = MyObjects[0][Data_SomeBool];
new Float:floatVar = MyObjects[0][Data_SomeFloat];
new String:stringVar[32];
strcopy(stringVar, sizeof(stringVar), MyObjects[0][Data_SomeString];
}
The object reference is the index (first dimension) in the MyObjectArray and the object data is values in the second dimension.
The advantage with this structure is that it's
really fast for direct lookup on values. It's also easy to loop through objects. The compiler also does tag checking so you get some sort of type safety. How fast you can search through it depends on how you order stuff, but there's a trick to get fast search too, which is explained later below.
Obviously it will use a constant amount of memory, whether all indexes is used or not. So this structure is not suitable for large amounts of indexes. If you get above 500-1000 entries you should reconsider your design - or use a database. If the structure itself is small you need to use really many indexes to spend just a few KB of RAM. But this is perfectly suitable for smaller amounts like storing a player class data or cached client settings.
Indexes - Looking up stuff fast
With many objects a linear search in a loop might be too slow, especially if you have to search for several objects in the same game event.
Usually you look up objects by a certain value, like a name. To speed up this search ADT tries can be used as indexes. A trie is a dynamic structure that maps a key (string) to a value. Its data is structured in a way that we can get very fast lookup on keys.
When creating a object we can use the object name (or other string value) as the key and set the value to the object index in the array. To find a object, all you need to do is to look it up by its name and you quickly get the object index in return.
Again this will result in some redundancy and more memory usage but it's usually just a matter of a few KB, which is a lot of data if you just store numbers and short strings.
PHP Code:
// Example of player class attributes.
enum ClassAttributes
{
String:Class_Name[32],
Float:Class_Speed,
Class_OtherAttribute
}
const MAX_CLASSES = 20;
// Class data.
new ClassData[MAX_CLASSES][ClassAttributes];
// Number of classes.
new ClassCount = 0;
// Handle to trie with class name index.
new Handle:ClassNameIndex;
CreateClass(const String:name[], Float:speed, otherAttribute)
{
// Set class data.
strcopy(ClassData[ClassCount][Class_Name], 32, name);
ClassData[ClassCount][Class_Speed] = speed;
ClassData[ClassCount][Class_OtherAttribute] = otherAttribute;
// Add name to index.
SetTrieValue(ClassNameIndex, name, ClassCount);
ClassCount++;
}
FindClass(const String:name[])
{
new classIndex = -1;
// Lookup the class name in the trie index. The value is inserted into the
// classIndex variable.
if (!GetTrieValue(ClassNameIndex, name, classIndex))
{
// Not found.
return -1;
}
return classIndex;
}
TestCase()
{
// The trie should be created somewhere, but we do it here to make
// it simple.
ClassNameIndex = CreateTrie();
// Create some test classes.
CreateClass("test class", 250, 2);
CreateClass("other", 400, 3);
CreateClass("third", 300, 6);
CreateClass("something", 200, 1);
// Find a class by name.
new theClass = FindClass("third");
// Check if found.
if (theClass >= 0)
{
// Found it. Do your stuff.
}
}
There's a similar tutorial in the AMX Mod X forum about enums and arrays:
http://forums.alliedmods.net/showthread.php?p=1319714
My tutorial is the SourcePawn version. It's the same concepts as the other one, but I figured this would be useful anyways. The other one didn't have my idea of using indexes.
__________________
Linear Mode
