My implementation uses a hash-function to locate the start of a "bitmap" which describes where to find all the keys with a given hash that reside in the hash-map. Now, due to the nature of the LSL's lists this implementation is a far-cry from the O(1) efficiency characteristic of hash-maps, indeed it's around 5 times slower or worse that using llListFindList followed by llList2List to pull out an entry.
But, here it is for people to peer and be horrified by:
CODE
integer hashSize = 0;
integer hashMaxEntries = 0;
integer hashBitmapWidth = 0;
list hashBitmap = [];
list hashBucket = [];
list hashValues = [];
hashInit(integer size, integer maxEntries) {
hashBitmap = hashBucket = hashValues = [];
hashSize = size;
hashMaxEntries = maxEntries;
hashBitmapWidth = llCeil((float)maxEntries / 32.0);
list l = []; integer i = 0;
while ((i++) < hashBitmapWidth) l += [0];
while ((--size) >= 0) hashBitmap += l;
}
hashToggleBit(integer bit, integer start) {
integer index = start + (bit / 32);
bit = bit % 32;
hashBitmap = llListReplaceList(
hashBitmap,
[llList2Integer(hashBitmap, index) ^ (1 << bit)],
index,
index
);
}
integer hashGetIndex(list k) {
integer hash = llGetListEntryType(k, 0);
if (hash == TYPE_INTEGER) hash = llList2Integer(k, 0);
else if (hash == TYPE_STRING) hash = hashString(llList2String(k, 0));
else if (hash == TYPE_KEY) hash = hashKey(llList2Key(k, 0));
else if (hash == TYPE_FLOAT) hash = hashFloat(llList2Float(k, 0));
else if (hash == TYPE_VECTOR) hash = hashVector(llList2Vector(k, 0));
else if (hash == TYPE_ROTATION) hash = hashRotation(llList2Rot(k, 0));
hash = (hash % hashSize) * hashBitmapWidth;
if (hash < 0) return -hash;
return hash;
}
integer hashFindKey(integer start, list k) {
integer word = 0; integer j = 0;
integer bit = 0; integer offset = 0; integer pos = 0;
integer found = FALSE;
integer i = start;
integer end = start + hashBitmapWidth;
for (; i < end; ++i) {
word = llList2Integer(hashBitmap, i);
if (word != 0) {
bit = 1;
for (j = 0; j < 32; ++j) {
if (word & bit) {
pos = offset + j;
if (!llListFindList(
llList2List(hashBucket, pos, pos), k)) {
found = TRUE;
jump break;
}
}
bit = bit << 1;
}
}
offset += 32;
}
@break;
if (found) return pos;
return -1;
}
// Puts v into the hash-map under the key k
list hashPut(list k, list v) {
integer index = hashGetIndex(k);
integer pos = hashFindKey(index, k);
if (pos >= 0) {
list old = llList2List(hashValues, pos, pos);
hashValues = llListReplaceList(hashValues, llList2List(v, 0, 0), pos, pos);
return old;
} else {
integer size = (hashBucket != []);
if (size >= hashMaxEntries) return ["Error", "HashMap is full"];
hashToggleBit(size, index);
hashBucket += k;
hashValues += v;
return [];
}
}
list hashGet(list k) {
integer pos = hashFindKey(hashGetIndex(k), k);
if (pos >= 0) return llList2List(hashValues, pos, pos);
return [];
}
list hashRemove(list k) {
integer index = hashGetIndex(k);
integer pos = hashFindKey(index, k);
if (pos >= 0) {
list old = llList2List(hashValues, pos, pos);
hashBucket = llDeleteSubList(hashBucket, pos, pos);
hashValues = llDeleteSubList(hashValues, pos, pos);
integer length = (hashBitmapWidth - 1);
if (pos == ((hashBucket != []) - 1)) // Lucky us! It's the last entry!
hashToggleBit(pos, index);
else { // Crap, need to fix all bitmaps
integer i = 0; integer start = 0; integer end = 0;
integer entry = pos / 32; integer bit = pos % 32;
integer j = 0; integer word = 0; integer carry = 0;
list newBitmap = []; list bitmap = [];
for (; i < hashSize; ++i) {
start = i * hashBitmapWidth;
end = start + length;
bitmap = llList2List(hashBitmap, start, end);
newBitmap = [];
// Shift upper values
for (j = length; j > entry; --j) {
carry = word & 1;
word = word >> 1;
newBitmap = [word] + newBitmap;
}
// Shift entry
word = llList2Integer(bitmap, entry);
j = word & ((1 << bit) - 1); // Preserve lower-end
word = (carry << 31) | ((word >> 1) & 0x7FFFFFFF) | j;
newBitmap = [word] + newBitmap;
// Copy remaining
if (entry > 0)
newBitmap = llList2List(bitmap, 0, entry - 1) + newBitmap;
hashBitmap = llListReplaceList(hashBitmap, newBitmap, start, end);
}
}
return old;
}
return [];
}
string hexc="0123456789ABCDEF";//faster
integer hashFloat(float input) {
// Modified by Haravikk Mistral from original "Float2Hex":
// Copyright Strife Onizuka, 2006-2007, LGPL,
// http://www.gnu.org/copyleft/lesser.html or (cc-by)
// http://creativecommons.org/licenses/by/3.0/
if(input != (integer)input) {
float unsigned = llFabs(input);
integer exponent = llFloor(llLog(unsigned) / 0.69314718055994530941723212145818);
integer mantissa = (integer)((unsigned / llPow(2., exponent -= ((exponent >> 31) | 1))) * 0x4000000);
integer index = (integer)(llLog(mantissa & -mantissa) / 0.69314718055994530941723212145818);
string str = "p" + (string)(exponent + index - 26);
mantissa = mantissa >> index;
do
str = llGetSubString(hexc, 15 & mantissa, 15 & mantissa) + str;
while(mantissa = mantissa >> 4);
if(input < 0)
return (integer)("-0x" + str);
return (integer)("0x" + str);
}
return (integer)llDeleteSubString((string)input,-7,-1);
}
integer hashVector(vector input) {
return hashFloat(input.x) ^ hashFloat(input.y) ^ hashFloat(input.z);
}
integer hashRotation(rotation input) {
return hashFloat(input.x) ^ hashFloat(input.y) ^ hashFloat(input.z) ^
hashFloat(input.s);
}
integer hashString(string input) {
return (integer)("0x" + llGetSubString(llMD5String(input, 0), 0, 7));
}
integer hashKey(key input) {
return hashString((string)input);
}
default {
state_entry() {
float time = 0.0; integer index;
integer i = 0; integer j = 0; integer count = 100;
integer size = 8; integer entries = 16;
for (; entries < 64; entries += 16) {
for (size = 8; size < 64; size += 8) {
hashInit(8, 16);
for (i = 0; i < entries; ++i)
hashPut(, [(string)i]);
llResetTime();
for (j = 0; j < count; ++j)
hashGet([j % entries]);
time = llGetTime();
llOwnerSay((string)(time / (float)count) + " per hashGet() on " + (string)entries + " entries in a hash-table of size " + (string)size);
llResetTime();
for (j = 0; j < count; ++j) {
index = llListFindList(hashBucket, [j % entries]);
llList2List(hashValues, index, index);
}
time = llGetTime();
llOwnerSay((string)(time / (float)count) + " per llList* on " + (string)entries + " entries in a hash-table of size " + (string)size);
}
}
}
}