3 Copyright 1995, 1998 The Open Group
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
11 The above copyright notice and this permission notice shall be
12 included in all copies or substantial portions of the Software.
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.
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
31 See the header set.h for a description of the set ADT.
33 Implementation Strategy
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.
48 #ifdef HAVE_DIX_CONFIG_H
49 #include <dix-config.h>
58 maxMemberInInterval(RecordSetInterval
* pIntervals
, int nIntervals
)
63 for (i
= 0; i
< nIntervals
; i
++) {
64 if (maxMember
< (int) pIntervals
[i
].last
)
65 maxMember
= pIntervals
[i
].last
;
71 NoopDestroySet(RecordSetPtr pSet
)
75 /***************************************************************************/
77 /* set operations for bit vector representation */
82 /* followed by the bit vector itself */
83 } BitVectorSet
, *BitVectorSetPtr
;
85 #define BITS_PER_LONG (sizeof(unsigned long) * 8)
88 BitVectorDestroySet(RecordSetPtr pSet
)
94 BitVectorIsMemberOfSet(RecordSetPtr pSet
, int pm
)
96 BitVectorSetPtr pbvs
= (BitVectorSetPtr
) pSet
;
97 unsigned long *pbitvec
;
99 if ((int) pm
> pbvs
->maxMember
)
101 pbitvec
= (unsigned long *) (&pbvs
[1]);
102 return (pbitvec
[pm
/ BITS_PER_LONG
] &
103 ((unsigned long) 1 << (pm
% BITS_PER_LONG
)));
107 BitVectorFindBit(RecordSetPtr pSet
, int iterbit
, Bool bitval
)
109 BitVectorSetPtr pbvs
= (BitVectorSetPtr
) pSet
;
110 unsigned long *pbitvec
= (unsigned long *) (&pbvs
[1]);
115 unsigned long skipval
;
117 unsigned long usefulbits
;
119 startlong
= iterbit
/ BITS_PER_LONG
;
120 pbitvec
+= startlong
;
121 startbit
= startlong
* BITS_PER_LONG
;
122 skipval
= bitval
? 0L : ~0L;
123 maxMember
= pbvs
->maxMember
;
125 if (startbit
> maxMember
)
128 usefulbits
= ~(((unsigned long) 1 << (iterbit
- startbit
)) - 1);
129 if ((bits
& usefulbits
) == (skipval
& usefulbits
)) {
131 startbit
+= BITS_PER_LONG
;
133 while (startbit
<= maxMember
&& *pbitvec
== skipval
) {
135 startbit
+= BITS_PER_LONG
;
137 if (startbit
> maxMember
)
141 walkbit
= (startbit
< iterbit
) ? iterbit
- startbit
: 0;
144 while (walkbit
< BITS_PER_LONG
&&
145 ((!(bits
& ((unsigned long) 1 << walkbit
))) == bitval
))
148 return startbit
+ walkbit
;
151 static RecordSetIteratePtr
152 BitVectorIterateSet(RecordSetPtr pSet
, RecordSetIteratePtr pIter
,
153 RecordSetInterval
* pInterval
)
155 int iterbit
= (int) (long) pIter
;
158 b
= BitVectorFindBit(pSet
, iterbit
, TRUE
);
160 return (RecordSetIteratePtr
) 0;
161 pInterval
->first
= b
;
163 b
= BitVectorFindBit(pSet
, b
, FALSE
);
164 pInterval
->last
= (b
< 0) ? ((BitVectorSetPtr
) pSet
)->maxMember
: b
- 1;
165 return (RecordSetIteratePtr
) (long) (pInterval
->last
+ 1);
168 static RecordSetOperations BitVectorSetOperations
= {
169 BitVectorDestroySet
, BitVectorIsMemberOfSet
, BitVectorIterateSet
172 static RecordSetOperations BitVectorNoFreeOperations
= {
173 NoopDestroySet
, BitVectorIsMemberOfSet
, BitVectorIterateSet
177 BitVectorSetMemoryRequirements(RecordSetInterval
* pIntervals
, int nIntervals
,
178 int maxMember
, int *alignment
)
182 *alignment
= sizeof(unsigned long);
183 nlongs
= (maxMember
+ BITS_PER_LONG
) / BITS_PER_LONG
;
184 return (sizeof(BitVectorSet
) + nlongs
* sizeof(unsigned long));
188 BitVectorCreateSet(RecordSetInterval
* pIntervals
, int nIntervals
,
189 void *pMem
, int memsize
)
191 BitVectorSetPtr pbvs
;
193 unsigned long *pbitvec
;
195 /* allocate all storage needed by this set in one chunk */
198 memset(pMem
, 0, memsize
);
199 pbvs
= (BitVectorSetPtr
) pMem
;
200 pbvs
->baseSet
.ops
= &BitVectorNoFreeOperations
;
203 pbvs
= (BitVectorSetPtr
) calloc(1, memsize
);
206 pbvs
->baseSet
.ops
= &BitVectorSetOperations
;
209 pbvs
->maxMember
= maxMemberInInterval(pIntervals
, nIntervals
);
211 /* fill in the set */
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
));
220 return (RecordSetPtr
) pbvs
;
223 /***************************************************************************/
225 /* set operations for interval list representation */
228 RecordSetRec baseSet
;
230 /* followed by the intervals (RecordSetInterval) */
231 } IntervalListSet
, *IntervalListSetPtr
;
234 IntervalListDestroySet(RecordSetPtr pSet
)
240 IntervalListIsMemberOfSet(RecordSetPtr pSet
, int pm
)
242 IntervalListSetPtr prls
= (IntervalListSetPtr
) pSet
;
243 RecordSetInterval
*pInterval
= (RecordSetInterval
*) (&prls
[1]);
248 hi
= prls
->nIntervals
- 1;
250 probe
= (hi
+ lo
) / 2;
251 if (pm
>= pInterval
[probe
].first
&& pm
<= pInterval
[probe
].last
)
253 else if (pm
< pInterval
[probe
].first
)
261 static RecordSetIteratePtr
262 IntervalListIterateSet(RecordSetPtr pSet
, RecordSetIteratePtr pIter
,
263 RecordSetInterval
* pIntervalReturn
)
265 RecordSetInterval
*pInterval
= (RecordSetInterval
*) pIter
;
266 IntervalListSetPtr prls
= (IntervalListSetPtr
) pSet
;
268 if (pInterval
== NULL
) {
269 pInterval
= (RecordSetInterval
*) (&prls
[1]);
272 if ((pInterval
- (RecordSetInterval
*) (&prls
[1])) < prls
->nIntervals
) {
273 *pIntervalReturn
= *pInterval
;
274 return (RecordSetIteratePtr
) (++pInterval
);
277 return (RecordSetIteratePtr
) NULL
;
280 static RecordSetOperations IntervalListSetOperations
= {
281 IntervalListDestroySet
, IntervalListIsMemberOfSet
, IntervalListIterateSet
284 static RecordSetOperations IntervalListNoFreeOperations
= {
285 NoopDestroySet
, IntervalListIsMemberOfSet
, IntervalListIterateSet
289 IntervalListMemoryRequirements(RecordSetInterval
* pIntervals
, int nIntervals
,
290 int maxMember
, int *alignment
)
292 *alignment
= sizeof(unsigned long);
293 return sizeof(IntervalListSet
) + nIntervals
* sizeof(RecordSetInterval
);
297 IntervalListCreateSet(RecordSetInterval
* pIntervals
, int nIntervals
,
298 void *pMem
, int memsize
)
300 IntervalListSetPtr prls
;
302 RecordSetInterval
*stackIntervals
= NULL
;
305 if (nIntervals
> 0) {
307 (RecordSetInterval
*) malloc(sizeof(RecordSetInterval
) *
312 /* sort intervals, store in stackIntervals (insertion sort) */
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
)
320 for (k
= i
; k
> j
; k
--) {
321 stackIntervals
[k
] = stackIntervals
[k
- 1];
323 stackIntervals
[j
] = pIntervals
[i
];
326 /* merge abutting/overlapping intervals */
328 for (i
= 0; i
< nIntervals
- 1;) {
329 if ((stackIntervals
[i
].last
+ (unsigned int) 1) <
330 stackIntervals
[i
+ 1].first
) {
331 i
++; /* disjoint intervals */
334 stackIntervals
[i
].last
= max(stackIntervals
[i
].last
,
335 stackIntervals
[i
+ 1].last
);
337 for (j
= i
+ 1; j
< nIntervals
; j
++)
338 stackIntervals
[j
] = stackIntervals
[j
+ 1];
343 /* allocate and fill in set structure */
346 prls
= (IntervalListSetPtr
) pMem
;
347 prls
->baseSet
.ops
= &IntervalListNoFreeOperations
;
350 prls
= (IntervalListSetPtr
)
351 malloc(sizeof(IntervalListSet
) +
352 nIntervals
* sizeof(RecordSetInterval
));
355 prls
->baseSet
.ops
= &IntervalListSetOperations
;
357 memcpy(&prls
[1], stackIntervals
, nIntervals
* sizeof(RecordSetInterval
));
358 prls
->nIntervals
= nIntervals
;
360 free(stackIntervals
);
361 return (RecordSetPtr
) prls
;
364 typedef RecordSetPtr(*RecordCreateSetProcPtr
) (RecordSetInterval
* pIntervals
,
366 void *pMem
, int memsize
);
369 _RecordSetMemoryRequirements(RecordSetInterval
* pIntervals
, int nIntervals
,
371 RecordCreateSetProcPtr
* ppCreateSet
)
373 int bmsize
, rlsize
, bma
, rla
;
376 /* find maximum member of set so we know how big to make the bit vector */
377 maxMember
= maxMemberInInterval(pIntervals
, nIntervals
);
379 bmsize
= BitVectorSetMemoryRequirements(pIntervals
, nIntervals
, maxMember
,
381 rlsize
= IntervalListMemoryRequirements(pIntervals
, nIntervals
, maxMember
,
383 if (((nIntervals
> 1) && (maxMember
<= 255))
384 || (bmsize
< rlsize
)) {
386 *ppCreateSet
= BitVectorCreateSet
;
391 *ppCreateSet
= IntervalListCreateSet
;
396 /***************************************************************************/
398 /* user-visible functions */
401 RecordSetMemoryRequirements(RecordSetInterval
* pIntervals
, int nIntervals
,
404 RecordCreateSetProcPtr pCreateSet
;
406 return _RecordSetMemoryRequirements(pIntervals
, nIntervals
, alignment
,
411 RecordCreateSet(RecordSetInterval
* pIntervals
, int nIntervals
, void *pMem
,
414 RecordCreateSetProcPtr pCreateSet
;
418 size
= _RecordSetMemoryRequirements(pIntervals
, nIntervals
, &alignment
,
421 if (((long) pMem
& (alignment
- 1)) || memsize
< size
)
424 return (*pCreateSet
) (pIntervals
, nIntervals
, pMem
, size
);