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
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
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)
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
106static int
107BitVectorFindBit(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
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)
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
168static RecordSetOperations BitVectorSetOperations = {
169    BitVectorDestroySet, BitVectorIsMemberOfSet, BitVectorIterateSet
170};
171
172static RecordSetOperations BitVectorNoFreeOperations = {
173    NoopDestroySet, BitVectorIsMemberOfSet, BitVectorIterateSet
174};
175
176static int
177BitVectorSetMemoryRequirements(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
187static RecordSetPtr
188BitVectorCreateSet(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
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;
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
261static RecordSetIteratePtr
262IntervalListIterateSet(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
280static RecordSetOperations IntervalListSetOperations = {
281    IntervalListDestroySet, IntervalListIsMemberOfSet, IntervalListIterateSet
282};
283
284static RecordSetOperations IntervalListNoFreeOperations = {
285    NoopDestroySet, IntervalListIsMemberOfSet, IntervalListIterateSet
286};
287
288static int
289IntervalListMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals,
290                               int maxMember, int *alignment)
291{
292    *alignment = sizeof(unsigned long);
293    return sizeof(IntervalListSet) + nIntervals * sizeof(RecordSetInterval);
294}
295
296static RecordSetPtr
297IntervalListCreateSet(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 = xallocarray(nIntervals, sizeof(RecordSetInterval));
307        if (!stackIntervals)
308            return NULL;
309
310        /* sort intervals, store in stackIntervals (insertion sort) */
311
312        for (i = 0; i < nIntervals; i++) {
313            first = pIntervals[i].first;
314            for (j = 0; j < i; j++) {
315                if (first < stackIntervals[j].first)
316                    break;
317            }
318            for (k = i; k > j; k--) {
319                stackIntervals[k] = stackIntervals[k - 1];
320            }
321            stackIntervals[j] = pIntervals[i];
322        }
323
324        /* merge abutting/overlapping intervals */
325
326        for (i = 0; i < nIntervals - 1;) {
327            if ((stackIntervals[i].last + (unsigned int) 1) <
328                stackIntervals[i + 1].first) {
329                i++;            /* disjoint intervals */
330            }
331            else {
332                stackIntervals[i].last = max(stackIntervals[i].last,
333                                             stackIntervals[i + 1].last);
334                nIntervals--;
335                for (j = i + 1; j < nIntervals; j++)
336                    stackIntervals[j] = stackIntervals[j + 1];
337            }
338        }
339    }
340
341    /* allocate and fill in set structure */
342
343    if (pMem) {
344        prls = (IntervalListSetPtr) pMem;
345        prls->baseSet.ops = &IntervalListNoFreeOperations;
346    }
347    else {
348        prls = (IntervalListSetPtr)
349            malloc(sizeof(IntervalListSet) +
350                   nIntervals * sizeof(RecordSetInterval));
351        if (!prls)
352            goto bailout;
353        prls->baseSet.ops = &IntervalListSetOperations;
354    }
355    memcpy(&prls[1], stackIntervals, nIntervals * sizeof(RecordSetInterval));
356    prls->nIntervals = nIntervals;
357 bailout:
358    free(stackIntervals);
359    return (RecordSetPtr) prls;
360}
361
362typedef RecordSetPtr(*RecordCreateSetProcPtr) (RecordSetInterval * pIntervals,
363                                               int nIntervals,
364                                               void *pMem, int memsize);
365
366static int
367_RecordSetMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals,
368                             int *alignment,
369                             RecordCreateSetProcPtr * ppCreateSet)
370{
371    int bmsize, rlsize, bma, rla;
372    int maxMember;
373
374    /* find maximum member of set so we know how big to make the bit vector */
375    maxMember = maxMemberInInterval(pIntervals, nIntervals);
376
377    bmsize = BitVectorSetMemoryRequirements(pIntervals, nIntervals, maxMember,
378                                            &bma);
379    rlsize = IntervalListMemoryRequirements(pIntervals, nIntervals, maxMember,
380                                            &rla);
381    if (((nIntervals > 1) && (maxMember <= 255))
382        || (bmsize < rlsize)) {
383        *alignment = bma;
384        *ppCreateSet = BitVectorCreateSet;
385        return bmsize;
386    }
387    else {
388        *alignment = rla;
389        *ppCreateSet = IntervalListCreateSet;
390        return rlsize;
391    }
392}
393
394/***************************************************************************/
395
396/* user-visible functions */
397
398int
399RecordSetMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals,
400                            int *alignment)
401{
402    RecordCreateSetProcPtr pCreateSet;
403
404    return _RecordSetMemoryRequirements(pIntervals, nIntervals, alignment,
405                                        &pCreateSet);
406}
407
408RecordSetPtr
409RecordCreateSet(RecordSetInterval * pIntervals, int nIntervals, void *pMem,
410                int memsize)
411{
412    RecordCreateSetProcPtr pCreateSet;
413    int alignment;
414    int size;
415
416    size = _RecordSetMemoryRequirements(pIntervals, nIntervals, &alignment,
417                                        &pCreateSet);
418    if (pMem) {
419        if (((long) pMem & (alignment - 1)) || memsize < size)
420            return NULL;
421    }
422    return (*pCreateSet) (pIntervals, nIntervals, pMem, size);
423}
424