1 files changed, 384 insertions, 0 deletions

diff --git a/private/rpc/ndrdbg/dict.cxx b/private/rpc/ndrdbg/dict.cxx
new file mode 100644
index 000000000..1084f8e1a
--- /dev/null
+++ b/private/rpc/ndrdbg/dict.cxx
@@ -0,0 +1,384 @@
+/*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ Copyright (c) 1989 Microsoft Corporation
+
+ Module Name:
+    
+    pdict.cxx
+
+ Abstract:
+
+	This file contains the definition for splay tree self
+	adjusting binary trees.
+
+ History:
+
+             1990        Dov Harel       Created
+
+ ----------------------------------------------------------------------------*/
+
+
+#include "pdict.hxx"
+
+// handly macros used to define common tree operations
+
+#define ROTATELEFT  tmp=t->right; t->right=tmp->left;  tmp->left =t; t=tmp
+#define ROTATERIGHT tmp=t->left;  t->left =tmp->right; tmp->right=t; t=tmp
+
+#define LINKLEFT  tmp=t; t = t->right; l = l->right = tmp
+#define LINKRIGHT tmp=t; t = t->left;  r = r->left = tmp
+
+#define ASSEMBLE r->left = t->right;	 l->right = t->left; \
+		 t->left = Dummy->right; t->right = Dummy->left
+
+static TreeNode Dumbo(Nil);
+static TreeNode *Dummy = &Dumbo;	// a global dummy node
+
+
+
+//*************************************************************************
+//***** 	     Core functions (internal)			      *****
+//*************************************************************************
+
+long					// return last comparision
+Dictionary::SplayUserType(		// general top down splay
+
+    pUserType keyItem	// pointer to a "key item" searched for
+
+) //-----------------------------------------------------------------------//
+{
+    TreeNode* t;	// current search point
+    TreeNode* l;        // root of "left subtree" < keyItem
+    TreeNode* r;        // root of "right subtree" > keyItem
+    long kcmp;		// cash comparison results
+    TreeNode* tmp;
+
+    if ((fCompare = Compare(keyItem, root->item)) == 0)
+	return (fCompare);
+
+    Dummy = l = r = &Dumbo;
+    Dumbo.left = Dumbo.right = Nil;
+
+    t = root;
+
+    do {
+	if ( fCompare < 0 ) {
+	    if ( t->left == Nil ) break;
+
+	    if ( (kcmp = Compare(keyItem, t->left->item)) == 0 ) {
+		LINKRIGHT;
+	    }
+	    else if ( kcmp < 0 ) {
+                ROTATERIGHT;
+		if ( t->left != Nil ) {
+		    LINKRIGHT;
+		}
+	    }
+            else { // keyItem > t->left->item
+                LINKRIGHT;
+		if ( t->right != Nil ) {
+		    LINKLEFT;
+		}
+	    }
+	}
+        else { // keyItem > t->item
+	    if ( t->right == Nil ) break;
+
+	    if ( (kcmp = Compare(keyItem, t->right->item)) == 0 ) {
+		LINKLEFT;
+	    }
+	    else if ( kcmp > 0 ) {
+                ROTATELEFT;
+		if ( t->right != Nil ) {
+		    LINKLEFT;
+		}
+	    }
+            else { // keyItem < t->right->item
+                LINKLEFT;
+		if ( t->left != Nil ) {
+		    LINKRIGHT;
+		}
+	    }
+        }
+    } while ( (fCompare = Compare(keyItem, t->item)) != 0 );
+
+    ASSEMBLE;
+
+    root = t;
+    return(fCompare);
+}
+
+TreeNode*
+SplayLeft(
+
+    TreeNode* t		// root of tree & current "search" point
+
+) //-----------------------------------------------------------------------//
+{
+    TreeNode* l=Dummy;  // root of "left subtree" < keyItem
+    TreeNode* r=Dummy;  // root of "right subtree" > keyItem
+    TreeNode* tmp;
+
+    if (t == Nil || t->left == Nil)
+	return(t);
+
+    if (t->left->left == Nil) {
+	ROTATERIGHT;
+	return(t);
+    }
+
+    Dummy->left = Dummy->right = Nil;
+
+    while ( t->left != Nil ) {
+        ROTATERIGHT;
+
+	if ( t->left != Nil ) {
+	    LINKRIGHT;
+	}
+    }
+    ASSEMBLE;
+    return(t);
+}
+
+#ifndef DICT_NOPREV
+
+TreeNode*
+SplayRight(
+
+    TreeNode* t		// root of tree & current "search" point
+
+) //-----------------------------------------------------------------------//
+{
+    TreeNode* l=Dummy;  // root of "left subtree" < keyItem
+    TreeNode* r=Dummy;  // root of "right subtree" > keyItem
+    TreeNode* tmp;
+
+    if (t == Nil || t->right == Nil)
+	return(t);
+
+    Dummy->left = Dummy->right = Nil;
+
+    while ( t->right != Nil ) {
+        ROTATELEFT;
+
+	if ( t->right != Nil ) {
+	    LINKLEFT;
+	}
+    }
+    ASSEMBLE;
+    return(t);
+}
+
+#endif
+
+
+
+// Class methods for Splay Tree
+
+Dict_Status
+Dictionary::Dict_Find(		// return a item that matches
+
+    pUserType itemI		// this value
+
+  // Returns:
+  //   itemCur - Nil if at not in Dict, else found item
+) //-----------------------------------------------------------------------//
+{
+    itemCur = Nil;
+
+    if (root == Nil)
+	return (EMPTY_DICTIONARY);
+
+    if (itemI == Nil)
+	return (NULL_ITEM);
+
+    if (SplayUserType (itemI) == 0){
+
+	itemCur = root->item;
+	return(SUCCESS);
+    }
+    return(ITEM_NOT_FOUND);
+}
+
+#ifndef DICT_NONEXT
+
+Dict_Status
+Dictionary::Dict_Next(		// return the next item
+
+    pUserType itemI		// of a key greater then this
+
+  // Returns:
+  //   itemCur - Nil if at end of Dict, else current item
+) //-----------------------------------------------------------------------//
+{
+    TreeNode* t;
+
+    itemCur = Nil;
+
+    if (root == Nil)
+	return (EMPTY_DICTIONARY);
+
+    if (itemI == Nil) { 		// no arg, return first record
+	root = SplayLeft (root);
+
+	itemCur = root->item;
+        return (SUCCESS);
+    }
+
+    if (itemI != root->item)
+
+	if (SplayUserType (itemI) > 0) {
+	    itemCur = root->item;
+	    return (SUCCESS);
+	}
+
+    if (root->right == Nil)
+	return (LAST_ITEM);
+
+    t = root;
+
+    root = SplayLeft (root->right);
+    root->left = t;
+    t->right = Nil;
+
+    itemCur = root->item;
+    return (SUCCESS);
+}
+#endif // DICT_NONEXT
+
+#ifndef DICT_NOPREV
+
+Dict_Status
+Dictionary::Dict_Prev(		// return the previous item
+
+    pUserType itemI		// of a key less then this
+
+  // Returns:
+  //   itemCur - Nil if at begining of Dict, else current item
+) //-----------------------------------------------------------------------//
+{
+    TreeNode* t;
+
+    itemCur = Nil;
+
+    if (root == Nil)
+	return (EMPTY_DICTIONARY);
+
+    if (itemI == Nil) { 		// no arg, return last record
+	root = SplayRight (root);
+
+	itemCur = root->item;
+        return (SUCCESS);
+    }
+
+    if (itemI != root->item)
+
+	if (SplayUserType (itemI) < 0) {
+	    itemCur = root->item;
+	    return (SUCCESS);
+	}
+
+    if (root->left == Nil)
+	return (LAST_ITEM);
+
+    t = root;
+    root = SplayRight (root->left);
+    root->right = t;
+    t->left = Nil;
+
+    itemCur = root->item;
+    return (SUCCESS);
+}
+
+#endif // DICT_NOPREV
+
+Dict_Status
+Dictionary::Dict_Insert(		// insert the given item into the tree
+
+    pUserType itemI		// the item to be inserted
+
+  // Returns:
+  //  itemCur - point to new item
+) //-----------------------------------------------------------------------//
+{
+    TreeNode *newNode, *t;
+
+    if ((itemCur = itemI) == Nil)
+	return (NULL_ITEM);
+
+    if (root == Nil) {
+	root = new TreeNode(itemI);
+        size++;
+        return (SUCCESS);
+    }
+
+    if (SplayUserType (itemI) == 0)
+        return (ITEM_ALREADY_PRESENT);
+
+    newNode = new TreeNode(itemI);
+    size++;
+
+    t = root;
+
+    if (fCompare > 0) {
+	newNode->right = t->right;	//  item >= t->item
+	newNode->left = t;
+	t->right = Nil;
+    }
+    else {
+	newNode->left = t->left;
+	newNode->right = t;
+	t->left = Nil;
+    }
+    root = newNode;
+
+    return (SUCCESS);
+}
+
+
+Dict_Status
+Dictionary::Dict_Delete(	// delete the given item from the tree
+
+    pUserType *itemI		// points to the (key) item to be deleted
+
+  // Returns:
+  //   itemCur is Nil - undefined
+) //-----------------------------------------------------------------------//
+{
+    TreeNode *t, *r;
+
+    itemCur = Nil;
+
+    if (root == Nil)
+	return (EMPTY_DICTIONARY);
+
+    if (itemI == Nil)
+	return (NULL_ITEM);
+
+    if (itemI != root->item) {
+
+	if (SplayUserType (*itemI) != 0)
+	    return(ITEM_NOT_FOUND);
+    }
+
+    *itemI = root->item;
+    t = root;
+
+    if (t->left == Nil)
+        root = t->right;
+
+    else if ( (r = t->right) == Nil)
+        root = t->left;
+
+    else {
+	r = SplayLeft (r);
+	r->left = t->left;	// at this point r->left == Nil
+        root = r;
+    }
+
+    delete t;
+    size--;
+
+    return (SUCCESS);
+}
+
+