论坛 › C/C++ › 在一个死亡的论坛上发一个从未活过的代码， 致我已经风飘云散的过去

zylthinking 发表于 2022-11-02 14:44

在一个死亡的论坛上发一个从未活过的代码， 致我已经风飘云散的过去

本帖最后由 zylthinking 于 2022-11-02 14:49 编辑

在一个死亡的论坛上发一个从未活过的 symbian 代码


致我已经风飘云散的过去



#ifndef _RBTree_H_
#define _RBTree_H_
#include <e32base.h>

#define EFailed ((TAny *)(-1))
typedef void (*TFree)(void*);
typedef TInt (*TComp)(void*, void*);

struct TUserOP{
    TFree iFree;
    TComp iCompare;
};

class TTreeNode;
class TTreeIterator;

class CRBTree : public CBase{
public:
    // TUser must not be NULL and iCompare should be
    // provided too. while, iFree can be NULL if not needed
    static IMPORT_C CRBTree* NewL(TUserOP* op);
    IMPORT_C ~CRBTree();

    // add a node to tree
    // aUser, data proviced by user which will be added to tree
    // aRep, if the data has exists, would it replace the old one
    // or failed
    // return value: EFailed, error occured
    // the old one being replaced by the aUser, if aRep is false or
    // there is data which is equal to aUser, return NULL
    IMPORT_C TAny* AddL(TAny* aUser, TBool aRep);

    // remove node
    IMPORT_C TAny* Unlink(TAny* aUser);
    IMPORT_C void Remove(TAny* aUser);

    // clear all nodes in the tree
    // the tree will be empty, while ok to add nodes again
    IMPORT_C void Reset();

    // number of nodes of the tree
    IMPORT_C TInt Length();

    // the min node in the tree
    // the compare is provided by TUserOP
    IMPORT_C TAny* Min();

    // the max node in the tree
    // the compare is provided by TUserOP
    IMPORT_C TAny* Max();

    // find the node in the tree, which is euqal to aUser
    // compared with TUserOP::iCompare
    IMPORT_C TAny* Find(TAny* aUser);

    // generate a handle for later FindNext
    // return -1, when can't find the aUser
    // the handle will be used for forward search only
    IMPORT_C TInt FindFirst(TAny* aUser);

    // generate a handle for later RFindNext
    // return -1, when can't find the aUser
    // the handle will be used for backward search only
    IMPORT_C TInt RFindFirst(TAny* aUser);

    // return data referenced by handle, and reposition the
    // handle to nexr data
    // return value: the data referenced by handle
    // EFailed if error occured
    // NULL when there is no more data
    IMPORT_C TAny* FindNext(TInt aHandle);

    // same with FindNext, but is a safer method, meaning, the
    // method will validate the handle provided by user, while
    // FindNext will not. The method is slower.
    IMPORT_C TAny* FindNextSafe(TInt aHandle);

    // return data referenced by handle, and reposition the
    // handle to previous data
    // return value: the data referenced by handle
    // EFailed if error occured
    // NULL when there is no more data
    IMPORT_C TAny* RFindNext(TInt aHandle);

    // same with RFindNext, but is a safer method, meaning, the
    // method will validate the handle provided by user, while
    // RFindNext will not. The method is slower.
    IMPORT_C TAny* RFindNextSafe(TInt aHandle);

    // Close the handle when finish using it.
    // must be called after using it to release resouce used internal
    IMPORT_C void CloseFindHandle(TInt handle);

    // A safe version of CloseFindHandle
    IMPORT_C void CloseFindHandleSafe(TInt handle);

#ifdef _DEBUG
    IMPORT_C TInt BlackHeight();
private:
    TInt CRBTree::BlackHeight(TTreeNode* aNode);
#endif

public:
    enum TColor{EBlack, ERed};
    enum TDirect{EForward, EBackward};

private:
    CRBTree(TUserOP* op);
    CRBTree::CRBTree(const CRBTree&);
    CRBTree& operator = (const CRBTree&);
    void ConstructL();
   
    void AdjustBeforeInsert(TTreeNode* aNode);
    void AdjustBeforeRemove(TTreeNode* aNode);
    void InsertL(TAny* aUser, TTreeNode* aFather, TInt aFlag);
    void InsertRotate(TTreeNode* aFather, TTreeNode* aNode);
    TAny* RemoveNode(TTreeNode* aNode);
   
    TTreeNode* Find(TAny* aUser, TInt& aFlag);
    TInt FindFirst(TAny* aUser, TDirect aDirect);
    TTreeNode* FindNext(TTreeNode* aNode);
    TTreeNode* RFindNext(TTreeNode* aNode);
    void AdjustFindHandles(TTreeNode* aNode);
   
    TInt ValidateHandle(TInt aHandle);
    TTreeNode** PointerOf(TTreeNode* aNode);
    void RotateLeft(TTreeNode* aFather, TTreeNode* aNode, TTreeNode** aPPNode);
    void RotateRight(TTreeNode* aFather, TTreeNode* aNode, TTreeNode** aPPNode);
   
private:
    TUserOP* iOps;
    TTreeNode* iRoot;
    TTreeIterator* iIterator;
    TInt iNrNodes;
};

#endif


#include "rbtree.h"
#include <e32std.h>

#define BLACK(x)    (x == NULL || x->iColor == EBlack)

class TTreeNode{
public:
    TTreeNode(CRBTree::TColor aColor){
      iLChild = iRChild = iFather = NULL;
      iColor = aColor;
    }
public:
    TTreeNode* iFather;
    TTreeNode* iLChild;
    TTreeNode* iRChild;
    CRBTree::TColor iColor;
    TAny* iUser;
};

class TTreeIterator{
public:
    TTreeIterator(TTreeNode* aNode, CRBTree::TDirect aDirection){
      ASSERT(aNode);

      iNext = iPrev = NULL;
      iNode = aNode;
      iDirection = aDirection;
    }

    TTreeNode* iNode;
    CRBTree::TDirect iDirection;
    TTreeIterator* iNext;
    TTreeIterator* iPrev;
};

//========================================================

CRBTree::CRBTree(TUserOP* aOp){
    iOps = aOp;
}

EXPORT_C CRBTree::~CRBTree(){
    Reset();
}

EXPORT_C CRBTree* CRBTree::NewL(TUserOP* aOp){
    CRBTree* self = new (ELeave) CRBTree(aOp);
    CleanupStack::PushL(self);
    self->ConstructL();
    CleanupStack::Pop();
    return self;
}

void CRBTree::ConstructL(){
    if(iOps == NULL || iOps->iCompare == NULL)
      User::Leave(KErrArgument);
}

EXPORT_C TInt CRBTree::Length(){
    return iNrNodes;
}

EXPORT_C TAny* CRBTree::Min(){
    TTreeNode* cur = iRoot;
    if(cur != NULL){
      while(cur->iLChild){
            cur = cur->iLChild;
      }
    }
    return cur->iUser;
}

EXPORT_C TAny* CRBTree::Max(){
    TTreeNode* cur = iRoot;
    if(cur != NULL){
      while(cur->iRChild){
            cur = cur->iRChild;
      }
    }
    return cur->iUser;
}

EXPORT_C void CRBTree::Reset(){
    TTreeNode* cur = iRoot;
LABEL:
    if(cur){
      if(cur->iLChild){
            cur = cur->iLChild;
            goto LABEL;
      }

      if(cur->iRChild){
            cur = cur->iRChild;
            goto LABEL;
      }

      if(iOps->iFree){
            iOps->iFree(cur->iUser);
      }

      TTreeNode* father = cur->iFather;
      delete cur;

      if(cur != iRoot){
            if(father->iLChild == cur)
                father->iLChild = NULL;
            else
                father->iRChild = NULL;

            cur = father;
            goto LABEL;
      }
    }

    TTreeIterator* it = iIterator;
    while(it){
      TTreeIterator* next = it->iNext;
      delete it;
      it = next;
    }

    iRoot = NULL;
    iIterator = NULL;
    iNrNodes = 0;
}

EXPORT_C TAny* CRBTree::AddL(TAny* aUser, TBool aRep){
    if(aUser == NULL)
      User::Leave(KErrArgument);

    if(iRoot == NULL){
      TTreeNode* node = new (ELeave) TTreeNode(EBlack);
      ++iNrNodes;

      iRoot = node;
      iRoot->iUser = aUser;
      return NULL;
    }
   
    TInt flag = 1;
    TTreeNode* node = Find(aUser, flag);
    ASSERT(node);

    TAny* oldkey = node->iUser;
    if(flag == 0){
      if(aRep){
            node->iUser = oldkey;
            return oldkey;
      }
      User::Leave(KErrAlreadyExists);
    }

    InsertL(aUser, node, flag);
    ++iNrNodes;
    return NULL;
}

void CRBTree::InsertL(TAny* aUser, TTreeNode* aFather, TInt aFlag){
    TTreeNode* newNode = new (ELeave) TTreeNode(ERed);
    newNode->iUser = aUser;

    if(aFlag > 0){
      aFather->iLChild = newNode;
      newNode->iFather = aFather;
    }else{
      aFather->iRChild = newNode;
      newNode->iFather = aFather;
    }

    if(aFather->iColor == ERed){
      InsertRotate(aFather, newNode);
    }
}

TTreeNode* CRBTree::Find(TAny* aUser, TInt& aFlag){
    ASSERT(aUser);

    TInt adjust = aFlag;
    TTreeNode* cur = iRoot;

    while(cur){
      aFlag = iOps->iCompare(cur->iUser, aUser);
      if(aFlag == 0)
            return cur;
      
      if(adjust && cur->iLChild && cur->iRChild &&
         cur->iColor == EBlack && cur->iLChild->iColor == ERed &&
         cur->iRChild->iColor == ERed){
            AdjustBeforeInsert(cur);
      }

      if(aFlag > 0 && cur->iLChild){
            cur = cur->iLChild;
      }else if(aFlag < 0 && cur->iRChild){
            cur = cur->iRChild;
      }else{
            return cur;
      }
    }

    return NULL;
}

void CRBTree::AdjustBeforeInsert(TTreeNode* aNode){
    aNode->iLChild->iColor = EBlack;
    aNode->iRChild->iColor = EBlack;

    if(aNode->iFather){
      aNode->iColor = ERed;
      if(aNode->iFather->iColor == ERed)
            InsertRotate(aNode->iFather, aNode);
    }
}

void CRBTree::InsertRotate(TTreeNode* aFather, TTreeNode* aNode){
    ASSERT(aNode->iColor == ERed);
    ASSERT(aFather->iColor == ERed);
    ASSERT(aFather->iFather);
   
    TTreeNode* grandpa = aFather->iFather;
    TBool left1 = (aFather->iLChild == aNode);
    TBool left2 = (grandpa->iLChild == aFather);
    TBool same = (left1 == left2);

    if(same){
      aNode = aFather;
      aFather = aNode->iFather;
    }

LABEL:
    TTreeNode** pp_node = PointerOf(aFather);
    if(left1){
      RotateRight(aFather, aNode, pp_node);
    }else{
      RotateLeft(aFather, aNode, pp_node);
    }

    if(!same){
      left1 = !left1;
      aFather = aNode->iFather;
      same = true;
      goto LABEL;
    }

    aNode->iColor = EBlack;
    if(left1){
      aNode->iRChild->iColor = ERed;
    }else{
      aNode->iLChild->iColor = ERed;
    }
}

void CRBTree::RotateLeft(TTreeNode* aFather, TTreeNode* aNode, TTreeNode** aPPNode){
    *aPPNode = aNode;
    aNode->iFather = aFather->iFather;
   
    aFather->iRChild = aNode->iLChild;
    if(aNode->iLChild){
      aNode->iLChild->iFather = aFather;
    }

    aNode->iLChild = aFather;
    aFather->iFather = aNode;
}
   
void CRBTree::RotateRight(TTreeNode* aFather, TTreeNode* aNode, TTreeNode** aPPNode){
    *aPPNode = aNode;
    aNode->iFather = aFather->iFather;
   
    aFather->iLChild = aNode->iRChild;
    if(aNode->iRChild){
      aNode->iRChild->iFather = aFather;
    }

    aNode->iRChild = aFather;
    aFather->iFather = aNode;
}

EXPORT_C TAny* CRBTree::Unlink(TAny* aUser){
    if(aUser == NULL){
      return NULL;
    }

    TAny* user = NULL;
    TInt flag = 0;

    TTreeNode* node = Find(aUser, flag);
    if(node != NULL && flag == 0){
      AdjustFindHandles(node);
      user = RemoveNode(node);
      --iNrNodes;
    }
    return user;
}

EXPORT_C void CRBTree::Remove(TAny* aUser){
    TAny* user = Unlink(aUser);
    if(user && iOps->iFree){
      iOps->iFree(user);
    }
}

TAny* CRBTree::RemoveNode(TTreeNode* aNode){
    ASSERT(aNode);

    if(aNode->iLChild && aNode->iRChild){
      TTreeNode* next = FindNext(aNode);
      TAny* saved_key = next->iUser;
      next->iUser = aNode->iUser;
      aNode->iUser = saved_key;
      aNode = next;
    }

    TTreeNode** pp_node = PointerOf(aNode);
    if(aNode->iRChild != NULL){
      aNode->iRChild->iFather = aNode->iFather;
      aNode->iRChild->iColor = EBlack;
      *pp_node = aNode->iRChild;
    }else if(aNode->iLChild != NULL){
      aNode->iLChild->iFather = aNode->iFather;
      aNode->iLChild->iColor = EBlack;
      *pp_node = aNode->iLChild;
    }else{
      if(aNode->iColor == EBlack){
            AdjustBeforeRemove(aNode);
      }
      *pp_node = NULL;
    }

    TAny* user = aNode->iUser;
    delete aNode;
    return user;
}

void CRBTree::AdjustBeforeRemove(TTreeNode* aNode){
LABEL:
    TTreeNode* father = aNode->iFather;
    if(father == NULL){
      return;
    }

    TTreeNode* brother;
    TBool left = father->iLChild == aNode;
    if(left){
      brother = father->iRChild;
    }else{
      brother = father->iLChild;
    }
    ASSERT(brother);

    if(brother->iColor == ERed){
      TTreeNode** pp_node = PointerOf(father);

      if(left){
            RotateLeft(father, brother, pp_node);
            brother = father->iRChild;
      }else{
            RotateRight(father, brother, pp_node);
            brother = father->iLChild;
      }

      father->iColor = ERed;
      father->iFather->iColor = EBlack;
    }

    if(BLACK(brother->iLChild) && BLACK(brother->iRChild)){
      if(father->iColor == ERed){
            father->iColor = EBlack;
            brother->iColor = ERed;
            return;
      }

      brother->iColor = ERed;
      aNode = father;
      goto LABEL;
    }

    if(left){
      if(BLACK(brother->iRChild)){
            ASSERT(brother->iLChild->iColor == ERed);
            RotateRight(brother, brother->iLChild, &(father->iRChild));

            brother = brother->iFather;
            brother->iColor = EBlack;
            brother->iRChild->iColor = ERed;
      }
    }else if(BLACK(brother->iLChild)){
      ASSERT(brother->iRChild->iColor == ERed);
      RotateLeft(brother, brother->iRChild, &(father->iLChild));

      brother = brother->iFather;
      brother->iColor = EBlack;
      brother->iLChild->iColor = ERed;
    }

    TTreeNode** pp_node = PointerOf(father);
    if(left){
      RotateLeft(father, brother, pp_node);
      brother->iRChild->iColor = EBlack;
    }else{
      RotateRight(father, brother, pp_node);
      brother->iLChild->iColor = EBlack;
    }

    brother->iColor = father->iColor;
    father->iColor = EBlack;
}

TTreeNode** CRBTree::PointerOf(TTreeNode* aNode){
    ASSERT(aNode);

    TTreeNode** pp_node;
    if(aNode->iFather){
      if(aNode->iFather->iLChild == aNode)
            pp_node = &aNode->iFather->iLChild;
      else
            pp_node = &aNode->iFather->iRChild;
    }else{
      pp_node = &iRoot;
    }

    return pp_node;
}

TTreeNode* CRBTree::FindNext(TTreeNode* aNode){
    ASSERT(aNode);

    TTreeNode* cur = aNode->iRChild;
    if(cur){
      while(cur->iLChild){
            cur = cur->iLChild;
      }
      return cur;
    }

    cur = aNode->iFather;
    while(cur){
      if(cur->iLChild == aNode){
            return cur;
      }
      aNode = cur;
      cur = cur->iFather;
    }

    return NULL;
}

TTreeNode* CRBTree::RFindNext(TTreeNode* aNode){
    ASSERT(aNode);

    TTreeNode* cur = aNode->iLChild;
    if(cur){
      while(cur->iRChild){
            cur = cur->iRChild;
      }
      return cur;
    }

    cur = aNode->iFather;
    while(cur){
      if(cur->iRChild == aNode){
            return cur;
      }
      aNode = cur;
      cur = cur->iFather;
    }

    return NULL;
}

void CRBTree::AdjustFindHandles(TTreeNode* aNode){
    TTreeIterator* it = iIterator;
    while(it){
      if(it->iNode == aNode){
            if(it->iDirection == EForward){
                it->iNode = FindNext(aNode);
            }else{
                it->iNode = RFindNext(aNode);
            }
      }
      it = it->iNext;
    }
}

TInt CRBTree::ValidateHandle(TInt aHandle){
    TTreeIterator* it = iIterator;
    TTreeIterator* in = (TTreeIterator *) aHandle;
    while(it){
      if(it == in){
            break;
      }
      it = it->iNext;
    }

    if(it == NULL){
      return -1;
    }
    return 0;
}

EXPORT_C TAny* CRBTree::Find(TAny* aUser){
    if(aUser == NULL){
      return NULL;
    }

    TInt flag = 0;
    TTreeNode* node = Find(aUser, flag);
    if(node == NULL || flag != 0){
      return NULL;
    }
    return node->iUser;   
}

TInt CRBTree::FindFirst(TAny* aUser, TDirect aDirect){
    if(aUser == NULL){
      return -1;
    }

    TInt flag = 0;
    TTreeNode* node = Find(aUser, flag);
    if(node == NULL){
      return -1;
    }

    if(flag == 0){
      TTreeIterator* it;
      TRAPD(err, it = new (ELeave) TTreeIterator(node, aDirect));
      if(KErrNone != err){
            return -1;
      }

      if(iIterator != NULL){
            it->iNext = iIterator;
            iIterator->iPrev = it;
      }

      iIterator = it;
      return (TInt) (iIterator);
    }

    return -1;
}

EXPORT_C TInt CRBTree::FindFirst(TAny* aUser){
    return FindFirst(aUser, EForward);
}

EXPORT_C TInt CRBTree::RFindFirst(TAny* aUser){
    return FindFirst(aUser, EBackward);
}

EXPORT_C TAny* CRBTree::FindNext(TInt handle){
    TTreeIterator* it = (TTreeIterator *) handle;
    if(it->iDirection != EForward){
      return EFailed;
    }

    TTreeNode* node = it->iNode;
    if(node == NULL){
      return NULL;
    }

    TTreeNode* next = FindNext(node);
    it->iNode = next;
    return node->iUser;
}

EXPORT_C TAny* CRBTree::FindNextSafe(TInt handle){
    if(-1 == ValidateHandle(handle)){
      return EFailed;
    }
    return FindNext(handle);
}

EXPORT_C TAny* CRBTree::RFindNext(TInt handle){
    TTreeIterator* it = (TTreeIterator *) handle;
    if(it->iDirection != EBackward){
      return EFailed;
    }

    TTreeNode* node = it->iNode;
    if(node == NULL){
      return NULL;
    }

    TTreeNode* next = RFindNext(node);
    it->iNode = next;
    return node->iUser;
}

EXPORT_C TAny* CRBTree::RFindNextSafe(TInt handle){
    if(-1 == ValidateHandle(handle)){
      return EFailed;
    }
    return RFindNext(handle);
}

EXPORT_C void CRBTree::CloseFindHandle(TInt handle){
    if(iIterator == NULL){
      return;
    }

    TTreeIterator* in = (TTreeIterator *) handle;
    if(iIterator == in){
      iIterator = in->iNext;
      if(iIterator)
            iIterator->iPrev = NULL;
    }else{
      in->iPrev->iNext = in->iNext;
      if(in->iNext)
            in->iNext->iPrev = in->iPrev;
    }

    delete in;
}
   
EXPORT_C void CRBTree::CloseFindHandleSafe(TInt handle){
    if(-1 != ValidateHandle(handle)){
      CloseFindHandle(handle);
    }
}

#ifdef _DEBUG
EXPORT_C TInt CRBTree::BlackHeight(){
    ASSERT(BLACK(iRoot));
    return BlackHeight(iRoot);
}

TInt CRBTree::BlackHeight(TTreeNode* aNode){
    TInt n = 0;
    if(BLACK(aNode)){
      n = 1;
    }else{
      ASSERT(BLACK(aNode->iLChild));
      ASSERT(BLACK(aNode->iRChild));
    }

    TInt n1 = 0;
    TInt n2 = 0;
    if(aNode){
      n1 = BlackHeight(aNode->iLChild);
      n2 = BlackHeight(aNode->iRChild);
    }
    ASSERT(n1 == n2);

    return (n + n1);
}
#endif

starwing83 发表于 2022-11-11 12:10

    TAny* oldkey = node->iUser;
    if(flag == 0){
      if(aRep){
            node->iUser = oldkey;
            return oldkey;
      }
      User::Leave(KErrAlreadyExists);
    }

AddL的这一段，应该是赋值aUser而不是oldkey吧？

pandaiam 发表于 2022-11-21 13:37

人都已经散了。。

zylthinking 发表于 2022-11-30 13:18

回复 2# starwing83

看上去像

zylthinking 发表于 2022-11-30 13:21

pandaiam 发表于 2022-11-21 13:37
人都已经散了。。

这代码以为早丢了， 然后科学上网上了一次 gmail 居然发现了
无论如何当时也写了好几天， 总要让它吹吹风

查看完整版本: 在一个死亡的论坛上发一个从未活过的代码， 致我已经风飘云散的过去