Scippy

SoPlex

Sequential object-oriented simPlex

nameset.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the class library */
4 /* SoPlex --- the Sequential object-oriented simPlex. */
5 /* */
6 /* Copyright (C) 1996-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SoPlex is distributed under the terms of the ZIB Academic Licence. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SoPlex; see the file COPYING. If not email to soplex@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 #include <string.h>
17 #include "soplex/spxdefines.h"
18 #include "soplex/nameset.h"
19 #include "soplex/spxalloc.h"
20 
21 namespace soplex
22 {
23 const char NameSet::Name::deflt = '\0';
24 
25 void NameSet::add(const char* str)
26 {
27  DataKey k;
28  add(k, str);
29 }
30 
31 void NameSet::add(DataKey& p_key, const char* str)
32 {
33  const Name nstr(str);
34 
35  if(!hashtab.has(nstr))
36  {
37  if(size() + 1 > max() * HASHTABLE_FILLFACTOR)
38  {
39  assert(factor >= 1);
40  reMax(int(factor * max() + 8));
41  }
42 
43  if(memSize() + int(strlen(str)) >= memMax())
44  {
45  memPack();
46 
47  if(memSize() + int(strlen(str)) >= memMax())
48  {
49  assert(memFactor >= 1);
50  memRemax(int(memFactor * memMax()) + 9 + int(strlen(str)));
51  assert(memSize() + int(strlen(str)) < memMax());
52  }
53  }
54 
55  int idx = memused;
56  char* tmp = &(mem[idx]);
57  memused += int(strlen(str)) + 1;
58 
59  spxSnprintf(tmp, SPX_MAXSTRLEN, "%s", str);
60  *(set.create(p_key)) = idx;
61  Name memname(tmp);
62  hashtab.add(memname, p_key);
63  }
64 }
65 
66 void NameSet::add(const NameSet& p_set)
67 {
68  for(int i = 0; i < p_set.num(); ++i)
69  {
70  Name iname(p_set[i]);
71 
72  if(!hashtab.has(iname))
73  add(p_set[i]);
74  }
75 }
76 
77 void NameSet::add(DataKey p_key[], const NameSet& p_set)
78 {
79  for(int i = 0; i < p_set.num(); ++i)
80  {
81  Name iname = Name(p_set[i]);
82 
83  if(!hashtab.has(iname))
84  add(p_key[i], p_set[i]);
85  }
86 }
87 
88 void NameSet::remove(const char* str)
89 {
90  const Name nam(str);
91 
92  if(hashtab.has(nam))
93  {
94  const DataKey* hkey = hashtab.get(nam);
95  assert(hkey != 0);
96  hashtab.remove(nam);
97  set.remove(*hkey);
98  }
99 }
100 
101 void NameSet::remove(const DataKey& p_key)
102 {
103  assert(has(p_key));
104 
105  hashtab.remove(Name(&mem[set[p_key]]));
106  set.remove(p_key);
107 }
108 
109 void NameSet::remove(const DataKey keys[], int n)
110 {
111  for(int i = 0; i < n; ++i)
112  remove(keys[i]);
113 }
114 
115 void NameSet::remove(const int nums[], int n)
116 {
117  for(int i = 0; i < n; ++i)
118  remove(nums[i]);
119 }
120 
121 void NameSet::remove(int dstat[])
122 {
123  for(int i = 0; i < set.num(); i++)
124  {
125  if(dstat[i] < 0)
126  {
127  const Name nam = &mem[set[i]];
128  hashtab.remove(nam);
129  }
130  }
131 
132  set.remove(dstat);
133 
134  assert(isConsistent());
135 }
136 
138 {
139  set.clear();
140  hashtab.clear();
141  memused = 0;
142 }
143 
144 void NameSet::reMax(int newmax)
145 {
146  hashtab.reMax(newmax);
147  set.reMax(newmax);
148 }
149 
150 void NameSet::memRemax(int newmax)
151 {
152  memmax = (newmax < memSize()) ? memSize() : newmax;
154 
155  hashtab.clear();
156 
157  for(int i = num() - 1; i >= 0; --i)
158  hashtab.add(Name(&mem[set[key(i)]]), key(i));
159 }
160 
162 {
163  char* newmem = 0;
164  int newlast = 0;
165  int i;
166 
167  hashtab.clear();
168 
169  spx_alloc(newmem, memSize());
170 
171  for(i = 0; i < num(); i++)
172  {
173  const char* t = &mem[set[i]];
174  spxSnprintf(&newmem[newlast], SPX_MAXSTRLEN, "%s", t);
175  set[i] = newlast;
176  newlast += int(strlen(t)) + 1;
177  }
178 
179  memcpy(mem, newmem, static_cast<size_t>(newlast));
180  memused = newlast;
181 
182  assert(memSize() <= memMax());
183 
184  spx_free(newmem);
185 
186  for(i = 0; i < num(); i++)
187  hashtab.add(Name(&mem[set[key(i)]]), key(i));
188 }
189 
190 /// returns the hash value of the name.
192 {
193  unsigned int res = 37;
194  const char* sptr = str->name;
195 
196  while(*sptr != '\0')
197  {
198  res *= 11;
199  res += (unsigned int)(*sptr++);
200 
201  }
202 
203  res %= 0x0fffffff;
204  return ((int) res);
205 }
206 
207 NameSet::NameSet(int p_max, int mmax, Real fac, Real memFac)
208  : set(p_max)
209  , mem(0)
210  , hashtab(NameSetNameHashFunction, set.max(), 0, fac)
211  , factor(fac)
212  , memFactor(memFac)
213 {
214  memused = 0;
215  memmax = (mmax < 1) ? (8 * set.max() + 1) : mmax;
216  spx_alloc(mem, memmax);
217 }
218 
220 {
221  spx_free(mem);
222 }
223 
225 {
226 #ifdef ENABLE_CONSISTENCY_CHECKS
227 
228  if(memused > memmax)
229  return MSGinconsistent("NameSet");
230 
231  int i;
232 
233  for(i = 0; i < num(); i++)
234  {
235  const char* t = &mem[set[i]];
236 
237  if(!has(t))
238  return MSGinconsistent("NameSet");
239 
240  if(strcmp(t, operator[](key(t))))
241  return MSGinconsistent("NameSet");
242  }
243 
244  return set.isConsistent() && hashtab.isConsistent();
245 #else
246  return true;
247 #endif
248 }
249 
250 std::ostream& operator<<(std::ostream& s, const NameSet& nset)
251 {
252  for(int i = 0; i < nset.num(); i++)
253  {
254  s << i << " "
255  << nset.key(i).info << "."
256  << nset.key(i).idx << "= "
257  << nset[i]
258  << std::endl;
259  }
260 
261  return s;
262 }
263 
264 
265 } // namespace soplex
static int NameSetNameHashFunction(const NameSet::Name *str)
returns the hash value of the name.
Definition: nameset.cpp:191
int memSize() const
returns used length of string memory.
Definition: nameset.h:198
const char * name
pointer to the name string.
Definition: nameset.h:86
int num() const
returns nr. of names in NameSet.
Definition: nameset.h:174
Memory allocation routines.
DataHashTable< Name, DataKey > hashtab
hashtable for names
Definition: nameset.h:153
void reMax(int newmax=0)
resets max() to newmax.
Definition: nameset.cpp:144
Set of strings.
#define HASHTABLE_FILLFACTOR
Definition: datahashtable.h:29
Entry identifier class for items of a DataSet.Every item in a DataSet is assigned a DataKey by which ...
Definition: datakey.h:46
static const char deflt
default zero string.
Definition: nameset.h:78
int memmax
size of string memory
Definition: nameset.h:147
Handles of names in a NameSet.Class Name provides the handles (i.e., char*s) of names in a NameSet...
Definition: nameset.h:71
NameSet(int max=10000, int mmax=-1, Real fac=2, Real memFac=2)
default constructor.
Definition: nameset.cpp:207
void spx_alloc(T &p, int n=1)
Allocate memory.
Definition: spxalloc.h:49
DataSet< int > set
name set.
Definition: nameset.h:145
double Real
Definition: spxdefines.h:256
std::ostream & operator<<(std::ostream &s, const VectorBase< R > &vec)
Output operator.
Definition: basevectors.h:1134
int spxSnprintf(char *t, size_t len, const char *s,...)
safe version of snprintf
Definition: spxdefines.h:392
int info
user information to store values -1, 0, +1
Definition: datakey.h:55
Real factor
memory extension factor for entries.
Definition: nameset.h:324
DataKey key(int pnum) const
returns DataKey of the pnum &#39;th name in NameSet.
Definition: nameset.h:204
void add(const char *str)
Definition: nameset.cpp:25
void clear()
removes all names from NameSet.
Definition: nameset.cpp:137
Debugging, floating point type and parameter definitions.
Set of strings.Class NameSet implements a symbol or name table. It allows to store or remove names (i...
Definition: nameset.h:61
char * mem
string memory
Definition: nameset.h:146
void spx_realloc(T &p, int n)
Change amount of allocated memory.
Definition: spxalloc.h:80
Everything should be within this namespace.
int memused
size of used string memory
Definition: nameset.h:148
void memRemax(int newmax=0)
resets memMax() to newmax.
Definition: nameset.cpp:150
void memPack()
garbage collection.
Definition: nameset.cpp:161
Real memFactor
memory extension factor for names.
Definition: nameset.h:332
bool isConsistent() const
consistency check.
Definition: nameset.cpp:224
#define MSGinconsistent(name)
Definition: spxdefines.h:164
int max() const
returns maximum nr. of names that fit into NameSet.
Definition: nameset.h:180
int size() const
returns maximum DataKey::idx used in NameSet.
Definition: nameset.h:186
void remove(const DataKey &key)
removes name with DataKey key from NameSet.
Definition: nameset.cpp:101
~NameSet()
destructor.
Definition: nameset.cpp:219
int idx
(locally) unique key index
Definition: datakey.h:56
void spx_free(T &p)
Release memory.
Definition: spxalloc.h:111
bool has(int pnum) const
does NameSet has a name with number pnum?
Definition: nameset.h:238
int memMax() const
returns maximum length of string memory.
Definition: nameset.h:192
#define SPX_MAXSTRLEN
Definition: spxdefines.h:287