Merge remote-tracking branch 'origin/released'

Conflicts:
	pixman/pixman/pixman-mmx.c
	xorg-server/Xext/shm.c
	xorg-server/Xext/syncsrv.h
	xorg-server/Xext/xvmain.c
	xorg-server/Xi/exevents.c
	xorg-server/Xi/opendev.c
	xorg-server/composite/compalloc.c
	xorg-server/composite/compoverlay.c
	xorg-server/dix/colormap.c
	xorg-server/dix/devices.c
	xorg-server/dix/dispatch.c
	xorg-server/dix/dixfonts.c
	xorg-server/dix/eventconvert.c
	xorg-server/dix/events.c
	xorg-server/dix/gc.c
	xorg-server/dix/getevents.c
	xorg-server/dix/main.c
	xorg-server/dix/privates.c
	xorg-server/dix/registry.c
	xorg-server/dix/resource.c
	xorg-server/exa/exa_accel.c
	xorg-server/exa/exa_migration_classic.c
	xorg-server/exa/exa_unaccel.c
	xorg-server/fb/fb.h
	xorg-server/fb/fbcopy.c
	xorg-server/fb/fbpixmap.c
	xorg-server/glx/dispatch.h
	xorg-server/glx/glapi.h
	xorg-server/glx/glapi_gentable.c
	xorg-server/glx/glapitable.h
	xorg-server/glx/glprocs.h
	xorg-server/glx/glxcmds.c
	xorg-server/glx/glxcmdsswap.c
	xorg-server/glx/glxdricommon.c
	xorg-server/glx/glxdriswrast.c
	xorg-server/glx/glxext.c
	xorg-server/glx/indirect_dispatch.c
	xorg-server/glx/indirect_dispatch.h
	xorg-server/glx/indirect_dispatch_swap.c
	xorg-server/glx/indirect_size.h
	xorg-server/glx/indirect_size_get.h
	xorg-server/glx/indirect_table.c
	xorg-server/glx/indirect_util.c
	xorg-server/glx/rensize.c
	xorg-server/glx/single2swap.c
	xorg-server/glx/singlepix.c
	xorg-server/glx/singlepixswap.c
	xorg-server/glx/singlesize.c
	xorg-server/hw/dmx/dmxinit.c
	xorg-server/hw/kdrive/ephyr/ephyr.c
	xorg-server/hw/kdrive/ephyr/hostx.c
	xorg-server/hw/kdrive/ephyr/hostx.h
	xorg-server/hw/kdrive/src/kinput.c
	xorg-server/hw/xfree86/common/compiler.h
	xorg-server/hw/xwin/InitInput.c
	xorg-server/hw/xwin/InitOutput.c
	xorg-server/hw/xwin/ddraw.h
	xorg-server/hw/xwin/glx/glwrap.c
	xorg-server/hw/xwin/glx/indirect.c
	xorg-server/hw/xwin/glx/wgl_ext_api.h
	xorg-server/hw/xwin/glx/winpriv.c
	xorg-server/hw/xwin/win.h
	xorg-server/hw/xwin/winallpriv.c
	xorg-server/hw/xwin/winauth.c
	xorg-server/hw/xwin/winclipboard.h
	xorg-server/hw/xwin/winclipboardinit.c
	xorg-server/hw/xwin/winclipboardthread.c
	xorg-server/hw/xwin/winclipboardunicode.c
	xorg-server/hw/xwin/winclipboardwndproc.c
	xorg-server/hw/xwin/winclipboardwrappers.c
	xorg-server/hw/xwin/winclipboardxevents.c
	xorg-server/hw/xwin/wincmap.c
	xorg-server/hw/xwin/winconfig.c
	xorg-server/hw/xwin/wincreatewnd.c
	xorg-server/hw/xwin/wincursor.c
	xorg-server/hw/xwin/windialogs.c
	xorg-server/hw/xwin/winengine.c
	xorg-server/hw/xwin/winerror.c
	xorg-server/hw/xwin/wingc.c
	xorg-server/hw/xwin/wingetsp.c
	xorg-server/hw/xwin/winkeybd.c
	xorg-server/hw/xwin/winkeybd.h
	xorg-server/hw/xwin/winlayouts.h
	xorg-server/hw/xwin/winmisc.c
	xorg-server/hw/xwin/winmonitors.c
	xorg-server/hw/xwin/winmouse.c
	xorg-server/hw/xwin/winmsg.c
	xorg-server/hw/xwin/winmsg.h
	xorg-server/hw/xwin/winmultiwindowclass.c
	xorg-server/hw/xwin/winmultiwindowicons.c
	xorg-server/hw/xwin/winmultiwindowshape.c
	xorg-server/hw/xwin/winmultiwindowwindow.c
	xorg-server/hw/xwin/winmultiwindowwm.c
	xorg-server/hw/xwin/winmultiwindowwndproc.c
	xorg-server/hw/xwin/winnativegdi.c
	xorg-server/hw/xwin/winpfbdd.c
	xorg-server/hw/xwin/winpixmap.c
	xorg-server/hw/xwin/winpolyline.c
	xorg-server/hw/xwin/winprefs.c
	xorg-server/hw/xwin/winprocarg.c
	xorg-server/hw/xwin/winregistry.c
	xorg-server/hw/xwin/winscrinit.c
	xorg-server/hw/xwin/winsetsp.c
	xorg-server/hw/xwin/winshaddd.c
	xorg-server/hw/xwin/winshadddnl.c
	xorg-server/hw/xwin/winshadgdi.c
	xorg-server/hw/xwin/wintrayicon.c
	xorg-server/hw/xwin/winwin32rootless.c
	xorg-server/hw/xwin/winwin32rootlesswindow.c
	xorg-server/hw/xwin/winwin32rootlesswndproc.c
	xorg-server/hw/xwin/winwindow.c
	xorg-server/hw/xwin/winwindow.h
	xorg-server/hw/xwin/winwindowswm.c
	xorg-server/hw/xwin/winwndproc.c
	xorg-server/include/callback.h
	xorg-server/include/dixstruct.h
	xorg-server/include/misc.h
	xorg-server/include/os.h
	xorg-server/include/scrnintstr.h
	xorg-server/mi/micmap.c
	xorg-server/mi/miinitext.c
	xorg-server/mi/mioverlay.c
	xorg-server/mi/misprite.c
	xorg-server/mi/mivaltree.c
	xorg-server/mi/miwindow.c
	xorg-server/miext/damage/damage.c
	xorg-server/miext/rootless/rootlessGC.c
	xorg-server/miext/rootless/rootlessWindow.c
	xorg-server/os/WaitFor.c
	xorg-server/os/access.c
	xorg-server/os/connection.c
	xorg-server/os/io.c
	xorg-server/os/log.c
	xorg-server/os/osinit.c
	xorg-server/os/utils.c
	xorg-server/os/xdmcp.c
	xorg-server/os/xprintf.c
	xorg-server/os/xstrans.c
	xorg-server/render/mipict.c
	xorg-server/xkb/xkbActions.c
	xorg-server/xkb/xkbInit.c
	xorg-server/xkeyboard-config/compat/default.in

1 files changed, 425 insertions, 431 deletions

diff --git a/xorg-server/record/set.c b/xorg-server/record/set.c
index d4bb4f2cc..34faa617e 100644
--- a/xorg-server/record/set.c
+++ b/xorg-server/record/set.c
@@ -1,431 +1,425 @@
-/*

-

-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);

-}

+/*
+
+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);
+}