/* AVL binary tree code by Lynx (or his instructor) modified for MUCK use by Sthiss Remodified by Foxen */ #include <string.h> #include "copyright.h" #include "config.h" #include "params.h" #include "db.h" #include "tune.h" #include "props.h" #include "externs.h" #define Comparator(x,y) string_compare(x,y) static PropPtr find(char *key, PropPtr avl) { int cmpval; while (avl) { cmpval = Comparator(key, PropName(avl)); if (cmpval > 0) { avl = AVL_RT(avl); } else if (cmpval < 0) { avl = AVL_LF(avl); } else { break; } } return avl; } static int height_of(PropPtr node) { if (node) return node->height; else return 0; } static int height_diff(PropPtr node) { if (node) return (height_of(AVL_RT(node)) - height_of(AVL_LF(node))); else return 0; } #ifndef WIN32 # define max(a, b) (a > b ? a : b) #endif static void fixup_height(PropPtr node) { if (node) node->height = 1 + max(height_of(AVL_LF(node)), height_of(AVL_RT(node))); } static PropPtr rotate_left_single(PropPtr a) { PropPtr b = AVL_RT(a); AVL_RT(a) = AVL_LF(b); AVL_LF(b) = a; fixup_height(a); fixup_height(b); return b; } static PropPtr rotate_left_double(PropPtr a) { PropPtr b = AVL_RT(a), c = AVL_LF(b); AVL_RT(a) = AVL_LF(c); AVL_LF(b) = AVL_RT(c); AVL_LF(c) = a; AVL_RT(c) = b; fixup_height(a); fixup_height(b); fixup_height(c); return c; } static PropPtr rotate_right_single(PropPtr a) { PropPtr b = AVL_LF(a); AVL_LF(a) = AVL_RT(b); AVL_RT(b) = a; fixup_height(a); fixup_height(b); return (b); } static PropPtr rotate_right_double(PropPtr a) { PropPtr b = AVL_LF(a), c = AVL_RT(b); AVL_LF(a) = AVL_RT(c); AVL_RT(b) = AVL_LF(c); AVL_RT(c) = a; AVL_LF(c) = b; fixup_height(a); fixup_height(b); fixup_height(c); return c; } static PropPtr balance_node(PropPtr a) { int dh = height_diff(a); if (abs(dh) < 2) { fixup_height(a); } else { if (dh == 2) if (height_diff(AVL_RT(a)) >= 0) a = rotate_left_single(a); else a = rotate_left_double(a); else if (height_diff(AVL_LF(a)) <= 0) a = rotate_right_single(a); else a = rotate_right_double(a); } return a; } PropPtr alloc_propnode(const char *name) { PropPtr new_node; new_node = (PropPtr) malloc(sizeof(struct plist) + strlen(name)); if (!new_node) { fprintf(stderr, "alloc_propnode(): Out of Memory!\n"); abort(); } AVL_LF(new_node) = NULL; AVL_RT(new_node) = NULL; new_node->height = 1; strcpy(PropName(new_node), name); SetPFlagsRaw(new_node, PROP_DIRTYP); SetPDataVal(new_node, 0); SetPDir(new_node, NULL); return new_node; } void free_propnode(PropPtr p) { if (!(PropFlags(p) & PROP_ISUNLOADED)) { if (PropType(p) == PROP_STRTYP) free((void *) PropDataStr(p)); if (PropType(p) == PROP_LOKTYP) free_boolexp(PropDataLok(p)); } free(p); } void clear_propnode(PropPtr p) { if (!(PropFlags(p) & PROP_ISUNLOADED)) { if (PropType(p) == PROP_STRTYP) { free((void *) PropDataStr(p)); PropDataStr(p) = NULL; } if (PropType(p) == PROP_LOKTYP) free_boolexp(PropDataLok(p)); } SetPDataVal(p, 0); SetPFlags(p, (PropFlags(p) & ~PROP_ISUNLOADED)); SetPType(p, PROP_DIRTYP); } static PropPtr insert(char *key, PropPtr * avl) { PropPtr ret; register PropPtr p = *avl; register int cmp; static short balancep; if (p) { cmp = Comparator(key, PropName(p)); if (cmp > 0) { ret = insert(key, &(AVL_RT(p))); } else if (cmp < 0) { ret = insert(key, &(AVL_LF(p))); } else { balancep = 0; return (p); } if (balancep) { *avl = balance_node(p); } return ret; } else { p = *avl = alloc_propnode(key); balancep = 1; return (p); } } static PropPtr getmax(PropPtr avl) { if (avl && AVL_RT(avl)) return getmax(AVL_RT(avl)); return avl; } static PropPtr remove_propnode(char *key, PropPtr * root) { PropPtr save; PropPtr tmp; PropPtr avl = *root; int cmpval; save = avl; if (avl) { cmpval = Comparator(key, PropName(avl)); if (cmpval < 0) { save = remove_propnode(key, &AVL_LF(avl)); } else if (cmpval > 0) { save = remove_propnode(key, &AVL_RT(avl)); } else if (!(AVL_LF(avl))) { avl = AVL_RT(avl); } else if (!(AVL_RT(avl))) { avl = AVL_LF(avl); } else { tmp = remove_propnode(PropName(getmax(AVL_LF(avl))), &AVL_LF(avl)); if (!tmp) abort(); /* this shouldn't be possible. */ AVL_LF(tmp) = AVL_LF(avl); AVL_RT(tmp) = AVL_RT(avl); avl = tmp; } if (save) { AVL_LF(save) = NULL; AVL_RT(save) = NULL; } *root = balance_node(avl); } return save; } static PropPtr delnode(char *key, PropPtr avl) { PropPtr save; save = remove_propnode(key, &avl); if (save) free_propnode(save); return avl; } void delete_proplist(PropPtr p) { if (!p) return; delete_proplist(AVL_LF(p)); delete_proplist(PropDir(p)); delete_proplist(AVL_RT(p)); free_propnode(p); } PropPtr locate_prop(PropPtr list, char *name) { return find(name, list); } PropPtr new_prop(PropPtr * list, char *name) { return insert(name, list); } PropPtr delete_prop(PropPtr * list, char *name) { *list = delnode(name, *list); return (*list); } PropPtr first_node(PropPtr list) { if (!list) return ((PropPtr) NULL); while (AVL_LF(list)) list = AVL_LF(list); return (list); } PropPtr next_node(PropPtr ptr, char *name) { PropPtr from; int cmpval; if (!ptr) return NULL; if (!name || !*name) return (PropPtr) NULL; cmpval = Comparator(name, PropName(ptr)); if (cmpval < 0) { from = next_node(AVL_LF(ptr), name); if (from) return from; return ptr; } else if (cmpval > 0) { return next_node(AVL_RT(ptr), name); } else if (AVL_RT(ptr)) { from = AVL_RT(ptr); while (AVL_LF(from)) from = AVL_LF(from); return from; } else { return NULL; } } /* copies properties */ void copy_proplist(dbref obj, PropPtr * nu, PropPtr old) { PropPtr p; if (old) { #ifdef DISKBASE propfetch(obj, old); #endif p = new_prop(nu, PropName(old)); SetPFlagsRaw(p, PropFlagsRaw(old)); switch (PropType(old)) { case PROP_STRTYP: SetPDataStr(p, alloc_string(PropDataStr(old))); break; case PROP_LOKTYP: if (PropFlags(old) & PROP_ISUNLOADED) { SetPDataLok(p, TRUE_BOOLEXP); SetPFlags(p, (PropFlags(p) & ~PROP_ISUNLOADED)); } else { SetPDataLok(p, copy_bool(PropDataLok(old))); } break; case PROP_DIRTYP: SetPDataVal(p, 0); break; case PROP_FLTTYP: SetPDataFVal(p, PropDataFVal(old)); break; default: SetPDataVal(p, PropDataVal(old)); break; } copy_proplist(obj, &PropDir(p), PropDir(old)); copy_proplist(obj, &AVL_LF(p), AVL_LF(old)); copy_proplist(obj, &AVL_RT(p), AVL_RT(old)); /* copy_proplist(obj, nu, AVL_LF(old)); copy_proplist(obj, nu, AVL_RT(old)); */ } } long size_proplist(PropPtr avl) { long bytes = 0; if (!avl) return 0; bytes += sizeof(struct plist); bytes += strlen(PropName(avl)); if (!(PropFlags(avl) & PROP_ISUNLOADED)) { switch (PropType(avl)) { case PROP_STRTYP: bytes += strlen(PropDataStr(avl)) + 1; break; case PROP_LOKTYP: bytes += size_boolexp(PropDataLok(avl)); break; default: break; } } bytes += size_proplist(AVL_LF(avl)); bytes += size_proplist(AVL_RT(avl)); bytes += size_proplist(PropDir(avl)); return bytes; } int Prop_Check(const char *name, const char what) { if (*name == what) return (1); while ((name = index(name, PROPDIR_DELIMITER))) { if (name[1] == what) return (1); name++; } return (0); }