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