← Back to branch summary

~gerchanovsky/xorg-server/trusty

« back to all changes in this revision

Viewing changes to record/set.c

  • Committer: Package Import Robot
  • Author(s): Timo Aaltonen
  • Date: 2016-01-13 00:01:28 UTC
  • Revision ID: package-import@ubuntu.com-20160113000128-oc1wb1mr1zfjqlm5
Tags: upstream-1.17.2
Import upstream version 1.17.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
record/set.c
 
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
}