Commit | Line | Data |
---|---|---|
a09e091a JB |
1 | /* |
2 | ||
3 | Copyright 1995, 1998 The Open Group | |
4 | ||
5 | Permission to use, copy, modify, distribute, and sell this software and its | |
6 | documentation for any purpose is hereby granted without fee, provided that | |
7 | the above copyright notice appear in all copies and that both that | |
8 | copyright notice and this permission notice appear in supporting | |
9 | documentation. | |
10 | ||
11 | The above copyright notice and this permission notice shall be | |
12 | included in all copies or substantial portions of the Software. | |
13 | ||
14 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, | |
15 | EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF | |
16 | MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. | |
17 | IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR | |
18 | OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, | |
19 | ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR | |
20 | OTHER DEALINGS IN THE SOFTWARE. | |
21 | ||
22 | Except as contained in this notice, the name of The Open Group shall | |
23 | not be used in advertising or otherwise to promote the sale, use or | |
24 | other dealings in this Software without prior written authorization | |
25 | from The Open Group. | |
26 | ||
27 | */ | |
28 | ||
29 | /* | |
30 | ||
31 | See the header set.h for a description of the set ADT. | |
32 | ||
33 | Implementation Strategy | |
34 | ||
35 | A bit vector is an obvious choice to represent the set, but may take | |
36 | too much memory, depending on the numerically largest member in the | |
37 | set. One expected common case is for the client to ask for *all* | |
38 | protocol. This means it would ask for minor opcodes 0 through 65535. | |
39 | Representing this as a bit vector takes 8K -- and there may be | |
40 | multiple minor opcode intervals, as many as one per major (extension) | |
41 | opcode). In such cases, a list-of-intervals representation would be | |
42 | preferable to reduce memory consumption. Both representations will be | |
43 | implemented, and RecordCreateSet will decide heuristically which one | |
44 | to use based on the set members. | |
45 | ||
46 | */ | |
47 | ||
48 | #ifdef HAVE_DIX_CONFIG_H | |
49 | #include <dix-config.h> | |
50 | #endif | |
51 | ||
52 | #include <string.h> | |
53 | ||
54 | #include "misc.h" | |
55 | #include "set.h" | |
56 | ||
57 | static int | |
58 | maxMemberInInterval(RecordSetInterval * pIntervals, int nIntervals) | |
59 | { | |
60 | int i; | |
61 | int maxMember = -1; | |
62 | ||
63 | for (i = 0; i < nIntervals; i++) { | |
64 | if (maxMember < (int) pIntervals[i].last) | |
65 | maxMember = pIntervals[i].last; | |
66 | } | |
67 | return maxMember; | |
68 | } | |
69 | ||
70 | static void | |
71 | NoopDestroySet(RecordSetPtr pSet) | |
72 | { | |
73 | } | |
74 | ||
75 | /***************************************************************************/ | |
76 | ||
77 | /* set operations for bit vector representation */ | |
78 | ||
79 | typedef struct { | |
80 | RecordSetRec baseSet; | |
81 | int maxMember; | |
82 | /* followed by the bit vector itself */ | |
83 | } BitVectorSet, *BitVectorSetPtr; | |
84 | ||
85 | #define BITS_PER_LONG (sizeof(unsigned long) * 8) | |
86 | ||
87 | static void | |
88 | BitVectorDestroySet(RecordSetPtr pSet) | |
89 | { | |
90 | free(pSet); | |
91 | } | |
92 | ||
93 | static unsigned long | |
94 | BitVectorIsMemberOfSet(RecordSetPtr pSet, int pm) | |
95 | { | |
96 | BitVectorSetPtr pbvs = (BitVectorSetPtr) pSet; | |
97 | unsigned long *pbitvec; | |
98 | ||
99 | if ((int) pm > pbvs->maxMember) | |
100 | return FALSE; | |
101 | pbitvec = (unsigned long *) (&pbvs[1]); | |
102 | return (pbitvec[pm / BITS_PER_LONG] & | |
103 | ((unsigned long) 1 << (pm % BITS_PER_LONG))); | |
104 | } | |
105 | ||
106 | static int | |
107 | BitVectorFindBit(RecordSetPtr pSet, int iterbit, Bool bitval) | |
108 | { | |
109 | BitVectorSetPtr pbvs = (BitVectorSetPtr) pSet; | |
110 | unsigned long *pbitvec = (unsigned long *) (&pbvs[1]); | |
111 | int startlong; | |
112 | int startbit; | |
113 | int walkbit; | |
114 | int maxMember; | |
115 | unsigned long skipval; | |
116 | unsigned long bits; | |
117 | unsigned long usefulbits; | |
118 | ||
119 | startlong = iterbit / BITS_PER_LONG; | |
120 | pbitvec += startlong; | |
121 | startbit = startlong * BITS_PER_LONG; | |
122 | skipval = bitval ? 0L : ~0L; | |
123 | maxMember = pbvs->maxMember; | |
124 | ||
125 | if (startbit > maxMember) | |
126 | return -1; | |
127 | bits = *pbitvec; | |
128 | usefulbits = ~(((unsigned long) 1 << (iterbit - startbit)) - 1); | |
129 | if ((bits & usefulbits) == (skipval & usefulbits)) { | |
130 | pbitvec++; | |
131 | startbit += BITS_PER_LONG; | |
132 | ||
133 | while (startbit <= maxMember && *pbitvec == skipval) { | |
134 | pbitvec++; | |
135 | startbit += BITS_PER_LONG; | |
136 | } | |
137 | if (startbit > maxMember) | |
138 | return -1; | |
139 | } | |
140 | ||
141 | walkbit = (startbit < iterbit) ? iterbit - startbit : 0; | |
142 | ||
143 | bits = *pbitvec; | |
144 | while (walkbit < BITS_PER_LONG && | |
145 | ((!(bits & ((unsigned long) 1 << walkbit))) == bitval)) | |
146 | walkbit++; | |
147 | ||
148 | return startbit + walkbit; | |
149 | } | |
150 | ||
151 | static RecordSetIteratePtr | |
152 | BitVectorIterateSet(RecordSetPtr pSet, RecordSetIteratePtr pIter, | |
153 | RecordSetInterval * pInterval) | |
154 | { | |
155 | int iterbit = (int) (long) pIter; | |
156 | int b; | |
157 | ||
158 | b = BitVectorFindBit(pSet, iterbit, TRUE); | |
159 | if (b == -1) | |
160 | return (RecordSetIteratePtr) 0; | |
161 | pInterval->first = b; | |
162 | ||
163 | b = BitVectorFindBit(pSet, b, FALSE); | |
164 | pInterval->last = (b < 0) ? ((BitVectorSetPtr) pSet)->maxMember : b - 1; | |
165 | return (RecordSetIteratePtr) (long) (pInterval->last + 1); | |
166 | } | |
167 | ||
168 | static RecordSetOperations BitVectorSetOperations = { | |
169 | BitVectorDestroySet, BitVectorIsMemberOfSet, BitVectorIterateSet | |
170 | }; | |
171 | ||
172 | static RecordSetOperations BitVectorNoFreeOperations = { | |
173 | NoopDestroySet, BitVectorIsMemberOfSet, BitVectorIterateSet | |
174 | }; | |
175 | ||
176 | static int | |
177 | BitVectorSetMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals, | |
178 | int maxMember, int *alignment) | |
179 | { | |
180 | int nlongs; | |
181 | ||
182 | *alignment = sizeof(unsigned long); | |
183 | nlongs = (maxMember + BITS_PER_LONG) / BITS_PER_LONG; | |
184 | return (sizeof(BitVectorSet) + nlongs * sizeof(unsigned long)); | |
185 | } | |
186 | ||
187 | static RecordSetPtr | |
188 | BitVectorCreateSet(RecordSetInterval * pIntervals, int nIntervals, | |
189 | void *pMem, int memsize) | |
190 | { | |
191 | BitVectorSetPtr pbvs; | |
192 | int i, j; | |
193 | unsigned long *pbitvec; | |
194 | ||
195 | /* allocate all storage needed by this set in one chunk */ | |
196 | ||
197 | if (pMem) { | |
198 | memset(pMem, 0, memsize); | |
199 | pbvs = (BitVectorSetPtr) pMem; | |
200 | pbvs->baseSet.ops = &BitVectorNoFreeOperations; | |
201 | } | |
202 | else { | |
203 | pbvs = (BitVectorSetPtr) calloc(1, memsize); | |
204 | if (!pbvs) | |
205 | return NULL; | |
206 | pbvs->baseSet.ops = &BitVectorSetOperations; | |
207 | } | |
208 | ||
209 | pbvs->maxMember = maxMemberInInterval(pIntervals, nIntervals); | |
210 | ||
211 | /* fill in the set */ | |
212 | ||
213 | pbitvec = (unsigned long *) (&pbvs[1]); | |
214 | for (i = 0; i < nIntervals; i++) { | |
215 | for (j = pIntervals[i].first; j <= (int) pIntervals[i].last; j++) { | |
216 | pbitvec[j / BITS_PER_LONG] |= | |
217 | ((unsigned long) 1 << (j % BITS_PER_LONG)); | |
218 | } | |
219 | } | |
220 | return (RecordSetPtr) pbvs; | |
221 | } | |
222 | ||
223 | /***************************************************************************/ | |
224 | ||
225 | /* set operations for interval list representation */ | |
226 | ||
227 | typedef struct { | |
228 | RecordSetRec baseSet; | |
229 | int nIntervals; | |
230 | /* followed by the intervals (RecordSetInterval) */ | |
231 | } IntervalListSet, *IntervalListSetPtr; | |
232 | ||
233 | static void | |
234 | IntervalListDestroySet(RecordSetPtr pSet) | |
235 | { | |
236 | free(pSet); | |
237 | } | |
238 | ||
239 | static unsigned long | |
240 | IntervalListIsMemberOfSet(RecordSetPtr pSet, int pm) | |
241 | { | |
242 | IntervalListSetPtr prls = (IntervalListSetPtr) pSet; | |
243 | RecordSetInterval *pInterval = (RecordSetInterval *) (&prls[1]); | |
244 | int hi, lo, probe; | |
245 | ||
246 | /* binary search */ | |
247 | lo = 0; | |
248 | hi = prls->nIntervals - 1; | |
249 | while (lo <= hi) { | |
250 | probe = (hi + lo) / 2; | |
251 | if (pm >= pInterval[probe].first && pm <= pInterval[probe].last) | |
252 | return 1; | |
253 | else if (pm < pInterval[probe].first) | |
254 | hi = probe - 1; | |
255 | else | |
256 | lo = probe + 1; | |
257 | } | |
258 | return 0; | |
259 | } | |
260 | ||
261 | static RecordSetIteratePtr | |
262 | IntervalListIterateSet(RecordSetPtr pSet, RecordSetIteratePtr pIter, | |
263 | RecordSetInterval * pIntervalReturn) | |
264 | { | |
265 | RecordSetInterval *pInterval = (RecordSetInterval *) pIter; | |
266 | IntervalListSetPtr prls = (IntervalListSetPtr) pSet; | |
267 | ||
268 | if (pInterval == NULL) { | |
269 | pInterval = (RecordSetInterval *) (&prls[1]); | |
270 | } | |
271 | ||
272 | if ((pInterval - (RecordSetInterval *) (&prls[1])) < prls->nIntervals) { | |
273 | *pIntervalReturn = *pInterval; | |
274 | return (RecordSetIteratePtr) (++pInterval); | |
275 | } | |
276 | else | |
277 | return (RecordSetIteratePtr) NULL; | |
278 | } | |
279 | ||
280 | static RecordSetOperations IntervalListSetOperations = { | |
281 | IntervalListDestroySet, IntervalListIsMemberOfSet, IntervalListIterateSet | |
282 | }; | |
283 | ||
284 | static RecordSetOperations IntervalListNoFreeOperations = { | |
285 | NoopDestroySet, IntervalListIsMemberOfSet, IntervalListIterateSet | |
286 | }; | |
287 | ||
288 | static int | |
289 | IntervalListMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals, | |
290 | int maxMember, int *alignment) | |
291 | { | |
292 | *alignment = sizeof(unsigned long); | |
293 | return sizeof(IntervalListSet) + nIntervals * sizeof(RecordSetInterval); | |
294 | } | |
295 | ||
296 | static RecordSetPtr | |
297 | IntervalListCreateSet(RecordSetInterval * pIntervals, int nIntervals, | |
298 | void *pMem, int memsize) | |
299 | { | |
300 | IntervalListSetPtr prls; | |
301 | int i, j, k; | |
302 | RecordSetInterval *stackIntervals = NULL; | |
303 | CARD16 first; | |
304 | ||
305 | if (nIntervals > 0) { | |
306 | stackIntervals = | |
307 | (RecordSetInterval *) malloc(sizeof(RecordSetInterval) * | |
308 | nIntervals); | |
309 | if (!stackIntervals) | |
310 | return NULL; | |
311 | ||
312 | /* sort intervals, store in stackIntervals (insertion sort) */ | |
313 | ||
314 | for (i = 0; i < nIntervals; i++) { | |
315 | first = pIntervals[i].first; | |
316 | for (j = 0; j < i; j++) { | |
317 | if (first < stackIntervals[j].first) | |
318 | break; | |
319 | } | |
320 | for (k = i; k > j; k--) { | |
321 | stackIntervals[k] = stackIntervals[k - 1]; | |
322 | } | |
323 | stackIntervals[j] = pIntervals[i]; | |
324 | } | |
325 | ||
326 | /* merge abutting/overlapping intervals */ | |
327 | ||
328 | for (i = 0; i < nIntervals - 1;) { | |
329 | if ((stackIntervals[i].last + (unsigned int) 1) < | |
330 | stackIntervals[i + 1].first) { | |
331 | i++; /* disjoint intervals */ | |
332 | } | |
333 | else { | |
334 | stackIntervals[i].last = max(stackIntervals[i].last, | |
335 | stackIntervals[i + 1].last); | |
336 | nIntervals--; | |
337 | for (j = i + 1; j < nIntervals; j++) | |
338 | stackIntervals[j] = stackIntervals[j + 1]; | |
339 | } | |
340 | } | |
341 | } | |
342 | ||
343 | /* allocate and fill in set structure */ | |
344 | ||
345 | if (pMem) { | |
346 | prls = (IntervalListSetPtr) pMem; | |
347 | prls->baseSet.ops = &IntervalListNoFreeOperations; | |
348 | } | |
349 | else { | |
350 | prls = (IntervalListSetPtr) | |
351 | malloc(sizeof(IntervalListSet) + | |
352 | nIntervals * sizeof(RecordSetInterval)); | |
353 | if (!prls) | |
354 | goto bailout; | |
355 | prls->baseSet.ops = &IntervalListSetOperations; | |
356 | } | |
357 | memcpy(&prls[1], stackIntervals, nIntervals * sizeof(RecordSetInterval)); | |
358 | prls->nIntervals = nIntervals; | |
359 | bailout: | |
360 | free(stackIntervals); | |
361 | return (RecordSetPtr) prls; | |
362 | } | |
363 | ||
364 | typedef RecordSetPtr(*RecordCreateSetProcPtr) (RecordSetInterval * pIntervals, | |
365 | int nIntervals, | |
366 | void *pMem, int memsize); | |
367 | ||
368 | static int | |
369 | _RecordSetMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals, | |
370 | int *alignment, | |
371 | RecordCreateSetProcPtr * ppCreateSet) | |
372 | { | |
373 | int bmsize, rlsize, bma, rla; | |
374 | int maxMember; | |
375 | ||
376 | /* find maximum member of set so we know how big to make the bit vector */ | |
377 | maxMember = maxMemberInInterval(pIntervals, nIntervals); | |
378 | ||
379 | bmsize = BitVectorSetMemoryRequirements(pIntervals, nIntervals, maxMember, | |
380 | &bma); | |
381 | rlsize = IntervalListMemoryRequirements(pIntervals, nIntervals, maxMember, | |
382 | &rla); | |
383 | if (((nIntervals > 1) && (maxMember <= 255)) | |
384 | || (bmsize < rlsize)) { | |
385 | *alignment = bma; | |
386 | *ppCreateSet = BitVectorCreateSet; | |
387 | return bmsize; | |
388 | } | |
389 | else { | |
390 | *alignment = rla; | |
391 | *ppCreateSet = IntervalListCreateSet; | |
392 | return rlsize; | |
393 | } | |
394 | } | |
395 | ||
396 | /***************************************************************************/ | |
397 | ||
398 | /* user-visible functions */ | |
399 | ||
400 | int | |
401 | RecordSetMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals, | |
402 | int *alignment) | |
403 | { | |
404 | RecordCreateSetProcPtr pCreateSet; | |
405 | ||
406 | return _RecordSetMemoryRequirements(pIntervals, nIntervals, alignment, | |
407 | &pCreateSet); | |
408 | } | |
409 | ||
410 | RecordSetPtr | |
411 | RecordCreateSet(RecordSetInterval * pIntervals, int nIntervals, void *pMem, | |
412 | int memsize) | |
413 | { | |
414 | RecordCreateSetProcPtr pCreateSet; | |
415 | int alignment; | |
416 | int size; | |
417 | ||
418 | size = _RecordSetMemoryRequirements(pIntervals, nIntervals, &alignment, | |
419 | &pCreateSet); | |
420 | if (pMem) { | |
421 | if (((long) pMem & (alignment - 1)) || memsize < size) | |
422 | return NULL; | |
423 | } | |
424 | return (*pCreateSet) (pIntervals, nIntervals, pMem, size); | |
425 | } |