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 }