00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00021 #ifndef INTELIB_SBINDTBL_HPP_SENTRY
00022 #define INTELIB_SBINDTBL_HPP_SENTRY
00023
00024 #include "sexpress.hpp"
00025
00027 static const unsigned long not_a_key = ~(0L);
00029
00032 static const unsigned long bind_table_sizes[] = {
00033 6, 12, 18, 38, 68, 132, 258, 522, 1032, 2054, 4100, 8210, 16412, 0
00034 };
00035
00037
00041 class IntelibBindTable {
00042 struct Item {
00043 union {
00044 unsigned long key;
00045 struct {
00046 unsigned int size : 8;
00047 unsigned int fill : 24;
00048 };
00049 };
00050 SReference binding;
00051 Item() : key(not_a_key), binding() {}
00052 };
00053 Item *array;
00054
00055 static unsigned long hash(unsigned long key)
00056 { return 0x9c406bb5 * ((key >> 2) ^ 0x12fade34); }
00057
00058 void Resize() {
00059 if(!array) {
00060 array = new Item[bind_table_sizes[0]];
00061 array[0].size = 0;
00062 array[0].fill = 0;
00063 return;
00064 }
00065 int size = array[0].size;
00066 if(!bind_table_sizes[size+1]) return;
00067 Item *tmp = array;
00068 size++;
00069 array = new Item[bind_table_sizes[size]];
00070 array[0].size = size;
00071 array[0].fill = 0;
00072 for(unsigned int i=1; i<bind_table_sizes[size-1]; i++) {
00073 if(tmp[i].key != not_a_key)
00074 *(AddBinding(tmp[i].key)) = tmp[i].binding;
00075 }
00076 delete[] tmp;
00077 }
00078 public:
00080 IntelibBindTable() : array(0) {}
00082 ~IntelibBindTable() { if(array && array!=(Item*)-1) delete[] array; }
00083
00085
00089 SReference *GetBinding(unsigned long key) const {
00090 if(!array) return 0;
00091 unsigned int pos = hash(key)%(bind_table_sizes[array[0].size]-1)+1;
00092 do {
00093 if(array[pos].key == key)
00094 return &(array[pos].binding);
00095 if(array[pos].key == not_a_key)
00096 return 0;
00097 pos++;
00098 if(pos >= bind_table_sizes[array[0].size]) pos = 1;
00099 } while(1);
00100 }
00102
00105 SReference *AddBinding(unsigned long key) {
00106 if(!array || array[0].fill * 2 > bind_table_sizes[array[0].size])
00107 Resize();
00108 unsigned int pos = hash(key)%(bind_table_sizes[array[0].size]-1)+1;
00109 do {
00110 if(array[pos].key == not_a_key) {
00111 array[pos].key = key;
00112 array[0].fill++;
00113 return &(array[pos].binding);
00114 }
00115 if(array[pos].key == key)
00116 return &(array[pos].binding);
00117 pos++;
00118 if(pos >= bind_table_sizes[array[0].size]) pos = 1;
00119 } while(1);
00120 }
00121
00123
00128 void Invalidate() {
00129 if(array && array!=(Item*)-1) delete[] array;
00130 array = (Item*)-1;
00131 }
00133 void DeInvalidate() { if(array == (Item*)-1) array = 0; }
00135 bool IsInvalid() const { return array == (Item*)-1; }
00136
00137 class Iterator;
00138 friend class IntelibBindTable::Iterator;
00139
00141 class Iterator {
00142 unsigned int idx;
00143 Item *array;
00144 public:
00146 Iterator(const IntelibBindTable &master)
00147 : idx(1), array(master.array) {}
00149 bool GetNext(unsigned long &key, SReference &ret) {
00150 if(!array) return false;
00151 unsigned int arrlen = bind_table_sizes[array[0].size];
00152 while(idx<arrlen && array[idx].key==not_a_key) idx++;
00153 if(idx>=arrlen) return false;
00154 key = array[idx].key;
00155 ret = array[idx].binding;
00156 idx++;
00157 return true;
00158 }
00159 };
00160
00161 private:
00163 IntelibBindTable(const IntelibBindTable &) {}
00164 void operator =(const IntelibBindTable &) {}
00165 };
00166
00167
00168 #endif