VTK
|
00001 /*========================================================================= 00002 00003 Program: Visualization Toolkit 00004 Module: $RCSfile: vtkInformationInternals.h,v $ 00005 00006 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen 00007 All rights reserved. 00008 See Copyright.txt or http://www.kitware.com/Copyright.htm for details. 00009 00010 This software is distributed WITHOUT ANY WARRANTY; without even 00011 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 00012 PURPOSE. See the above copyright notice for more information. 00013 00014 =========================================================================*/ 00023 #ifndef __vtkInformationInternals_h 00024 #define __vtkInformationInternals_h 00025 00026 #include "vtkInformationKey.h" 00027 #include "vtkObjectBase.h" 00028 00029 #include <assert.h> 00030 00031 00032 // Note: assumes long is at least 32 bits. 00033 enum { _stl_num_primes = 16 }; 00034 static const unsigned short _stl_prime_list[_stl_num_primes] = 00035 { 00036 5u, 11u, 23u, 31u, 41u, 00037 53u, 97u, 193u, 389u, 769u, 00038 1543u, 3079u, 6151u, 12289u, 24593u, 00039 49157u 00040 }; 00041 00042 // use a mod hash or a bit hash 00043 #define USE_MOD 1 00044 00045 //---------------------------------------------------------------------------- 00046 class vtkInformationInternals 00047 { 00048 public: 00049 // Vector to store ordered key/value pairs for efficient lookup with 00050 // a binary search. Typically not many pairs are stored so linear 00051 // insertion time is okay. 00052 vtkInformationKey** Keys; 00053 vtkObjectBase** Values; 00054 unsigned short TableSize; 00055 unsigned short HashKey; 00056 00057 vtkInformationInternals() 00058 { 00059 this->ComputeHashKey(33); 00060 this->Keys = new vtkInformationKey* [this->TableSize]; 00061 this->Values = new vtkObjectBase* [this->TableSize]; 00062 int i; 00063 for (i = 0; i < this->TableSize; ++i) 00064 { 00065 this->Keys[i] = 0; 00066 } 00067 } 00068 00069 vtkInformationInternals(int size) 00070 { 00071 assert(size < 65000 && "information cannot grow to more than 65000 entries"); 00072 this->ComputeHashKey(size); 00073 this->Keys = new vtkInformationKey* [this->TableSize]; 00074 this->Values = new vtkObjectBase* [this->TableSize]; 00075 int i; 00076 for (i = 0; i < this->TableSize; ++i) 00077 { 00078 this->Keys[i] = 0; 00079 } 00080 } 00081 00082 ~vtkInformationInternals() 00083 { 00084 unsigned short i; 00085 for (i = 0; i < this->TableSize; ++i) 00086 { 00087 vtkObjectBase *value = this->Values[i]; 00088 if (this->Keys[i] && value) 00089 { 00090 this->Keys[i] = 0; 00091 this->Values[i] = 0; 00092 value->UnRegister(0); 00093 } 00094 } 00095 delete [] this->Keys; 00096 delete [] this->Values; 00097 } 00098 00099 void ComputeHashKey(int size) 00100 { 00101 // finds the best hash key for the target table size 00102 // and then adjust table size to fit the hash size 00103 #if USE_MOD 00104 unsigned short i = 1; 00105 while(i < _stl_num_primes && _stl_prime_list[i] + 1 <= size) 00106 { 00107 i++; 00108 } 00109 this->HashKey = _stl_prime_list[i-1]; 00110 this->TableSize = this->HashKey + 1; 00111 #else 00112 this->HashKey = 1; 00113 while (this->HashKey + 1 <= size) 00114 { 00115 this->HashKey *= 2; 00116 } 00117 this->HashKey = this->HashKey/2-1; 00118 this->TableSize = this->HashKey + 2; 00119 #endif 00120 } 00121 00122 unsigned short Hash(unsigned long hv) 00123 { 00124 #if USE_MOD 00125 return hv % this->HashKey; 00126 #else 00127 return (hv >> 2 & this->HashKey); 00128 #endif 00129 } 00130 }; 00131 00132 #endif