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