Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #include <shogun/lib/HashSet.h>
00013
00014 using namespace shogun;
00015
00016 CHashSet::CHashSet()
00017 {
00018 array_size = 0;
00019 hash_array = NULL;
00020 }
00021
00022 CHashSet::CHashSet(int32_t size)
00023 {
00024 array_size = size;
00025 hash_array = SG_MALLOC(HashSetNode*, array_size);
00026 for(int32_t i = 0; i < array_size; i++)
00027 {
00028 hash_array[i] = NULL;
00029 }
00030 }
00031
00032 CHashSet::~CHashSet()
00033 {
00034 if(hash_array != NULL)
00035 {
00036 for(int32_t i = 0; i < array_size; i++)
00037 {
00038 delete hash_array[i];
00039 }
00040 SG_FREE(hash_array);
00041 }
00042 }
00043
00044 bool CHashSet::insert_key(int32_t key, float64_t data)
00045 {
00046 int32_t index = hash(key);
00047 if(chain_search(index, key) != NULL)
00048 {
00049
00050 return false;
00051 }
00052
00053
00054 HashSetNode* new_node = new HashSetNode;
00055 new_node->key = key;
00056 new_node->data = data;
00057 new_node->left = NULL;
00058 new_node->right = NULL;
00059
00060
00061 if(hash_array[index] == NULL)
00062 {
00063 hash_array[index] = new_node;
00064 }
00065 else
00066 {
00067 hash_array[index]->left = new_node;
00068 new_node->right = hash_array[index];
00069
00070 hash_array[index] = new_node;
00071 }
00072
00073 return true;
00074 }
00075
00076 bool CHashSet::search_key(int32_t key, float64_t &ret_data)
00077 {
00078 int index = hash(key);
00079
00080 HashSetNode* result = chain_search(index, key);
00081 if(result == NULL)
00082 {
00083 return false;
00084 }
00085 else
00086 {
00087 ret_data = result->data;
00088 return true;
00089 }
00090 }
00091
00092 HashSetNode* CHashSet::chain_search(int32_t index, int32_t key)
00093 {
00094 if(hash_array[index] == NULL)
00095 {
00096 return NULL;
00097 }
00098 else
00099 {
00100 HashSetNode* current = hash_array[index];
00101
00102
00103 do
00104 {
00105 if(current->key == key)
00106 {
00107 return current;
00108 }
00109
00110 current = current->right;
00111
00112 } while(current != NULL);
00113
00114 return NULL;
00115 }
00116 }
00117
00118 void CHashSet::delete_key(int32_t key)
00119 {
00120 int index = hash(key);
00121 HashSetNode* result = chain_search(index, key);
00122
00123 if(result == NULL)
00124 {
00125 return;
00126 }
00127
00128 if(result->right != NULL)
00129 {
00130 result->right->left = result->left;
00131 }
00132
00133 if(result->left != NULL)
00134 {
00135 result->left->right = result->right;
00136 }
00137 else
00138 {
00139 hash_array[index] = result->right;
00140 }
00141
00142 result->left = NULL;
00143 result->right = NULL;
00144
00145 delete result;
00146 }
00147
00148 void CHashSet::debug()
00149 {
00150 for(int32_t i = 0; i < array_size; i++)
00151 {
00152 HashSetNode* current = hash_array[i];
00153
00154 if(current == NULL)
00155 {
00156 SG_SPRINT("NULL\n");
00157 continue;
00158 }
00159
00160 do
00161 {
00162 SG_SPRINT("%d ", current->key);
00163 current = current->right;
00164 }
00165 while(current != NULL);
00166 printf("\n");
00167 }
00168 }
00169
00170 int32_t CHashSet::hash(int32_t key)
00171 {
00172 return CHash::MurmurHash2((uint8_t*)(&key), 4, 1) % array_size;
00173 }
00174