1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the class library */ 4 /* SoPlex --- the Sequential object-oriented simPlex. */ 5 /* */ 6 /* Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SoPlex; see the file LICENSE. If not email to soplex@zib.de. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 #include <string.h> 26 #include "soplex/spxdefines.h" 27 #include "soplex/nameset.h" 28 #include "soplex/spxalloc.h" 29 30 namespace soplex 31 { 32 const char NameSet::Name::deflt = '\0'; 33 34 void NameSet::add(const char* str) 35 { 36 DataKey k; 37 add(k, str); 38 } 39 40 void NameSet::add(DataKey& p_key, const char* str) 41 { 42 const Name nstr(str); 43 44 if(!hashtab.has(nstr)) 45 { 46 if(size() + 1 > max() * SOPLEX_HASHTABLE_FILLFACTOR) 47 { 48 assert(factor >= 1); 49 reMax(int(factor * max() + 8)); 50 } 51 52 if(memSize() + int(strlen(str)) >= memMax()) 53 { 54 memPack(); 55 56 if(memSize() + int(strlen(str)) >= memMax()) 57 { 58 assert(memFactor >= 1); 59 memRemax(int(memFactor * memMax()) + 9 + int(strlen(str))); 60 assert(memSize() + int(strlen(str)) < memMax()); 61 } 62 } 63 64 int idx = memused; 65 char* tmp = &(mem[idx]); 66 memused += int(strlen(str)) + 1; 67 68 spxSnprintf(tmp, SPX_MAXSTRLEN, "%s", str); 69 *(set.create(p_key)) = idx; 70 Name memname(tmp); 71 hashtab.add(memname, p_key); 72 } 73 } 74 75 void NameSet::add(const NameSet& p_set) 76 { 77 for(int i = 0; i < p_set.num(); ++i) 78 { 79 Name iname(p_set[i]); 80 81 if(!hashtab.has(iname)) 82 add(p_set[i]); 83 } 84 } 85 86 void NameSet::add(DataKey p_key[], const NameSet& p_set) 87 { 88 for(int i = 0; i < p_set.num(); ++i) 89 { 90 Name iname = Name(p_set[i]); 91 92 if(!hashtab.has(iname)) 93 add(p_key[i], p_set[i]); 94 } 95 } 96 97 void NameSet::remove(const char* str) 98 { 99 const Name nam(str); 100 101 if(hashtab.has(nam)) 102 { 103 const DataKey* hkey = hashtab.get(nam); 104 assert(hkey != 0); 105 hashtab.remove(nam); 106 set.remove(*hkey); 107 } 108 } 109 110 void NameSet::remove(const DataKey& p_key) 111 { 112 assert(has(p_key)); 113 114 hashtab.remove(Name(&mem[set[p_key]])); 115 set.remove(p_key); 116 } 117 118 void NameSet::remove(const DataKey keys[], int n) 119 { 120 for(int i = 0; i < n; ++i) 121 remove(keys[i]); 122 } 123 124 void NameSet::remove(const int nums[], int n) 125 { 126 for(int i = 0; i < n; ++i) 127 remove(nums[i]); 128 } 129 130 void NameSet::remove(int dstat[]) 131 { 132 for(int i = 0; i < set.num(); i++) 133 { 134 if(dstat[i] < 0) 135 { 136 const Name nam = &mem[set[i]]; 137 hashtab.remove(nam); 138 } 139 } 140 141 set.remove(dstat); 142 143 assert(isConsistent()); 144 } 145 146 void NameSet::clear() 147 { 148 set.clear(); 149 hashtab.clear(); 150 memused = 0; 151 } 152 153 void NameSet::reMax(int newmax) 154 { 155 hashtab.reMax(newmax); 156 set.reMax(newmax); 157 } 158 159 void NameSet::memRemax(int newmax) 160 { 161 memmax = (newmax < memSize()) ? memSize() : newmax; 162 spx_realloc(mem, memmax); 163 164 hashtab.clear(); 165 166 for(int i = num() - 1; i >= 0; --i) 167 hashtab.add(Name(&mem[set[key(i)]]), key(i)); 168 } 169 170 void NameSet::memPack() 171 { 172 char* newmem = 0; 173 int newlast = 0; 174 int i; 175 176 hashtab.clear(); 177 178 spx_alloc(newmem, memSize()); 179 180 for(i = 0; i < num(); i++) 181 { 182 const char* t = &mem[set[i]]; 183 spxSnprintf(&newmem[newlast], SPX_MAXSTRLEN, "%s", t); 184 set[i] = newlast; 185 newlast += int(strlen(t)) + 1; 186 } 187 188 memcpy(mem, newmem, static_cast<size_t>(newlast)); 189 memused = newlast; 190 191 assert(memSize() <= memMax()); 192 193 spx_free(newmem); 194 195 for(i = 0; i < num(); i++) 196 hashtab.add(Name(&mem[set[key(i)]]), key(i)); 197 } 198 199 /// returns the hash value of the name. 200 static int NameSetNameHashFunction(const NameSet::Name* str) 201 { 202 unsigned int res = 37; 203 const char* sptr = str->name; 204 205 while(*sptr != '\0') 206 { 207 res *= 11; 208 res += (unsigned int)(*sptr++); 209 210 } 211 212 res %= 0x0fffffff; 213 return ((int) res); 214 } 215 216 NameSet::NameSet(int p_max, int mmax, Real fac, Real memFac) 217 : set(p_max) 218 , mem(0) 219 , hashtab(NameSetNameHashFunction, set.max(), 0, fac) 220 , factor(fac) 221 , memFactor(memFac) 222 { 223 memused = 0; 224 memmax = (mmax < 1) ? (8 * set.max() + 1) : mmax; 225 spx_alloc(mem, memmax); 226 } 227 228 NameSet::~NameSet() 229 { 230 spx_free(mem); 231 } 232 233 bool NameSet::isConsistent() const 234 { 235 #ifdef ENABLE_CONSISTENCY_CHECKS 236 237 if(memused > memmax) 238 return SPX_MSG_INCONSISTENT("NameSet"); 239 240 int i; 241 242 for(i = 0; i < num(); i++) 243 { 244 const char* t = &mem[set[i]]; 245 246 if(!has(t)) 247 return SPX_MSG_INCONSISTENT("NameSet"); 248 249 if(strcmp(t, operator[](key(t)))) 250 return SPX_MSG_INCONSISTENT("NameSet"); 251 } 252 253 return set.isConsistent() && hashtab.isConsistent(); 254 #else 255 return true; 256 #endif 257 } 258 259 std::ostream& operator<<(std::ostream& s, const NameSet& nset) 260 { 261 for(int i = 0; i < nset.num(); i++) 262 { 263 s << i << " " 264 << nset.key(i).info << "." 265 << nset.key(i).idx << "= " 266 << nset[i] 267 << std::endl; 268 } 269 270 return s; 271 } 272 273 274 } // namespace soplex 275