[deb_xorg-server.git] / record / set.c

/*

Copyright 1995, 1998  The Open Group

Permission to use, copy, modify, distribute, and sell this software and its
documentation for any purpose is hereby granted without fee, provided that
the above copyright notice appear in all copies and that both that
copyright notice and this permission notice appear in supporting
documentation.

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.

Except as contained in this notice, the name of The Open Group shall
not be used in advertising or otherwise to promote the sale, use or
other dealings in this Software without prior written authorization
from The Open Group.

*/

/*

    See the header set.h for a description of the set ADT.

    Implementation Strategy

    A bit vector is an obvious choice to represent the set, but may take
    too much memory, depending on the numerically largest member in the
    set.  One expected common case is for the client to ask for *all*
    protocol.  This means it would ask for minor opcodes 0 through 65535.
    Representing this as a bit vector takes 8K -- and there may be
    multiple minor opcode intervals, as many as one per major (extension)
    opcode).  In such cases, a list-of-intervals representation would be
    preferable to reduce memory consumption.  Both representations will be
    implemented, and RecordCreateSet will decide heuristically which one
    to use based on the set members.

*/

#ifdef HAVE_DIX_CONFIG_H
#include <dix-config.h>
#endif

#include <string.h>

#include "misc.h"
#include "set.h"

static int
maxMemberInInterval(RecordSetInterval * pIntervals, int nIntervals)
{
    int i;
    int maxMember = -1;

    for (i = 0; i < nIntervals; i++) {
        if (maxMember < (int) pIntervals[i].last)
            maxMember = pIntervals[i].last;
    }
    return maxMember;
}

static void
NoopDestroySet(RecordSetPtr pSet)
{
}

/***************************************************************************/

/* set operations for bit vector representation */

typedef struct {
    RecordSetRec baseSet;
    int maxMember;
    /* followed by the bit vector itself */
} BitVectorSet, *BitVectorSetPtr;

#define BITS_PER_LONG (sizeof(unsigned long) * 8)

static void
BitVectorDestroySet(RecordSetPtr pSet)
{
    free(pSet);
}

static unsigned long
BitVectorIsMemberOfSet(RecordSetPtr pSet, int pm)
{
    BitVectorSetPtr pbvs = (BitVectorSetPtr) pSet;
    unsigned long *pbitvec;

    if ((int) pm > pbvs->maxMember)
        return FALSE;
    pbitvec = (unsigned long *) (&pbvs[1]);
    return (pbitvec[pm / BITS_PER_LONG] &
            ((unsigned long) 1 << (pm % BITS_PER_LONG)));
}

static int
BitVectorFindBit(RecordSetPtr pSet, int iterbit, Bool bitval)
{
    BitVectorSetPtr pbvs = (BitVectorSetPtr) pSet;
    unsigned long *pbitvec = (unsigned long *) (&pbvs[1]);
    int startlong;
    int startbit;
    int walkbit;
    int maxMember;
    unsigned long skipval;
    unsigned long bits;
    unsigned long usefulbits;

    startlong = iterbit / BITS_PER_LONG;
    pbitvec += startlong;
    startbit = startlong * BITS_PER_LONG;
    skipval = bitval ? 0L : ~0L;
    maxMember = pbvs->maxMember;

    if (startbit > maxMember)
        return -1;
    bits = *pbitvec;
    usefulbits = ~(((unsigned long) 1 << (iterbit - startbit)) - 1);
    if ((bits & usefulbits) == (skipval & usefulbits)) {
        pbitvec++;
        startbit += BITS_PER_LONG;

        while (startbit <= maxMember && *pbitvec == skipval) {
            pbitvec++;
            startbit += BITS_PER_LONG;
        }
        if (startbit > maxMember)
            return -1;
    }

    walkbit = (startbit < iterbit) ? iterbit - startbit : 0;

    bits = *pbitvec;
    while (walkbit < BITS_PER_LONG &&
           ((!(bits & ((unsigned long) 1 << walkbit))) == bitval))
        walkbit++;

    return startbit + walkbit;
}

static RecordSetIteratePtr
BitVectorIterateSet(RecordSetPtr pSet, RecordSetIteratePtr pIter,
                    RecordSetInterval * pInterval)
{
    int iterbit = (int) (long) pIter;
    int b;

    b = BitVectorFindBit(pSet, iterbit, TRUE);
    if (b == -1)
        return (RecordSetIteratePtr) 0;
    pInterval->first = b;

    b = BitVectorFindBit(pSet, b, FALSE);
    pInterval->last = (b < 0) ? ((BitVectorSetPtr) pSet)->maxMember : b - 1;
    return (RecordSetIteratePtr) (long) (pInterval->last + 1);
}

static RecordSetOperations BitVectorSetOperations = {
    BitVectorDestroySet, BitVectorIsMemberOfSet, BitVectorIterateSet
};

static RecordSetOperations BitVectorNoFreeOperations = {
    NoopDestroySet, BitVectorIsMemberOfSet, BitVectorIterateSet
};

static int
BitVectorSetMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals,
                               int maxMember, int *alignment)
{
    int nlongs;

    *alignment = sizeof(unsigned long);
    nlongs = (maxMember + BITS_PER_LONG) / BITS_PER_LONG;
    return (sizeof(BitVectorSet) + nlongs * sizeof(unsigned long));
}

static RecordSetPtr
BitVectorCreateSet(RecordSetInterval * pIntervals, int nIntervals,
                   void *pMem, int memsize)
{
    BitVectorSetPtr pbvs;
    int i, j;
    unsigned long *pbitvec;

    /* allocate all storage needed by this set in one chunk */

    if (pMem) {
        memset(pMem, 0, memsize);
        pbvs = (BitVectorSetPtr) pMem;
        pbvs->baseSet.ops = &BitVectorNoFreeOperations;
    }
    else {
        pbvs = (BitVectorSetPtr) calloc(1, memsize);
        if (!pbvs)
            return NULL;
        pbvs->baseSet.ops = &BitVectorSetOperations;
    }

    pbvs->maxMember = maxMemberInInterval(pIntervals, nIntervals);

    /* fill in the set */

    pbitvec = (unsigned long *) (&pbvs[1]);
    for (i = 0; i < nIntervals; i++) {
        for (j = pIntervals[i].first; j <= (int) pIntervals[i].last; j++) {
            pbitvec[j / BITS_PER_LONG] |=
                ((unsigned long) 1 << (j % BITS_PER_LONG));
        }
    }
    return (RecordSetPtr) pbvs;
}

/***************************************************************************/

/* set operations for interval list representation */

typedef struct {
    RecordSetRec baseSet;
    int nIntervals;
    /* followed by the intervals (RecordSetInterval) */
} IntervalListSet, *IntervalListSetPtr;

static void
IntervalListDestroySet(RecordSetPtr pSet)
{
    free(pSet);
}

static unsigned long
IntervalListIsMemberOfSet(RecordSetPtr pSet, int pm)
{
    IntervalListSetPtr prls = (IntervalListSetPtr) pSet;
    RecordSetInterval *pInterval = (RecordSetInterval *) (&prls[1]);
    int hi, lo, probe;

    /* binary search */
    lo = 0;
    hi = prls->nIntervals - 1;
    while (lo <= hi) {
        probe = (hi + lo) / 2;
        if (pm >= pInterval[probe].first && pm <= pInterval[probe].last)
            return 1;
        else if (pm < pInterval[probe].first)
            hi = probe - 1;
        else
            lo = probe + 1;
    }
    return 0;
}

static RecordSetIteratePtr
IntervalListIterateSet(RecordSetPtr pSet, RecordSetIteratePtr pIter,
                       RecordSetInterval * pIntervalReturn)
{
    RecordSetInterval *pInterval = (RecordSetInterval *) pIter;
    IntervalListSetPtr prls = (IntervalListSetPtr) pSet;

    if (pInterval == NULL) {
        pInterval = (RecordSetInterval *) (&prls[1]);
    }

    if ((pInterval - (RecordSetInterval *) (&prls[1])) < prls->nIntervals) {
        *pIntervalReturn = *pInterval;
        return (RecordSetIteratePtr) (++pInterval);
    }
    else
        return (RecordSetIteratePtr) NULL;
}

static RecordSetOperations IntervalListSetOperations = {
    IntervalListDestroySet, IntervalListIsMemberOfSet, IntervalListIterateSet
};

static RecordSetOperations IntervalListNoFreeOperations = {
    NoopDestroySet, IntervalListIsMemberOfSet, IntervalListIterateSet
};

static int
IntervalListMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals,
                               int maxMember, int *alignment)
{
    *alignment = sizeof(unsigned long);
    return sizeof(IntervalListSet) + nIntervals * sizeof(RecordSetInterval);
}

static RecordSetPtr
IntervalListCreateSet(RecordSetInterval * pIntervals, int nIntervals,
                      void *pMem, int memsize)
{
    IntervalListSetPtr prls;
    int i, j, k;
    RecordSetInterval *stackIntervals = NULL;
    CARD16 first;

    if (nIntervals > 0) {
        stackIntervals =
            (RecordSetInterval *) malloc(sizeof(RecordSetInterval) *
                                         nIntervals);
        if (!stackIntervals)
            return NULL;

        /* sort intervals, store in stackIntervals (insertion sort) */

        for (i = 0; i < nIntervals; i++) {
            first = pIntervals[i].first;
            for (j = 0; j < i; j++) {
                if (first < stackIntervals[j].first)
                    break;
            }
            for (k = i; k > j; k--) {
                stackIntervals[k] = stackIntervals[k - 1];
            }
            stackIntervals[j] = pIntervals[i];
        }

        /* merge abutting/overlapping intervals */

        for (i = 0; i < nIntervals - 1;) {
            if ((stackIntervals[i].last + (unsigned int) 1) <
                stackIntervals[i + 1].first) {
                i++;            /* disjoint intervals */
            }
            else {
                stackIntervals[i].last = max(stackIntervals[i].last,
                                             stackIntervals[i + 1].last);
                nIntervals--;
                for (j = i + 1; j < nIntervals; j++)
                    stackIntervals[j] = stackIntervals[j + 1];
            }
        }
    }

    /* allocate and fill in set structure */

    if (pMem) {
        prls = (IntervalListSetPtr) pMem;
        prls->baseSet.ops = &IntervalListNoFreeOperations;
    }
    else {
        prls = (IntervalListSetPtr)
            malloc(sizeof(IntervalListSet) +
                   nIntervals * sizeof(RecordSetInterval));
        if (!prls)
            goto bailout;
        prls->baseSet.ops = &IntervalListSetOperations;
    }
    memcpy(&prls[1], stackIntervals, nIntervals * sizeof(RecordSetInterval));
    prls->nIntervals = nIntervals;
 bailout:
    free(stackIntervals);
    return (RecordSetPtr) prls;
}

typedef RecordSetPtr(*RecordCreateSetProcPtr) (RecordSetInterval * pIntervals,
                                               int nIntervals,
                                               void *pMem, int memsize);

static int
_RecordSetMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals,
                             int *alignment,
                             RecordCreateSetProcPtr * ppCreateSet)
{
    int bmsize, rlsize, bma, rla;
    int maxMember;

    /* find maximum member of set so we know how big to make the bit vector */
    maxMember = maxMemberInInterval(pIntervals, nIntervals);

    bmsize = BitVectorSetMemoryRequirements(pIntervals, nIntervals, maxMember,
                                            &bma);
    rlsize = IntervalListMemoryRequirements(pIntervals, nIntervals, maxMember,
                                            &rla);
    if (((nIntervals > 1) && (maxMember <= 255))
        || (bmsize < rlsize)) {
        *alignment = bma;
        *ppCreateSet = BitVectorCreateSet;
        return bmsize;
    }
    else {
        *alignment = rla;
        *ppCreateSet = IntervalListCreateSet;
        return rlsize;
    }
}

/***************************************************************************/

/* user-visible functions */

int
RecordSetMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals,
                            int *alignment)
{
    RecordCreateSetProcPtr pCreateSet;

    return _RecordSetMemoryRequirements(pIntervals, nIntervals, alignment,
                                        &pCreateSet);
}

RecordSetPtr
RecordCreateSet(RecordSetInterval * pIntervals, int nIntervals, void *pMem,
                int memsize)
{
    RecordCreateSetProcPtr pCreateSet;
    int alignment;
    int size;

    size = _RecordSetMemoryRequirements(pIntervals, nIntervals, &alignment,
                                        &pCreateSet);
    if (pMem) {
        if (((long) pMem & (alignment - 1)) || memsize < size)
            return NULL;
    }
    return (*pCreateSet) (pIntervals, nIntervals, pMem, size);
}
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	}