The Labs \ Source Viewer \ SSCLI \ System.Xml \ TernaryTreeReadOnly

  1. //------------------------------------------------------------------------------
  2. // <copyright file="ReadOnlyTernaryTree.cs" company="Microsoft">
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. // </copyright>
  14. //------------------------------------------------------------------------------
  15. using System;
  16. using System.IO;
  17. using System.Diagnostics;
  18. namespace System.Xml
  19. {
  20.    
  21.     // Array index to indicate the meaning of the each byte.
  22.     internal enum TernaryTreeByte
  23.     {
  24.         characterByte = 0,
  25.         leftTree = 1,
  26.         rightTree = 2,
  27.         data = 3
  28.     }
  29.    
  30.     //
  31.     // XSL HTML output method properties
  32.     //
  33.     // Keep the first four bits in sync, so that the element and attribute mask operation can be combined.
  34.     internal enum ElementProperties : uint
  35.     {
  36.         DEFAULT = 0,
  37.         URI_PARENT = 1,
  38.         BOOL_PARENT = 2,
  39.         NAME_PARENT = 4,
  40.         EMPTY = 8,
  41.         NO_ENTITIES = 16,
  42.         HEAD = 32,
  43.         BLOCK_WS = 64,
  44.         HAS_NS = 128
  45.     }
  46.     internal enum AttributeProperties : uint
  47.     {
  48.         DEFAULT = 0,
  49.         URI = 1,
  50.         BOOLEAN = 2,
  51.         NAME = 4
  52.     }
  53.    
  54.    
  55. /**
  56.     * TernaryTreeRO
  57.     * -------------
  58.     *
  59.     * Ternary tree implementation used to make fast dictionary lookups in pre-generated
  60.     * ternary trees.
  61.     *
  62.     * Note: Only strings composed of ASCII characters can exist in the tree.
  63.     */   
  64.     /// <include file='doc\ReadOnlyTernaryTree.uex' path='docs/doc[@for="TernaryTreeReadOnly"]/*' />
  65.     internal class TernaryTreeReadOnly
  66.     {
  67.        
  68.         byte[] nodeBuffer;
  69.        
  70.         //define the array positions
  71.        
  72.        
  73.         /// <include file='doc\ReadOnlyTernaryTree.uex' path='docs/doc[@for="TernaryTreeReadOnly.TernaryTreeReadOnly"]/*' />
  74.         public TernaryTreeReadOnly(byte[] nodeBuffer)
  75.         {
  76.             this.nodeBuffer = nodeBuffer;
  77.         }
  78.        
  79. /*  ----------------------------------------------------------------------------
  80.             findStringI()
  81.             Find a Unicode string in the ternary tree and return the data byte it's
  82.             mapped to.  Find is case-insensitive.
  83.         */       
  84.         /// <include file='doc\ReadOnlyTernaryTree.uex' path='docs/doc[@for="TernaryTreeReadOnly.FindCaseInsensitiveString"]/*' />
  85.         public byte FindCaseInsensitiveString(string stringToFind)
  86.         {
  87.            
  88.             //Debug.Assert(wszFind != null && wszFind.Length != 0);
  89.            
  90.             int stringPos = 0;
  91.             int nodePos = 0;
  92.             int charToFind;
  93.             int charInTheTree;
  94.             byte[] node = nodeBuffer;
  95.            
  96.             charToFind = stringToFind[stringPos];
  97.            
  98.             if (charToFind > 'z')
  99.                 return 0;
  100.             // Ternary tree only stores ASCII strings
  101.             if (charToFind >= 'a')
  102.                 charToFind -= ('a' - 'A');
  103.             // Normalize to upper case
  104.             while (true) {
  105.                 int pos = nodePos * 4;
  106.                
  107.                 charInTheTree = node[pos + (int)TernaryTreeByte.characterByte];
  108.                 //Console.WriteLine("charToFind: {0},charInTheTree: {1}, nodePos: {2}", charToFind, charInTheTree, nodePos);
  109.                
  110.                 if (charToFind < charInTheTree) {
  111.                    
  112.                     // If input character is less than the tree character, take the left branch
  113.                     if (node[pos + (int)TernaryTreeByte.leftTree] == 0) {
  114.                         break;
  115.                     }
  116.                     nodePos = nodePos + node[pos + (int)TernaryTreeByte.leftTree];
  117.                    
  118.                 }
  119.                 else if (charToFind > charInTheTree) {
  120.                     // If input character is greater than the tree character, take the right branch
  121.                     if (node[pos + (int)TernaryTreeByte.rightTree] == 0)
  122.                         break;
  123.                     nodePos = nodePos + node[pos + (int)TernaryTreeByte.rightTree];
  124.                    
  125.                 }
  126.                 else {
  127.                     // If input character is equal to the tree character, take the equal branch
  128.                     if (charToFind == 0)
  129.                         return node[pos + (int)TernaryTreeByte.data];
  130.                    
  131.                     // The offset for the equal branch is always one
  132.                     ++nodePos;
  133.                    
  134.                     // Move to the next input character
  135.                     ++stringPos;
  136.                     if (stringPos == stringToFind.Length) {
  137.                         charToFind = 0;
  138.                     }
  139.                     else {
  140.                         charToFind = stringToFind[stringPos];
  141.                         if (charToFind > 'z')
  142.                             return 0;
  143.                         // Ternary tree only stores ASCII strings
  144.                         if (charToFind >= 'a')
  145.                             charToFind -= ('a' - 'A');
  146.                         // Normalize to upper case
  147.                     }
  148.                 }
  149.             }
  150.            
  151.             // Return default
  152.             return 0;
  153.         }
  154.     }
  155. }

Developer Fusion