summaryrefslogtreecommitdiffstats
path: root/private/rpc/ndrdbg/dict.cxx
diff options
context:
space:
mode:
Diffstat (limited to 'private/rpc/ndrdbg/dict.cxx')
-rw-r--r--private/rpc/ndrdbg/dict.cxx384
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);
+}
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-18 21:27:45 +0100