SHOGUN
v1.1.0
|
00001 /* 00002 * This program is free software; you can redistribute it and/or modify 00003 * it under the terms of the GNU General Public License as published by 00004 * the Free Software Foundation; either version 3 of the License, or 00005 * (at your option) any later version. 00006 * 00007 * Written (W) 2011 Evgeniy Andreev (gsomix) 00008 * 00009 * Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society 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 // this key is already in set 00050 return false; 00051 } 00052 00053 // init new node 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 // add new node in start of list 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 // iterating all items in the list 00104 { 00105 if(current->key == key) 00106 { 00107 return current; // it's a search key 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