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 /*
  58  * Ideally we would always use _Alignof(type) here, but that requires C11, so
  59  * we approximate this using sizeof(void*) for older C standards as that
  60  * should be a valid assumption on all supported architectures.
  61  */
  62 #if defined(__STDC__) && (__STDC_VERSION__ - 0 >= 201112L)
  63 #define MinSetAlignment(type) max(_Alignof(type), _Alignof(unsigned long))
  64 #else
  65 #define MinSetAlignment(type) max(sizeof(void*), sizeof(unsigned long))
  66 #endif
  67
  68 static int
  69 maxMemberInInterval(RecordSetInterval * pIntervals, int nIntervals)
  70 {
  71     int i;
  72     int maxMember = -1;
  73
  74     for (i = 0; i < nIntervals; i++) {
  75         if (maxMember < (int) pIntervals[i].last)
  76             maxMember = pIntervals[i].last;
  77     }
  78     return maxMember;
  79 }
  80
  81 static void
  82 NoopDestroySet(RecordSetPtr pSet)
  83 {
  84 }
  85
  86 /***************************************************************************/
  87
  88 /* set operations for bit vector representation */
  89
  90 typedef struct {
  91     RecordSetRec baseSet;
  92     int maxMember;
  93     /* followed by the bit vector itself */
  94 } BitVectorSet, *BitVectorSetPtr;
  95
  96 #define BITS_PER_LONG (sizeof(unsigned long) * 8)
  97
  98 static void
  99 BitVectorDestroySet(RecordSetPtr pSet)
 100 {
 101     free(pSet);
 102 }
 103
 104 static unsigned long
 105 BitVectorIsMemberOfSet(RecordSetPtr pSet, int pm)
 106 {
 107     BitVectorSetPtr pbvs = (BitVectorSetPtr) pSet;
 108     unsigned long *pbitvec;
 109
 110     if ((int) pm > pbvs->maxMember)
 111         return FALSE;
 112     pbitvec = (unsigned long *) (&pbvs[1]);
 113     return (pbitvec[pm / BITS_PER_LONG] &
 114             ((unsigned long) 1 << (pm % BITS_PER_LONG)));
 115 }
 116
 117 static int
 118 BitVectorFindBit(RecordSetPtr pSet, int iterbit, Bool bitval)
 119 {
 120     BitVectorSetPtr pbvs = (BitVectorSetPtr) pSet;
 121     unsigned long *pbitvec = (unsigned long *) (&pbvs[1]);
 122     int startlong;
 123     int startbit;
 124     int walkbit;
 125     int maxMember;
 126     unsigned long skipval;
 127     unsigned long bits;
 128     unsigned long usefulbits;
 129
 130     startlong = iterbit / BITS_PER_LONG;
 131     pbitvec += startlong;
 132     startbit = startlong * BITS_PER_LONG;
 133     skipval = bitval ? 0L : ~0L;
 134     maxMember = pbvs->maxMember;
 135
 136     if (startbit > maxMember)
 137         return -1;
 138     bits = *pbitvec;
 139     usefulbits = ~(((unsigned long) 1 << (iterbit - startbit)) - 1);
 140     if ((bits & usefulbits) == (skipval & usefulbits)) {
 141         pbitvec++;
 142         startbit += BITS_PER_LONG;
 143
 144         while (startbit <= maxMember && *pbitvec == skipval) {
 145             pbitvec++;
 146             startbit += BITS_PER_LONG;
 147         }
 148         if (startbit > maxMember)
 149             return -1;
 150     }
 151
 152     walkbit = (startbit < iterbit) ? iterbit - startbit : 0;
 153
 154     bits = *pbitvec;
 155     while (walkbit < BITS_PER_LONG &&
 156            ((!(bits & ((unsigned long) 1 << walkbit))) == bitval))
 157         walkbit++;
 158
 159     return startbit + walkbit;
 160 }
 161
 162 static RecordSetIteratePtr
 163 BitVectorIterateSet(RecordSetPtr pSet, RecordSetIteratePtr pIter,
 164                     RecordSetInterval * pInterval)
 165 {
 166     int iterbit = (int) (long) pIter;
 167     int b;
 168
 169     b = BitVectorFindBit(pSet, iterbit, TRUE);
 170     if (b == -1)
 171         return (RecordSetIteratePtr) 0;
 172     pInterval->first = b;
 173
 174     b = BitVectorFindBit(pSet, b, FALSE);
 175     pInterval->last = (b < 0) ? ((BitVectorSetPtr) pSet)->maxMember : b - 1;
 176     return (RecordSetIteratePtr) (long) (pInterval->last + 1);
 177 }
 178
 179 static RecordSetOperations BitVectorSetOperations = {
 180     BitVectorDestroySet, BitVectorIsMemberOfSet, BitVectorIterateSet
 181 };
 182
 183 static RecordSetOperations BitVectorNoFreeOperations = {
 184     NoopDestroySet, BitVectorIsMemberOfSet, BitVectorIterateSet
 185 };
 186
 187 static int
 188 BitVectorSetMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals,
 189                                int maxMember, int *alignment)
 190 {
 191     int nlongs;
 192
 193     *alignment = MinSetAlignment(BitVectorSet);
 194     nlongs = (maxMember + BITS_PER_LONG) / BITS_PER_LONG;
 195     return (sizeof(BitVectorSet) + nlongs * sizeof(unsigned long));
 196 }
 197
 198 static RecordSetPtr
 199 BitVectorCreateSet(RecordSetInterval * pIntervals, int nIntervals,
 200                    void *pMem, int memsize)
 201 {
 202     BitVectorSetPtr pbvs;
 203     int i, j;
 204     unsigned long *pbitvec;
 205
 206     /* allocate all storage needed by this set in one chunk */
 207
 208     if (pMem) {
 209         memset(pMem, 0, memsize);
 210         pbvs = (BitVectorSetPtr) pMem;
 211         pbvs->baseSet.ops = &BitVectorNoFreeOperations;
 212     }
 213     else {
 214         pbvs = (BitVectorSetPtr) calloc(1, memsize);
 215         if (!pbvs)
 216             return NULL;
 217         pbvs->baseSet.ops = &BitVectorSetOperations;
 218     }
 219
 220     pbvs->maxMember = maxMemberInInterval(pIntervals, nIntervals);
 221
 222     /* fill in the set */
 223
 224     pbitvec = (unsigned long *) (&pbvs[1]);
 225     for (i = 0; i < nIntervals; i++) {
 226         for (j = pIntervals[i].first; j <= (int) pIntervals[i].last; j++) {
 227             pbitvec[j / BITS_PER_LONG] |=
 228                 ((unsigned long) 1 << (j % BITS_PER_LONG));
 229         }
 230     }
 231     return (RecordSetPtr) pbvs;
 232 }
 233
 234 /***************************************************************************/
 235
 236 /* set operations for interval list representation */
 237
 238 typedef struct {
 239     RecordSetRec baseSet;
 240     int nIntervals;
 241     /* followed by the intervals (RecordSetInterval) */
 242 } IntervalListSet, *IntervalListSetPtr;
 243
 244 static void
 245 IntervalListDestroySet(RecordSetPtr pSet)
 246 {
 247     free(pSet);
 248 }
 249
 250 static unsigned long
 251 IntervalListIsMemberOfSet(RecordSetPtr pSet, int pm)
 252 {
 253     IntervalListSetPtr prls = (IntervalListSetPtr) pSet;
 254     RecordSetInterval *pInterval = (RecordSetInterval *) (&prls[1]);
 255     int hi, lo, probe;
 256
 257     /* binary search */
 258     lo = 0;
 259     hi = prls->nIntervals - 1;
 260     while (lo <= hi) {
 261         probe = (hi + lo) / 2;
 262         if (pm >= pInterval[probe].first && pm <= pInterval[probe].last)
 263             return 1;
 264         else if (pm < pInterval[probe].first)
 265             hi = probe - 1;
 266         else
 267             lo = probe + 1;
 268     }
 269     return 0;
 270 }
 271
 272 static RecordSetIteratePtr
 273 IntervalListIterateSet(RecordSetPtr pSet, RecordSetIteratePtr pIter,
 274                        RecordSetInterval * pIntervalReturn)
 275 {
 276     RecordSetInterval *pInterval = (RecordSetInterval *) pIter;
 277     IntervalListSetPtr prls = (IntervalListSetPtr) pSet;
 278
 279     if (pInterval == NULL) {
 280         pInterval = (RecordSetInterval *) (&prls[1]);
 281     }
 282
 283     if ((pInterval - (RecordSetInterval *) (&prls[1])) < prls->nIntervals) {
 284         *pIntervalReturn = *pInterval;
 285         return (RecordSetIteratePtr) (++pInterval);
 286     }
 287     else
 288         return (RecordSetIteratePtr) NULL;
 289 }
 290
 291 static RecordSetOperations IntervalListSetOperations = {
 292     IntervalListDestroySet, IntervalListIsMemberOfSet, IntervalListIterateSet
 293 };
 294
 295 static RecordSetOperations IntervalListNoFreeOperations = {
 296     NoopDestroySet, IntervalListIsMemberOfSet, IntervalListIterateSet
 297 };
 298
 299 static int
 300 IntervalListMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals,
 301                                int maxMember, int *alignment)
 302 {
 303     *alignment = MinSetAlignment(IntervalListSet);
 304     return sizeof(IntervalListSet) + nIntervals * sizeof(RecordSetInterval);
 305 }
 306
 307 static RecordSetPtr
 308 IntervalListCreateSet(RecordSetInterval * pIntervals, int nIntervals,
 309                       void *pMem, int memsize)
 310 {
 311     IntervalListSetPtr prls;
 312     int i, j, k;
 313     RecordSetInterval *stackIntervals = NULL;
 314     CARD16 first;
 315
 316     if (nIntervals > 0) {
 317         stackIntervals = xallocarray(nIntervals, sizeof(RecordSetInterval));
 318         if (!stackIntervals)
 319             return NULL;
 320
 321         /* sort intervals, store in stackIntervals (insertion sort) */
 322
 323         for (i = 0; i < nIntervals; i++) {
 324             first = pIntervals[i].first;
 325             for (j = 0; j < i; j++) {
 326                 if (first < stackIntervals[j].first)
 327                     break;
 328             }
 329             for (k = i; k > j; k--) {
 330                 stackIntervals[k] = stackIntervals[k - 1];
 331             }
 332             stackIntervals[j] = pIntervals[i];
 333         }
 334
 335         /* merge abutting/overlapping intervals */
 336
 337         for (i = 0; i < nIntervals - 1;) {
 338             if ((stackIntervals[i].last + (unsigned int) 1) <
 339                 stackIntervals[i + 1].first) {
 340                 i++;            /* disjoint intervals */
 341             }
 342             else {
 343                 stackIntervals[i].last = max(stackIntervals[i].last,
 344                                              stackIntervals[i + 1].last);
 345                 nIntervals--;
 346                 for (j = i + 1; j < nIntervals; j++)
 347                     stackIntervals[j] = stackIntervals[j + 1];
 348             }
 349         }
 350     }
 351
 352     /* allocate and fill in set structure */
 353
 354     if (pMem) {
 355         prls = (IntervalListSetPtr) pMem;
 356         prls->baseSet.ops = &IntervalListNoFreeOperations;
 357     }
 358     else {
 359         prls = (IntervalListSetPtr)
 360             malloc(sizeof(IntervalListSet) +
 361                    nIntervals * sizeof(RecordSetInterval));
 362         if (!prls)
 363             goto bailout;
 364         prls->baseSet.ops = &IntervalListSetOperations;
 365     }
 366     memcpy(&prls[1], stackIntervals, nIntervals * sizeof(RecordSetInterval));
 367     prls->nIntervals = nIntervals;
 368  bailout:
 369     free(stackIntervals);
 370     return (RecordSetPtr) prls;
 371 }
 372
 373 typedef RecordSetPtr(*RecordCreateSetProcPtr) (RecordSetInterval * pIntervals,
 374                                                int nIntervals,
 375                                                void *pMem, int memsize);
 376
 377 static int
 378 _RecordSetMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals,
 379                              int *alignment,
 380                              RecordCreateSetProcPtr * ppCreateSet)
 381 {
 382     int bmsize, rlsize, bma, rla;
 383     int maxMember;
 384
 385     /* find maximum member of set so we know how big to make the bit vector */
 386     maxMember = maxMemberInInterval(pIntervals, nIntervals);
 387
 388     bmsize = BitVectorSetMemoryRequirements(pIntervals, nIntervals, maxMember,
 389                                             &bma);
 390     rlsize = IntervalListMemoryRequirements(pIntervals, nIntervals, maxMember,
 391                                             &rla);
 392     if (((nIntervals > 1) && (maxMember <= 255))
 393         || (bmsize < rlsize)) {
 394         *alignment = bma;
 395         *ppCreateSet = BitVectorCreateSet;
 396         return bmsize;
 397     }
 398     else {
 399         *alignment = rla;
 400         *ppCreateSet = IntervalListCreateSet;
 401         return rlsize;
 402     }
 403 }
 404
 405 /***************************************************************************/
 406
 407 /* user-visible functions */
 408
 409 int
 410 RecordSetMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals,
 411                             int *alignment)
 412 {
 413     RecordCreateSetProcPtr pCreateSet;
 414
 415     return _RecordSetMemoryRequirements(pIntervals, nIntervals, alignment,
 416                                         &pCreateSet);
 417 }
 418
 419 RecordSetPtr
 420 RecordCreateSet(RecordSetInterval * pIntervals, int nIntervals, void *pMem,
 421                 int memsize)
 422 {
 423     RecordCreateSetProcPtr pCreateSet;
 424     int alignment;
 425     int size;
 426
 427     size = _RecordSetMemoryRequirements(pIntervals, nIntervals, &alignment,
 428                                         &pCreateSet);
 429     if (pMem) {
 430         if (((long) pMem & (alignment - 1)) || memsize < size)
 431             return NULL;
 432     }
 433     return (*pCreateSet) (pIntervals, nIntervals, pMem, size);
 434 }