set.c (12691B)
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 = xallocarray(nIntervals, sizeof(RecordSetInterval)); 307 if (!stackIntervals) 308 return NULL; 309 310 /* sort intervals, store in stackIntervals (insertion sort) */ 311 312 for (i = 0; i < nIntervals; i++) { 313 first = pIntervals[i].first; 314 for (j = 0; j < i; j++) { 315 if (first < stackIntervals[j].first) 316 break; 317 } 318 for (k = i; k > j; k--) { 319 stackIntervals[k] = stackIntervals[k - 1]; 320 } 321 stackIntervals[j] = pIntervals[i]; 322 } 323 324 /* merge abutting/overlapping intervals */ 325 326 for (i = 0; i < nIntervals - 1;) { 327 if ((stackIntervals[i].last + (unsigned int) 1) < 328 stackIntervals[i + 1].first) { 329 i++; /* disjoint intervals */ 330 } 331 else { 332 stackIntervals[i].last = max(stackIntervals[i].last, 333 stackIntervals[i + 1].last); 334 nIntervals--; 335 for (j = i + 1; j < nIntervals; j++) 336 stackIntervals[j] = stackIntervals[j + 1]; 337 } 338 } 339 } 340 341 /* allocate and fill in set structure */ 342 343 if (pMem) { 344 prls = (IntervalListSetPtr) pMem; 345 prls->baseSet.ops = &IntervalListNoFreeOperations; 346 } 347 else { 348 prls = (IntervalListSetPtr) 349 malloc(sizeof(IntervalListSet) + 350 nIntervals * sizeof(RecordSetInterval)); 351 if (!prls) 352 goto bailout; 353 prls->baseSet.ops = &IntervalListSetOperations; 354 } 355 memcpy(&prls[1], stackIntervals, nIntervals * sizeof(RecordSetInterval)); 356 prls->nIntervals = nIntervals; 357 bailout: 358 free(stackIntervals); 359 return (RecordSetPtr) prls; 360 } 361 362 typedef RecordSetPtr(*RecordCreateSetProcPtr) (RecordSetInterval * pIntervals, 363 int nIntervals, 364 void *pMem, int memsize); 365 366 static int 367 _RecordSetMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals, 368 int *alignment, 369 RecordCreateSetProcPtr * ppCreateSet) 370 { 371 int bmsize, rlsize, bma, rla; 372 int maxMember; 373 374 /* find maximum member of set so we know how big to make the bit vector */ 375 maxMember = maxMemberInInterval(pIntervals, nIntervals); 376 377 bmsize = BitVectorSetMemoryRequirements(pIntervals, nIntervals, maxMember, 378 &bma); 379 rlsize = IntervalListMemoryRequirements(pIntervals, nIntervals, maxMember, 380 &rla); 381 if (((nIntervals > 1) && (maxMember <= 255)) 382 || (bmsize < rlsize)) { 383 *alignment = bma; 384 *ppCreateSet = BitVectorCreateSet; 385 return bmsize; 386 } 387 else { 388 *alignment = rla; 389 *ppCreateSet = IntervalListCreateSet; 390 return rlsize; 391 } 392 } 393 394 /***************************************************************************/ 395 396 /* user-visible functions */ 397 398 int 399 RecordSetMemoryRequirements(RecordSetInterval * pIntervals, int nIntervals, 400 int *alignment) 401 { 402 RecordCreateSetProcPtr pCreateSet; 403 404 return _RecordSetMemoryRequirements(pIntervals, nIntervals, alignment, 405 &pCreateSet); 406 } 407 408 RecordSetPtr 409 RecordCreateSet(RecordSetInterval * pIntervals, int nIntervals, void *pMem, 410 int memsize) 411 { 412 RecordCreateSetProcPtr pCreateSet; 413 int alignment; 414 int size; 415 416 size = _RecordSetMemoryRequirements(pIntervals, nIntervals, &alignment, 417 &pCreateSet); 418 if (pMem) { 419 if (((long) pMem & (alignment - 1)) || memsize < size) 420 return NULL; 421 } 422 return (*pCreateSet) (pIntervals, nIntervals, pMem, size); 423 }