b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync/* $Xorg: set.h,v 1.4 2001/02/09 02:05:27 xorgcvs Exp $ */
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncCopyright 1995, 1998 The Open Group
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncPermission to use, copy, modify, distribute, and sell this software and its
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncdocumentation for any purpose is hereby granted without fee, provided that
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncthe above copyright notice appear in all copies and that both that
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsynccopyright notice and this permission notice appear in supporting
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncdocumentation.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncThe above copyright notice and this permission notice shall be
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncincluded in all copies or substantial portions of the Software.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncTHE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncEXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncMERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncIN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncOTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncOTHER DEALINGS IN THE SOFTWARE.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncExcept as contained in this notice, the name of The Open Group shall
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncnot be used in advertising or otherwise to promote the sale, use or
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncother dealings in this Software without prior written authorization
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsyncfrom The Open Group.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync/* $XFree86$ */
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync A Set Abstract Data Type (ADT) for the RECORD Extension
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync David P. Wiggins
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync The RECORD extension server code needs to maintain sets of numbers
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync that designate protocol message types. In most cases the interval of
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync numbers starts at 0 and does not exceed 255, but in a few cases (minor
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync opcodes of extension requests) the maximum is 65535. This disparity
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync suggests that a single set representation may not be suitable for all
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync sets, especially given that server memory is precious. We introduce a
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync set ADT to hide implementation differences so that multiple
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync simultaneous set representations can exist. A single interface is
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync presented to the set user regardless of the implementation in use for
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync a particular set.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync The existing RECORD SI appears to require only four set operations:
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync create (given a list of members), destroy, see if a particular number
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync is a member of the set, and iterate over the members of a set. Though
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync many more set operations are imaginable, to keep the code space down,
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync we won't provide any more operations than are needed.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync The following types and functions/macros define the ADT.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync/* an interval of set members */
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsynctypedef struct {
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsynctypedef struct _RecordSetRec *RecordSetPtr; /* primary set type */
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync/* table of function pointers for set operations.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync set users should never declare a variable of this type.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsynctypedef struct {
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync unsigned long (*IsMemberOfSet)(
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync/* "base class" for sets.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync set users should never declare a variable of this type.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsynctypedef struct _RecordSetRec {
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync RecordCreateSet creates and returns a new set having members specified
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync by intervals and nintervals. nintervals is the number of RecordSetInterval
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync structures pointed to by intervals. The elements belonging to the new
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync set are determined as follows. For each RecordSetInterval structure, the
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync elements between first and last inclusive are members of the new set.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync If a RecordSetInterval's first field is greater than its last field, the
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync results are undefined. It is valid to create an empty set (nintervals ==
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync 0). If RecordCreateSet returns NULL, the set could not be created due
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync to resource constraints.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync int /*nintervals*/,
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync int * /*alignment*/
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync /* void */ (*_pSet->ops->DestroySet)(/* RecordSetPtr */ _pSet)
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync RecordDestroySet frees all resources used by _pSet. _pSet should not be
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync used after it is destroyed.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync /* unsigned long */ (*_pSet->ops->IsMemberOfSet)(/* RecordSetPtr */ _pSet, \
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync RecordIsMemberOfSet returns a non-zero value if _m is a member of
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync _pSet, else it returns zero.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync#define RecordIterateSet(_pSet, _pIter, _interval) \
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync /* RecordSetIteratePtr */ (*_pSet->ops->IterateSet)(/* RecordSetPtr */ _pSet,\
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync /* RecordSetIteratePtr */ _pIter, /* RecordSetInterval */ _interval)
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync RecordIterateSet returns successive intervals of members of _pSet. If
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync _pIter is NULL, the first interval of set members is copied into _interval.
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync The return value should be passed as _pIter in the next call to
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync RecordIterateSet to obtain the next interval. When the return value is
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync NULL, there were no more intervals in the set, and nothing is copied into
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync the _interval parameter. Intervals appear in increasing numerical order
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync with no overlap between intervals. As such, the list of intervals produced
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync by RecordIterateSet may not match the list of intervals that were passed
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync in RecordCreateSet. Typical usage:
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync pIter = NULL;
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync while (pIter = RecordIterateSet(pSet, pIter, &interval))
b8e299dddd091ae24e0c08c45d91b8f937bd14d2vboxsync process interval;