| File: | record/set.c |
| Location: | line 355, column 5 |
| Description: | Null pointer argument in call to memory copy function |
| 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_H1 | |||||
| 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) (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 FALSE0; | |||||
| 101 | pbitvec = (unsigned long *) (&pbvs[1]); | |||||
| 102 | return (pbitvec[pm / BITS_PER_LONG(sizeof(unsigned long) * 8)] & | |||||
| 103 | ((unsigned long) 1 << (pm % BITS_PER_LONG(sizeof(unsigned long) * 8)))); | |||||
| 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(sizeof(unsigned long) * 8); | |||||
| 120 | pbitvec += startlong; | |||||
| 121 | startbit = startlong * BITS_PER_LONG(sizeof(unsigned long) * 8); | |||||
| 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(sizeof(unsigned long) * 8); | |||||
| 132 | ||||||
| 133 | while (startbit <= maxMember && *pbitvec == skipval) { | |||||
| 134 | pbitvec++; | |||||
| 135 | startbit += BITS_PER_LONG(sizeof(unsigned long) * 8); | |||||
| 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(sizeof(unsigned long) * 8) && | |||||
| 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, TRUE1); | |||||
| 159 | if (b == -1) | |||||
| 160 | return (RecordSetIteratePtr) 0; | |||||
| 161 | pInterval->first = b; | |||||
| 162 | ||||||
| 163 | b = BitVectorFindBit(pSet, b, FALSE0); | |||||
| 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(sizeof(unsigned long) * 8)) / BITS_PER_LONG(sizeof(unsigned long) * 8); | |||||
| 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)__builtin___memset_chk (pMem, 0, memsize, __builtin_object_size (pMem, 0)); | |||||
| 199 | pbvs = (BitVectorSetPtr) pMem; | |||||
| 200 | pbvs->baseSet.ops = &BitVectorNoFreeOperations; | |||||
| 201 | } | |||||
| 202 | else { | |||||
| 203 | pbvs = (BitVectorSetPtr) calloc(1, memsize); | |||||
| 204 | if (!pbvs) | |||||
| 205 | return NULL((void*)0); | |||||
| 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(sizeof(unsigned long) * 8)] |= | |||||
| 217 | ((unsigned long) 1 << (j % BITS_PER_LONG(sizeof(unsigned long) * 8))); | |||||
| 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((void*)0)) { | |||||
| 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((void*)0); | |||||
| 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((void*)0); | |||||
| ||||||
| 303 | CARD16 first; | |||||
| 304 | ||||||
| 305 | if (nIntervals > 0) { | |||||
| 306 | stackIntervals = xallocarray(nIntervals, sizeof(RecordSetInterval))xreallocarray(((void*)0), (nIntervals), (sizeof(RecordSetInterval ))); | |||||
| 307 | if (!stackIntervals) | |||||
| 308 | return NULL((void*)0); | |||||
| 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,(((stackIntervals[i].last) > (stackIntervals[i + 1].last)) ? (stackIntervals[i].last) : (stackIntervals[i + 1].last)) | |||||
| 333 | stackIntervals[i + 1].last)(((stackIntervals[i].last) > (stackIntervals[i + 1].last)) ? (stackIntervals[i].last) : (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))__builtin___memcpy_chk (&prls[1], stackIntervals, nIntervals * sizeof(RecordSetInterval), __builtin_object_size (&prls [1], 0)); | |||||
| ||||||
| 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((void*)0); | |||||
| 421 | } | |||||
| 422 | return (*pCreateSet) (pIntervals, nIntervals, pMem, size); | |||||
| 423 | } |