| 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 | } |