Open64 (mfef90, whirl2f, and IR tools)
TAG: version-openad; SVN changeset: 916
|
00001 /* 00002 00003 Copyright (C) 2000, 2001 Silicon Graphics, Inc. All Rights Reserved. 00004 00005 This program is free software; you can redistribute it and/or modify it 00006 under the terms of version 2 of the GNU General Public License as 00007 published by the Free Software Foundation. 00008 00009 This program is distributed in the hope that it would be useful, but 00010 WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00012 00013 Further, this software is distributed without any warranty that it is 00014 free of the rightful claim of any third person regarding infringement 00015 or the like. Any license provided herein, whether implied or 00016 otherwise, applies only to this software file. Patent licenses, if 00017 any, provided herein do not apply to combinations of this program with 00018 other software, or any other product whatsoever. 00019 00020 You should have received a copy of the GNU General Public License along 00021 with this program; if not, write the Free Software Foundation, Inc., 59 00022 Temple Place - Suite 330, Boston MA 02111-1307, USA. 00023 00024 Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pky, 00025 Mountain View, CA 94043, or: 00026 00027 http://www.sgi.com 00028 00029 For further information regarding this notice, see: 00030 00031 http://oss.sgi.com/projects/GenInfo/NoticeExplan 00032 00033 */ 00034 00035 00036 /* ==================================================================== 00037 * ==================================================================== 00038 * 00039 * 00040 * Revision history: 00041 * 05-03-93 - Original Version 00042 * 00043 * Description: 00044 * 00045 * Bitset implementation. 00046 * 00047 * ==================================================================== 00048 * ==================================================================== 00049 */ 00050 00051 #ifdef _KEEP_RCS_ID 00052 static const char source_file[] = __FILE__; 00053 #endif 00054 00055 #include "defs.h" 00056 #include "mempool.h" 00057 #include "errors.h" 00058 #include "bitset.h" 00059 00060 /* A designated bad memory pool to support assertions that the sets 00061 * shouldn't have to grow: 00062 */ 00063 static MEM_POOL bad_pool_struct; 00064 static MEM_POOL *bad_pool = &bad_pool_struct; 00065 00066 /* ==================================================================== 00067 * 00068 * bs_Malloc 00069 * 00070 * Return a new BS* 00071 * 00072 * length is the number of words to allocate for members 00073 * pool is a pool in which to allocate it 00074 * 00075 * 00076 * ==================================================================== 00077 */ 00078 00079 static BS* 00080 bs_Malloc( 00081 size_t length, 00082 MEM_POOL *pool 00083 ) 00084 { 00085 BS *new_set; 00086 00087 Is_True(pool != bad_pool,("Shouldn't be allocating.")); 00088 00089 new_set = (BS *) TYPE_MEM_POOL_ALLOC_N(BS_WORD,pool,length + 1); 00090 00091 BS_word_count(new_set) = length; 00092 return new_set; 00093 } 00094 00095 /* ==================================================================== 00096 * 00097 * bs_Realloc 00098 * 00099 * Grows the allocation of a BS, potentially returning a new pointer 00100 * to it. 00101 * 00102 * set is the set to grow 00103 * length is the new number of words to allocate for members 00104 * pool is a pool to use for this 00105 * 00106 * ==================================================================== 00107 */ 00108 00109 static BS* 00110 bs_Realloc( 00111 BS *set, 00112 size_t length, 00113 MEM_POOL *pool 00114 ) 00115 { 00116 BS *new_set; 00117 BS_ELT i; 00118 BS_ELT old_length = BS_word_count(set); 00119 size_t new_length; 00120 00121 Is_True(pool != bad_pool,("Shouldn't be allocating.")); 00122 00123 if (length <= old_length) return set; 00124 00125 /* extend length to be a power of 2 */ 00126 for (new_length = 2; new_length < length; new_length <<= 1); 00127 length = new_length; 00128 00129 new_set = (BS *)TYPE_MEM_POOL_REALLOC_N(BS_WORD, pool, set, old_length+1, 00130 length+1); 00131 00132 if (!MEM_POOL_Zeroed(pool)) 00133 for ( i = old_length; i < length; ++i ) 00134 BS_word(new_set,i) = bs_ZEROS; 00135 00136 BS_word_count(new_set) = length; 00137 00138 return new_set; 00139 } 00140 00141 /* ==================================================================== 00142 * 00143 * BS_Create 00144 * 00145 * See interface description 00146 * 00147 * ==================================================================== 00148 */ 00149 00150 extern BS* 00151 BS_Create( 00152 BS_ELT size, 00153 MEM_POOL *pool 00154 ) 00155 { 00156 Is_True(size >= 0,("BS_Create called with negative size.")); 00157 00158 return bs_Malloc(bs_QBPW(size + (BITS_PER_BS_WORD - 1)),pool); 00159 } 00160 00161 /* ==================================================================== 00162 * 00163 * BS_Size_Alloc_Size 00164 * 00165 * See interface description 00166 * 00167 * ==================================================================== 00168 */ 00169 00170 extern size_t 00171 BS_Size_Alloc_Size( 00172 BS_ELT size 00173 ) 00174 { 00175 return (1 + bs_QBPW(size + (BITS_PER_BS_WORD - 1) )) * sizeof(BS_WORD); 00176 } 00177 00178 /* ==================================================================== 00179 * 00180 * BS_Alloc_Size 00181 * 00182 * See interface description 00183 * 00184 * ==================================================================== 00185 */ 00186 00187 extern size_t 00188 BS_Alloc_Size( 00189 BS *set 00190 ) 00191 { 00192 return (BS_word_count(set) + 1) * sizeof(BS_WORD); 00193 } 00194 00195 /* ==================================================================== 00196 * 00197 * BS_ClearD 00198 * 00199 * See interface description 00200 * 00201 * ==================================================================== 00202 */ 00203 00204 extern BS* 00205 BS_ClearD( 00206 BS *set 00207 ) 00208 { 00209 BS_ELT i; 00210 00211 for ( i = 0; i < BS_word_count(set); ++i ) 00212 BS_word(set,i) = bs_ZEROS; 00213 00214 return set; 00215 } 00216 00217 /* ==================================================================== 00218 * 00219 * BS_Create_Empty 00220 * 00221 * See interface description 00222 * 00223 * ==================================================================== 00224 */ 00225 00226 extern BS* 00227 BS_Create_Empty( 00228 BS_ELT size, 00229 MEM_POOL *pool 00230 ) 00231 { 00232 BS *set = BS_Create(size, pool); 00233 if (!MEM_POOL_Zeroed(pool)) 00234 BS_ClearD(set); 00235 return set; 00236 } 00237 00238 /* ==================================================================== 00239 * 00240 * BS_Resize 00241 * 00242 * See interface description 00243 * 00244 * ==================================================================== 00245 */ 00246 00247 extern BS* 00248 BS_ResizeD( 00249 BS* set, 00250 BS_ELT new_size, 00251 MEM_POOL *pool 00252 ) 00253 { 00254 BS_ELT new_words = bs_QBPW(new_size + (BITS_PER_BS_WORD - 1)); 00255 00256 if ( new_words > BS_word_count(set) ) { 00257 set = bs_Realloc(set,new_words,pool); 00258 } 00259 return set; 00260 } 00261 00262 #ifndef MONGOOSE_BE 00263 /* ==================================================================== 00264 * 00265 * BS_Range 00266 * 00267 * See interface description 00268 * 00269 * ==================================================================== 00270 */ 00271 00272 extern BS* 00273 BS_Range( 00274 BS_ELT low, 00275 BS_ELT high, 00276 MEM_POOL *pool 00277 ) 00278 { 00279 return BS_RangeD(BS_Create(high + 1,pool),low,high,bad_pool); 00280 } 00281 #endif /* MONGOOSE_BE */ 00282 00283 /* ==================================================================== 00284 * 00285 * BS_RangeD 00286 * 00287 * See interface description 00288 * 00289 * ==================================================================== 00290 */ 00291 00292 extern BS* 00293 BS_RangeD( 00294 BS* set, 00295 BS_ELT low, 00296 BS_ELT high, 00297 MEM_POOL *pool 00298 ) 00299 { 00300 BS_ELT first_w, last_w, first_b, last_b; 00301 BS_ELT i; 00302 00303 Is_True(low >= 0, 00304 ("BS_RangeD called with negative low element.")); 00305 00306 Is_True(high - low + 1 >= 0, 00307 ("BS_RangeD called with negative range size.")); 00308 00309 if ( low > high ) 00310 return BS_ClearD(set); 00311 00312 first_w = bs_QBPW(low); /* index of first non 0 word */ 00313 last_w = bs_QBPW(high); /* index of last non 0 word */ 00314 first_b = bs_QBPB(low); 00315 last_b = bs_QBPB(high); 00316 00317 /* Reallocate if necessary. 00318 */ 00319 if ( last_w >= BS_word_count(set) ) 00320 set = bs_Realloc(set,last_w + 1,pool); 00321 00322 set = BS_ClearD(set); 00323 00324 /* Set every byte above the first up to and including the last to be 00325 * all ones. This complexity is required in order to make the 00326 * representation endian independent. We win back with a fast 00327 * endian independent ffo for machines with load byte instructions. 00328 */ 00329 00330 /* Set every word above the first and below the last to be all ones. 00331 */ 00332 for ( i = first_w + 1; i < last_w; ++i ) 00333 BS_word(set,i) = bs_ONES; 00334 00335 /* Set every byte in the first word above the first byte to be all 00336 * ones. 00337 */ 00338 /* for ( i = first_b; i < bs_PBPB(first_w + 1); ++i ) shin 03-29-95 */ 00339 for ( i = first_b; i < bs_PBytesPW(first_w + 1) && i <= last_b; ++i ) 00340 BS_byte(set,i) = (BS_BYTE)bs_ONES; 00341 00342 /* Set every byte in the last word up to and including the last byte 00343 * to be all ones. 00344 */ 00345 /* for ( i = bs_PBPB(last_w); i <= last_b; ++i ) fchow 04-11-95 */ 00346 if (first_w != last_w) 00347 for ( i = bs_PBytesPW(last_w); i <= last_b; ++i ) 00348 BS_byte(set,i) = (BS_BYTE)bs_ONES; 00349 00350 /* Fix up the first and last bytes. Order is important! Remember 00351 * that we have already set all the bits in the last byte and that 00352 * the first and last bytes might be the same. 00353 */ 00354 BS_byte(set,first_b) = bs_ONES << bs_RBPB(low); 00355 BS_byte(set,last_b) &= 00356 bs_ONES >> ((BITS_PER_BS_WORD - 1) - bs_RBPB(high)); 00357 00358 return set; 00359 } 00360 00361 /* ==================================================================== 00362 * 00363 * BS_Singleton 00364 * 00365 * See interface description 00366 * 00367 * ==================================================================== 00368 */ 00369 00370 extern BS* 00371 BS_Singleton( 00372 BS_ELT element, 00373 MEM_POOL *pool 00374 ) 00375 { 00376 return BS_SingletonD(BS_Create(element + 1,pool), 00377 element, 00378 bad_pool); 00379 } 00380 00381 /* ==================================================================== 00382 * 00383 * BS_SingletonD 00384 * 00385 * See interface description 00386 * 00387 * ==================================================================== 00388 */ 00389 00390 extern BS* 00391 BS_SingletonD( 00392 BS *set, 00393 BS_ELT element, 00394 MEM_POOL *pool 00395 ) 00396 { 00397 BS_ELT word; 00398 00399 Is_True(element >= 0, 00400 ("BS_SingletonD called with negative element.")); 00401 00402 word = bs_QBPW(element); 00403 00404 /* Reallocate if necessary. 00405 */ 00406 if ( word >= BS_word_count(set) ) 00407 set = bs_Realloc(set,word + 1,pool); 00408 00409 set = BS_ClearD(set); 00410 BS_byte(set,bs_QBPB(element)) = bs_ONE << bs_RBPB(element); 00411 00412 return set; 00413 } 00414 00415 /* ==================================================================== 00416 * 00417 * BS_Universe 00418 * 00419 * See interface description 00420 * 00421 * ==================================================================== 00422 */ 00423 00424 extern BS* 00425 BS_Universe( 00426 BS_ELT size, 00427 MEM_POOL *pool 00428 ) 00429 { 00430 return BS_UniverseD(BS_Create(size,pool),size,bad_pool); 00431 } 00432 00433 /* ==================================================================== 00434 * 00435 * BS_UniverseD 00436 * 00437 * See interface description 00438 * 00439 * ==================================================================== 00440 */ 00441 00442 extern BS* 00443 BS_UniverseD( 00444 BS *set, 00445 BS_ELT size, 00446 MEM_POOL *pool 00447 ) 00448 { 00449 return BS_RangeD(set,0,size - 1,bad_pool); 00450 } 00451 00452 /* ==================================================================== 00453 * 00454 * BS_Copy 00455 * 00456 * See interface description 00457 * 00458 * ==================================================================== 00459 */ 00460 00461 extern BS* 00462 BS_Copy( 00463 BS *set, 00464 MEM_POOL *pool 00465 ) 00466 { 00467 size_t size; 00468 BS* newset; 00469 BS_ELT i; 00470 00471 size = BS_word_count(set); 00472 newset = bs_Malloc(size,pool); 00473 00474 for ( i = 0; i < size; ++i ) 00475 BS_word(newset,i) = BS_word(set,i); 00476 00477 return newset; 00478 } 00479 00480 /* ==================================================================== 00481 * 00482 * BS_CopyD 00483 * 00484 * See interface description 00485 * 00486 * ==================================================================== 00487 */ 00488 00489 extern BS* 00490 BS_CopyD( 00491 BS *set1, 00492 BS *set2, 00493 MEM_POOL *pool 00494 ) 00495 { 00496 BS_ELT i; 00497 BS_ELT size1 = BS_word_count(set1); 00498 BS_ELT size2 = BS_word_count(set2); 00499 00500 /* Reallocate if necessary. 00501 */ 00502 if ( size1 < size2 ) 00503 set1 = bs_Realloc(set1,size2,pool); 00504 else { 00505 /* Else zero out excess. 00506 */ 00507 for ( i = size2; i < size1; ++i ) 00508 BS_word(set1,i) = bs_ZEROS; 00509 } 00510 00511 /* Copy in common part. 00512 */ 00513 for ( i = 0; i < size2; ++i ) 00514 BS_word(set1,i) = BS_word(set2,i); 00515 00516 return set1; 00517 } 00518 00519 /* Mapping from 8 bit unsigned integers to the index of the first one 00520 * bit: 00521 */ 00522 static const mUINT8 first_one [256] = { 00523 0, /* 0 */ 00524 0, /* 1 */ 00525 1, /* 2 */ 00526 0, /* 3 */ 00527 2, /* 4 */ 00528 0, /* 5 */ 00529 1, /* 6 */ 00530 0, /* 7 */ 00531 3, /* 8 */ 00532 0, /* 9 */ 00533 1, /* 10 */ 00534 0, /* 11 */ 00535 2, /* 12 */ 00536 0, /* 13 */ 00537 1, /* 14 */ 00538 0, /* 15 */ 00539 4, /* 16 */ 00540 0, /* 17 */ 00541 1, /* 18 */ 00542 0, /* 19 */ 00543 2, /* 20 */ 00544 0, /* 21 */ 00545 1, /* 22 */ 00546 0, /* 23 */ 00547 3, /* 24 */ 00548 0, /* 25 */ 00549 1, /* 26 */ 00550 0, /* 27 */ 00551 2, /* 28 */ 00552 0, /* 29 */ 00553 1, /* 30 */ 00554 0, /* 31 */ 00555 5, /* 32 */ 00556 0, /* 33 */ 00557 1, /* 34 */ 00558 0, /* 35 */ 00559 2, /* 36 */ 00560 0, /* 37 */ 00561 1, /* 38 */ 00562 0, /* 39 */ 00563 3, /* 40 */ 00564 0, /* 41 */ 00565 1, /* 42 */ 00566 0, /* 43 */ 00567 2, /* 44 */ 00568 0, /* 45 */ 00569 1, /* 46 */ 00570 0, /* 47 */ 00571 4, /* 48 */ 00572 0, /* 49 */ 00573 1, /* 50 */ 00574 0, /* 51 */ 00575 2, /* 52 */ 00576 0, /* 53 */ 00577 1, /* 54 */ 00578 0, /* 55 */ 00579 3, /* 56 */ 00580 0, /* 57 */ 00581 1, /* 58 */ 00582 0, /* 59 */ 00583 2, /* 60 */ 00584 0, /* 61 */ 00585 1, /* 62 */ 00586 0, /* 63 */ 00587 6, /* 64 */ 00588 0, /* 65 */ 00589 1, /* 66 */ 00590 0, /* 67 */ 00591 2, /* 68 */ 00592 0, /* 69 */ 00593 1, /* 70 */ 00594 0, /* 71 */ 00595 3, /* 72 */ 00596 0, /* 73 */ 00597 1, /* 74 */ 00598 0, /* 75 */ 00599 2, /* 76 */ 00600 0, /* 77 */ 00601 1, /* 78 */ 00602 0, /* 79 */ 00603 4, /* 80 */ 00604 0, /* 81 */ 00605 1, /* 82 */ 00606 0, /* 83 */ 00607 2, /* 84 */ 00608 0, /* 85 */ 00609 1, /* 86 */ 00610 0, /* 87 */ 00611 3, /* 88 */ 00612 0, /* 89 */ 00613 1, /* 90 */ 00614 0, /* 91 */ 00615 2, /* 92 */ 00616 0, /* 93 */ 00617 1, /* 94 */ 00618 0, /* 95 */ 00619 5, /* 96 */ 00620 0, /* 97 */ 00621 1, /* 98 */ 00622 0, /* 99 */ 00623 2, /* 100 */ 00624 0, /* 101 */ 00625 1, /* 102 */ 00626 0, /* 103 */ 00627 3, /* 104 */ 00628 0, /* 105 */ 00629 1, /* 106 */ 00630 0, /* 107 */ 00631 2, /* 108 */ 00632 0, /* 109 */ 00633 1, /* 110 */ 00634 0, /* 111 */ 00635 4, /* 112 */ 00636 0, /* 113 */ 00637 1, /* 114 */ 00638 0, /* 115 */ 00639 2, /* 116 */ 00640 0, /* 117 */ 00641 1, /* 118 */ 00642 0, /* 119 */ 00643 3, /* 120 */ 00644 0, /* 121 */ 00645 1, /* 122 */ 00646 0, /* 123 */ 00647 2, /* 124 */ 00648 0, /* 125 */ 00649 1, /* 126 */ 00650 0, /* 127 */ 00651 7, /* 128 */ 00652 0, /* 129 */ 00653 1, /* 130 */ 00654 0, /* 131 */ 00655 2, /* 132 */ 00656 0, /* 133 */ 00657 1, /* 134 */ 00658 0, /* 135 */ 00659 3, /* 136 */ 00660 0, /* 137 */ 00661 1, /* 138 */ 00662 0, /* 139 */ 00663 2, /* 140 */ 00664 0, /* 141 */ 00665 1, /* 142 */ 00666 0, /* 143 */ 00667 4, /* 144 */ 00668 0, /* 145 */ 00669 1, /* 146 */ 00670 0, /* 147 */ 00671 2, /* 148 */ 00672 0, /* 149 */ 00673 1, /* 150 */ 00674 0, /* 151 */ 00675 3, /* 152 */ 00676 0, /* 153 */ 00677 1, /* 154 */ 00678 0, /* 155 */ 00679 2, /* 156 */ 00680 0, /* 157 */ 00681 1, /* 158 */ 00682 0, /* 159 */ 00683 5, /* 160 */ 00684 0, /* 161 */ 00685 1, /* 162 */ 00686 0, /* 163 */ 00687 2, /* 164 */ 00688 0, /* 165 */ 00689 1, /* 166 */ 00690 0, /* 167 */ 00691 3, /* 168 */ 00692 0, /* 169 */ 00693 1, /* 170 */ 00694 0, /* 171 */ 00695 2, /* 172 */ 00696 0, /* 173 */ 00697 1, /* 174 */ 00698 0, /* 175 */ 00699 4, /* 176 */ 00700 0, /* 177 */ 00701 1, /* 178 */ 00702 0, /* 179 */ 00703 2, /* 180 */ 00704 0, /* 181 */ 00705 1, /* 182 */ 00706 0, /* 183 */ 00707 3, /* 184 */ 00708 0, /* 185 */ 00709 1, /* 186 */ 00710 0, /* 187 */ 00711 2, /* 188 */ 00712 0, /* 189 */ 00713 1, /* 190 */ 00714 0, /* 191 */ 00715 6, /* 192 */ 00716 0, /* 193 */ 00717 1, /* 194 */ 00718 0, /* 195 */ 00719 2, /* 196 */ 00720 0, /* 197 */ 00721 1, /* 198 */ 00722 0, /* 199 */ 00723 3, /* 200 */ 00724 0, /* 201 */ 00725 1, /* 202 */ 00726 0, /* 203 */ 00727 2, /* 204 */ 00728 0, /* 205 */ 00729 1, /* 206 */ 00730 0, /* 207 */ 00731 4, /* 208 */ 00732 0, /* 209 */ 00733 1, /* 210 */ 00734 0, /* 211 */ 00735 2, /* 212 */ 00736 0, /* 213 */ 00737 1, /* 214 */ 00738 0, /* 215 */ 00739 3, /* 216 */ 00740 0, /* 217 */ 00741 1, /* 218 */ 00742 0, /* 219 */ 00743 2, /* 220 */ 00744 0, /* 221 */ 00745 1, /* 222 */ 00746 0, /* 223 */ 00747 5, /* 224 */ 00748 0, /* 225 */ 00749 1, /* 226 */ 00750 0, /* 227 */ 00751 2, /* 228 */ 00752 0, /* 229 */ 00753 1, /* 230 */ 00754 0, /* 231 */ 00755 3, /* 232 */ 00756 0, /* 233 */ 00757 1, /* 234 */ 00758 0, /* 235 */ 00759 2, /* 236 */ 00760 0, /* 237 */ 00761 1, /* 238 */ 00762 0, /* 239 */ 00763 4, /* 240 */ 00764 0, /* 241 */ 00765 1, /* 242 */ 00766 0, /* 243 */ 00767 2, /* 244 */ 00768 0, /* 245 */ 00769 1, /* 246 */ 00770 0, /* 247 */ 00771 3, /* 248 */ 00772 0, /* 249 */ 00773 1, /* 250 */ 00774 0, /* 251 */ 00775 2, /* 252 */ 00776 0, /* 253 */ 00777 1, /* 254 */ 00778 0, /* 255 */ 00779 }; 00780 00781 /* ==================================================================== 00782 * 00783 * BS_Choose 00784 * 00785 * See interface description 00786 * 00787 * ==================================================================== 00788 */ 00789 00790 extern BS_ELT 00791 BS_Choose( 00792 const BS* set 00793 ) 00794 { 00795 BS_ELT i, j; 00796 00797 for ( i = 0; i < BS_word_count(set); ++i ) { 00798 if ( BS_word(set,i) != bs_ZEROS ) { 00799 BS_ELT first_byte = bs_PBytesPW(i); 00800 00801 for ( j = 0; j < BYTES_PER_BS_WORD; ++j ) { 00802 BS_BYTE byte = BS_byte(set,j + first_byte); 00803 00804 if ( byte != bs_ZEROS ) 00805 return first_one[byte] + bs_PBPB(j + first_byte); 00806 } 00807 00808 Is_True(FALSE,("Word not zero, but no byte found")); 00809 } 00810 } 00811 00812 return BS_CHOOSE_FAILURE; 00813 } 00814 00815 /* ==================================================================== 00816 * 00817 * BS_Choose_Range 00818 * 00819 * See interface description 00820 * 00821 * ==================================================================== 00822 */ 00823 00824 extern BS_ELT 00825 BS_Choose_Range( 00826 BS *set, 00827 BS_ELT low, 00828 BS_ELT high 00829 ) 00830 { 00831 BS_BYTE byte; 00832 BS_ELT last_first_word_full_byte, i, j; 00833 BS_ELT first_word, last_word; 00834 BS_ELT first_byte, last_byte; 00835 BS_ELT last_elt_in_set; 00836 00837 Is_True(low >= 0, 00838 ("BS_Choose_Range called with negative low element.")); 00839 Is_True(high - low >= -1, 00840 ("BS_Choose_Range called with negative range size.")); 00841 00842 /* Adjust high to be within the set: 00843 */ 00844 last_elt_in_set = bs_PBPW(BS_word_count(set)) - 1; 00845 if ( high > last_elt_in_set ) 00846 high = last_elt_in_set; 00847 00848 /* The following check is needed becaause we won't catch it if low is in 00849 * the next byte from high. 00850 */ 00851 if ( low > high ) 00852 return BS_CHOOSE_FAILURE; 00853 00854 first_byte = bs_QBPB(low); 00855 last_byte = bs_QBPB(high); 00856 00857 /* Check first byte. Since it also might be the last byte, we have 00858 * to be careful to mask out both ends of the range. After this we 00859 * can assume the first byte and last byte are different, which 00860 * simplifies things quite a bit. 00861 */ 00862 byte = BS_byte(set,first_byte) & (bs_ONES << bs_RBPB(low)); 00863 if ( first_byte == last_byte ) 00864 byte &= bs_ONES >> ((BITS_PER_BS_WORD - 1) - bs_RBPB(high)); 00865 00866 if ( byte != bs_ZEROS ) 00867 return first_one[byte] + bs_PBPB(first_byte); 00868 else if (first_byte == last_byte) 00869 return BS_CHOOSE_FAILURE; 00870 00871 /* Chack remaining full bytes in the first word. Since the last 00872 * byte might be in the first word, we have to avoid checking it as 00873 * a full byte. 00874 */ 00875 first_word = bs_QBPW(low); 00876 last_first_word_full_byte = (first_word + 1) * sizeof(BS_WORD) - 1; 00877 00878 if ( last_first_word_full_byte >= last_byte ) 00879 last_first_word_full_byte = last_byte - 1; 00880 00881 for ( i = first_byte + 1; i <= last_first_word_full_byte; ++i ) { 00882 byte = BS_byte(set,i); 00883 00884 if ( byte != bs_ZEROS ) 00885 return first_one[byte] + bs_PBPB(i); 00886 } 00887 00888 /* Now we are either full word aligned or the last byte was in the 00889 * first word. Check full words above the first word and below the 00890 * last word. Notice that this loop won't trip if the last byte was 00891 * in the first word (or the next one for that matter.) 00892 */ 00893 last_word = bs_QBPW(high); 00894 00895 for ( i = first_word + 1; i < last_word; ++i ) { 00896 if ( BS_word(set,i) != bs_ZEROS ) { 00897 /* Found the word, now locate the byte in that word. 00898 */ 00899 for ( j = 0; j < sizeof(BS_WORD); ++j ) { 00900 byte = BS_byte(set, j + i * BYTES_PER_BS_WORD); 00901 00902 if ( byte != 0 ) 00903 return first_one[byte] + bs_PBPB(j) + bs_PBPW(i); 00904 } 00905 } 00906 } 00907 00908 /* Check any unchecked full bytes in the last word. This loop will 00909 * only trip if the last word is greater than the first word, since 00910 * otherwise the loop above leaves i above the first word, no matter 00911 * what. In fact, at this point i is the index of the first 00912 * unchecked word. 00913 */ 00914 for ( i *= sizeof(BS_WORD); i < last_byte; ++i ) { 00915 byte = BS_byte(set,i); 00916 00917 if ( byte != 0 ) 00918 return first_one[byte] + 8 * i; 00919 } 00920 00921 /* Now we'll check the final byte, which we have assumed is partial. 00922 * Even if it is full, the following will work. 00923 */ 00924 byte = BS_byte(set,last_byte) 00925 & (bs_ONES >> ((BITS_PER_BS_WORD - 1) - bs_RBPB(high))); 00926 00927 if ( byte != 0 ) 00928 return first_one[byte] + bs_PBPB(last_byte); 00929 00930 return BS_CHOOSE_FAILURE; 00931 } 00932 00933 00934 /* ======================================================================= 00935 * 00936 * BS_Choose_Next 00937 * 00938 * See interface description. 00939 * 00940 * ======================================================================= 00941 */ 00942 00943 extern BS_ELT 00944 BS_Choose_Next( 00945 const BS* set, 00946 BS_ELT bound 00947 ) 00948 { 00949 BS_ELT i, j, inx_first_byte, inx_first_byte_second_word, word_count; 00950 BS_BYTE byte; 00951 00952 ++bound; /* Now bound is inclusive. */ 00953 00954 if ( bound >= bs_PBPW(BS_word_count(set)) ) 00955 return BS_CHOOSE_FAILURE; 00956 00957 /* Search first byte with stuff below bound masked out: 00958 */ 00959 inx_first_byte = bs_QBPB(bound); 00960 byte = BS_byte(set,inx_first_byte) & (bs_ONES << bs_RBPB(bound)); 00961 if ( byte != bs_ZEROS ) 00962 return first_one[byte] + bs_PBPB(inx_first_byte); 00963 00964 /* Search remaining bytes in first word: 00965 */ 00966 inx_first_byte_second_word = (bs_QBPW(bound) + 1) * sizeof(BS_WORD); 00967 00968 for ( i = inx_first_byte + 1; i < inx_first_byte_second_word; ++i ) { 00969 byte = BS_byte(set,i); 00970 00971 if ( byte != bs_ZEROS ) 00972 return first_one[byte] + bs_PBPB(i); 00973 } 00974 00975 /* search remaining words: 00976 */ 00977 word_count = BS_word_count(set); 00978 00979 for ( i = bs_QBPW(bound) + 1; i < word_count; ++i ) { 00980 if ( BS_word(set,i) != bs_ZEROS ) { 00981 BS_ELT first_byte = bs_PBytesPW(i); 00982 00983 /* There's something in this word, search each byte for it: 00984 */ 00985 for ( j = 0; j < BYTES_PER_BS_WORD; ++j ) { 00986 BS_BYTE byte = BS_byte(set,j + first_byte); 00987 00988 if ( byte != bs_ZEROS ) 00989 return first_one[byte] + bs_PBPB(j + first_byte); 00990 } 00991 00992 Is_True(FALSE,("Word not zero, but no byte found")); 00993 } 00994 } 00995 00996 return BS_CHOOSE_FAILURE; 00997 } 00998 00999 01000 /* ==================================================================== 01001 * 01002 * BS_Intersection_Choose 01003 * 01004 * See interface description 01005 * 01006 * ==================================================================== 01007 */ 01008 01009 extern BS_ELT 01010 BS_Intersection_Choose( 01011 BS* set1, 01012 BS* set2 01013 ) 01014 { 01015 BS_ELT i, j; 01016 BS_ELT last_word; 01017 01018 if ( BS_word_count(set1) < BS_word_count(set2) ) 01019 last_word = BS_word_count(set1); 01020 else 01021 last_word = BS_word_count(set2); 01022 01023 for ( i = 0; i < last_word; ++i ) { 01024 if ( (BS_word(set1,i) & BS_word(set2,i)) != bs_ZEROS ) { 01025 BS_ELT first_byte = bs_PBytesPW(i); 01026 01027 for ( j = 0; j < BYTES_PER_BS_WORD; ++j ) { 01028 BS_BYTE byte = BS_byte(set1,j + first_byte) 01029 & BS_byte(set2,j + first_byte); 01030 01031 if ( byte != bs_ZEROS ) 01032 return first_one[byte] + bs_PBPB(j + first_byte); 01033 } 01034 01035 Is_True(FALSE,("Word not zero, but no byte found")); 01036 } 01037 } 01038 01039 return BS_CHOOSE_FAILURE; 01040 } 01041 01042 01043 01044 /* ======================================================================= 01045 * 01046 * BS_Intersection_Choose_Next 01047 * 01048 * See interface description. 01049 * 01050 * ======================================================================= 01051 */ 01052 01053 extern BS_ELT 01054 BS_Intersection_Choose_Next( 01055 BS* set1, 01056 BS* set2, 01057 BS_ELT bound 01058 ) 01059 { 01060 BS_ELT i, j, inx_first_byte, inx_first_byte_second_word, word_count; 01061 BS_BYTE byte; 01062 01063 if ( BS_word_count(set1) < BS_word_count(set2) ) 01064 word_count = BS_word_count(set1); 01065 else 01066 word_count = BS_word_count(set2); 01067 01068 ++bound; /* Now bound is inclusive. */ 01069 01070 if ( bound >= bs_PBPW(word_count) ) 01071 return BS_CHOOSE_FAILURE; 01072 01073 /* Search first byte with stuff below bound masked out: 01074 */ 01075 inx_first_byte = bs_QBPB(bound); 01076 byte = BS_byte(set1,inx_first_byte) 01077 & BS_byte(set2,inx_first_byte) 01078 & (bs_ONES << bs_RBPB(bound)); 01079 if ( byte != bs_ZEROS ) 01080 return first_one[byte] + bs_PBPB(inx_first_byte); 01081 01082 /* Search remaining bytes in first word: 01083 */ 01084 inx_first_byte_second_word = (bs_QBPW(bound) + 1) * sizeof(BS_WORD); 01085 01086 for ( i = inx_first_byte + 1; i < inx_first_byte_second_word; ++i ) { 01087 byte = BS_byte(set1,i) 01088 & BS_byte(set2,i); 01089 01090 if ( byte != bs_ZEROS ) 01091 return first_one[byte] + bs_PBPB(i); 01092 } 01093 01094 /* search remaining words: 01095 */ 01096 for ( i = bs_QBPW(bound) + 1; i < word_count; ++i ) { 01097 if ( (BS_word(set1,i) & BS_word(set2,i)) != bs_ZEROS ) { 01098 BS_ELT first_byte = bs_PBytesPW(i); 01099 01100 /* There's something in this word, search each byte for it: 01101 */ 01102 for ( j = 0; j < BYTES_PER_BS_WORD; ++j ) { 01103 BS_BYTE byte = BS_byte(set1,j + first_byte) 01104 & BS_byte(set2,j + first_byte); 01105 01106 if ( byte != bs_ZEROS ) 01107 return first_one[byte] + bs_PBPB(j + first_byte); 01108 } 01109 01110 Is_True(FALSE,("Word not zero, but no byte found")); 01111 } 01112 } 01113 01114 return BS_CHOOSE_FAILURE; 01115 } 01116 01117 01118 01119 /* ==================================================================== 01120 * 01121 * BS_Difference 01122 * 01123 * See interface description 01124 * 01125 * ==================================================================== 01126 */ 01127 01128 extern BS* 01129 BS_Difference( 01130 BS *set1, 01131 BS *set2, 01132 MEM_POOL *pool 01133 ) 01134 { 01135 BS *set; 01136 BS_ELT i; 01137 BS_ELT size1 = BS_word_count(set1); 01138 BS_ELT size2 = BS_word_count(set2); 01139 BS_ELT minsize = Min(size1,size2); 01140 01141 set = bs_Malloc(size1,pool); 01142 01143 /* Common part: copy in the difference. 01144 */ 01145 for ( i = 0; i < minsize; ++i ) 01146 BS_word(set,i) = BS_word(set1,i) & ~BS_word(set2,i); 01147 01148 /* Excess of set1 over set2: just copy it in. 01149 */ 01150 for ( i = minsize; i < size1; ++i ) 01151 BS_word(set,i) = BS_word(set1,i); 01152 01153 return set; 01154 } 01155 01156 /* ==================================================================== 01157 * 01158 * BS_DifferenceD 01159 * 01160 * See interface description 01161 * 01162 * ==================================================================== 01163 */ 01164 01165 extern BS* 01166 BS_DifferenceD( 01167 BS* set1, 01168 BS* set2 01169 ) 01170 { 01171 BS_ELT i; 01172 BS_ELT minsize = Min(BS_word_count(set1),BS_word_count(set2)); 01173 01174 for ( i = 0; i < minsize; ++i ) 01175 BS_word(set1,i) &= ~BS_word(set2,i); 01176 01177 return set1; 01178 } 01179 01180 /* ==================================================================== 01181 * 01182 * BS_Difference1 01183 * 01184 * See interface description 01185 * 01186 * ==================================================================== 01187 */ 01188 01189 extern BS* 01190 BS_Difference1( 01191 BS *set, 01192 BS_ELT x, 01193 MEM_POOL *pool 01194 ) 01195 { 01196 return BS_Difference1D(BS_Copy(set,pool),x); 01197 } 01198 01199 /* ==================================================================== 01200 * 01201 * BS_Difference1D 01202 * 01203 * See interface description 01204 * 01205 * ==================================================================== 01206 */ 01207 01208 extern BS* 01209 BS_Difference1D( 01210 BS *set, 01211 BS_ELT x 01212 ) 01213 { 01214 Is_True(x >= 0, 01215 ("BS_Difference1D called with negative element.")); 01216 01217 if ( bs_QBPW(x) < BS_word_count(set) ) 01218 BS_byte(set,bs_QBPB(x)) &= ~(bs_ONE << bs_RBPB(x)); 01219 01220 return set; 01221 } 01222 01223 /* ==================================================================== 01224 * 01225 * BS_Intersection 01226 * 01227 * See interface description 01228 * 01229 * ==================================================================== 01230 */ 01231 01232 extern BS* 01233 BS_Intersection( 01234 BS *set1, 01235 BS *set2, 01236 MEM_POOL *pool 01237 ) 01238 { 01239 BS_ELT i; 01240 BS_ELT size; 01241 BS *newset; 01242 01243 if ( BS_word_count(set1) < BS_word_count(set2) ) 01244 size = BS_word_count(set1); 01245 else 01246 size = BS_word_count(set2); 01247 01248 newset = bs_Malloc(size,pool); 01249 01250 for ( i = 0; i < size; ++i ) 01251 BS_word(newset,i) = BS_word(set1,i) & BS_word(set2,i); 01252 01253 return newset; 01254 } 01255 01256 /* ==================================================================== 01257 * 01258 * BS_IntersectionD 01259 * 01260 * See interface description 01261 * 01262 * ==================================================================== 01263 */ 01264 01265 extern BS* 01266 BS_IntersectionD( 01267 BS* set1, 01268 BS* set2 01269 ) 01270 { 01271 BS_ELT i; 01272 BS_ELT minsize; 01273 01274 minsize = MIN( BS_word_count(set1), BS_word_count(set2) ); 01275 01276 /* Form intersection of common part: 01277 */ 01278 for ( i = 0; i < minsize; ++i ) 01279 BS_word(set1,i) &= BS_word(set2,i); 01280 01281 /* Zero surplus words in set1: 01282 */ 01283 for ( i = i; i < BS_word_count(set1); ++i ) 01284 BS_word(set1,i) = bs_ZEROS; 01285 01286 return set1; 01287 } 01288 01289 01290 /* ==================================================================== 01291 * 01292 * BS_IntersectionR 01293 * 01294 * See interface description 01295 * 01296 * ==================================================================== 01297 */ 01298 01299 extern BS* 01300 BS_IntersectionR( 01301 BS* result, 01302 const BS* set1, 01303 const BS* set2 01304 ) 01305 { 01306 BS_ELT i; 01307 BS_ELT minsize; 01308 01309 minsize = MIN( BS_word_count(set1), BS_word_count(set2) ); 01310 01311 /* Form intersection of common part: 01312 */ 01313 for ( i = 0; i < minsize; ++i ) 01314 BS_word(result,i) = BS_word(set1,i) & BS_word(set2,i); 01315 01316 /* Zero surplus words in result: 01317 */ 01318 for ( i = i; i < BS_word_count(result); ++i ) 01319 BS_word(result,i) = bs_ZEROS; 01320 01321 return result; 01322 } 01323 01324 01325 /* Count of bits in all the one byte numbers. Used to count members. 01326 */ 01327 static unsigned const char bit_count[256] = { 01328 0, /* 0 */ 01329 1, /* 1 */ 01330 1, /* 2 */ 01331 2, /* 3 */ 01332 1, /* 4 */ 01333 2, /* 5 */ 01334 2, /* 6 */ 01335 3, /* 7 */ 01336 1, /* 8 */ 01337 2, /* 9 */ 01338 2, /* 10 */ 01339 3, /* 11 */ 01340 2, /* 12 */ 01341 3, /* 13 */ 01342 3, /* 14 */ 01343 4, /* 15 */ 01344 1, /* 16 */ 01345 2, /* 17 */ 01346 2, /* 18 */ 01347 3, /* 19 */ 01348 2, /* 20 */ 01349 3, /* 21 */ 01350 3, /* 22 */ 01351 4, /* 23 */ 01352 2, /* 24 */ 01353 3, /* 25 */ 01354 3, /* 26 */ 01355 4, /* 27 */ 01356 3, /* 28 */ 01357 4, /* 29 */ 01358 4, /* 30 */ 01359 5, /* 31 */ 01360 1, /* 32 */ 01361 2, /* 33 */ 01362 2, /* 34 */ 01363 3, /* 35 */ 01364 2, /* 36 */ 01365 3, /* 37 */ 01366 3, /* 38 */ 01367 4, /* 39 */ 01368 2, /* 40 */ 01369 3, /* 41 */ 01370 3, /* 42 */ 01371 4, /* 43 */ 01372 3, /* 44 */ 01373 4, /* 45 */ 01374 4, /* 46 */ 01375 5, /* 47 */ 01376 2, /* 48 */ 01377 3, /* 49 */ 01378 3, /* 50 */ 01379 4, /* 51 */ 01380 3, /* 52 */ 01381 4, /* 53 */ 01382 4, /* 54 */ 01383 5, /* 55 */ 01384 3, /* 56 */ 01385 4, /* 57 */ 01386 4, /* 58 */ 01387 5, /* 59 */ 01388 4, /* 60 */ 01389 5, /* 61 */ 01390 5, /* 62 */ 01391 6, /* 63 */ 01392 1, /* 64 */ 01393 2, /* 65 */ 01394 2, /* 66 */ 01395 3, /* 67 */ 01396 2, /* 68 */ 01397 3, /* 69 */ 01398 3, /* 70 */ 01399 4, /* 71 */ 01400 2, /* 72 */ 01401 3, /* 73 */ 01402 3, /* 74 */ 01403 4, /* 75 */ 01404 3, /* 76 */ 01405 4, /* 77 */ 01406 4, /* 78 */ 01407 5, /* 79 */ 01408 2, /* 80 */ 01409 3, /* 81 */ 01410 3, /* 82 */ 01411 4, /* 83 */ 01412 3, /* 84 */ 01413 4, /* 85 */ 01414 4, /* 86 */ 01415 5, /* 87 */ 01416 3, /* 88 */ 01417 4, /* 89 */ 01418 4, /* 90 */ 01419 5, /* 91 */ 01420 4, /* 92 */ 01421 5, /* 93 */ 01422 5, /* 94 */ 01423 6, /* 95 */ 01424 2, /* 96 */ 01425 3, /* 97 */ 01426 3, /* 98 */ 01427 4, /* 99 */ 01428 3, /* 100 */ 01429 4, /* 101 */ 01430 4, /* 102 */ 01431 5, /* 103 */ 01432 3, /* 104 */ 01433 4, /* 105 */ 01434 4, /* 106 */ 01435 5, /* 107 */ 01436 4, /* 108 */ 01437 5, /* 109 */ 01438 5, /* 110 */ 01439 6, /* 111 */ 01440 3, /* 112 */ 01441 4, /* 113 */ 01442 4, /* 114 */ 01443 5, /* 115 */ 01444 4, /* 116 */ 01445 5, /* 117 */ 01446 5, /* 118 */ 01447 6, /* 119 */ 01448 4, /* 120 */ 01449 5, /* 121 */ 01450 5, /* 122 */ 01451 6, /* 123 */ 01452 5, /* 124 */ 01453 6, /* 125 */ 01454 6, /* 126 */ 01455 7, /* 127 */ 01456 1, /* 128 */ 01457 2, /* 129 */ 01458 2, /* 130 */ 01459 3, /* 131 */ 01460 2, /* 132 */ 01461 3, /* 133 */ 01462 3, /* 134 */ 01463 4, /* 135 */ 01464 2, /* 136 */ 01465 3, /* 137 */ 01466 3, /* 138 */ 01467 4, /* 139 */ 01468 3, /* 140 */ 01469 4, /* 141 */ 01470 4, /* 142 */ 01471 5, /* 143 */ 01472 2, /* 144 */ 01473 3, /* 145 */ 01474 3, /* 146 */ 01475 4, /* 147 */ 01476 3, /* 148 */ 01477 4, /* 149 */ 01478 4, /* 150 */ 01479 5, /* 151 */ 01480 3, /* 152 */ 01481 4, /* 153 */ 01482 4, /* 154 */ 01483 5, /* 155 */ 01484 4, /* 156 */ 01485 5, /* 157 */ 01486 5, /* 158 */ 01487 6, /* 159 */ 01488 2, /* 160 */ 01489 3, /* 161 */ 01490 3, /* 162 */ 01491 4, /* 163 */ 01492 3, /* 164 */ 01493 4, /* 165 */ 01494 4, /* 166 */ 01495 5, /* 167 */ 01496 3, /* 168 */ 01497 4, /* 169 */ 01498 4, /* 170 */ 01499 5, /* 171 */ 01500 4, /* 172 */ 01501 5, /* 173 */ 01502 5, /* 174 */ 01503 6, /* 175 */ 01504 3, /* 176 */ 01505 4, /* 177 */ 01506 4, /* 178 */ 01507 5, /* 179 */ 01508 4, /* 180 */ 01509 5, /* 181 */ 01510 5, /* 182 */ 01511 6, /* 183 */ 01512 4, /* 184 */ 01513 5, /* 185 */ 01514 5, /* 186 */ 01515 6, /* 187 */ 01516 5, /* 188 */ 01517 6, /* 189 */ 01518 6, /* 190 */ 01519 7, /* 191 */ 01520 2, /* 192 */ 01521 3, /* 193 */ 01522 3, /* 194 */ 01523 4, /* 195 */ 01524 3, /* 196 */ 01525 4, /* 197 */ 01526 4, /* 198 */ 01527 5, /* 199 */ 01528 3, /* 200 */ 01529 4, /* 201 */ 01530 4, /* 202 */ 01531 5, /* 203 */ 01532 4, /* 204 */ 01533 5, /* 205 */ 01534 5, /* 206 */ 01535 6, /* 207 */ 01536 3, /* 208 */ 01537 4, /* 209 */ 01538 4, /* 210 */ 01539 5, /* 211 */ 01540 4, /* 212 */ 01541 5, /* 213 */ 01542 5, /* 214 */ 01543 6, /* 215 */ 01544 4, /* 216 */ 01545 5, /* 217 */ 01546 5, /* 218 */ 01547 6, /* 219 */ 01548 5, /* 220 */ 01549 6, /* 221 */ 01550 6, /* 222 */ 01551 7, /* 223 */ 01552 3, /* 224 */ 01553 4, /* 225 */ 01554 4, /* 226 */ 01555 5, /* 227 */ 01556 4, /* 228 */ 01557 5, /* 229 */ 01558 5, /* 230 */ 01559 6, /* 231 */ 01560 4, /* 232 */ 01561 5, /* 233 */ 01562 5, /* 234 */ 01563 6, /* 235 */ 01564 5, /* 236 */ 01565 6, /* 237 */ 01566 6, /* 238 */ 01567 7, /* 239 */ 01568 4, /* 240 */ 01569 5, /* 241 */ 01570 5, /* 242 */ 01571 6, /* 243 */ 01572 5, /* 244 */ 01573 6, /* 245 */ 01574 6, /* 246 */ 01575 7, /* 247 */ 01576 5, /* 248 */ 01577 6, /* 249 */ 01578 6, /* 250 */ 01579 7, /* 251 */ 01580 6, /* 252 */ 01581 7, /* 253 */ 01582 7, /* 254 */ 01583 8 /* 255 */ 01584 }; 01585 01586 /* ==================================================================== 01587 * 01588 * BS_Size 01589 * 01590 * See interface description 01591 * 01592 * ==================================================================== 01593 */ 01594 01595 extern BS_ELT 01596 BS_Size( 01597 BS* set 01598 ) 01599 { 01600 /* Add up the population count of each byte in the set. We get the 01601 * population counts from the table above. Great for a machine with 01602 * effecient loadbyte instructions! 01603 */ 01604 BS_ELT i; 01605 BS_ELT byte_count = BS_word_count(set) * sizeof(BS_WORD); 01606 size_t result = 0; 01607 01608 for ( i = 0; i < byte_count; ++i ) 01609 result += bit_count[BS_byte(set,i)]; 01610 01611 return result; 01612 } 01613 01614 /* ==================================================================== 01615 * 01616 * BS_Union 01617 * 01618 * See interface description 01619 * 01620 * ==================================================================== 01621 */ 01622 01623 extern BS* 01624 BS_Union( 01625 BS *set1, 01626 BS *set2, 01627 MEM_POOL *pool 01628 ) 01629 { 01630 BS *set; 01631 BS_ELT i; 01632 BS_ELT size1 = BS_word_count(set1); 01633 BS_ELT size2 = BS_word_count(set2); 01634 01635 if ( size1 < size2 ) { 01636 /* Normalize so set1 is at least as large: 01637 */ 01638 BS *tmps = set1; 01639 BS_ELT tmpe = size1; 01640 01641 set1 = set2; 01642 set2 = tmps; 01643 size1 = size2; 01644 size2 = tmpe; 01645 } 01646 01647 set = bs_Malloc(size1,pool); 01648 for ( i = 0; i < size2; ++i ) 01649 BS_word(set,i) = BS_word(set1,i) | BS_word(set2,i); 01650 for ( i = size2; i < size1; ++i ) 01651 BS_word(set,i) = BS_word(set1,i); 01652 01653 return set; 01654 } 01655 01656 /* ==================================================================== 01657 * 01658 * BS_UnionD 01659 * 01660 * See interface description 01661 * 01662 * ==================================================================== 01663 */ 01664 01665 extern BS* 01666 BS_UnionD( 01667 BS *set1, 01668 BS *set2, 01669 MEM_POOL *pool 01670 ) 01671 { 01672 BS_ELT i; 01673 BS_ELT size1 = BS_word_count(set1); 01674 BS_ELT size2 = BS_word_count(set2); 01675 01676 if ( size1 < size2 ) 01677 set1 = bs_Realloc(set1,size2,pool); 01678 01679 for ( i = 0; i < size2; ++i ) 01680 BS_word(set1,i) |= BS_word(set2,i); 01681 01682 return set1; 01683 } 01684 01685 /* ==================================================================== 01686 * 01687 * BS_UnionR 01688 * 01689 * See interface description 01690 * 01691 * ==================================================================== 01692 */ 01693 01694 extern BS* 01695 BS_UnionR( 01696 BS *result, 01697 BS *set1, 01698 BS *set2, 01699 MEM_POOL *pool 01700 ) 01701 { 01702 BS_ELT i; 01703 BS_ELT size1 = BS_word_count(set1); 01704 BS_ELT size2 = BS_word_count(set2); 01705 BS_ELT maxsize = MAX( size1, size2 ); 01706 BS_ELT rsize = BS_word_count(result); 01707 01708 if ( rsize < maxsize ) 01709 result = bs_Realloc(result,maxsize,pool); 01710 01711 for ( i = 0; i < maxsize; ++i ) 01712 BS_word(result,i) = BS_word(set1,i) | BS_word(set2,i); 01713 01714 return result; 01715 } 01716 01717 /* ==================================================================== 01718 * 01719 * BS_UnionD_Intersection 01720 * 01721 * See interface description 01722 * 01723 * ==================================================================== 01724 */ 01725 01726 extern BS* 01727 BS_UnionD_Intersection( 01728 BS *set1, 01729 BS *set2, 01730 BS *set3, 01731 MEM_POOL *pool 01732 ) 01733 { 01734 BS_ELT i; 01735 BS_ELT size1 = BS_word_count(set1); 01736 BS_ELT minsize = MIN( BS_word_count(set2), BS_word_count(set3) ); 01737 01738 if ( size1 < minsize ) 01739 set1 = bs_Realloc(set1,minsize,pool); 01740 01741 for ( i = 0; i < minsize; ++i ) 01742 BS_word(set1,i) |= BS_word(set2,i) & BS_word(set3,i); 01743 01744 return set1; 01745 } 01746 01747 /* ==================================================================== 01748 * 01749 * BS_Union1 01750 * 01751 * See interface description 01752 * 01753 * ==================================================================== 01754 */ 01755 01756 extern BS* 01757 BS_Union1( 01758 BS *set, 01759 BS_ELT x, 01760 MEM_POOL *pool 01761 ) 01762 { 01763 BS_ELT newsize; 01764 BS *newset; 01765 01766 if ( BS_word_count(set) > bs_QBPW(x) + 1 ) 01767 newsize = bs_PBPW(BS_word_count(set)); 01768 else 01769 newsize = x + 1; 01770 01771 newset = BS_Create_Empty(newsize,pool); 01772 newset = BS_CopyD(newset,set,bad_pool); 01773 return BS_Union1D(newset,x,bad_pool); 01774 } 01775 01776 /* ==================================================================== 01777 * 01778 * BS_Union1D 01779 * 01780 * See interface description 01781 * 01782 * ==================================================================== 01783 */ 01784 01785 extern BS* 01786 BS_Union1D( 01787 BS *set, 01788 BS_ELT x, 01789 MEM_POOL *pool 01790 ) 01791 { 01792 BS_ELT minsize = bs_QBPW(x) + 1; 01793 01794 Is_True(x >= 0,("BS_Union1D called with negative element.")); 01795 01796 if ( minsize > BS_word_count(set) ) 01797 set = bs_Realloc(set,minsize,pool); 01798 01799 BS_byte(set,bs_QBPB(x)) |= bs_ONE << bs_RBPB(x); 01800 01801 return set; 01802 } 01803 01804 /* ==================================================================== 01805 * 01806 * BS_2_1_Minus_3_Or_R 01807 * 01808 * See interface description 01809 * 01810 * ==================================================================== 01811 */ 01812 01813 extern BS* 01814 BS_2_1_Minus_3_Or_R( 01815 BS *result, 01816 const BS *set1, 01817 const BS *set2, 01818 const BS *set3, 01819 MEM_POOL *pool 01820 ) 01821 { 01822 BS_ELT i; 01823 BS_ELT rsize = BS_word_count(result); 01824 BS_ELT size3 = BS_word_count(set3); 01825 01826 Is_True( BS_word_count(set1) == size3, 01827 ("BS_2_1_Minus_3_Or_R: set1 size (%d) < set3 size (%d)", 01828 (BS_ELT)BS_word_count(set1), size3) ); 01829 Is_True( BS_word_count(set2) == size3, 01830 ("BS_2_1_Minus_3_Or_R: set2 size (%d) < set3 size (%d)", 01831 (BS_ELT)BS_word_count(set2), size3) ); 01832 01833 if ( rsize < size3 ) 01834 result = bs_Realloc(result,size3,pool); 01835 01836 for ( i = 0; i < size3; ++i ) 01837 BS_word(result,i) = (~BS_word(set1,i) & BS_word(set2,i)) | 01838 BS_word(set3,i); 01839 01840 return result; 01841 } 01842 01843 extern BS* 01844 BS_3_2_Minus_1_Or_D( 01845 BS *set1, 01846 const BS *set2, 01847 const BS *set3, 01848 MEM_POOL *pool 01849 ) 01850 { 01851 BS_ELT i; 01852 BS_ELT size1 = BS_word_count(set1); 01853 BS_ELT size2 = BS_word_count(set2); 01854 BS_ELT size3 = BS_word_count(set3); 01855 01856 Is_True( size2 == size3, 01857 ("BS_3_2_Minus_1_Or_D: set2 size (%d) != set3 size (%d)", 01858 size2, size3) ); 01859 01860 if ( size1 < size3 ) 01861 set1 = bs_Realloc(set1,size3,pool); 01862 01863 for ( i = 0; i < size3; ++i ) 01864 BS_word(set1,i) |= (~BS_word(set2,i) & BS_word(set3,i)); 01865 01866 return set1; 01867 } 01868 01869 /* ==================================================================== 01870 * 01871 * BS_3_2_Minus_4_Or_1_Or_D 01872 * 01873 * set1 += ((~set2) AND set3) OR set4 01874 * set1 += (set3 - set2) + set4 01875 * 01876 * ==================================================================== 01877 */ 01878 01879 extern BS* 01880 BS_3_2_Minus_4_Or_1_Or_D( 01881 BS *set1, 01882 const BS *set2, 01883 const BS *set3, 01884 const BS *set4, 01885 MEM_POOL *pool ) 01886 { 01887 BS_ELT i; 01888 BS_ELT size1 = BS_word_count(set1); 01889 BS_ELT size2 = BS_word_count(set2); 01890 BS_ELT size3 = BS_word_count(set3); 01891 BS_ELT size4 = BS_word_count(set4); 01892 01893 Is_True( size2 == size3 && size3 == size4, 01894 ("BS_3_2_Minus_4_Or_1_Or_D: sizes not equal %d, %d, %d", 01895 size2, size3, size4) ); 01896 01897 if ( size1 < size2 ) 01898 set1 = bs_Realloc(set1,size2,pool); 01899 01900 for ( i = 0; i < size2; ++i ) 01901 BS_word(set1,i) |= (~BS_word(set2,i) & BS_word(set3,i)) | 01902 BS_word(set4,i); 01903 01904 return set1; 01905 } 01906 01907 01908 /* ==================================================================== 01909 * 01910 * BS_3_2_Minus_4_Or_5_Or_1_Or_D 01911 * 01912 * set1 += ((~set2) AND set3) OR set4 OR set5 01913 * set1 += (set3 - set2) + set4 + set5 01914 * 01915 * ==================================================================== 01916 */ 01917 01918 extern BS* 01919 BS_3_2_Minus_4_Or_5_Or_1_Or_D( 01920 BS *set1, 01921 const BS *set2, 01922 const BS *set3, 01923 const BS *set4, 01924 const BS *set5, 01925 MEM_POOL *pool ) 01926 { 01927 BS_ELT i; 01928 BS_ELT size1 = BS_word_count(set1); 01929 BS_ELT size5 = BS_word_count(set5); 01930 01931 Is_True( BS_word_count(set2) == size5, 01932 ("BS_3_2_Minus_4_Or_5_Or_1_Or_D: set2 size (%d) != set5 size (%d)", 01933 (BS_ELT)BS_word_count(set2), size5) ); 01934 Is_True( BS_word_count(set3) == size5, 01935 ("BS_3_2_Minus_4_Or_5_Or_1_Or_D: set3 size (%d) != set5 size (%d)", 01936 (BS_ELT)BS_word_count(set3), size5) ); 01937 Is_True( BS_word_count(set4) == size5, 01938 ("BS_3_2_Minus_4_Or_5_Or_1_Or_D: set4 size (%d) != set5 size (%d)", 01939 (BS_ELT)BS_word_count(set4), size5) ); 01940 01941 if ( size1 < size5 ) 01942 set1 = bs_Realloc(set1,size5,pool); 01943 01944 for ( i = 0; i < size5; ++i ) 01945 BS_word(set1,i) |= (~BS_word(set2,i) & BS_word(set3,i)) | 01946 BS_word(set4,i) | BS_word(set5,i); 01947 01948 return set1; 01949 } 01950 01951 01952 /* ==================================================================== 01953 * 01954 * BS_2_1_Minus_3_Or_4_And_5_And_6_And_R 01955 * 01956 * See interface description 01957 * 01958 * ==================================================================== 01959 */ 01960 01961 extern BS* 01962 BS_2_1_Minus_3_Or_4_And_5_And_6_And_R( 01963 BS *result, 01964 const BS *set1, 01965 const BS *set2, 01966 const BS *set3, 01967 const BS *set4, 01968 const BS *set5, 01969 const BS *set6, 01970 MEM_POOL *pool 01971 ) 01972 { 01973 BS_ELT i; 01974 BS_ELT rsize = BS_word_count(result); 01975 BS_ELT size3 = BS_word_count(set3); 01976 01977 Is_True( BS_word_count(set1) == size3, 01978 ("BS_2_1_Minus_3_Or_4_And_5_And_6_And_R: set1 size (%d) < set3 size (%d)", 01979 (BS_ELT)BS_word_count(set1), size3) ); 01980 Is_True( BS_word_count(set2) == size3, 01981 ("BS_2_1_Minus_3_Or_4_And_5_And_6_And_R: set2 size (%d) < set3 size (%d)", 01982 (BS_ELT)BS_word_count(set2), size3) ); 01983 Is_True( BS_word_count(set4) == size3, 01984 ("BS_2_1_Minus_3_Or_4_And_5_And_6_And_R: set4 size (%d) < set3 size (%d)", 01985 (BS_ELT)BS_word_count(set4), size3) ); 01986 Is_True( BS_word_count(set5) == size3, 01987 ("BS_2_1_Minus_3_Or_4_And_5_And_6_And_R: set5 size (%d) < set3 size (%d)", 01988 (BS_ELT)BS_word_count(set4), size3) ); 01989 Is_True( BS_word_count(set6) == size3, 01990 ("BS_2_1_Minus_3_Or_4_And_5_And_6_And_R: set6 size (%d) < set3 size (%d)", 01991 (BS_ELT)BS_word_count(set6), size3) ); 01992 01993 if ( rsize < size3 ) 01994 result = bs_Realloc(result,size3,pool); 01995 01996 for ( i = 0; i < size3; ++i ) 01997 BS_word(result,i) = ((~BS_word(set1,i) & BS_word(set2,i)) | 01998 BS_word(set3,i)) & 01999 BS_word(set4,i) & 02000 BS_word(set5,i) & 02001 BS_word(set6,i); 02002 02003 return result; 02004 } 02005 02006 /* ==================================================================== 02007 * 02008 * BS_2_1_Minus_3_Or_4_And_R 02009 * 02010 * See interface description 02011 * 02012 * ==================================================================== 02013 */ 02014 02015 extern BS* 02016 BS_2_1_Minus_3_Or_4_And_R( 02017 BS *result, 02018 const BS *set1, 02019 const BS *set2, 02020 const BS *set3, 02021 const BS *set4, 02022 MEM_POOL *pool 02023 ) 02024 { 02025 BS_ELT i; 02026 BS_ELT rsize = BS_word_count(result); 02027 BS_ELT size3 = BS_word_count(set3); 02028 02029 Is_True( BS_word_count(set1) == size3, 02030 ("BS_2_1_Minus_3_Or_4_And_R: set1 size (%d) < set3 size (%d)", 02031 (BS_ELT)BS_word_count(set1), size3) ); 02032 Is_True( BS_word_count(set2) == size3, 02033 ("BS_2_1_Minus_3_Or_4_And_R: set2 size (%d) < set3 size (%d)", 02034 (BS_ELT)BS_word_count(set2), size3) ); 02035 Is_True( BS_word_count(set4) == size3, 02036 ("BS_2_1_Minus_3_Or_4_And_R: set4 size (%d) < set3 size (%d)", 02037 (BS_ELT)BS_word_count(set4), size3) ); 02038 02039 if ( rsize < size3 ) 02040 result = bs_Realloc(result,size3,pool); 02041 02042 for ( i = 0; i < size3; ++i ) 02043 BS_word(result,i) = ((~BS_word(set1,i) & BS_word(set2,i)) | 02044 BS_word(set3,i)) & 02045 BS_word(set4,i); 02046 02047 return result; 02048 } 02049 02050 /* ==================================================================== 02051 * 02052 * BS_1_Not_2_Or_3_Minus_4_And_R 02053 * 02054 * See interface description 02055 * 02056 * ==================================================================== 02057 */ 02058 02059 extern BS* 02060 BS_1_Not_2_Or_3_Minus_4_And_R( 02061 BS *result, 02062 const BS *set1, 02063 const BS *set2, 02064 const BS *set3, 02065 const BS *set4, 02066 MEM_POOL *pool 02067 ) 02068 { 02069 BS_ELT i; 02070 BS_ELT rsize = BS_word_count(result); 02071 BS_ELT size2 = BS_word_count(set2); 02072 02073 Is_True( BS_word_count(set1) == size2, 02074 ("BS_1_Not_2_Or_3_Minus_4_And_R: set1 size (%d) < set2 size (%d)", 02075 (BS_ELT)BS_word_count(set1), size2) ); 02076 Is_True( BS_word_count(set3) == size2, 02077 ("BS_1_Not_2_Or_3_Minus_4_And_R: set3 size (%d) < set2 size (%d)", 02078 (BS_ELT)BS_word_count(set3), size2) ); 02079 Is_True( BS_word_count(set4) == size2, 02080 ("BS_1_Not_2_Or_3_Minus_4_And_R: set4 size (%d) < set2 size (%d)", 02081 (BS_ELT)BS_word_count(set4), size2) ); 02082 02083 if ( rsize < size2 ) 02084 result = bs_Realloc(result,size2,pool); 02085 02086 for ( i = 0; i < size2; ++i ) 02087 BS_word(result,i) = (~BS_word(set1,i) | BS_word(set2,i)) & 02088 (~BS_word(set3,i)) & 02089 BS_word(set4,i); 02090 return result; 02091 } 02092 02093 /* ==================================================================== 02094 * 02095 * BS_2_3_Or_1_Or_D 02096 * 02097 * set1 += (set2 OR set3) 02098 * set1 += (set2 + set3) 02099 * 02100 * ==================================================================== 02101 */ 02102 02103 extern BS* 02104 BS_2_3_Or_1_Or_D( 02105 BS *set1, 02106 const BS *set2, 02107 const BS *set3, 02108 MEM_POOL *pool ) 02109 { 02110 BS_ELT i; 02111 BS_ELT size1 = BS_word_count(set1); 02112 BS_ELT size2 = BS_word_count(set2); 02113 BS_ELT size3 = BS_word_count(set3); 02114 02115 Is_True( size2 == size3, 02116 ("BS_2_3_Or_1_Or_D: sizes not equal %d, %d", 02117 size2, size3) ); 02118 02119 if ( size1 < size2 ) 02120 set1 = bs_Realloc(set1,size2,pool); 02121 02122 for ( i = 0; i < size2; ++i ) 02123 BS_word(set1,i) |= (BS_word(set2,i) | BS_word(set3,i)); 02124 02125 return set1; 02126 } 02127 02128 /* ==================================================================== 02129 * 02130 * BS_1_2_Or_3_And_R 02131 * 02132 * See interface description 02133 * 02134 * ==================================================================== 02135 */ 02136 02137 extern BS* 02138 BS_1_2_Or_3_And_R( 02139 BS *result, 02140 const BS *set1, 02141 const BS *set2, 02142 const BS *set3, 02143 MEM_POOL *pool 02144 ) 02145 { 02146 BS_ELT i; 02147 BS_ELT rsize = BS_word_count(result); 02148 BS_ELT size1 = BS_word_count(set1); 02149 02150 Is_True( BS_word_count(set2) == size1, 02151 ("BS_1_2_Or_3_And_R: set2 size (%d) < set1 size (%d)", 02152 (BS_ELT)BS_word_count(set2), size1) ); 02153 Is_True( BS_word_count(set3) == size1, 02154 ("BS_1_2_Or_3_And_R: set3 size (%d) < set1 size (%d)", 02155 (BS_ELT)BS_word_count(set3), size1) ); 02156 02157 if ( rsize < size1 ) 02158 result = bs_Realloc(result,size1,pool); 02159 02160 for ( i = 0; i < size1; ++i ) 02161 BS_word(result,i) = (BS_word(set1,i) | BS_word(set2,i)) & 02162 BS_word(set3,i); 02163 02164 return result; 02165 } 02166 02167 /* ==================================================================== 02168 * 02169 * BS_2_3_And_1_Or_D 02170 * 02171 * See interface description 02172 * 02173 * ==================================================================== 02174 */ 02175 02176 extern BS* 02177 BS_2_3_And_1_Or_D( 02178 BS *set1, 02179 const BS *set2, 02180 const BS *set3, 02181 MEM_POOL *pool 02182 ) 02183 { 02184 BS_ELT i; 02185 BS_ELT size1 = BS_word_count(set1); 02186 BS_ELT size = MIN(BS_word_count(set2),BS_word_count(set3)); 02187 02188 if ( size1 < size ) 02189 set1 = bs_Realloc(set1,size,pool); 02190 02191 for ( i = 0; i < size; ++i ) 02192 BS_word(set1,i) |= BS_word(set2,i) & BS_word(set3,i); 02193 02194 return set1; 02195 } 02196 02197 /* ==================================================================== 02198 * 02199 * BS_3_Not_4_Or_2_And_1_Or_D 02200 * 02201 * See interface description 02202 * 02203 * ==================================================================== 02204 */ 02205 02206 extern BS* 02207 BS_3_Not_4_Or_2_And_1_Or_D( 02208 BS *set1, 02209 const BS *set2, 02210 const BS *set3, 02211 const BS *set4, 02212 MEM_POOL *pool 02213 ) 02214 { 02215 BS_ELT i; 02216 BS_ELT size1 = BS_word_count(set1); 02217 BS_ELT size2 = BS_word_count(set2); 02218 02219 Is_True( BS_word_count(set3) == size2, 02220 ("BS_3_Not_4_Or_2_And_1_Or_D: set3 size (%d) < set2 size (%d)", 02221 (BS_ELT)BS_word_count(set3), size2) ); 02222 Is_True( BS_word_count(set4) == size2, 02223 ("BS_3_Not_4_Or_2_And_1_Or_D: set4 size (%d) < set2 size (%d)", 02224 (BS_ELT)BS_word_count(set4), size2) ); 02225 02226 if ( size1 < size2 ) 02227 set1 = bs_Realloc(set1,size2,pool); 02228 02229 for ( i = 0; i < size2; ++i ) 02230 BS_word(set1,i) |= BS_word(set2,i) & 02231 (~BS_word(set3,i) | BS_word(set4,i)); 02232 02233 return set1; 02234 } 02235 02236 /* ==================================================================== 02237 * 02238 * BS_4_3_Minus_2_Not_Or_1_And_D 02239 * 02240 * See interface description 02241 * 02242 * ==================================================================== 02243 */ 02244 02245 extern BS* 02246 BS_4_3_Minus_2_Not_Or_1_And_D( 02247 BS *set1, 02248 const BS *set2, 02249 const BS *set3, 02250 const BS *set4, 02251 MEM_POOL *pool 02252 ) 02253 { 02254 BS_ELT i; 02255 BS_ELT size1 = BS_word_count(set1); 02256 BS_ELT size2 = BS_word_count(set2); 02257 02258 Is_True( BS_word_count(set3) == size2, 02259 ("BS_4_3_Minus_2_Not_Or_1_And_D: set3 size (%d) < set2 size (%d)", 02260 (BS_ELT)BS_word_count(set3), size2) ); 02261 Is_True( BS_word_count(set4) == size2, 02262 ("BS_4_3_Minus_2_Not_Or_1_And_D: set4 size (%d) < set2 size (%d)", 02263 (BS_ELT)BS_word_count(set4), size2) ); 02264 02265 if ( size1 < size2 ) 02266 set1 = bs_Realloc(set1,size2,pool); 02267 02268 for ( i = 0; i < size2; ++i ) 02269 BS_word(set1,i) &= ~BS_word(set2,i) | 02270 (BS_word(set4,i) & ~BS_word(set3,i)); 02271 02272 return set1; 02273 } 02274 02275 /* ==================================================================== 02276 * 02277 * BS_2_3_Minus_1_Or_D 02278 * 02279 * See interface description 02280 * 02281 * ==================================================================== 02282 */ 02283 02284 extern BS* 02285 BS_2_3_Minus_1_Or_D( 02286 BS *set1, 02287 const BS *set2, 02288 const BS *set3, 02289 MEM_POOL *pool 02290 ) 02291 { 02292 BS_ELT i; 02293 BS_ELT size1 = BS_word_count(set1); 02294 BS_ELT size2 = BS_word_count(set2); 02295 BS_ELT size3 = BS_word_count(set3); 02296 02297 Is_True( size2 == size3, 02298 ("BS_2_3_Minus_1_Or_D: sizes not equal %d, %d", 02299 size2, size3) ); 02300 02301 if ( size1 < size2 ) 02302 set1 = bs_Realloc(set1,size2,pool); 02303 02304 for ( i = 0; i < size2; ++i ) 02305 BS_word(set1,i) |= BS_word(set2,i) & ~BS_word(set3,i); 02306 02307 return set1; 02308 } 02309 02310 /* ==================================================================== 02311 * 02312 * BS_2_3_Minus_4_Minus_1_Or_D 02313 * 02314 * See interface description 02315 * 02316 * ==================================================================== 02317 */ 02318 02319 extern BS* 02320 BS_2_3_Minus_4_Minus_1_Or_D( 02321 BS *set1, 02322 const BS *set2, 02323 const BS *set3, 02324 const BS *set4, 02325 MEM_POOL *pool 02326 ) 02327 { 02328 BS_ELT i; 02329 BS_ELT size1 = BS_word_count(set1); 02330 BS_ELT size2 = BS_word_count(set2); 02331 BS_ELT size3 = BS_word_count(set3); 02332 BS_ELT size4 = BS_word_count(set4); 02333 02334 Is_True( size2 == size3 && size3 == size4, 02335 ("BS_2_3_Minus_4_Minus_1_Or_D: sizes not equal %d, %d, %d", 02336 size2, size3, size4) ); 02337 02338 if ( size1 < size2 ) 02339 set1 = bs_Realloc(set1,size2,pool); 02340 02341 for ( i = 0; i < size2; ++i ) 02342 BS_word(set1,i) |= BS_word(set2,i) & ~BS_word(set3,i) 02343 & ~BS_word(set4,i); 02344 02345 return set1; 02346 } 02347 02348 /* ==================================================================== 02349 * 02350 * BS_ContainsP 02351 * 02352 * See interface description 02353 * 02354 * ==================================================================== 02355 */ 02356 02357 extern BOOL 02358 BS_ContainsP( 02359 BS *set1, 02360 BS *set2 02361 ) 02362 { 02363 BS_ELT minsize; 02364 BS_ELT i; 02365 02366 if ( BS_word_count(set1) < BS_word_count(set2) ) 02367 minsize = BS_word_count(set1); 02368 else 02369 minsize = BS_word_count(set2); 02370 02371 /* Check common part. 02372 */ 02373 for ( i = 0; i < minsize; ++i ) { 02374 if ( BS_word(set1,i) != (BS_word(set1,i) | BS_word(set2,i)) ) 02375 return FALSE; 02376 } 02377 02378 /* Check excess in set2. 02379 */ 02380 for ( ; i < BS_word_count(set2); ++i ) { 02381 if ( BS_word(set2,i) != bs_ZEROS ) 02382 return FALSE; 02383 } 02384 02385 return TRUE; 02386 } 02387 02388 /* ==================================================================== 02389 * 02390 * BS_EmptyP 02391 * 02392 * See interface description 02393 * 02394 * ==================================================================== 02395 */ 02396 02397 extern BOOL 02398 BS_EmptyP( 02399 BS *set 02400 ) 02401 { 02402 BS_ELT i; 02403 02404 for ( i = 0; i < BS_word_count(set); ++i ) { 02405 if ( BS_word(set,i) != bs_ZEROS ) 02406 return FALSE; 02407 } 02408 02409 return TRUE; 02410 } 02411 02412 /* ==================================================================== 02413 * 02414 * BS_EqualP 02415 * 02416 * See interface description 02417 * 02418 * ==================================================================== 02419 */ 02420 02421 extern BOOL 02422 BS_EqualP( 02423 BS *set1, 02424 BS *set2 02425 ) 02426 { 02427 BS_ELT i; 02428 02429 /* Normalize so set1 is smaller: 02430 */ 02431 if ( BS_word_count(set1) > BS_word_count(set2) ) { 02432 BS *tmp = set1; 02433 set1 = set2; 02434 set2 = tmp; 02435 } 02436 02437 for ( i = 0; i < BS_word_count(set1); ++i ) { 02438 if ( BS_word(set1,i) != BS_word(set2,i) ) 02439 return FALSE; 02440 } 02441 02442 for ( ; i < BS_word_count(set2); ++i ) { 02443 if ( BS_word(set2,i) != bs_ZEROS ) 02444 return FALSE; 02445 } 02446 02447 return TRUE; 02448 } 02449 02450 /* ==================================================================== 02451 * 02452 * BS_IntersectsP 02453 * 02454 * See interface description 02455 * 02456 * ==================================================================== 02457 */ 02458 02459 extern BOOL 02460 BS_IntersectsP( 02461 BS *set1, 02462 BS *set2 02463 ) 02464 { 02465 BS_ELT minsize, i; 02466 02467 if ( BS_word_count(set1) < BS_word_count(set2) ) 02468 minsize = BS_word_count(set1); 02469 else 02470 minsize = BS_word_count(set2); 02471 02472 for ( i = 0; i < minsize; ++i ) { 02473 if ( (BS_word(set1,i) & BS_word(set2,i)) != bs_ZEROS ) 02474 return TRUE; 02475 } 02476 02477 return FALSE; 02478 } 02479 02480 /* ==================================================================== 02481 * 02482 * BS_MemberP 02483 * 02484 * See interface description 02485 * 02486 * ==================================================================== 02487 */ 02488 02489 extern BOOL 02490 BS_MemberP( 02491 BS *set, 02492 BS_ELT x 02493 ) 02494 { 02495 Is_True(x >= 0,("BS_Member called with negative element.")); 02496 02497 if ( bs_QBPW(x) >= BS_word_count(set) ) 02498 return FALSE; 02499 else 02500 return (BS_byte(set,bs_QBPB(x)) & (bs_ONE << bs_RBPB(x))) 02501 != bs_ZEROS; 02502 } 02503 02504 /* ==================================================================== 02505 * 02506 * BS_Intersection_MemberP 02507 * 02508 * See interface description 02509 * 02510 * ==================================================================== 02511 */ 02512 02513 extern BOOL 02514 BS_Intersection_MemberP( 02515 BS *set1, 02516 BS *set2, 02517 BS_ELT x 02518 ) 02519 { 02520 Is_True(x >= 0,("BS_Member called with negative element.")); 02521 02522 if ( bs_QBPW(x) >= BS_word_count(set1) 02523 || bs_QBPW(x) >= BS_word_count(set2) 02524 ) { 02525 return FALSE; 02526 } 02527 else { 02528 return ( BS_byte(set1,bs_QBPB(x)) 02529 & BS_byte(set2,bs_QBPB(x)) 02530 & (bs_ONE << bs_RBPB(x))) 02531 != bs_ZEROS; 02532 } 02533 } 02534 02535 /* ==================================================================== 02536 * 02537 * PrintRange 02538 * 02539 * Subroutine for BS_Print to print a range within the set. 02540 * 02541 * f - The file to print to 02542 * low - First elemnt of range 02543 * high - Last element of range 02544 * first - First range to be printed. (Reference argument) 02545 * 02546 * ==================================================================== 02547 */ 02548 02549 static void 02550 PrintRange( 02551 FILE *f, 02552 BS_ELT low, 02553 BS_ELT high, 02554 BOOL *first 02555 ) 02556 { 02557 if ( *first ) 02558 *first = FALSE; 02559 else 02560 fprintf(f,","); 02561 02562 if ( low == high ) 02563 fprintf(f,"%d",low); 02564 else 02565 fprintf(f,"%d-%d",low,high); 02566 } 02567 02568 /* ==================================================================== 02569 * 02570 * BS_Print 02571 * 02572 * See interface description 02573 * 02574 * ==================================================================== 02575 */ 02576 02577 extern void 02578 BS_Print( 02579 BS *set, 02580 FILE *f 02581 ) 02582 { 02583 BS_ELT range_first, last_elt, elt; 02584 BOOL first = TRUE; 02585 02586 if ( set == NULL ) { 02587 fprintf ( f, "<NULL>" ); 02588 return; 02589 } 02590 02591 fprintf(f,"{"); 02592 02593 elt = BS_Choose(set); 02594 if ( elt == BS_CHOOSE_FAILURE ) { 02595 fprintf(f,"}"); 02596 return; 02597 } 02598 range_first = elt; 02599 last_elt = range_first; 02600 02601 while ( (elt = BS_Choose_Next(set,elt)) != BS_CHOOSE_FAILURE ) { 02602 if ( elt != last_elt + 1 ) { 02603 /* renge_first .. last_elt was a range 02604 */ 02605 02606 PrintRange(f,range_first,last_elt,&first); 02607 range_first = elt; 02608 } 02609 last_elt = elt; 02610 } 02611 02612 PrintRange(f,range_first,last_elt,&first); 02613 fprintf(f,"}"); 02614 } 02615 02616 /* ==================================================================== 02617 * 02618 * BS_Print_dbg - same as BS_Print, but to stderr, to be called from 02619 * dbx 02620 * 02621 * ==================================================================== 02622 */ 02623 02624 extern void 02625 BS_Print_dbg(BS *set) 02626 { 02627 BS_Print(set, stderr); 02628 fprintf(stderr, "\n"); 02629 } 02630 02631 02632 /* ==================================================================== 02633 * 02634 * FBS_MemberP 02635 * 02636 * See interface description 02637 * 02638 * ==================================================================== 02639 */ 02640 02641 extern BOOL 02642 FBS_MemberP_Validate( 02643 BS *set, 02644 BS_ELT x 02645 ) 02646 { 02647 Is_True(x >= 0,("FBS_Member called with negative element.")); 02648 Is_True( bs_QBPW(x) < BS_word_count(set), ("FBS_Member called with out of bound element.")); 02649 return (BS_byte(set,bs_QBPB(x)) & (bs_ONE << bs_RBPB(x))) != bs_ZEROS; 02650 } 02651 02652 02653 /* ==================================================================== 02654 * 02655 * FBS_Union1D 02656 * 02657 * See interface description 02658 * 02659 * ==================================================================== 02660 */ 02661 02662 void 02663 FBS_Union1D_Validate( 02664 BS *set, 02665 BS_ELT x 02666 ) 02667 { 02668 BS_ELT minsize = bs_QBPW(x) + 1; 02669 Is_True(x >= 0,("FBS_Union1D called with negative element.")); 02670 Is_True( minsize <= BS_word_count(set), ("FBS_Union1D called with out of bound element.")); 02671 BS_byte(set,bs_QBPB(x)) |= bs_ONE << bs_RBPB(x); 02672 } 02673 02674 02675