ecere/containers: Map/CustomAVLTree optimizations

- Index with creation will not scan again to place new item
- Add/Find inner loop optimizations
- Free: Avoid rebalancing for each item

diff --git a/compiler/bootstrap/ecere/bootstrap/CustomAVLTree.c b/compiler/bootstrap/ecere/bootstrap/CustomAVLTree.c
index 5f7fdc9..2151d2c 100644 (file)
--- a/compiler/bootstrap/ecere/bootstrap/CustomAVLTree.c
+++ b/compiler/bootstrap/ecere/bootstrap/CustomAVLTree.c
@@ -481,6 +481,8 @@ extern long long __ecereNameSpace__ecere__com__eClass_GetProperty(struct __ecere
 
 extern void __ecereNameSpace__ecere__com__eClass_SetProperty(struct __ecereNameSpace__ecere__com__Class * _class, const char *  name, long long value);
 
+extern void __ecereNameSpace__ecere__com__eEnum_AddFixedValue(struct __ecereNameSpace__ecere__com__Class * _class, const char *  string, long long value);
+
 extern struct __ecereNameSpace__ecere__com__Property * __ecereNameSpace__ecere__com__eClass_AddProperty(struct __ecereNameSpace__ecere__com__Class * _class, const char *  name, const char *  dataType, void *  setStmt, void *  getStmt, int declMode);
 
 extern void __ecereNameSpace__ecere__com__eClass_DoneAddingTemplateParameters(struct __ecereNameSpace__ecere__com__Class * base);
@@ -714,32 +716,33 @@ char *  parsedCommand;
 struct __ecereNameSpace__ecere__com__NameSpace systemNameSpace;
 } ecere_gcc_struct;
 
+static struct __ecereNameSpace__ecere__com__Class * __ecereClass___ecereNameSpace__ecere__com__AddSide;
+
 static struct __ecereNameSpace__ecere__com__Class * __ecereClass___ecereNameSpace__ecere__com__AVLNode;
 
 static struct __ecereNameSpace__ecere__com__Class * __ecereClass___ecereNameSpace__ecere__com__CustomAVLTree;
 
 struct __ecereNameSpace__ecere__com__AVLNode * __ecereMethod___ecereNameSpace__ecere__com__AVLNode_Find(struct __ecereNameSpace__ecere__com__AVLNode * this, struct __ecereNameSpace__ecere__com__Class * Tclass, const uint64 key)
 {
-while(this)
-{
-int result;
-unsigned char * a, * b;
+unsigned char * a;
+unsigned int reference = 0;
+unsigned int offset = 0;
+int t = Tclass->type;
+int (* onCompare)(void *, void *, void *) = (void *)Tclass->_vTbl[__ecereVMethodID_class_OnCompare];
 
-if((Tclass->type == 1000 && !Tclass->byValueSystemClass) || Tclass->type == 2 || Tclass->type == 4 || Tclass->type == 3)
+reference = (t == 1000 && !Tclass->byValueSystemClass) || t == 2 || t == 4 || t == 3;
+offset = __ENDIAN_PAD(Tclass->typeSize);
+a = reference ? ((unsigned char *)&key) + offset : (unsigned char *)(uintptr_t)key;
+if(t == 1)
 {
-a = (unsigned char *)&key;
-a += __ENDIAN_PAD(Tclass->typeSize);
+reference = 1;
+offset = __ENDIAN_PAD(sizeof(void *));
 }
-else
-a = (unsigned char *)(uintptr_t)key;
-if((Tclass->type == 1000 && !Tclass->byValueSystemClass) || Tclass->type == 2 || Tclass->type == 4 || Tclass->type == 3 || Tclass->type == 1)
+while(this)
 {
-b = (unsigned char *)&this->key;
-b += __ENDIAN_PAD((Tclass->type == 1) ? sizeof(void *) : Tclass->typeSize);
-}
-else
-b = (unsigned char *)(uintptr_t)(uint64)(this->key);
-result = ((int (*)(void *, void *, void *))(void *)Tclass->_vTbl[__ecereVMethodID_class_OnCompare])(Tclass, a, b);
+unsigned char * b = reference ? ((unsigned char *)&this->key) + offset : (unsigned char *)(uintptr_t)(uint64)(this->key);
+int result = onCompare(Tclass, a, b);
+
 if(result < 0)
 this = this->left;
 else if(result > 0)
@@ -754,6 +757,8 @@ extern struct __ecereNameSpace__ecere__com__Class * __ecereClass___ecereNameSpac
 
 extern struct __ecereNameSpace__ecere__com__Class * __ecereClass_uint64;
 
+extern struct __ecereNameSpace__ecere__com__Class * __ecereClass_uint;
+
 extern struct __ecereNameSpace__ecere__com__Class * __ecereClass___ecereNameSpace__ecere__com__Instance;
 
 extern struct __ecereNameSpace__ecere__com__Class * __ecereClass___ecereNameSpace__ecere__com__Module;
@@ -838,55 +843,46 @@ __attribute__((unused)) struct __ecereNameSpace__ecere__com__CustomAVLTree * __e
 return (struct __ecereNameSpace__ecere__com__IteratorPointer *)((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(value)));
 }
 
-unsigned int __ecereMethod___ecereNameSpace__ecere__com__AVLNode_Add(struct __ecereNameSpace__ecere__com__AVLNode * this, struct __ecereNameSpace__ecere__com__Class * Tclass, struct __ecereNameSpace__ecere__com__AVLNode * node)
+unsigned int __ecereMethod___ecereNameSpace__ecere__com__AVLNode_Add(struct __ecereNameSpace__ecere__com__AVLNode * this, struct __ecereNameSpace__ecere__com__Class * Tclass, struct __ecereNameSpace__ecere__com__AVLNode * node, int addSide)
 {
+int t;
+int (* onCompare)(void *, void *, void *);
+unsigned int offset = 0;
+unsigned int reference = 0;
+unsigned char * a;
+
 if(!Tclass)
 Tclass = __ecereClass_uint64;
+t = Tclass->type;
+onCompare = (void *)Tclass->_vTbl[__ecereVMethodID_class_OnCompare];
+if((t == 1000 && !Tclass->byValueSystemClass) || t == 2 || t == 4 || t == 3 || t == 1)
+{
+reference = 1;
+offset = __ENDIAN_PAD((t == 1) ? sizeof(void *) : Tclass->typeSize);
+}
+a = reference ? ((unsigned char *)&node->key + offset) : ((unsigned char *)(uintptr_t)(uint64)(node->key));
 while(1)
 {
 int result;
-unsigned char * a, * b;
 
-if((Tclass->type == 1000 && !Tclass->byValueSystemClass) || Tclass->type == 2 || Tclass->type == 4 || Tclass->type == 3 || Tclass->type == 1)
-{
-a = (unsigned char *)&node->key;
-b = (unsigned char *)&this->key;
-a += __ENDIAN_PAD((Tclass->type == 1) ? sizeof(void *) : Tclass->typeSize);
-b += __ENDIAN_PAD((Tclass->type == 1) ? sizeof(void *) : Tclass->typeSize);
-}
+if(addSide)
+result = addSide;
 else
 {
-a = (unsigned char *)(uintptr_t)(uint64)(node->key);
-b = (unsigned char *)(uintptr_t)(uint64)(this->key);
+unsigned char * b = reference ? ((unsigned char *)&this->key + offset) : (unsigned char *)(uintptr_t)(uint64)(this->key);
+
+result = onCompare(Tclass, a, b);
 }
-result = ((int (*)(void *, void *, void *))(void *)Tclass->_vTbl[__ecereVMethodID_class_OnCompare])(Tclass, a, b);
 if(!result)
-{
 return 0;
-}
 else if(result > 0)
 {
 if(this->right)
 this = this->right;
 else
 {
-node->parent = this;
 this->right = node;
-node->depth = 0;
-{
-struct __ecereNameSpace__ecere__com__AVLNode * n;
-
-for(n = this; n; n = n->parent)
-{
-int __simpleStruct0, __simpleStruct1;
-int newDepth = (__simpleStruct0 = n->left ? (n->left->depth + 1) : 0, __simpleStruct1 = n->right ? (n->right->depth + 1) : 0, (__simpleStruct0 > __simpleStruct1) ? __simpleStruct0 : __simpleStruct1);
-
-if(newDepth == n->depth)
 break;
-n->depth = newDepth;
-}
-}
-return 1;
 }
 }
 else
@@ -895,8 +891,12 @@ if(this->left)
 this = this->left;
 else
 {
-node->parent = this;
 this->left = node;
+break;
+}
+}
+}
+node->parent = this;
 node->depth = 0;
 {
 struct __ecereNameSpace__ecere__com__AVLNode * n;
@@ -913,8 +913,74 @@ n->depth = newDepth;
 }
 return 1;
 }
+
+struct __ecereNameSpace__ecere__com__AVLNode * __ecereMethod___ecereNameSpace__ecere__com__AVLNode_FindEx(struct __ecereNameSpace__ecere__com__AVLNode * this, struct __ecereNameSpace__ecere__com__Class * Tclass, const uint64 key, struct __ecereNameSpace__ecere__com__AVLNode ** addTo, int * addSide)
+{
+unsigned char * a;
+unsigned int reference = 0;
+unsigned int offset = 0;
+int t = Tclass->type;
+int (* onCompare)(void *, void *, void *) = (void *)Tclass->_vTbl[__ecereVMethodID_class_OnCompare];
+
+reference = (t == 1000 && !Tclass->byValueSystemClass) || t == 2 || t == 4 || t == 3;
+offset = __ENDIAN_PAD(Tclass->typeSize);
+a = reference ? ((unsigned char *)&key) + offset : (unsigned char *)(uintptr_t)key;
+if(t == 1)
+{
+reference = 1;
+offset = __ENDIAN_PAD(sizeof(void *));
+}
+if(Tclass == __ecereClass_uint)
+{
+unsigned int ia = *(unsigned int *)a;
+
+while(this)
+{
+unsigned int ib = *(unsigned int *)(reference ? ((unsigned char *)&this->key) + offset : (unsigned char *)(uintptr_t)(uint64)(this->key));
+int result = ia > ib ? 1 : ia < ib ? -1 : 0;
+
+if(result)
+{
+struct __ecereNameSpace__ecere__com__AVLNode * node = result < 0 ? this->left : this->right;
+
+if(!node)
+{
+if(addTo)
+*addTo = this;
+if(addSide)
+*addSide = (int)result;
+}
+this = node;
+}
+else
+break;
+}
+}
+else
+{
+while(this)
+{
+unsigned char * b = reference ? ((unsigned char *)&this->key) + offset : (unsigned char *)(uintptr_t)(uint64)(this->key);
+int result = onCompare(Tclass, a, b);
+
+if(result)
+{
+struct __ecereNameSpace__ecere__com__AVLNode * node = result < 0 ? this->left : this->right;
+
+if(!node)
+{
+if(addTo)
+*addTo = this;
+if(addSide)
+*addSide = (int)result;
+}
+this = node;
+}
+else
+break;
 }
 }
+return this;
 }
 
 void __ecereMethod___ecereNameSpace__ecere__com__CustomAVLTree_Delete(struct __ecereNameSpace__ecere__com__Instance * this, struct __ecereNameSpace__ecere__com__IteratorPointer * _item)
@@ -931,11 +997,33 @@ void __ecereMethod___ecereNameSpace__ecere__com__CustomAVLTree_Free(struct __ece
 __attribute__((unused)) struct __ecereNameSpace__ecere__com__CustomAVLTree * __ecerePointer___ecereNameSpace__ecere__com__CustomAVLTree = (struct __ecereNameSpace__ecere__com__CustomAVLTree *)(this ? (((char *)this) + 0 + sizeof(struct __ecereNameSpace__ecere__com__Instance)) : 0);
 struct __ecereNameSpace__ecere__com__AVLNode * item;
 
-while((item = ((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(__ecerePointer___ecereNameSpace__ecere__com__CustomAVLTree->root)))))
+item = ((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(__ecerePointer___ecereNameSpace__ecere__com__CustomAVLTree->root)));
+while(item)
+{
+if(((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(item)))->left)
+{
+struct __ecereNameSpace__ecere__com__AVLNode * left = ((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(item)))->left;
+
+((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(item)))->left = (((void *)0));
+item = ((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(left)));
+}
+else if(((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(item)))->right)
+{
+struct __ecereNameSpace__ecere__com__AVLNode * right = ((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(item)))->right;
+
+((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(item)))->right = (((void *)0));
+item = ((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(right)));
+}
+else
 {
-((void (*)(struct __ecereNameSpace__ecere__com__Instance *, struct __ecereNameSpace__ecere__com__IteratorPointer * it))__ecereClass___ecereNameSpace__ecere__com__CustomAVLTree->_vTbl[__ecereVMethodID___ecereNameSpace__ecere__com__Container_Remove])(this, (void *)(((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(item)))));
+struct __ecereNameSpace__ecere__com__AVLNode * parent = ((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(item)))->parent;
+
 (((void (* )(void *  _class, void *  data))((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[3].__anon1.__anon1.dataTypeClass->_vTbl[__ecereVMethodID_class_OnFree])(((struct __ecereNameSpace__ecere__com__Instance * )(char * )this)->_class->templateArgs[3].__anon1.__anon1.dataTypeClass, ((void * )((uintptr_t)(item)))), item = 0);
+item = ((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(parent)));
+}
 }
+__ecerePointer___ecereNameSpace__ecere__com__CustomAVLTree->root = (((void *)0));
+__ecerePointer___ecereNameSpace__ecere__com__CustomAVLTree->count = 0;
 }
 
 struct __ecereNameSpace__ecere__com__AVLNode * __ecereMethod___ecereNameSpace__ecere__com__CustomAVLTree_GetAtPosition(struct __ecereNameSpace__ecere__com__Instance * this, const uint64 pos, unsigned int create, unsigned int * justAdded)
@@ -971,7 +1059,30 @@ if(!Tclass)
 {
 Tclass = ((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[3].__anon1.__anon1.dataTypeClass->templateArgs[0].__anon1.__anon1.dataTypeClass = __ecereNameSpace__ecere__com__eSystem_FindClass(((struct __ecereNameSpace__ecere__com__Module *)(((char *)__thisModule + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->application, ((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[3].__anon1.__anon1.dataTypeClass->templateArgs[0].__anon1.__anon1.dataTypeString);
 }
-if(__ecereMethod___ecereNameSpace__ecere__com__AVLNode_Add(((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(__ecerePointer___ecereNameSpace__ecere__com__CustomAVLTree->root))), Tclass, ((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(node)))))
+if(__ecereMethod___ecereNameSpace__ecere__com__AVLNode_Add(((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(__ecerePointer___ecereNameSpace__ecere__com__CustomAVLTree->root))), Tclass, ((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(node))), (int)0))
+__ecerePointer___ecereNameSpace__ecere__com__CustomAVLTree->root = __ecereMethod___ecereNameSpace__ecere__com__AVLNode_Rebalance(((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(node))));
+else
+return (((void *)0));
+}
+__ecerePointer___ecereNameSpace__ecere__com__CustomAVLTree->count++;
+return (struct __ecereNameSpace__ecere__com__IteratorPointer *)((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(node)));
+}
+
+struct __ecereNameSpace__ecere__com__IteratorPointer * __ecereMethod___ecereNameSpace__ecere__com__CustomAVLTree_AddEx(struct __ecereNameSpace__ecere__com__Instance * this, uint64 node, uint64 addNode, int addSide)
+{
+__attribute__((unused)) struct __ecereNameSpace__ecere__com__CustomAVLTree * __ecerePointer___ecereNameSpace__ecere__com__CustomAVLTree = (struct __ecereNameSpace__ecere__com__CustomAVLTree *)(this ? (((char *)this) + 0 + sizeof(struct __ecereNameSpace__ecere__com__Instance)) : 0);
+
+if(!((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(__ecerePointer___ecereNameSpace__ecere__com__CustomAVLTree->root))))
+__ecerePointer___ecereNameSpace__ecere__com__CustomAVLTree->root = ((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(node)));
+else
+{
+struct __ecereNameSpace__ecere__com__Class * Tclass = ((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[3].__anon1.__anon1.dataTypeClass->templateArgs[0].__anon1.__anon1.dataTypeClass;
+
+if(!Tclass)
+{
+Tclass = ((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[3].__anon1.__anon1.dataTypeClass->templateArgs[0].__anon1.__anon1.dataTypeClass = __ecereNameSpace__ecere__com__eSystem_FindClass(((struct __ecereNameSpace__ecere__com__Module *)(((char *)__thisModule + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->application, ((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[3].__anon1.__anon1.dataTypeClass->templateArgs[0].__anon1.__anon1.dataTypeString);
+}
+if(__ecereMethod___ecereNameSpace__ecere__com__AVLNode_Add(((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(addNode))), Tclass, ((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(node))), addSide))
 __ecerePointer___ecereNameSpace__ecere__com__CustomAVLTree->root = __ecereMethod___ecereNameSpace__ecere__com__AVLNode_Rebalance(((struct __ecereNameSpace__ecere__com__AVLNode *)((uintptr_t)(node))));
 else
 return (((void *)0));
@@ -994,6 +1105,12 @@ struct __ecereNameSpace__ecere__com__ClassTemplateArgument __simpleStruct0 =
 };
 struct __ecereNameSpace__ecere__com__Class __attribute__((unused)) * class;
 
+class = __ecereNameSpace__ecere__com__eSystem_RegisterClass(4, "ecere::com::AddSide", "int", 0, 0, (void *)0, (void *)0, module, 2, 1);
+if(((struct __ecereNameSpace__ecere__com__Module *)(((char *)module + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->application == ((struct __ecereNameSpace__ecere__com__Module *)(((char *)__thisModule + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->application && class)
+__ecereClass___ecereNameSpace__ecere__com__AddSide = class;
+__ecereNameSpace__ecere__com__eEnum_AddFixedValue(class, "compare", 0);
+__ecereNameSpace__ecere__com__eEnum_AddFixedValue(class, "left", -1);
+__ecereNameSpace__ecere__com__eEnum_AddFixedValue(class, "right", 1);
 class = __ecereNameSpace__ecere__com__eSystem_RegisterClass(5, "ecere::com::AVLNode", "ecere::com::IteratorPointer", sizeof(struct __ecereNameSpace__ecere__com__AVLNode), 0, (void *)0, (void *)0, module, 4, 1);
 if(((struct __ecereNameSpace__ecere__com__Module *)(((char *)module + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->application == ((struct __ecereNameSpace__ecere__com__Module *)(((char *)__thisModule + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->application && class)
 __ecereClass___ecereNameSpace__ecere__com__AVLNode = class;

diff --git a/compiler/bootstrap/ecere/bootstrap/Map.c b/compiler/bootstrap/ecere/bootstrap/Map.c
index e2841d1..0687a1c 100644 (file)
--- a/compiler/bootstrap/ecere/bootstrap/Map.c
+++ b/compiler/bootstrap/ecere/bootstrap/Map.c
@@ -267,6 +267,8 @@ int __ecereVMethodID___ecereNameSpace__ecere__com__Container_Remove;
 
 int __ecereVMethodID___ecereNameSpace__ecere__com__Container_Find;
 
+struct __ecereNameSpace__ecere__com__IteratorPointer * __ecereMethod___ecereNameSpace__ecere__com__CustomAVLTree_AddEx(struct __ecereNameSpace__ecere__com__Instance * this, uint64 node, uint64 addNode, int addSide);
+
 int __ecereVMethodID___ecereNameSpace__ecere__com__Container_RemoveAll;
 
 int __ecereVMethodID___ecereNameSpace__ecere__com__Container_GetFirst;
@@ -322,6 +324,8 @@ struct __ecereNameSpace__ecere__com__AVLNode * __ecereProp___ecereNameSpace__ece
 
 struct __ecereNameSpace__ecere__com__AVLNode * __ecereMethod___ecereNameSpace__ecere__com__AVLNode_Find(struct __ecereNameSpace__ecere__com__AVLNode * this, struct __ecereNameSpace__ecere__com__Class * Tclass, const uint64 key);
 
+struct __ecereNameSpace__ecere__com__AVLNode * __ecereMethod___ecereNameSpace__ecere__com__AVLNode_FindEx(struct __ecereNameSpace__ecere__com__AVLNode * this, struct __ecereNameSpace__ecere__com__Class * Tclass, const uint64 key, struct __ecereNameSpace__ecere__com__AVLNode **  addTo, int *  addSide);
+
 struct __ecereNameSpace__ecere__com__MapNode * __ecereProp___ecereNameSpace__ecere__com__MapNode_Get_prev(struct __ecereNameSpace__ecere__com__MapNode * this)
 {
 return (struct __ecereNameSpace__ecere__com__MapNode *)__ecereProp___ecereNameSpace__ecere__com__AVLNode_Get_prev((void *)(this));
@@ -675,28 +679,11 @@ __internal_ClassInst ? __internal_ClassInst->_vTbl : __ecereClass___ecereNameSpa
 __ecereNameSpace__ecere__com__eInstance_FireSelfWatchers(this, __ecereProp___ecereNameSpace__ecere__com__Map_mapSrc), __ecereNameSpace__ecere__com__eInstance_FireSelfWatchers(this, __ecerePropM___ecereNameSpace__ecere__com__Map_mapSrc);
 }
 
-void __ecereMethod___ecereNameSpace__ecere__com__Map_Free(struct __ecereNameSpace__ecere__com__Instance * this)
-{
-struct __ecereNameSpace__ecere__com__MapNode * node;
-
-while((node = (void *)(((struct __ecereNameSpace__ecere__com__CustomAVLTree *)(((char *)this + 0 + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->root)))
-{
-struct __ecereNameSpace__ecere__com__MapNode * n = node;
-
-if(((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[5].__anon1.__anon1.dataTypeClass->type == 1)
-n = (struct __ecereNameSpace__ecere__com__MapNode *)(((unsigned char *)node) + ((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[5].__anon1.__anon1.dataTypeClass->structSize - sizeof node->key);
-(((void (* )(void *  _class, void *  data))((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[6].__anon1.__anon1.dataTypeClass->_vTbl[__ecereVMethodID_class_OnFree])(((struct __ecereNameSpace__ecere__com__Instance * )(char * )this)->_class->templateArgs[6].__anon1.__anon1.dataTypeClass, ((void * )((uintptr_t)(__ecereProp___ecereNameSpace__ecere__com__MapNode_Get_value(n))))), __ecereProp___ecereNameSpace__ecere__com__MapNode_Set_value(n, 0));
-((void (*)(struct __ecereNameSpace__ecere__com__Instance *, struct __ecereNameSpace__ecere__com__IteratorPointer * it))__extension__ ({
-struct __ecereNameSpace__ecere__com__Instance * __internal_ClassInst = this;
-
-__internal_ClassInst ? __internal_ClassInst->_vTbl : __ecereClass___ecereNameSpace__ecere__com__Map->_vTbl;
-})[__ecereVMethodID___ecereNameSpace__ecere__com__Container_Remove])(this, (void *)(node));
-}
-}
-
 struct __ecereNameSpace__ecere__com__MapNode * __ecereMethod___ecereNameSpace__ecere__com__Map_GetAtPosition(struct __ecereNameSpace__ecere__com__Instance * this, const uint64 pos, unsigned int create, unsigned int * justAdded)
 {
-struct __ecereNameSpace__ecere__com__MapNode * node = (void *)(((struct __ecereNameSpace__ecere__com__CustomAVLTree *)(((char *)this + 0 + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->root ? __ecereMethod___ecereNameSpace__ecere__com__AVLNode_Find(((struct __ecereNameSpace__ecere__com__CustomAVLTree *)(((char *)this + 0 + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->root, ((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[5].__anon1.__anon1.dataTypeClass, pos) : (((void *)0)));
+struct __ecereNameSpace__ecere__com__AVLNode * addNode = (((void *)0));
+int addSide = 0;
+struct __ecereNameSpace__ecere__com__MapNode * node = (void *)(((struct __ecereNameSpace__ecere__com__CustomAVLTree *)(((char *)this + 0 + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->root ? __ecereMethod___ecereNameSpace__ecere__com__AVLNode_FindEx(((struct __ecereNameSpace__ecere__com__CustomAVLTree *)(((char *)this + 0 + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->root, ((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[5].__anon1.__anon1.dataTypeClass, pos, &addNode, &addSide) : (((void *)0)));
 
 if(!node && create)
 {
@@ -725,7 +712,7 @@ if((Tclass->type == 1000 && !Tclass->byValueSystemClass) || Tclass->type == 2 ||
 onCopy(Tclass, (unsigned char *)&node->key + __ENDIAN_PAD(Tclass->typeSize), (unsigned char *)((char *)&pos + __ENDIAN_PAD(((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[5].__anon1.__anon1.dataTypeClass->typeSize)) + __ENDIAN_PAD(Tclass->typeSize));
 else
 onCopy(Tclass, (unsigned char *)&node->key + __ENDIAN_PAD(sizeof(void *)), (void *)(uintptr_t)pos);
-((struct __ecereNameSpace__ecere__com__IteratorPointer * (*)(struct __ecereNameSpace__ecere__com__Instance *, uint64 value))__ecereClass___ecereNameSpace__ecere__com__CustomAVLTree->_vTbl[__ecereVMethodID___ecereNameSpace__ecere__com__Container_Add])(this, (uint64)(uintptr_t)node);
+__ecereMethod___ecereNameSpace__ecere__com__CustomAVLTree_AddEx(this, (uint64)node, (uint64)addNode, addSide);
 if(justAdded)
 *justAdded = 1;
 }
@@ -797,6 +784,45 @@ __ecereClass___ecereNameSpace__ecere__com__MapNode->Destructor ? __ecereClass___
 }) : 0), node = 0);
 }
 
+void __ecereMethod___ecereNameSpace__ecere__com__Map_Free(struct __ecereNameSpace__ecere__com__Instance * this)
+{
+struct __ecereNameSpace__ecere__com__MapNode * node = (void *)(((struct __ecereNameSpace__ecere__com__CustomAVLTree *)(((char *)this + 0 + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->root);
+size_t offset = ((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[5].__anon1.__anon1.dataTypeClass->type == 1 ? ((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[5].__anon1.__anon1.dataTypeClass->structSize - sizeof node->key : 0;
+
+while(node)
+{
+if(node->left)
+{
+struct __ecereNameSpace__ecere__com__MapNode * left = node->left;
+
+node->left = (((void *)0));
+node = left;
+}
+else if(node->right)
+{
+struct __ecereNameSpace__ecere__com__MapNode * right = node->right;
+
+node->right = (((void *)0));
+node = right;
+}
+else
+{
+struct __ecereNameSpace__ecere__com__MapNode * parent = node->parent;
+struct __ecereNameSpace__ecere__com__MapNode * n = (struct __ecereNameSpace__ecere__com__MapNode *)((unsigned char *)node + offset);
+
+(((void (* )(void *  _class, void *  data))((struct __ecereNameSpace__ecere__com__Instance *)(char *)this)->_class->templateArgs[6].__anon1.__anon1.dataTypeClass->_vTbl[__ecereVMethodID_class_OnFree])(((struct __ecereNameSpace__ecere__com__Instance * )(char * )this)->_class->templateArgs[6].__anon1.__anon1.dataTypeClass, ((void * )((uintptr_t)(__ecereProp___ecereNameSpace__ecere__com__MapNode_Get_value(n))))), __ecereProp___ecereNameSpace__ecere__com__MapNode_Set_value(n, 0));
+((node ? __extension__ ({
+void * __ecerePtrToDelete = (node);
+
+__ecereClass___ecereNameSpace__ecere__com__MapNode->Destructor ? __ecereClass___ecereNameSpace__ecere__com__MapNode->Destructor((void *)__ecerePtrToDelete) : 0, __ecereClass___ecereNameSpace__ecere__com__AVLNode->Destructor ? __ecereClass___ecereNameSpace__ecere__com__AVLNode->Destructor((void *)__ecerePtrToDelete) : 0, __ecereClass___ecereNameSpace__ecere__com__IteratorPointer->Destructor ? __ecereClass___ecereNameSpace__ecere__com__IteratorPointer->Destructor((void *)__ecerePtrToDelete) : 0, __ecereNameSpace__ecere__com__eSystem_Delete(__ecerePtrToDelete);
+}) : 0), node = 0);
+node = parent;
+}
+}
+((struct __ecereNameSpace__ecere__com__CustomAVLTree *)(((char *)this + 0 + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->root = (((void *)0));
+((struct __ecereNameSpace__ecere__com__CustomAVLTree *)(((char *)this + 0 + sizeof(struct __ecereNameSpace__ecere__com__Instance))))->count = 0;
+}
+
 void __ecereMethod___ecereNameSpace__ecere__com__Map_Copy(struct __ecereNameSpace__ecere__com__Instance * this, struct __ecereNameSpace__ecere__com__Instance * source)
 {
 struct __ecereNameSpace__ecere__com__IteratorPointer * i;

diff --git a/ecere/src/com/containers/CustomAVLTree.ec b/ecere/src/com/containers/CustomAVLTree.ec
index 2bd33f0..6938a5b 100644 (file)
--- a/ecere/src/com/containers/CustomAVLTree.ec
+++ b/ecere/src/com/containers/CustomAVLTree.ec
@@ -8,6 +8,8 @@ extern int __ecereVMethodID_class_OnCompare;
 extern int __ecereVMethodID_class_OnCopy;
 private:
 
+enum AddSide : int { compare = 0, left = -1, right = 1};
+
 public class AVLNode<class T> : IteratorPointer
 {
    class_fixed
@@ -85,53 +87,45 @@ private:
       delete this;
    }
 
-   bool Add(Class Tclass, thisclass node)
+   bool Add(Class Tclass, thisclass node, AddSide addSide)
    {
+      ClassType t;
+      int (* onCompare)(void *, void *, void *);
+      uint offset = 0;
+      bool reference = false;
+      byte * a;
+
       if(!Tclass)
          Tclass = class(uint64);
+      t = Tclass.type;
+      onCompare = (void *)Tclass._vTbl[__ecereVMethodID_class_OnCompare];
+      if((t == systemClass && !Tclass.byValueSystemClass) || t == bitClass || t == enumClass || t == unitClass || t == structClass)
+      {
+         reference = true;
+         offset = __ENDIAN_PAD((t == structClass) ? sizeof(void *) : Tclass.typeSize);
+      }
+      a = reference ? ((byte *)&node.key + offset) : ((byte *)(uintptr)node.key);
+
       while(true)
       {
-         // *** NEED COMPARISON OPERATOR SUPPORT HERE INVOKING OnCompare, AS WELL AS TYPE INFORMATION PASSED ***
          int result;
-         byte * a, * b;
-         if((Tclass.type == systemClass && !Tclass.byValueSystemClass) || Tclass.type == bitClass || Tclass.type == enumClass || Tclass.type == unitClass || Tclass.type == structClass)
-         {
-            a = (byte *)&node.key;
-            b = (byte *)&key;
-            a += __ENDIAN_PAD((Tclass.type == structClass) ? sizeof(void *) : Tclass.typeSize);
-            b += __ENDIAN_PAD((Tclass.type == structClass) ? sizeof(void *) : Tclass.typeSize);
-         }
+         if(addSide)
+            result = addSide;
          else
          {
-            a = (byte *)(uintptr)node.key;
-            b = (byte *)(uintptr)key;
+            byte * b = reference ? ((byte *)&key + offset) : (byte *)(uintptr)key;
+            result = onCompare(Tclass, a, b);
          }
-
-         result = ((int (*)(void *, void *, void *))(void *)Tclass._vTbl[__ecereVMethodID_class_OnCompare])(Tclass, a, b);
          if(!result)
-         {
             return false;
-         }
          else if(result > 0)
          {
             if(right)
                this = right;
             else
             {
-               node.parent = this;
                        right = node;
-               node.depth = 0;
-               {
-                  AVLNode<T> n;
-                  for(n = this; n; n = n.parent)
-                  {
-                     int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
-                     if(newDepth == n.depth)
-                        break;
-                     n.depth = newDepth;
-                  }
-               }
-               return true;
+               break;
                }
        }
          else
@@ -140,50 +134,48 @@ private:
                this = left;
             else
             {
-               node.parent = this;
                left = node;
-               node.depth = 0;
-               {
-                  AVLNode<T> n;
-                  for(n = this; n; n = n.parent)
-                  {
-                     int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
-                     if(newDepth == n.depth)
-                        break;
-                     n.depth = newDepth;
-                  }
-               }
-               return true;
+               break;
             }
        }
       }
+      node.parent = this;
+      node.depth = 0;
+      {
+         AVLNode<T> n;
+         for(n = this; n; n = n.parent)
+         {
+            int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
+            if(newDepth == n.depth)
+               break;
+            n.depth = newDepth;
+         }
+      }
+      return true;
    }
 
    public thisclass Find(Class Tclass, const T key)
    {
+      byte * a;
+      bool reference = false;
+      uint offset = 0;
+      ClassType t = Tclass.type;
+      int (* onCompare)(void *, void *, void *) = (void *)Tclass._vTbl[__ecereVMethodID_class_OnCompare];
+
+      reference = (t == systemClass && !Tclass.byValueSystemClass) || t == bitClass || t == enumClass || t == unitClass;
+      offset = __ENDIAN_PAD(Tclass.typeSize);
+      a = reference ? ((byte *)&(uint64)key) + offset : (byte *)(uintptr)key;
+      if(t == structClass)
+      {
+         reference = true;
+         offset = __ENDIAN_PAD(sizeof(void *));
+      }
+
       while(this)
       {
          // *** NEED COMPARISON OPERATOR SUPPORT HERE INVOKING OnCompare, AS WELL AS TYPE INFORMATION PASSED ***
-         int result;
-         byte * a, * b;
-         if((Tclass.type == systemClass && !Tclass.byValueSystemClass) || Tclass.type == bitClass || Tclass.type == enumClass || Tclass.type == unitClass)
-         {
-            a = (byte *)&(uint64)key;
-            a += __ENDIAN_PAD(Tclass.typeSize);
-         }
-         else
-            a = (byte *)(uintptr)key;
-
-         if((Tclass.type == systemClass && !Tclass.byValueSystemClass) || Tclass.type == bitClass || Tclass.type == enumClass || Tclass.type == unitClass || Tclass.type == structClass)
-         {
-            b = (byte *)&this.key;
-            b += __ENDIAN_PAD((Tclass.type == structClass) ? sizeof(void *) : Tclass.typeSize);
-         }
-         else
-            b = (byte *)(uintptr)this.key;
-
-         result = ((int (*)(void *, void *, void *))(void *)Tclass._vTbl[__ecereVMethodID_class_OnCompare])(Tclass, a, b);
-
+         byte * b = reference ? ((byte *)&this.key) + offset : (byte *)(uintptr)this.key;
+         int result = onCompare(Tclass, a, b);
          if(result < 0)
             this = left;
          else if(result > 0)
@@ -194,6 +186,67 @@ private:
       return this;
    }
 
+   thisclass FindEx(Class Tclass, const T key, AVLNode */*thisclass **/ addTo, AddSide * addSide)
+   {
+      byte * a;
+      bool reference = false;
+      uint offset = 0;
+      ClassType t = Tclass.type;
+      int (* onCompare)(void *, void *, void *) = (void *)Tclass._vTbl[__ecereVMethodID_class_OnCompare];
+
+      reference = (t == systemClass && !Tclass.byValueSystemClass) || t == bitClass || t == enumClass || t == unitClass;
+      offset = __ENDIAN_PAD(Tclass.typeSize);
+      a = reference ? ((byte *)&(uint64)key) + offset : (byte *)(uintptr)key;
+      if(t == structClass)
+      {
+         reference = true;
+         offset = __ENDIAN_PAD(sizeof(void *));
+      }
+
+      if(Tclass == class(uint))
+      {
+         uint ia = *(uint *)a;
+         while(this)
+         {
+            uint ib = *(uint *)(reference ? ((byte *)&this.key) + offset : (byte *)(uintptr)this.key);
+            int result = ia > ib ? 1 : ia < ib ? -1 : 0;
+            if(result)
+            {
+               thisclass node = result < 0 ? left : right;
+               if(!node)
+               {
+                  if(addTo) *addTo = this;
+                  if(addSide) *addSide = (AddSide)result;
+               }
+               this = node;
+            }
+            else
+               break;
+         }
+      }
+      else
+      {
+         while(this)
+         {
+            byte * b = reference ? ((byte *)&this.key) + offset : (byte *)(uintptr)this.key;
+            int result = onCompare(Tclass, a, b);
+            if(result)
+            {
+               thisclass node = result < 0 ? left : right;
+               if(!node)
+               {
+                  if(addTo) *addTo = this;
+                  if(addSide) *addSide = (AddSide)result;
+               }
+               this = node;
+            }
+            else
+               break;
+         }
+      }
+      return this;
+   }
+
    thisclass FindAll(const T key)
    {
       AVLNode<T> result = null;
@@ -426,7 +479,7 @@ private:
       right.SingleRotateRight();
       SingleRotateLeft();
    }
-};
+}
 
 public class CustomAVLTree<class BT:AVLNode, class KT = uint64> : Container<BT, I = KT>
 {
@@ -459,7 +512,28 @@ public:
             Tclass = class(BT).templateArgs[0].dataTypeClass =
                eSystem_FindClass(__thisModule.application, class(BT).templateArgs[0].dataTypeString);
          }
-         if(root.Add(Tclass /*class(BT).templateArgs[0].dataTypeClass*/, node))
+         if(root.Add(Tclass, node, 0))
+            root = node.Rebalance();
+         else
+            return null;
+      }
+      count++;
+      return (IteratorPointer)node;
+   }
+
+   private IteratorPointer AddEx(BT node, BT addNode, AddSide addSide)
+   {
+      if(!root)
+         root = node;
+      else
+      {
+         Class Tclass = class(BT).templateArgs[0].dataTypeClass;
+         if(!Tclass)
+         {
+            Tclass = class(BT).templateArgs[0].dataTypeClass =
+               eSystem_FindClass(__thisModule.application, class(BT).templateArgs[0].dataTypeString);
+         }
+         if(addNode.Add(Tclass, node, addSide))
             root = node.Rebalance();
          else
             return null;
@@ -491,12 +565,30 @@ public:
    void Free()
    {
       BT item;
-      while((item = root))
+      item = root;
+      while(item)
       {
-         // THIS SHOULDN'T BE CALLING THE VIRTUAL FUNCTION
-         CustomAVLTree::Remove(item);
-         delete item;
+         if(item.left)
+         {
+            BT left = item.left;
+            item.left = null;
+            item = left;
+         }
+         else if(item.right)
+         {
+            BT right = item.right;
+            item.right = null;
+            item = right;
+         }
+         else
+         {
+            BT parent = item.parent;
+            delete item;
+            item = parent;
+         }
       }
+      root = null;
+      count = 0;
    }
 
    IteratorPointer Find(BT value)

diff --git a/ecere/src/com/containers/Map.ec b/ecere/src/com/containers/Map.ec
index e21f848..2a186ee 100644 (file)
--- a/ecere/src/com/containers/Map.ec
+++ b/ecere/src/com/containers/Map.ec
@@ -139,18 +139,34 @@ public class Map<class MT, class V> : CustomAVLTree<MapNode<MT, V>, I = MT, D =
 
    void Free()
    {
-      MapNode<MT, V> node;
-      while((node = root))
+      MapNode<MT, V> node = root;
+      uintsize offset = class(MT).type == structClass ? class(MT).structSize - sizeof(node.AVLNode::key) : 0;
+      while(node)
       {
-         MapNode<MT, V> n = node;
-
-         // Adjust node pointer for non-standard AVLNode
-         if(class(MT).type == structClass)
-            n = (MapNode<MT, V>)(((byte *) node) + class(MT).structSize - sizeof(node.AVLNode::key));
+         if(node.left)
+         {
+            MapNode<MT, V> left = node.left;
+            node.left = null;
+            node = left;
+         }
+         else if(node.right)
+         {
+            MapNode<MT, V> right = node.right;
+            node.right = null;
+            node = right;
+         }
+         else
+         {
+            MapNode<MT, V> parent = node.parent;
+            MapNode<MT, V> n = (MapNode<MT, V>)((byte *)node + offset);
+            delete n.value;
+            delete node;
 
-         delete n.value;
-         Remove(node);
+            node = parent;
+         }
       }
+      root = null;
+      count = 0;
    }
 
    void Delete(MapNode<MT, V> node)
@@ -173,7 +189,9 @@ public class Map<class MT, class V> : CustomAVLTree<MapNode<MT, V>, I = MT, D =
 
    MapNode<MT, V> GetAtPosition(const MT pos, bool create, bool * justAdded)
    {
-      MapNode<MT, V> node = root ? root.Find(class(MT), pos) : null;
+      AVLNode addNode = null;
+      AddSide addSide = compare;
+      MapNode<MT, V> node = root ? root.FindEx(class(MT), pos, &addNode, &addSide) : null;
       if(!node && create)
       {
          Class Tclass = class(MT);
@@ -195,7 +213,7 @@ public class Map<class MT, class V> : CustomAVLTree<MapNode<MT, V>, I = MT, D =
             onCopy(Tclass, (byte *)&node.key + __ENDIAN_PAD(Tclass.typeSize), (byte *)&pos + __ENDIAN_PAD(Tclass.typeSize));
          else
             onCopy(Tclass, (byte *)&node.key + __ENDIAN_PAD(sizeof(void *)), (void *)pos);
-         CustomAVLTree::Add((T)node);
+         CustomAVLTree::AddEx((T)node, (T)addNode, addSide);
          if(justAdded) *justAdded = true;
       }
       return node;