/****************************************************************************** MODUL varsbases.c DESCRIPTION lowlevel Variable support for DME/XDME (Basic List/AVL-Tree Functions) NOTES Either use AVLTREES or MLISTS For ALL commands (even to the searches) You must use the address of a tree/list, not the tree/list itself (that was done to simplify source-modification: just replace 'List'/[M]LIST by 'Tree'/APTR, and go) BUGS TODO More homogene Interface - Use of an opaque type (So that silly redefinition in other modules can go away) EXAMPLES -/- SEE ALSO vars.c INDEX HISTORY ******************************************************************************/ /* ** (C)Copyright 1992 by Bernd Noll for null/zero-soft ** All Rights Reserved ** ** RCS Header: $Id: varsbases.c,v 1.65 92/12/04 21:00:32 b_noll Exp $ ** ** Basic Functions to work with trees/lists of DME-Variables ** Put together to start a little bit of modularisation ** in the sources. ** */ /************************************** Includes **************************************/ #include "defs.h" /************************************** Exports **************************************/ /* --- You can only use either LISTS or AVL-Trees!!! */ /* Tree Operations in common */ Prototype void * FindTreeNode ( void ** tree, CHAR * name ); Prototype void * AddTreeNode ( void ** tree, void * obj ); Prototype void * RemTreeNode ( void ** tree, void * obj ); /* Vars Operations on trees */ Prototype void DelAllVarsFromTree ( void ** tree ); Prototype void DelVarFromTree ( void ** tree, CHAR * name ); Prototype CHAR * GetVarFromTree ( void ** tree, CHAR * name ); Prototype void SetVarIntoTree ( void ** tree, CHAR * name, CHAR * value ); /* Lists Operations in Common */ Prototype CHAR* names2string ( MLIST* list, CHAR* buffer, CHAR delimiter, void* filter ); /* assumes buffer is 1/4k * BUFFERS chgars long */ Prototype int numnodes ( MLIST* list ); Prototype NODE* findnode ( MLIST* list, CHAR* name, short len ); /* Vars Operations on lists */ Prototype void DelAllVarsFromList ( MLIST* list ); Prototype void DelVarFromList ( MLIST* list, CHAR* name ); Prototype CHAR* GetVarFromList ( MLIST* list, CHAR* name ); Prototype void SetVarIntoList ( MLIST* list, CHAR* name, CHAR* value ); #ifdef PATCH_NULL /************************************** Interne Defines & Strukturen **************************************/ #ifdef PATCH_AVL # ifdef TEST # define error printf # define nomemory() # endif typedef struct TreeNode { /* that struct should exactly fit into a Node */ void * tn_Left; void * tn_Right; char tn_Balance; /* char tn_Type; */ CHAR * tn_Name; } TNODE; typedef struct _VARS { TNODE Node; CHAR * Str; } VARS; #define VBASE VARS* #else typedef struct _VARS { NODE Node; CHAR * Str; } VARS; #define VBASE MLIST #endif /* (not) PATCH_AVL */ /************************************** Implementation **************************************/ #ifdef PATCH_AVL TNODE * FindTreeNode (TNODE** tree, CHAR* name) { TNODE* n; if (!tree || !(*tree)) { return(NULL); } /* if */ for (n = *tree; n; ) { switch (strcmp (name, n->tn_Name)) { case 0: return(n); case 1: n = n->tn_Right; break; case -1: n = n->tn_Left; break; default: error ("VARS:\ninvalid result from strcmp"); return(NULL); } /* switch */ } /* for */ return(NULL); } /* FindTreeNode */ static char BalanceTree (TNODE** t) { TNODE * ot = *t; TNODE * lt = ot->tn_Left; TNODE * rt = ot->tn_Right; char b = ot->tn_Balance; /* printf("balancing\n"); */ switch (b) { case -1: case 0: case +1: error ("called without need\n"); return (b); case +2: b = lt->tn_Balance; switch (b) { case -1: /* printf("LR\n"); */ rt = lt->tn_Right; *t = rt; ot->tn_Left = rt->tn_Right; lt->tn_Right = rt->tn_Left; rt->tn_Left = lt; rt->tn_Right = ot; b = rt->tn_Balance; rt->tn_Balance = 0; lt->tn_Balance = (1-b)/2; /* -:1 0:0 +:0 */ ot->tn_Balance = -(1+b)/2; /* 0 0 -1 */ return(0); case 0: case +1: /* LL */ /* printf("LL\n"); */ *t = lt; ot->tn_Left = lt->tn_Right; lt->tn_Right = ot; ot->tn_Balance = -(b-1); /* 0:+1; +1:0 */ lt->tn_Balance = +(b-1); /* -1; 0 */ return (b-1); default: error ("VARS:\nBalance called with corrupt tree"); } /* switch */ break; case -2: b = rt->tn_Balance; switch (b) { case +1: /* printf("RL\n"); */ lt = rt->tn_Left; *t = lt; ot->tn_Right = lt->tn_Left; rt->tn_Left = lt->tn_Right; lt->tn_Left = ot; lt->tn_Right = rt; b = lt->tn_Balance; lt->tn_Balance = 0; rt->tn_Balance = (1+b)/2; /* -:0 0:0 +: */ ot->tn_Balance = (1-b)/2; /* 1 0 */ /* printf ("b== %d\n",b); */ return(0); case 0: case -1: /* RR */ /* printf("RR\n"); */ *t = rt; ot->tn_Right = rt->tn_Left; rt->tn_Left = ot; /* Vorzeichen ??? */ ot->tn_Balance = -(b+1); /* 0:-1; -1:0 */ rt->tn_Balance = +(b+1); /* +1; 0 */ /* printf("ot%d rt%d\n", -(b+1), (b+1)); */ return -(b-1); default: error ("VARS:\nBalance called with corrupt tree"); } /* switch */ break; default: error ("VARS:\nBalance called with corrupt tree"); } /* switch */ return(0); } /* BalanceTree */ static char swap_best_right (TNODE** swapme) { TNODE* root = *swapme; TNODE* curr = root; TNODE* prev = NULL; TNODE* z; char bal = root->tn_Balance; /* printf("swappin'\n"); */ if ((curr = root->tn_Right) == NULL) { return(0); } /* if */ while (z = curr->tn_Left) { prev = curr; curr = z; } /* while */ z = curr->tn_Right; if (prev) { prev->tn_Left = root; curr->tn_Right = root->tn_Right; } else { curr->tn_Right = root; } /* if */ root->tn_Right = z; *swapme = curr; curr->tn_Left = root->tn_Left; root->tn_Left = NULL; /* swap the balances!!!! */ root->tn_Balance = curr->tn_Balance; curr->tn_Balance = bal; return(1); } /* swap_best_right */ static char R_remtreenode (TNODE** tree, TNODE* obj) { TNODE * n = *tree; char mod = 0; if (!n) { error ("VARS:\nCan't remove not-exsiting node"); return(0); } /* if */ switch (strcmp (obj->tn_Name, n->tn_Name)) { case 0: if (n != obj) { error ("VARS:\nCan't manage multiple entries in a tree"); return(0); } /* if */ if (swap_best_right(tree)) { /* noch nich' am boden */ n = *tree; goto remright; /* ab hier koennte es beschleunigt werden */ } else { /* schon am rand - abschneiden */ *tree = n->tn_Right; return(1); } /* if am rand */ case 1: remright: if ( R_remtreenode(&n->tn_Right, obj) ) { n->tn_Balance ++; if (n->tn_Balance == 2) { BalanceTree(tree); } /* if */ return(!(*tree)->tn_Balance); } /* if */ return(0); case -1: if ( R_remtreenode(&n->tn_Left, obj) ) { n->tn_Balance --; if (n->tn_Balance == -2) { BalanceTree(tree); } /* if */ return(!(*tree)->tn_Balance); } /* if */ return(0); default: error ("VARS:\ninvalid result from strcmp"); return(0); } /* switch */ } /* R_remtreenode */ static char R_addtreenode (TNODE** tree, TNODE* obj) { TNODE * n = *tree; if (!n) { *tree = obj; obj->tn_Right = NULL; obj->tn_Left = NULL; obj->tn_Balance = 0; return(1); } /* if */ switch (strcmp (obj->tn_Name, n->tn_Name)) { case 0: error ("VARS:\nCan't manage multiple entries in a tree"); return(0); case 1: if (R_addtreenode(&n->tn_Right, obj)) { n->tn_Balance --; if (n->tn_Balance == -2) { BalanceTree(tree); } else { return(n->tn_Balance); } /* if */ } /* if */ return(0); case -1: if (R_addtreenode(&n->tn_Left, obj)) { n->tn_Balance ++; if (n->tn_Balance == 2) { BalanceTree(tree); } else { return(n->tn_Balance); } /* if */ } /* if */ return(0); default: error ("VARS:\ninvalid result from strcmp"); return(0); } /* switch */ } /* R_addtreenode */ /* ** RemTreeNode ** Remove a node from an avl-tree; the right ** position is searched with strcmp() ** ** NOTE U first have to search for the node which ** is to be deleted e.g.: ** RemTreeNode(&tree, FindTreeNode(&tree, name )); */ TNODE * RemTreeNode (TNODE** tree, TNODE* obsolete) { if ((!tree) || (!(*tree))) return (NULL); if (obsolete) R_remtreenode (tree, obsolete); return (*tree); } /* RemTreeNode */ /* ** AddTreeNode ** Append a new node to an avl-tree; the right ** position is calculated with strcmp() ** ** NOTE U cannot define two nodes with the same ** name in one tree */ TNODE * AddTreeNode (TNODE** tree, TNODE* new) { if (!tree) return (NULL); if (new) R_addtreenode (tree, new); return (*tree); } /* AddTreeNode */ /* ** DelAllVarsFromTree() ** recursively remove all nodes from a certain tree ** and free them and their associated names&values */ void DelAllVarsFromTree (VARS** tree) { if (!tree || !(*tree)) { return; } /* if */ DelAllVarsFromTree(&(*tree)->Node.tn_Left); /* first free its sons */ DelAllVarsFromTree(&(*tree)->Node.tn_Right); free((*tree)->Node.tn_Name); /* then free it and all its subs */ free((*tree)->Str); free((*tree)); } /* DelAllVarsFromTree */ /* ** SetVarIntoTree() ** define a node with a cetain name and value in ** a given tree if therew is already a node of the ** chosen name the previous node is removed ** (actually only the old value is removed) ** if any allocation went wrong, call nomemory() */ void SetVarIntoTree (VBASE* tree, CHAR* name, CHAR* value) { VARS* v = NULL; CHAR* vn = NULL; CHAR* vv = NULL; if (v = (VARS*)FindTreeNode(tree, name)) { if (vv = strdup(value)) { free(v->Str); v->Str = vv; return; } /* if malloced */ v = NULL; /* avoid freeing the found node */ } else { v = malloc(sizeof(VARS)); vv = strdup(value); vn = strdup(name); if (v && vv && vn) { v->Str = vv; v->Node.tn_Name = vn; AddTreeNode (tree, (TNODE *)v); return; } /* if malloced */ } /* if (no) old node */ /* --- if we didn't return prior, (if everything worked fine) remove all allocated data */ if (v) free(v); if (vv) free(vv); if (vn) free(vn); nomemory(); abort(); } /* SetVarIntoTree */ /* ** DelVarFromTree() ** remove a certain node (found w/ FindTreeNode) ** from a given tree; do not panik, if there is no ** node found */ void DelVarFromTree (VBASE* tree, CHAR* name) { VARS *v = NULL; if (v = (VARS*)FindTreeNode(tree, name)) { /* if there is a node of the right name */ RemTreeNode (tree, (TNODE *)v); /* remove it and all its subs */ free(v->Node.tn_Name); free(v->Str); free(v); } /* if */ } /* DelVarFromTree */ /* ** GetVarFromTree() ** find a node in a certain tree (w/ FindTreeNode) ** duplicate its value and return the copy ** return NULL if there was no node found ** and call nomemory() if duplicate failed */ CHAR* GetVarFromTree (VBASE* tree, CHAR* name) { CHAR* str = NULL; VARS* v = NULL; if (v = (VARS*)FindTreeNode(tree, name)) { /* if there is a node of the right name */ if (str = strdup(v->Str)) { /* return a copy of its value */ return(str); } else { nomemory(); abort(NULL); } /* if */ } /* if */ return(NULL); } /* GetVarFromTree */ #ifdef TEST void zeigebaum(TNODE* t) { if (t==NULL) { printf( "-" ); return; } printf("(%d%s ",t->tn_Balance,t->tn_Name); printf("L"); zeigebaum(t->tn_Left); printf("R"); zeigebaum(t->tn_Right); printf(")"); } /* zeigebaum */ CHAR* testnamen[] = { "prag", "lima", "tokio", "bonn", "paris", "sofia", "wien", "bern", "kairo", "oslo", "rom", "athen", NULL }; int main(int ac, char* av[]) { CHAR** tt; CHAR buffer [100]; TNODE* staedte = NULL; TNODE* rem = NULL; for (tt = testnamen; *tt; tt++) { printf(">%s\n",*tt); SetVarIntoTree(&staedte, *tt, ""); /* gets (buffer); */ } /* for */ zeigebaum (staedte); rem = FindTreeNode(&staedte, "bonn"); printf ("\nrem == %08lx %s\n", rem, rem->tn_Name); RemTreeNode(&staedte, rem); zeigebaum(staedte); printf("\n"); } /* main */ #endif TEST #else /* ** GetVarFromList() ** find a node in a certain list (w/ FindName) ** duplicate its value and return the copy ** return NULL if there was no node found ** and call nomemory() if duplicate failed */ CHAR* GetVarFromList (VBASE* list, CHAR* name) { CHAR* str = NULL; VARS* v = NULL; if (v = (VARS*)FindName((LIST*)list, name)) { /* if there is a node of the right name */ if (str = strdup(v->Str)) { /* return a copy of its value */ return(str); } else { nomemory(); abort(NULL); } /* if */ } /* if */ return(NULL); } /* GetVarFromList */ /* ** DelVarFromList() ** remove a certain node (found w/ FindName) ** from a given list; do not panik, if there is no ** node found */ void DelVarFromList (VBASE* list, CHAR* name) { VARS *v = NULL; if (v = (VARS*)FindName((LIST*)list, name)) { /* if there is a node of the right name */ Remove((NODE *)v); /* remove it and all its subs */ free(v->Node.ln_Name); free(v->Str); free(v); } /* if */ } /* DelVarFromList */ /* ** DelAllVarsFromList() ** remove all nodes from a certain list ** and free them and their associated names&values */ void DelAllVarsFromList (VBASE* list) { VARS* v = NULL; while (v = (VARS*)RemHead((LIST*)list)) { /* while there is an entry left in the list */ free(v->Node.ln_Name); /* free it and all its subs */ free(v->Str); free(v); } /* while */ } /* DelAllVarsFromList */ /* ** SetVarIntoList() ** define a node with a cetain name and value in ** a given list if therew is already a node of the ** chosen name the previous node is removed ** (actually only the old value is removed) ** if any allocation went wrong, call nomemory() */ void SetVarIntoList (VBASE* list, CHAR* name, CHAR* value) { VARS* v = NULL; CHAR* vn = NULL; CHAR* vv = NULL; #ifdef N_DEF /* old method *//* POSITION DIFFERS BETWEEN XDME AND DME (+-12) */ /* --- First it is checked, if You have a Special variable */ /* ** these checks may be object of some changes in near future ** - I do now think, that it would be quite better ** to introduce a new function SETSPC for special variables ** and to call "SETLOCAL " to set a local flag instead of "SET i" */ if (SetAnyFlag(name, value) || SetSpecialInt(name, value) || SetSpecialVar(name, value) ) { return(); } /* if */ /* --- The Current variable - if exists - is deleted */ DelVarFromList(list, name); /* --- Then a new one is created and appended to the list */ if (v = malloc(sizeof(VARS))) { if (v->Node.ln_Name = strdup(name)) { if (v->Str = strdup(value)) { AddHead((LIST *)list, (NODE *)v); return; } /* if */ free(v->Node.ln_Name); } /* if */ free(v); } /* if */ nomemory(); #endif /* N_DEF */ /* ** that routine is a little bit longer than the old one, ** but we need not free all data of older entries any ** more, so memory fragmentation should be reduced a bit: ** if there's an older entry, simply replace its value ** by the new one, else create a full new entry. */ if (v = (VARS*)FindName((LIST*)list, name)) { if (vv = strdup(value)) { free(v->Str); v->Str = vv; /* --- it might be senseful moving the changed entry to startoflist */ /* Remove(v); */ /* AddHead((LIST*)list, v) */ return; } /* if malloced */ v = NULL; /* avoid removing the found node */ } else { v = malloc(sizeof(VARS)); vv = strdup(value); vn = strdup(name); if (v && vv && vn) { v->Str = vv; v->Node.ln_Name = vn; AddHead((LIST *)list, (NODE *)v); return; } /* if malloced */ } /* if (no) old node */ /* --- if we didn't return prior, (if everything worked fine) remove all allocated data */ if (v) free(v); if (vv) free(vv); if (vn) free(vn); nomemory(); abort(); } /* SetVarIntoList */ /* ** Names 2 String ** copies all ln_Name s of a given List into a String and returns it ** (if filter != NULL the names are filtered before) ** There _must_ be a buffer big enough to fit all the Strings: ** definements in defs.h: ** BUFFERS is the number of "LINES" reserved for buffer ** and LINE_LENGTH (== 256) is the length of one such line ** should be included ** ** name2string does _not_ allocate memory!!!! ** currently filter MUST BE SET to NULL to guarantee compatibility to later versions! ** list MUST BE VALID! (there is no check) */ CHAR* names2string (MLIST* list, CHAR* buffer, CHAR delimiter, CHAR* (*filter)()) { struct Node* node; CHAR* buf = buffer; int i = 0; CHAR delim[2] = {delimiter,0}; /* CHAR inter[128]; */ node = (NODE*)list->mlh_Head; while (node->ln_Succ && node != (NODE*)&list->mlh_Tail) { buffer = buf+i; /* ************************************ Hier gehoert noch der filter hin, ich brauchte ihn nur bisher noch nicht, daher liess ich ihn weg * */ if ((i += strlen(node->ln_Name)) < BUFFERS*LINE_LENGTH-1) { strcpy(buffer, node->ln_Name); if (i < BUFFERS*LINE_LENGTH-1) { buffer = buf+i; strcpy(buffer, delim); i++; } else { return(buf); } /* if */ } else { break; } /* if */ node = node->ln_Succ; } /* while */ *buffer = 0; return(buf); } /* names2string */ /* ** numnodes() - return the number of entries in a list ** ** list MUST BE VALID! (there is no check) */ int numnodes(MLIST* list) { register int i = 0; register MNODE* n; for (n = list->mlh_Head; (n != NULL) && (n->mln_Succ != NULL); n = n->mln_Succ) { i++; } /* for */ return(i); } /* numnodes */ /* ** findnode() - find a certain node in a list ** ** search may be done up to a certain strlength (own function) or via FindName ** ** list MUST BE VALID! (there is no check) */ NODE* findnode(MLIST* list, CHAR* name, short len) { register NODE* node; if (len) { for (node = (NODE*)list->mlh_Head; node && node->ln_Succ; node = node->ln_Succ) { if (strncmp(node->ln_Name, name, len) == 0) { return(node); } /* if */ } /* for */ } else { return(FindName((LIST*)list, name)); } /* if */ return(NULL); } /* findnode */ #endif /* (not) PATCH_AVL */ #endif /* PATCH_NULL */ /****************************************************************************** ***** ENDE varsbases.c ******************************************************************************/