The Labs \ Source Viewer \ SSCLI \ System.Net \ ICredentialPolicy

  1. //------------------------------------------------------------------------------
  2. // <copyright file="AuthenticationManager.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. namespace System.Net
  16. {
  17.    
  18.     using System.Collections;
  19.     using System.Collections.Generic;
  20.     using System.Collections.Specialized;
  21.     using System.Configuration;
  22.     using System.Globalization;
  23.     using System.Net.Configuration;
  24.     using System.Reflection;
  25.     using System.Security.Permissions;
  26.     using System;
  27.     using System.Threading;
  28.    
  29.    
  30.     //
  31.     // A contract that applications can use to restrict auth scenarios in current appDomain
  32.     //
  33.     public interface ICredentialPolicy
  34.     {
  35.         bool ShouldSendCredential(Uri challengeUri, WebRequest request, NetworkCredential credential, IAuthenticationModule authenticationModule);
  36.     }
  37.    
  38.     /// <devdoc>
  39.     /// <para>Manages the authentication modules called during the client authentication
  40.     /// process.</para>
  41.     /// </devdoc>
  42.     public class AuthenticationManager
  43.     {
  44.        
  45.         //also used as a lock object
  46.         private static PrefixLookup s_ModuleBinding = new PrefixLookup();
  47.        
  48.         private static ArrayList s_ModuleList;
  49.         private static ICredentialPolicy s_ICredentialPolicy;
  50.         private static SpnDictionary m_SpnDictionary = new SpnDictionary();
  51.        
  52.         // not creatable...
  53.         //
  54.         private AuthenticationManager()
  55.         {
  56.         }
  57.        
  58.         //
  59.         //
  60.         //
  61.         public static ICredentialPolicy CredentialPolicy {
  62.             get { return s_ICredentialPolicy; }
  63.             set {
  64.                 ExceptionHelper.ControlPolicyPermission.Demand();
  65.                 s_ICredentialPolicy = value;
  66.             }
  67.         }
  68.         //
  69.         //
  70.         public static StringDictionary CustomTargetNameDictionary {
  71.             get { return m_SpnDictionary; }
  72.         }
  73.         //
  74.         // This will give access to some internal methods
  75.         //
  76.         static internal SpnDictionary SpnDictionary {
  77.             get { return m_SpnDictionary; }
  78.         }
  79.        
  80.         //
  81.         //
  82.         static internal void EnsureConfigLoaded()
  83.         {
  84.             try {
  85.                 object o = ModuleList;
  86.             }
  87.             catch (Exception e) {
  88.                 if (e is ThreadAbortException || e is OutOfMemoryException || e is StackOverflowException)
  89.                     throw;
  90.                 // A Config System has circular dependency on HttpWebRequest so they call this method to
  91.                 // trigger the config. For some reason they don't want any exceptions from here.
  92.             }
  93.             catch {
  94.                 // A Config System has circular dependency on HttpWebRequest so they call this method to
  95.                 // trigger the config. For some reason they don't want any exceptions from here.
  96.             }
  97.         }
  98.        
  99.         //
  100.         // ModuleList - static initialized property -
  101.         // contains list of Modules used for Authentication
  102.         //
  103.        
  104.         private static ArrayList ModuleList {
  105.            
  106.             get {
  107.                
  108.                 //
  109.                 // GetConfig() might use us, so we have a circular dependency issue,
  110.                 // that causes us to nest here, we grab the lock, only
  111.                 // if we haven't initialized, or another thread is busy in initialization
  112.                 //
  113.                
  114.                 if (s_ModuleList == null) {
  115.                     lock (s_ModuleBinding) {
  116.                         if (s_ModuleList == null) {
  117.                             GlobalLog.Print("AuthenticationManager::Initialize(): calling ConfigurationManager.GetSection()");
  118.                            
  119.                             // This will never come back as null. Additionally, it will
  120.                             // have the items the user wants available.
  121.                             List<Type> authenticationModuleTypes = AuthenticationModulesSectionInternal.GetSection().AuthenticationModules;
  122.                            
  123.                             //
  124.                             // Should be registered in a growing list of encryption/algorithm strengths
  125.                             // basically, walk through a list of Types, and create new Auth objects
  126.                             // from them.
  127.                             //
  128.                             // order is meaningful here:
  129.                             // load the registered list of auth types
  130.                             // with growing level of encryption.
  131.                             //
  132.                            
  133.                             ArrayList moduleList = new ArrayList();
  134.                             IAuthenticationModule moduleToRegister;
  135.                             foreach (Type type in authenticationModuleTypes) {
  136.                                 try {
  137.                                         // Binder
  138.                                         // no arguments
  139.                                     moduleToRegister = Activator.CreateInstance(type, BindingFlags.CreateInstance | BindingFlags.Instance | BindingFlags.NonPublic | BindingFlags.Public, null, new object[0], CultureInfo.InvariantCulture) as IAuthenticationModule;
  140.                                     if (moduleToRegister != null) {
  141.                                         GlobalLog.Print("WebRequest::Initialize(): Register:" + moduleToRegister.AuthenticationType);
  142.                                         RemoveAuthenticationType(moduleList, moduleToRegister.AuthenticationType);
  143.                                         moduleList.Add(moduleToRegister);
  144.                                     }
  145.                                 }
  146.                                 catch (Exception exception) {
  147.                                     //
  148.                                     // ignore failure (log exception for debugging)
  149.                                     //
  150.                                     GlobalLog.Print("AuthenticationManager::constructor failed to initialize: " + exception.ToString());
  151.                                 }
  152.                                 catch {
  153.                                     //
  154.                                     // ignore failure (log exception for debugging)
  155.                                     //
  156.                                     GlobalLog.Print("AuthenticationManager::constructor failed to initialize: Non-CLS Compliant Exception");
  157.                                 }
  158.                             }
  159.                            
  160.                             s_ModuleList = moduleList;
  161.                         }
  162.                     }
  163.                 }
  164.                
  165.                 return s_ModuleList;
  166.             }
  167.         }
  168.        
  169.        
  170.         private static void RemoveAuthenticationType(ArrayList list, string typeToRemove)
  171.         {
  172.             for (int i = 0; i < list.Count; ++i) {
  173.                 if (string.Compare(((IAuthenticationModule)list[i]).AuthenticationType, typeToRemove, StringComparison.OrdinalIgnoreCase) == 0) {
  174.                     list.RemoveAt(i);
  175.                     break;
  176.                 }
  177.                
  178.             }
  179.         }
  180.        
  181.         /// <devdoc>
  182.         /// <para>Call each registered authentication module to determine the first module that
  183.         /// can respond to the authentication request.</para>
  184.         /// </devdoc>
  185.         public static Authorization Authenticate(string challenge, WebRequest request, ICredentials credentials)
  186.         {
  187.             //
  188.             // parameter validation
  189.             //
  190.             if (request == null) {
  191.                 throw new ArgumentNullException("request");
  192.             }
  193.             if (credentials == null) {
  194.                 throw new ArgumentNullException("credentials");
  195.             }
  196.             if (challenge == null) {
  197.                 throw new ArgumentNullException("challenge");
  198.             }
  199.            
  200.             GlobalLog.Print("AuthenticationManager::Authenticate() challenge:[" + challenge + "]");
  201.            
  202.             Authorization response = null;
  203.            
  204.             HttpWebRequest httpWebRequest = request as HttpWebRequest;
  205.             if (httpWebRequest != null && httpWebRequest.CurrentAuthenticationState.Module != null) {
  206.                 response = httpWebRequest.CurrentAuthenticationState.Module.Authenticate(challenge, request, credentials);
  207.             }
  208.             else {
  209.                 // This is the case where we would try to find the module on the first server challenge
  210.                 lock (s_ModuleBinding) {
  211.                     //
  212.                     // fastest way of iterating on the ArryList
  213.                     //
  214.                     for (int i = 0; i < ModuleList.Count; i++) {
  215.                         IAuthenticationModule authenticationModule = (IAuthenticationModule)ModuleList[i];
  216.                         //
  217.                         // the AuthenticationModule will
  218.                         // 1) return a valid string on success
  219.                         // 2) return null if it knows it cannot respond
  220.                         // 3) throw if it could have responded but unexpectedly failed to do so
  221.                         //
  222.                         if (httpWebRequest != null) {
  223.                             httpWebRequest.CurrentAuthenticationState.Module = authenticationModule;
  224.                         }
  225.                         response = authenticationModule.Authenticate(challenge, request, credentials);
  226.                        
  227.                         if (response != null) {
  228.                             //
  229.                             // found the Authentication Module, return it
  230.                             //
  231.                             GlobalLog.Print("AuthenticationManager::Authenticate() found IAuthenticationModule:[" + authenticationModule.AuthenticationType + "]");
  232.                             break;
  233.                         }
  234.                     }
  235.                 }
  236.             }
  237.            
  238.             return response;
  239.         }
  240.        
  241.         /// <devdoc>
  242.         /// <para>Pre-authenticates a request.</para>
  243.         /// </devdoc>
  244.         public static Authorization PreAuthenticate(WebRequest request, ICredentials credentials)
  245.         {
  246.             GlobalLog.Print("AuthenticationManager::PreAuthenticate() request:" + ValidationHelper.HashString(request) + " credentials:" + ValidationHelper.HashString(credentials));
  247.             if (request == null) {
  248.                 throw new ArgumentNullException("request");
  249.             }
  250.             if (credentials == null) {
  251.                 return null;
  252.             }
  253.            
  254.             HttpWebRequest httpWebRequest = request as HttpWebRequest;
  255.             IAuthenticationModule authenticationModule;
  256.             if (httpWebRequest == null)
  257.                 return null;
  258.            
  259.             //
  260.             // PrefixLookup is thread-safe
  261.             //
  262.             string moduleName = s_ModuleBinding.Lookup(httpWebRequest.ChallengedUri.AbsoluteUri) as string;
  263.             GlobalLog.Print("AuthenticationManager::PreAuthenticate() s_ModuleBinding.Lookup returns:" + ValidationHelper.ToString(moduleName));
  264.             if (moduleName == null)
  265.                 return null;
  266.             authenticationModule = findModule(moduleName);
  267.             if (authenticationModule == null) {
  268.                 // The module could have been unregistered
  269.                 // No preauthentication is possible
  270.                 return null;
  271.             }
  272.            
  273.             // Otherwise invoke the PreAuthenticate method
  274.             // we're guaranteed that CanPreAuthenticate is true because we check before calling BindModule()
  275.             Authorization authorization = authenticationModule.PreAuthenticate(request, credentials);
  276.            
  277.             if (authorization != null && !authorization.Complete && httpWebRequest != null)
  278.                 httpWebRequest.CurrentAuthenticationState.Module = authenticationModule;
  279.            
  280.             GlobalLog.Print("AuthenticationManager::PreAuthenticate() IAuthenticationModule.PreAuthenticate() returned authorization:" + ValidationHelper.HashString(authorization));
  281.             return authorization;
  282.         }
  283.        
  284.        
  285.         /// <devdoc>
  286.         /// <para>Registers an authentication module with the authentication manager.</para>
  287.         /// </devdoc>
  288.         public static void Register(IAuthenticationModule authenticationModule)
  289.         {
  290.             ExceptionHelper.UnmanagedPermission.Demand();
  291.             if (authenticationModule == null) {
  292.                 throw new ArgumentNullException("authenticationModule");
  293.             }
  294.             GlobalLog.Print("AuthenticationManager::Register() registering :[" + authenticationModule.AuthenticationType + "]");
  295.             lock (s_ModuleBinding) {
  296.                 IAuthenticationModule existentModule = findModule(authenticationModule.AuthenticationType);
  297.                 if (existentModule != null) {
  298.                     ModuleList.Remove(existentModule);
  299.                 }
  300.                 ModuleList.Add(authenticationModule);
  301.             }
  302.         }
  303.        
  304.         /// <devdoc>
  305.         /// <para>Unregisters authentication modules for an authentication scheme.</para>
  306.         /// </devdoc>
  307.         public static void Unregister(IAuthenticationModule authenticationModule)
  308.         {
  309.             ExceptionHelper.UnmanagedPermission.Demand();
  310.             if (authenticationModule == null) {
  311.                 throw new ArgumentNullException("authenticationModule");
  312.             }
  313.             GlobalLog.Print("AuthenticationManager::Unregister() unregistering :[" + authenticationModule.AuthenticationType + "]");
  314.             lock (s_ModuleBinding) {
  315.                 if (!ModuleList.Contains(authenticationModule)) {
  316.                     throw new InvalidOperationException(SR.GetString(SR.net_authmodulenotregistered));
  317.                 }
  318.                 ModuleList.Remove(authenticationModule);
  319.             }
  320.         }
  321.         /// <devdoc>
  322.         /// <para>Unregisters authentication modules for an authentication scheme.</para>
  323.         /// </devdoc>
  324.         public static void Unregister(string authenticationScheme)
  325.         {
  326.             ExceptionHelper.UnmanagedPermission.Demand();
  327.             if (authenticationScheme == null) {
  328.                 throw new ArgumentNullException("authenticationScheme");
  329.             }
  330.             GlobalLog.Print("AuthenticationManager::Unregister() unregistering :[" + authenticationScheme + "]");
  331.             lock (s_ModuleBinding) {
  332.                 IAuthenticationModule existentModule = findModule(authenticationScheme);
  333.                 if (existentModule == null) {
  334.                     throw new InvalidOperationException(SR.GetString(SR.net_authschemenotregistered));
  335.                 }
  336.                 ModuleList.Remove(existentModule);
  337.             }
  338.         }
  339.        
  340.         /// <devdoc>
  341.         /// <para>
  342.         /// Returns a list of registered authentication modules.
  343.         /// </para>
  344.         /// </devdoc>
  345.         public static IEnumerator RegisteredModules {
  346.             get { return ModuleList.GetEnumerator(); }
  347.         }
  348.        
  349.         /// <devdoc>
  350.         /// <para>
  351.         /// Binds an authentication response to a request for pre-authentication.
  352.         /// </para>
  353.         /// </devdoc>
  354.         // Create binding between an authorization response and the module
  355.         // generating that response
  356.         // This association is used for deciding which module to invoke
  357.         // for preauthentication purposes
  358.         static internal void BindModule(Uri uri, Authorization response, IAuthenticationModule module)
  359.         {
  360.             GlobalLog.Assert(module.CanPreAuthenticate, "AuthenticationManager::BindModule()|module.CanPreAuthenticate == false");
  361.             if (response.ProtectionRealm != null) {
  362.                 // The authentication module specified which Uri prefixes
  363.                 // will be preauthenticated
  364.                 string[] prefix = response.ProtectionRealm;
  365.                
  366.                 for (int k = 0; k < prefix.Length; k++) {
  367.                     //
  368.                     // PrefixLookup is thread-safe
  369.                     //
  370.                     s_ModuleBinding.Add(prefix[k], module.AuthenticationType);
  371.                 }
  372.             }
  373.             else {
  374.                 // Otherwise use the default policy for "fabricating"
  375.                 // some protection realm generalizing the particular Uri
  376.                 string prefix = generalize(uri);
  377.                 //
  378.                 // PrefixLookup is thread-safe
  379.                 //
  380.                 s_ModuleBinding.Add(prefix, module.AuthenticationType);
  381.             }
  382.         }
  383.        
  384.         //
  385.         // Lookup module by AuthenticationType
  386.         //
  387.         private static IAuthenticationModule findModule(string authenticationType)
  388.         {
  389.             IAuthenticationModule returnAuthenticationModule = null;
  390.             ArrayList moduleList = ModuleList;
  391.             IAuthenticationModule authenticationModule;
  392.             for (int k = 0; k < moduleList.Count; k++) {
  393.                 authenticationModule = (IAuthenticationModule)moduleList[k];
  394.                 if (string.Compare(authenticationModule.AuthenticationType, authenticationType, StringComparison.OrdinalIgnoreCase) == 0) {
  395.                     returnAuthenticationModule = authenticationModule;
  396.                     break;
  397.                 }
  398.             }
  399.             return returnAuthenticationModule;
  400.         }
  401.        
  402.         // This function returns a prefix of the given absolute Uri
  403.         // which will be used for associating authentication information
  404.         // The purpose is to associate the module-binding not with a single
  405.         // Uri but some collection generalizing that Uri to the loosely-defined
  406.         // notion of "protection realm"
  407.         private static string generalize(Uri location)
  408.         {
  409.             string completeUri = location.AbsoluteUri;
  410.             int lastFwdSlash = completeUri.LastIndexOf('/');
  411.             if (lastFwdSlash < 0) {
  412.                 return completeUri;
  413.             }
  414.             return completeUri.Substring(0, lastFwdSlash + 1);
  415.         }
  416.        
  417.         //
  418.         // The method will extract the blob that does correspond to the moduled with the name passed in signature parameter
  419.         // The method avoids confusion arisen from the parameters passed in a quoted string, such as:
  420.         // WWW-Authenticate: Digest username="NTLM", realm="wit", NTLM ...
  421.         //
  422.         static internal int FindSubstringNotInQuotes(string challenge, string signature)
  423.         {
  424.             int index = -1;
  425.             if (challenge != null && signature != null && challenge.Length >= signature.Length) {
  426.                 int firstQuote = -1;
  427.                 int secondQuote = -1;
  428.                 for (int i = 0; i < challenge.Length; i++) {
  429.                     if (challenge[i] == '"') {
  430.                         if (firstQuote <= secondQuote)
  431.                             firstQuote = i;
  432.                         else
  433.                             secondQuote = i;
  434.                     }
  435.                    
  436.                     if (i == challenge.Length - 1 || (challenge[i] == '"' && firstQuote > secondQuote)) {
  437.                         // see if the portion of challenge out of the quotes contains
  438.                         // the signature of the IAuthenticationModule
  439.                         if (i == challenge.Length - 1)
  440.                             firstQuote = challenge.Length;
  441.                        
  442.                         if (firstQuote < secondQuote + 3)
  443.                             continue;
  444.                        
  445.                         index = IndexOf(challenge, signature, secondQuote + 1, firstQuote - secondQuote - 1);
  446.                        
  447.                         if (index >= 0) {
  448.                             if ((index == 0 || challenge[index - 1] == ' ' || challenge[index - 1] == ',') && (index + signature.Length == challenge.Length || challenge[index + signature.Length] == ' ' || challenge[index + signature.Length] == ',')) {
  449.                                 break;
  450.                             }
  451.                             index = -1;
  452.                         }
  453.                     }
  454.                 }
  455.             }
  456.             GlobalLog.Print("AuthenticationManager::FindSubstringNotInQuotes(" + challenge + ", " + signature + ")=" + index.ToString());
  457.             return index;
  458.         }
  459.         //
  460.         private static int IndexOf(string challenge, string lwrCaseSignature, int start, int count)
  461.         {
  462.             count += start + 1 - lwrCaseSignature.Length;
  463.             for (; start < count; ++start) {
  464.                 int i = 0;
  465.                 for (; i < lwrCaseSignature.Length; ++i) {
  466.                     // force a challenge char to lowecase (safe assuming it works on trusted ASCII source)
  467.                     if ((challenge[start + i] | 32) != lwrCaseSignature[i])
  468.                         break;
  469.                 }
  470.                 if (i == lwrCaseSignature.Length)
  471.                     return start;
  472.             }
  473.             return -1;
  474.         }
  475.         //
  476.         // this method is called by the IAuthenticationModule implementations
  477.         // (mainly Digest) to safely find their list of parameters in a challenge.
  478.         // it returns the index of the first ',' that is not included in quotes,
  479.         // -1 is returned on error or end of string. on return offset contains the
  480.         // index of the first '=' that is not included in quotes, -1 if no '=' was found.
  481.         //
  482.         static internal int SplitNoQuotes(string challenge, ref int offset)
  483.         {
  484.             // GlobalLog.Print("SplitNoQuotes([" + challenge + "], " + offset.ToString() + ")");
  485.             //
  486.             // save offset
  487.             //
  488.             int realOffset = offset;
  489.             //
  490.             // default is not found
  491.             //
  492.             offset = -1;
  493.            
  494.             if (challenge != null && realOffset < challenge.Length) {
  495.                 int firstQuote = -1;
  496.                 int secondQuote = -1;
  497.                
  498.                 for (int i = realOffset; i < challenge.Length; i++) {
  499.                     //
  500.                     // firstQuote>secondQuote means we are in a quoted string
  501.                     //
  502.                     if (firstQuote > secondQuote && challenge[i] == '\\' && i + 1 < challenge.Length && challenge[i + 1] == '"') {
  503.                         //
  504.                         // skip <\"> when in a quoted string
  505.                         //
  506.                         i++;
  507.                     }
  508.                     else if (challenge[i] == '"') {
  509.                         if (firstQuote <= secondQuote) {
  510.                             firstQuote = i;
  511.                         }
  512.                         else {
  513.                             secondQuote = i;
  514.                         }
  515.                     }
  516.                     else if (challenge[i] == '=' && firstQuote <= secondQuote && offset < 0) {
  517.                         offset = i;
  518.                     }
  519.                     else if (challenge[i] == ',' && firstQuote <= secondQuote) {
  520.                         return i;
  521.                     }
  522.                 }
  523.             }
  524.            
  525.             return -1;
  526.         }
  527.        
  528.        
  529.        
  530.     }
  531.     // class AuthenticationManager
  532.     //
  533.     // This internal class implements a data structure which can be
  534.     // used for storing a set of objects keyed by string prefixes
  535.     // Looking up an object given a string returns the value associated
  536.     // with the longest matching prefix
  537.     // (A prefix "matches" a string IFF the string starts with that prefix
  538.     // The degree of the match is prefix length)
  539.     //
  540.     internal class PrefixLookup
  541.     {
  542.         //
  543.         // our prefix store (a Hashtable) needs to support multiple readers and multiple writers.
  544.         // the documentation on Hashtable says:
  545.         // "A Hashtable can safely support one writer and multiple readers concurrently.
  546.         // To support multiple writers, all operations must be done through the wrapper
  547.         // returned by the Synchronized method."
  548.         // it's safe enough, for our use, to just synchronize (with a call to lock()) all write operations
  549.         // so we always fall in the supported "one writer and multiple readers" scenario.
  550.         //
  551.         private Hashtable m_Store = new Hashtable();
  552.        
  553.         internal void Add(string prefix, object value)
  554.         {
  555.             // Hashtable will overwrite existing key
  556.             lock (m_Store) {
  557.                 // writers are locked
  558.                 m_Store[prefix] = value;
  559.             }
  560.         }
  561.        
  562. /*
  563.         internal void Remove(string prefix) {
  564.             // Hashtable will be unchanged if key is not existing
  565.             lock (m_Store) {
  566.                 // writers are locked
  567.                 m_Store.Remove(prefix);
  568.             }
  569.         }
  570.         */       
  571.        
  572.         internal object Lookup(string lookupKey)
  573.         {
  574.             if (lookupKey == null) {
  575.                 return null;
  576.             }
  577.             object mostSpecificMatch = null;
  578.             int longestMatchPrefix = 0;
  579.             int prefixLen;
  580.             lock (m_Store) {
  581.                 //
  582.                 // readers don't need to be locked, but we lock() because:
  583.                 // "The enumerator does not have exclusive access to the collection.
  584.                 //
  585.                 // When an enumerator is instantiated, it takes a snapshot of the current state
  586.                 // of the collection. If changes are made to the collection, such as adding,
  587.                 // modifying or deleting elements, the snapshot gets out of sync and the
  588.                 // enumerator throws an InvalidOperationException. Two enumerators instantiated
  589.                 // from the same collection at the same time can have different snapshots of the
  590.                 // collection."
  591.                 //
  592.                 // enumerate through every credential in the cache
  593.                 //
  594.                 string prefix;
  595.                 foreach (DictionaryEntry entry in m_Store) {
  596.                     prefix = (string)entry.Key;
  597.                     if (lookupKey.StartsWith(prefix)) {
  598.                         prefixLen = prefix.Length;
  599.                         //
  600.                         // check if the match is better than the current-most-specific match
  601.                         //
  602.                         if (prefixLen > longestMatchPrefix) {
  603.                             //
  604.                             // Yes-- update the information about currently preferred match
  605.                             //
  606.                             longestMatchPrefix = prefixLen;
  607.                             mostSpecificMatch = entry.Value;
  608.                         }
  609.                     }
  610.                 }
  611.             }
  612.             return mostSpecificMatch;
  613.         }
  614.        
  615.         /*
  616.     //
  617.     // This is the core implementation of a general prefix string table
  618.     // The keys are all converted to lowercase
  619.     //
  620.     internal struct PrefixTable: ICollection {
  621.         internal enum Action {
  622.             Find,
  623.             Insert,
  624.             Remove
  625.         }
  626.         private DictionaryEntry[]  m_Entries;
  627.         internal object this[string key] {
  628.             get {
  629.                 DictionaryEntry[] local = m_Entries;
  630.                 int idx = BinaryFindInsertRemove(ref local, key, Action.Find);
  631.                 if (idx < 0) {
  632.                     return null;
  633.                 }
  634.                 return local[idx].Value;
  635.             }
  636.         }
  637.         internal void Set(string key, object value) {
  638.             DictionaryEntry[] local = m_Entries;
  639.             int idx = BinaryFindInsertRemove(ref local, key, Action.Insert);
  640.             if (idx < 0) {
  641.                 //need to add a new entry
  642.                 local[~idx].Key  = key;
  643.                 local[~idx].Value = value;
  644.                 m_Entries = local;
  645.             }
  646.             else {
  647.                 local[idx].Value  = value;
  648.             }
  649.         }
  650.         internal void Remove(string key) {
  651.             DictionaryEntry[] local = m_Entries;
  652.             int idx = BinaryFindInsertRemove(ref local, key, Action.Remove);
  653.             if (idx >= 0) {
  654.                 //found and removed, update entries.
  655.                 m_Entries = local;
  656.             }
  657.         }
  658.         //
  659.         // ICollection interfaces
  660.         //
  661.         int ICollection.Count {
  662.             get {
  663.                 DictionaryEntry[] local = m_Entries;
  664.                 return local == null? 0: local.Length;
  665.             }
  666.         }
  667.         public bool IsSynchronized {
  668.             get {return true;}
  669.         }
  670.         public IEnumerator GetEnumerator() {
  671.             return new DictionaryEnumerator(m_Entries);
  672.         }
  673.         object ICollection.SyncRoot {
  674.             get {return this;}
  675.         }
  676.         void ICollection.CopyTo (Array array, int index) {
  677.             DictionaryEntry[] local = m_Entries;
  678.             if (local == null) {
  679.                 return;
  680.             }
  681.             local.CopyTo(array, index);
  682.         }
  683.         //
  684.         // Binary search and performing an action on a sorted array of prefixes
  685.         // Derived from Array code, adopted for multithreading and substring search.
  686.         //
  687.         // For Find returns either the matching prefix index or -1
  688.         // For Insert returns either the matching index or ~pos for the first larger prefix in which case the slot is allocated.
  689.         // For Remove returns -1 if not found or pos of successfully removed slot
  690.         //
  691.         private unsafe static int BinaryFindInsertRemove(ref DictionaryEntry[] entries, string key, Action action) {
  692.             if (entries == null || entries.Length == 0) {
  693.                 if (action != Action.Insert) {
  694.                     return -1;
  695.                 }
  696.                 entries = new DictionaryEntry[1];
  697.                 return ~0;
  698.             }
  699.             int lo = 0;
  700.             int hi = entries.Length-1;
  701.             int lastPrefix = -1;
  702.             fixed (char* pKey = key) {
  703.                 while (lo <= hi) {
  704.                     int i = (lo + hi) >> 1;
  705.                     int c = ComparePrefix((string)entries[i].Key, pKey, key.Length);
  706.                     if (c < 0) {
  707.                         if (c < -1) {
  708.                             lastPrefix = i;
  709.                         }
  710.                         lo = i + 1;
  711.                     }
  712.                     else if (c > 0) {
  713.                         hi = i - 1;
  714.                     }
  715.                     else {
  716.                         //Exact match
  717.                         if (action == Action.Remove) {
  718.                             DictionaryEntry[] newEntries = new DictionaryEntry[entries.Length-1];
  719.                             if (i != 0) {
  720.                                 Array.Copy(entries, 0, newEntries, 0, i);
  721.                             }
  722.                             if (i != entries.Length-1) {
  723.                                 Array.Copy(entries, i+1, newEntries, i, entries.Length-i-1);
  724.                             }
  725.                             entries = newEntries;
  726.                         }
  727.                         return i;
  728.                     }
  729.                 }
  730.             }
  731.             // Here 'lo' points to the closest "larger" key, i.e. the place to insert an new element to.
  732.             // The lastPrefix if not -1, will point to the closest prefix match if found.
  733.             switch (action) {
  734.             case Action.Remove:
  735.                             return -1;
  736.             case Action.Insert:
  737.                             DictionaryEntry[] newEntries = new DictionaryEntry[entries.Length+1];
  738.                             if (lo != 0) {
  739.                                 Array.Copy(entries, 0, newEntries, 0, lo);
  740.                             }
  741.                             if (lo != entries.Length) {
  742.                                 Array.Copy(entries, lo, newEntries, lo+1, entries.Length-lo);
  743.                             }
  744.                             entries = newEntries;
  745.                             break;
  746.             default:
  747.                     // Assuming Find.
  748.                     if (lastPrefix >= 0) {
  749.                         return lastPrefix;
  750.                     }
  751.                     return -1;
  752.             }
  753.             return ~lo;
  754.         }
  755.         //
  756.         // Performs bitwise string comparison assuming that both parameteres are in lower case
  757.         // +1  prefix is greater
  758.         // >+1 prefix is greater but only because the prefix length is greater
  759.         // 0  equal
  760.         // -1  prefix is less
  761.         // <-1 prefix is less but is THE prefix for the key
  762.         private unsafe static int ComparePrefix(string prefix, char* key, int keyLength) {
  763.             int len = prefix.Length < keyLength? prefix.Length: keyLength;
  764.             fixed (char* pPrefix = prefix) {
  765.                 for (int i =0; i < len; ++i) {
  766.                     if (pPrefix[i] == key[i]) {
  767.                         continue;
  768.                     }
  769.                     else if (pPrefix[i] > key[i]) {
  770.                         return 1;
  771.                     }
  772.                     else {
  773.                         return -1;
  774.                     }
  775.                 }
  776.             }
  777.             return (len == keyLength)
  778.                         ? prefix.Length == keyLength ? 0: 8
  779.                         : -8;
  780.         }
  781.     }
  782.     internal class DictionaryEnumerator: IDictionaryEnumerator {
  783.         DictionaryEntry[]  m_Entries;
  784.         int                m_CurIdx;
  785.         internal DictionaryEnumerator(DictionaryEntry[] entries) {
  786.             if (entries == null) {
  787.                 entries = new DictionaryEntry[0];
  788.             }
  789.             m_Entries = entries;
  790.             m_CurIdx = -1;
  791.         }
  792.         public Object Current {
  793.             get {
  794.                 if (m_CurIdx < 0 || m_CurIdx >= m_Entries.Length) {
  795.                     throw new InvalidOperationException("index");
  796.                 }
  797.                 return m_Entries[m_CurIdx];
  798.             }
  799.         }
  800.         public void Reset() {
  801.             m_CurIdx = -1;
  802.         }
  803.         public bool MoveNext() {
  804.             if (m_CurIdx >= m_Entries.Length) {
  805.                 return false;
  806.             }
  807.             ++m_CurIdx;
  808.             return m_CurIdx < m_Entries.Length;
  809.         }
  810.         public DictionaryEntry Entry {
  811.             get {
  812.                 if (m_CurIdx < 0 || m_CurIdx >= m_Entries.Length) {
  813.                     throw new InvalidOperationException("index");
  814.                 }
  815.                 return m_Entries[m_CurIdx];
  816.             }
  817.         }
  818.         public object Key {
  819.             get {
  820.                 if (m_CurIdx < 0 || m_CurIdx >= m_Entries.Length) {
  821.                     throw new InvalidOperationException("index");
  822.                 }
  823.                 return m_Entries[m_CurIdx].Key;
  824.             }
  825.         }
  826.         public object Value {
  827.             get {
  828.                 if (m_CurIdx < 0 || m_CurIdx >= m_Entries.Length) {
  829.                     throw new InvalidOperationException("index");
  830.                 }
  831.                 return m_Entries[m_CurIdx].Value;
  832.             }
  833.         }
  834.     }
  835. */       
  836.        
  837.     }
  838.     // class PrefixLookup
  839.    
  840. }
  841. // namespace System.Net

Developer Fusion