mDNSMacOSX/BonjourTop/source/LLRBTree.cpp

   1 //
   2 //  LLRBTree.cpp
   3 //  TestTB
   4 //
   5 //  Created by Terrin Eager on 7/9/12.
   6 //
   7 //
   8
   9 #include "LLRBTree.h"
  10
  11
  12
  13 #include <stdio.h>
  14 #import <stdlib.h>
  15 #include <string.h>
  16 #include <curses.h>
  17
  18 #include "bjtypes.h"
  19
  20 #include <time.h>
  21
  22 void test3();
  23
  24
  25
  26
  27
  28
  29 ////////////////////
  30
  31 ////////////////
  32 // test case
  33 // Integrity checks
  34
  35 /*********************
  36 BJ_BOOL isBST(CRBNode* pRecord, BJ_UINT64 min, BJ_UINT64 max);
  37 BJ_BOOL is234(CRBNode* pRecord);
  38 BJ_BOOL isBalanced(CLLRBTree* pCache);
  39 BJ_BOOL isBalancedNode(CRBNode* pRecord, int black);
  40
  41 BJ_BOOL check(CLLRBTree* pCache)
  42 {  // Is this tree a red-black tree?
  43     BJ_BOOL bBST = isBST(pCache->GetRoot(),pCache->minRecord(pCache->GetRoot())->nKey,pCache->maxRecord(pCache->GetRoot())->nKey);
  44     BJ_BOOL b234 = is234(pCache->GetRoot());
  45     BJ_BOOL bisBalanced = isBalanced(pCache);
  46
  47     printf("Bst=%d,234=%d, Balanced=%d",bBST,b234,bisBalanced);
  48
  49     return bBST && b234 && bisBalanced;
  50 }
  51
  52
  53 BJ_BOOL isBST(CRBNode* pRecord, BJ_UINT64 min, BJ_UINT64 max)
  54 {  // Are all the values in the BST rooted at x between min and max,
  55     // and does the same property hold for both subtrees?
  56     if (pRecord == NULL) return 1;
  57     if ((pRecord->nKey > min) || (max > pRecord->nKey)) return 0;
  58     return isBST(pRecord->m_rbLeft, min, pRecord->nKey) && isBST(pRecord->m_rbRight, pRecord->nKey, max);
  59 }
  60 BJ_BOOL is234(CRBNode* pRecord)
  61 {  // Does the tree have no red right links, and at most two (left)
  62     // red links in a row on any path?
  63     if (pRecord == NULL) return 1;
  64     if (IsRed(pRecord->m_rbRight)) return 0;
  65     if (IsRed(pRecord))
  66         if (IsRed(pRecord->m_rbLeft))
  67             if (IsRed(pRecord->m_rbLeft->m_rbLeft)) return 0;
  68     return is234(pRecord->m_rbLeft) && is234(pRecord->m_rbRight);
  69 }
  70
  71 BJ_BOOL isBalanced(CLLRBTree* pCache)
  72 { // Do all paths from root to leaf have same number of black edges?
  73     int black = 0;     // number of black links on path from root to min
  74     CRBNode* pRecord = pCache->m_Root;
  75     while (pRecord != NULL)
  76     {
  77         if (!IsRed(pRecord)) black++;
  78         pRecord = pRecord->m_rbLeft;
  79     }
  80     return isBalancedNode(pCache->root, black);
  81 }
  82
  83 BJ_BOOL isBalancedNode(CRBNode* pRecord, int black)
  84 { // Does every path from the root to a leaf have the given number
  85     // of black links?
  86     if      (pRecord == NULL && black == 0) return 1;
  87     else if (pRecord == NULL && black != 0) return 0;
  88     if (!IsRed(pRecord)) black--;
  89     return isBalancedNode(pRecord->m_rbLeft, black) && isBalancedNode(pRecord->m_rbRight, black);
  90 }
  91 ****************/
  92
  93 /**
  94 // sample code for testing
  95 void CStringNode_test()
  96 {
  97     CStringTree Cache;
  98
  99
 100     char DummyData[] = {'a','b','d','x'};
 101     BJ_UINT64 i = 0;
 102     CStringNode* pRecord;
 103
 104     while (i++ < sizeof(DummyData))
 105     {
 106
 107         pRecord = (CStringNode*)Cache.FindwithAddRecord(&i);
 108         if (pRecord)
 109             pRecord->m_Value[0] = DummyData[i];
 110     }
 111
 112     i = 2;
 113     pRecord = (CStringNode*)Cache.Find(&i);
 114
 115
 116     test3();
 117
 118 }
 119
 120 void test3()
 121 {
 122     //  float nSaveCPU =0;
 123
 124     CStringTree Cache;
 125
 126     CStringNode test;
 127
 128
 129     BJ_UINT64 i = 0;
 130     long starttime = clock();
 131     float elapsedtime = 0;
 132     CStringNode* pRecord;
 133
 134     // nSaveCPU = getCPUtime();
 135     while (i++ < 1000000)
 136     {
 137         pRecord = (CStringNode*) Cache.FindwithAddRecord(&i);
 138         if (pRecord)
 139             memccpy(pRecord->m_Value, "test",4, 1);
 140
 141         // snprintf(pRecord->m_Value,sizeof(pRecord->m_Value),"%llx",key.m_nKey);
 142     }
 143     elapsedtime = clock() - starttime;
 144     elapsedtime /= CLOCKS_PER_SEC;
 145
 146     // elapsedtime = getCPUtime() - nSaveCPU;
 147
 148     printf("Test elapsed time %f, check = %d\n",elapsedtime,0);
 149
 150
 151
 152
 153 }
 154
 155 *****/
 156 ///////////////
 157