File: FrameworkFork\Microsoft.Xml\Xml\Cache\XPathNodeInfoAtom.cs
Web Access
Project: src\src\dotnet-svcutil\lib\src\dotnet-svcutil-lib.csproj (dotnet-svcutil-lib)
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
 
using System.Collections;
using System.Text;
using Microsoft.Xml;
using Microsoft.Xml.Schema;
using Microsoft.Xml.XPath;
using System.Diagnostics;
 
namespace MS.Internal.Xml.Cache
{
    /// <summary>
    /// The 0th node in each page contains a non-null reference to an XPathNodePageInfo internal class that provides
    /// information about that node's page.  The other fields in the 0th node are undefined and should never
    /// be used.
    /// </summary>
    sealed internal class XPathNodePageInfo
    {
        private int _pageNum;
        private int _nodeCount;
        private XPathNode[] _pagePrev;
        private XPathNode[] _pageNext;
 
        /// <summary>
        /// Constructor.
        /// </summary>
        public XPathNodePageInfo(XPathNode[] pagePrev, int pageNum)
        {
            _pagePrev = pagePrev;
            _pageNum = pageNum;
            _nodeCount = 1;         // Every node page contains PageInfo at 0th position
        }
 
        /// <summary>
        /// Return the sequential page number of the page containing nodes that share this information atom.
        /// </summary>
        public int PageNumber
        {
            get { return _pageNum; }
        }
 
        /// <summary>
        /// Return the number of nodes allocated in this page.
        /// </summary>
        public int NodeCount
        {
            get { return _nodeCount; }
            set { _nodeCount = value; }
        }
 
        /// <summary>
        /// Return the previous node page in the document.
        /// </summary>
        public XPathNode[] PreviousPage
        {
            get { return _pagePrev; }
        }
 
        /// <summary>
        /// Return the next node page in the document.
        /// </summary>
        public XPathNode[] NextPage
        {
            get { return _pageNext; }
            set { _pageNext = value; }
        }
    }
 
 
    /// <summary>
    /// There is a great deal of redundancy in typical Xml documents.  Even in documents with thousands or millions
    /// of nodes, there are a small number of common names and types.  And since nodes are allocated in pages in
    /// document order, nodes on the same page with the same name and type are likely to have the same sibling and
    /// parent pages as well.
    /// Redundant information is shared by creating immutable, atomized objects.  This is analogous to the
    /// string.Intern() operation.  If a node's name, type, or parent/sibling pages are modified, then a new
    /// InfoAtom needs to be obtained, since other nodes may still be referencing the old InfoAtom.
    /// </summary>
    sealed internal class XPathNodeInfoAtom
    {
        private string _localName;
        private string _namespaceUri;
        private string _prefix;
        private string _baseUri;
        private XPathNode[] _pageParent;
        private XPathNode[] _pageSibling;
        private XPathNode[] _pageSimilar;
        private XPathDocument _doc;
        private int _lineNumBase;
        private int _linePosBase;
        private int _hashCode;
        private int _localNameHash;
        private XPathNodeInfoAtom _next;
        private XPathNodePageInfo _pageInfo;
 
 
        /// <summary>
        /// Construct information for the 0th node in each page.  The only field which is defined is this.pageInfo,
        /// and it contains information about that page (pageNum, nextPage, etc.).
        /// </summary>
        public XPathNodeInfoAtom(XPathNodePageInfo pageInfo)
        {
            _pageInfo = pageInfo;
        }
 
        /// <summary>
        /// Construct a new shared information atom.  This method should only be used by the XNodeInfoTable.
        /// </summary>
        public XPathNodeInfoAtom(string localName, string namespaceUri, string prefix, string baseUri,
                                         XPathNode[] pageParent, XPathNode[] pageSibling, XPathNode[] pageSimilar,
                                         XPathDocument doc, int lineNumBase, int linePosBase)
        {
            Init(localName, namespaceUri, prefix, baseUri, pageParent, pageSibling, pageSimilar, doc, lineNumBase, linePosBase);
        }
 
        /// <summary>
        /// Initialize an existing shared information atom.  This method should only be used by the XNodeInfoTable.
        /// </summary>
        public void Init(string localName, string namespaceUri, string prefix, string baseUri,
                         XPathNode[] pageParent, XPathNode[] pageSibling, XPathNode[] pageSimilar,
                         XPathDocument doc, int lineNumBase, int linePosBase)
        {
            Debug.Assert(localName != null && namespaceUri != null && prefix != null && doc != null);
 
            _localName = localName;
            _namespaceUri = namespaceUri;
            _prefix = prefix;
            _baseUri = baseUri;
            _pageParent = pageParent;
            _pageSibling = pageSibling;
            _pageSimilar = pageSimilar;
            _doc = doc;
            _lineNumBase = lineNumBase;
            _linePosBase = linePosBase;
            _next = null;
            _pageInfo = null;
 
            _hashCode = 0;
            _localNameHash = 0;
            for (int i = 0; i < _localName.Length; i++)
                _localNameHash += (_localNameHash << 7) ^ _localName[i];
        }
 
        /// <summary>
        /// Returns information about the node page.  Only the 0th node on each page has this property defined.
        /// </summary>
        public XPathNodePageInfo PageInfo
        {
            get { return _pageInfo; }
        }
 
        /// <summary>
        /// Return the local name part of nodes that share this information atom.
        /// </summary>
        public string LocalName
        {
            get { return _localName; }
        }
 
        /// <summary>
        /// Return the namespace name part of nodes that share this information atom.
        /// </summary>
        public string NamespaceUri
        {
            get { return _namespaceUri; }
        }
 
        /// <summary>
        /// Return the prefix name part of nodes that share this information atom.
        /// </summary>
        public string Prefix
        {
            get { return _prefix; }
        }
 
        /// <summary>
        /// Return the base Uri of nodes that share this information atom.
        /// </summary>
        public string BaseUri
        {
            get { return _baseUri; }
        }
 
        /// <summary>
        /// Return the page containing the next sibling of nodes that share this information atom.
        /// </summary>
        public XPathNode[] SiblingPage
        {
            get { return _pageSibling; }
        }
 
        /// <summary>
        /// Return the page containing the next element having a name which has same hashcode as this element.
        /// </summary>
        public XPathNode[] SimilarElementPage
        {
            get { return _pageSimilar; }
        }
 
        /// <summary>
        /// Return the page containing the parent of nodes that share this information atom.
        /// </summary>
        public XPathNode[] ParentPage
        {
            get { return _pageParent; }
        }
 
        /// <summary>
        /// Return the page containing the owner document of nodes that share this information atom.
        /// </summary>
        public XPathDocument Document
        {
            get { return _doc; }
        }
 
        /// <summary>
        /// Return the line number to which a line number offset stored in the XPathNode is added.
        /// </summary>
        public int LineNumberBase
        {
            get { return _lineNumBase; }
        }
 
        /// <summary>
        /// Return the line position to which a line position offset stored in the XPathNode is added.
        /// </summary>
        public int LinePositionBase
        {
            get { return _linePosBase; }
        }
 
        /// <summary>
        /// Return cached hash code of the local name of nodes which share this information atom.
        /// </summary>
        public int LocalNameHashCode
        {
            get { return _localNameHash; }
        }
 
        /// <summary>
        /// Link together InfoAtoms that hash to the same hashtable bucket (should only be used by XPathNodeInfoTable)
        /// </summary>
        public XPathNodeInfoAtom Next
        {
            get { return _next; }
            set { _next = value; }
        }
 
        /// <summary>
        /// Return this information atom's hash code, previously computed for performance.
        /// </summary>
        public override int GetHashCode()
        {
            if (_hashCode == 0)
            {
                int hashCode;
 
                // Start with local name
                hashCode = _localNameHash;
 
                // Add page indexes
                if (_pageSibling != null)
                    hashCode += (hashCode << 7) ^ _pageSibling[0].PageInfo.PageNumber;
 
                if (_pageParent != null)
                    hashCode += (hashCode << 7) ^ _pageParent[0].PageInfo.PageNumber;
 
                if (_pageSimilar != null)
                    hashCode += (hashCode << 7) ^ _pageSimilar[0].PageInfo.PageNumber;
 
                // Save hashcode.  Don't save 0, so that it won't ever be recomputed.
                _hashCode = ((hashCode == 0) ? 1 : hashCode);
            }
 
            return _hashCode;
        }
 
        /// <summary>
        /// Return true if this InfoAtom has the same values as another InfoAtom.
        /// </summary>
        public override bool Equals(object other)
        {
            XPathNodeInfoAtom that = other as XPathNodeInfoAtom;
            Debug.Assert(that != null);
            Debug.Assert((object)_doc == (object)that._doc);
            Debug.Assert(_pageInfo == null);
 
            // Assume that name parts are atomized
            if (this.GetHashCode() == that.GetHashCode())
            {
                if ((object)_localName == (object)that._localName &&
                    (object)_pageSibling == (object)that._pageSibling &&
                    (object)_namespaceUri == (object)that._namespaceUri &&
                    (object)_pageParent == (object)that._pageParent &&
                    (object)_pageSimilar == (object)that._pageSimilar &&
                    (object)_prefix == (object)that._prefix &&
                    (object)_baseUri == (object)that._baseUri &&
                    _lineNumBase == that._lineNumBase &&
                    _linePosBase == that._linePosBase)
                {
                    return true;
                }
            }
            return false;
        }
 
        /// <summary>
        /// Return InfoAtom formatted as a string:
        ///     hash=xxx, {http://my.com}foo:bar, parent=1, sibling=1, lineNum=0, linePos=0
        /// </summary>
        public override string ToString()
        {
            StringBuilder bldr = new StringBuilder();
 
            bldr.Append("hash=");
            bldr.Append(GetHashCode());
            bldr.Append(", ");
 
            if (_localName.Length != 0)
            {
                bldr.Append('{');
                bldr.Append(_namespaceUri);
                bldr.Append('}');
 
                if (_prefix.Length != 0)
                {
                    bldr.Append(_prefix);
                    bldr.Append(':');
                }
 
                bldr.Append(_localName);
                bldr.Append(", ");
            }
 
            if (_pageParent != null)
            {
                bldr.Append("parent=");
                bldr.Append(_pageParent[0].PageInfo.PageNumber);
                bldr.Append(", ");
            }
 
            if (_pageSibling != null)
            {
                bldr.Append("sibling=");
                bldr.Append(_pageSibling[0].PageInfo.PageNumber);
                bldr.Append(", ");
            }
 
            if (_pageSimilar != null)
            {
                bldr.Append("similar=");
                bldr.Append(_pageSimilar[0].PageInfo.PageNumber);
                bldr.Append(", ");
            }
 
            bldr.Append("lineNum=");
            bldr.Append(_lineNumBase);
            bldr.Append(", ");
 
            bldr.Append("linePos=");
            bldr.Append(_linePosBase);
 
            return bldr.ToString();
        }
    }
 
 
    /// <summary>
    /// An atomization table for XPathNodeInfoAtom.
    /// </summary>
    sealed internal class XPathNodeInfoTable
    {
        private XPathNodeInfoAtom[] _hashTable;
        private int _sizeTable;
        private XPathNodeInfoAtom _infoCached;
 
#if DEBUG
        private const int DefaultTableSize = 2;
#else
        private const int DefaultTableSize = 32;
#endif
 
        /// <summary>
        /// Constructor.
        /// </summary>
        public XPathNodeInfoTable()
        {
            _hashTable = new XPathNodeInfoAtom[DefaultTableSize];
            _sizeTable = 0;
        }
 
        /// <summary>
        /// Create a new XNodeInfoAtom and ensure it is atomized in the table.
        /// </summary>
        public XPathNodeInfoAtom Create(string localName, string namespaceUri, string prefix, string baseUri,
                                          XPathNode[] pageParent, XPathNode[] pageSibling, XPathNode[] pageSimilar,
                                          XPathDocument doc, int lineNumBase, int linePosBase)
        {
            XPathNodeInfoAtom info;
 
            // If this.infoCached already exists, then reuse it; else create new InfoAtom
            if (_infoCached == null)
            {
                info = new XPathNodeInfoAtom(localName, namespaceUri, prefix, baseUri,
                                             pageParent, pageSibling, pageSimilar,
                                             doc, lineNumBase, linePosBase);
            }
            else
            {
                info = _infoCached;
                _infoCached = info.Next;
 
                info.Init(localName, namespaceUri, prefix, baseUri,
                          pageParent, pageSibling, pageSimilar,
                          doc, lineNumBase, linePosBase);
            }
 
            return Atomize(info);
        }
 
 
        /// <summary>
        /// Add a shared information item to the atomization table.  If a matching item already exists, then that
        /// instance is returned.  Otherwise, a new item is created.  Thus, if itemX and itemY have both been added
        /// to the same InfoTable:
        /// 1. itemX.Equals(itemY) != true
        /// 2. (object) itemX != (object) itemY
        /// </summary>
        private XPathNodeInfoAtom Atomize(XPathNodeInfoAtom info)
        {
            XPathNodeInfoAtom infoNew, infoNext;
 
            // Search for existing XNodeInfoAtom in the table
            infoNew = _hashTable[info.GetHashCode() & (_hashTable.Length - 1)];
            while (infoNew != null)
            {
                if (info.Equals(infoNew))
                {
                    // Found existing atom, so return that.  Reuse "info".
                    info.Next = _infoCached;
                    _infoCached = info;
                    return infoNew;
                }
                infoNew = infoNew.Next;
            }
 
            // Expand table and rehash if necessary
            if (_sizeTable >= _hashTable.Length)
            {
                XPathNodeInfoAtom[] oldTable = _hashTable;
                _hashTable = new XPathNodeInfoAtom[oldTable.Length * 2];
 
                for (int i = 0; i < oldTable.Length; i++)
                {
                    infoNew = oldTable[i];
                    while (infoNew != null)
                    {
                        infoNext = infoNew.Next;
                        AddInfo(infoNew);
                        infoNew = infoNext;
                    }
                }
            }
 
            // Can't find an existing XNodeInfoAtom, so use the one that was passed in
            AddInfo(info);
 
            return info;
        }
 
        /// <summary>
        /// Add a previously constructed InfoAtom to the table.  If a collision occurs, then insert "info"
        /// as the head of a linked list.
        /// </summary>
        private void AddInfo(XPathNodeInfoAtom info)
        {
            int idx = info.GetHashCode() & (_hashTable.Length - 1);
            info.Next = _hashTable[idx];
            _hashTable[idx] = info;
            _sizeTable++;
        }
 
        /// <summary>
        /// Return InfoAtomTable formatted as a string.
        /// </summary>
        public override string ToString()
        {
            StringBuilder bldr = new StringBuilder();
            XPathNodeInfoAtom infoAtom;
 
            for (int i = 0; i < _hashTable.Length; i++)
            {
                bldr.AppendFormat("{0,4}: ", i);
 
                infoAtom = _hashTable[i];
 
                while (infoAtom != null)
                {
                    if ((object)infoAtom != (object)_hashTable[i])
                        bldr.Append("\n      ");
 
                    bldr.Append(infoAtom);
 
                    infoAtom = infoAtom.Next;
                }
 
                bldr.Append('\n');
            }
 
            return bldr.ToString();
        }
    }
}