bit_set.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 852 行 · 第 1/3 页

  
  int index, offset;
  long pos = this->curpos;
  if (pos == (-1)) {
    index = 0;
    offset = -1;
  } else {
    index = ((int) (pos >> 3));
    offset = ((int) (pos & 0x07));
  }
  int end = min(this->number_elements, b.number_elements);
  register int value = (~powers_of_2_minus_1[offset+1]);
  while(index < end) {
    value &= this->data[index] &~b.data[index];
    if (value != 0) goto found;
    value = -1;
    index++;
  }
  if (index < (end = this->number_elements)) {
    while(index < end) {
      value &= this->data[index];
      if (value != 0) goto found;
      value = -1;
      index++;
    }
  } else {
  }
  this->curpos = (-1);
  return (0);
 found:
  this->curpos = ((index << 3) | bit_pos[value]);
  return (1);
}

// next_xor -- Position at the zero-relative integer of the next bit in 
//             the XOR of two bit sets.
// Input:      Reference to Bit Set object
// Output:     TRUE/FALSE, current position updated

Boolean CoolBit_Set::next_xor (const CoolBit_Set& b) {
  //generate_next(^b.data[index];,1,1)     // take out macro expansion
  
  int index, offset;
  long pos = this->curpos;
  if (pos == (-1)) {
    index = 0;
    offset = -1;
  } else {
    index = ((int) (pos >> 3));
    offset = ((int) (pos & 0x07));
  }
  int end = min(this->number_elements, b.number_elements);
  register int value = (~powers_of_2_minus_1[offset+1]);
  while(index < end) {
    value &= this->data[index] ^b.data[index];;
    if (value != 0) goto found;
    value = -1;
    index++;
  }
  if (index < (end = this->number_elements)) {
    while(index < end) {
      value &= this->data[index];
      if (value != 0) goto found;
      value = -1;
      index++;
    }
  } else {
    end = b.number_elements;
    while(index < end) {
      value &= b.data[index];
      if (value != 0) goto found;
      value = -1;
      index++;
    }
  }
  this->curpos = (-1);
  return (0);
 found:
  this->curpos = ((index << 3) | bit_pos[value]);
  return (1);
}


// prev -- Decrement the current position index
// Input:  None
// Output: Boolean TRUE/FALSE

Boolean CoolBit_Set::prev () {
  int index, value, offset;
  long pos = this->curpos;
  if (pos == INVALID) {                         // If invalid current position
    index = this->number_elements;              // Start at last byte
    offset = BS_BITSPERBYTE;                    // Start at last bit bit
  } else {
    index = BS_BYTE_NUMBER(pos);                // Get current byte index
    offset = BS_BYTE_OFFSET(pos);               // Get current bit offset
  }
  value = (this->data[index] & 
           (~powers_of_2_minus_1[offset-1]));   //Reset low bits
  while (value == 0) {                          // If no more bits set
    if (index <0){                              // If we are at start of vector
      this->curpos = INVALID;                   // Invalidate current position
      return FALSE;                             // Return failure
    }
    value = this->data[--index];                // Else get next byte value
  }
    this->curpos = BS_MAKE_POSITION(index,bit_pos[value]);
  return TRUE;                                  // Indicate success
}


// find -- Set the current position to the nth bit
// Input:  Bit position desired (really, it's an integer value)
// Output: TRUE/FALSE

Boolean CoolBit_Set::find (int n) {
#if ERROR_CHECKING
  if (BS_BYTE_NUMBER(n) >= this->size) {        // If outside allocated range
    this->find_error (n);                       // Raise exception
    this->curpos = INVALID;                     // Invalidate current position
    return FALSE;                               // Return failure
  }
#endif
    this->curpos = n;
  return(((this->data[BS_BYTE_NUMBER(n)]) >> BS_BYTE_OFFSET(n)) & 0x01);
}


// put -- Put an element to the set
// Input: Bit position desired (really, it's an integer value)
// Output: TRUE/FALSE

Boolean CoolBit_Set::put (int n) {
  int nbytes = BS_BYTE_COUNT(n+1);              // Calculate byte index
  if (nbytes >= this->number_elements) {        // If bigger than largest
    if (nbytes >= this->size)                   // If outside allocated range
      this->grow (n);                           // Grow the bit vector
    this->number_elements = nbytes;
  }
  this->data[BS_BYTE_NUMBER(n)] |= (1 << BS_BYTE_OFFSET(n)); // Set proper bit
  this->curpos = n;
  return TRUE;                                  // Return success
}


// put -- Put a range of elements to the set
// Input: Start, end bit positions (really, they're just integer values)
// Output: TRUE/FALSE

Boolean CoolBit_Set::put (int start, int end) {
  if (start > end) {                            // If start is passed the end!
#if ERROR_CHECKING
    this->put_error (start,end);                // Raise exception
#endif
    this->curpos = INVALID;                     // Invalidate current position
    return FALSE;                               // Return failure
  }
  int last = BS_BYTE_COUNT(end);
  if (last >= this->number_elements) {
    if (last >= this->size)
      this->grow (end);                         // Grow the bit vector
    this->number_elements = last;
  }
  // This could be made MUCH faster by banging a byte at a time
  for (int i = start; i <= end; i++) // For each element in range
    this->data[BS_BYTE_NUMBER(i)] |= (1 << (BS_BYTE_OFFSET(i))); // Set bit
  this->curpos = start;
  return TRUE;                                  // Return success
}


// remove -- Remove element from set at current position
// Input:    None
// Output:   TRUE/FALSE

Boolean CoolBit_Set::remove () {
#if ERROR_CHECKING
  if (this->curpos == INVALID) {                // If current position INVALID
    this->remove_error ();                      // Raise exception
    return FALSE;                               // Return failure
  }
#endif
  int mask = ~(1 << BS_BYTE_OFFSET(this->curpos)); // Make bit mask
  this->data[BS_BYTE_NUMBER(this->curpos)] &= mask; // Turn off bit
  return TRUE;
}


// remove -- Remove the specified element from the set
// Input:    Element to be removed (really just an integer value)
// Output:   TRUE/FALSE

Boolean CoolBit_Set::remove (int n) {
  if (BS_BYTE_NUMBER(n) >= this->number_elements) // If out of range
    return FALSE;                                 // Return failure
  int mask = ~(1 << BS_BYTE_OFFSET(n));           // Make bit mask
  this->data[BS_BYTE_NUMBER(n)] &= mask;          // Turn off bit
  this->curpos = n;
  return TRUE;                                  // Return success
}


// remove -- Remove range of elements from the set
// Input:    Start, end bit positions (really, they're just integer values)
// Output:   TRUE/FALSE

Boolean CoolBit_Set::remove (int start, int end) {
#if ERROR_CHECKING
  if (start > end) {
    this->rem_start_end_error (start,end);      // Raise exception
    this->curpos = INVALID;                     // Invalidate current pos
    return FALSE;                               // Return failure
  }
#endif
    if (BS_BYTE_NUMBER(start) >= this->number_elements) {
    this->curpos = INVALID;                     // Invalidate current pos
    return FALSE;                               // Return failure
  }
  if (BS_BYTE_NUMBER(end) >= this->number_elements)
    end = this->number_elements * BS_BITSPERBYTE;
  for (int i = start; i <= end; i++)            // For each element in range
    this->data[BS_BYTE_NUMBER(i)] &= ~(1 << (BS_BYTE_OFFSET(i))); // Reset bit
  this->curpos = start;
  return TRUE;                                  // Return success
}


// search -- Determine if one Bit Set is a subset of another
// Input:    Reference to a Bit Set object
// Output:   TRUE/FALSE

Boolean CoolBit_Set::search (const CoolBit_Set& b) const {
  int len = min(this->number_elements, b.number_elements);
  int i;
  for (i = 0; i < len; i++)                       // For each byte in set
    if ((this->data[i] & b.data[i]) != b.data[i]) // If not as first set
      return FALSE;                               // Then not a subset
  if (i < b.number_elements)                      // If more elements in 2nd
    for (; i < b.number_elements; i++)            // Its still subset if all
      if (b.data[i] != 0)                         // other elemenst are 0
        return FALSE;                             // Nope! Return failure
  return TRUE;                                    // Subset; return success
}


// operator- -- Overload unary minus operator to return elements not in set
// Input:       None
// Output:      Bit Set object containing complement of this set

CoolBit_SetE CoolBit_Set::operator- () {
  CoolBit_Set temp (this->number_elements * BS_BITSPERBYTE);    // New bit set
  for (int i = 0; i < this->number_elements; i++) // For each byte in vector
    temp.data[i] = ~(this->data[i]);            // Copy complement of set
  temp.curpos = INVALID;                        // Reset current position
  temp.number_elements = this->number_elements; // Update number of elements
  CoolBit_SetE& result = (CoolBit_SetE&) temp;  // same physical object
  return result;                                // shallow swap on return
}


// MACRO generate_set_operator(a, b, op, excess=0) {
//   int a_size = BS_WORD_COUNT(a->number_elements);
//   int b_size = BS_WORD_COUNT(b.number_elements);
//   unsigned int* a_data = (unsigned int*) a->data;
//   unsigned int* b_data = (unsigned int*) b.data;
//   int min_size = min(a_size, b_size);
//   for (int i = 0; i < min_size; i++)
//     a_data[i] = a_data[i] op b_data[i];              // 
//   for (; i < b_size; i++)
//     a_data[i] = excess;                              // operate on excess b's
// }


#define generate_set_operator(a, b, op, excess)                               \
  int a_size = a->number_elements;                                            \
  int b_size = b.number_elements;                                             \
  unsigned char* a_data = a->data;                                            \
  unsigned char* b_data = b.data;                                             \
  int min_size = min(a_size, b_size);                                         \
  int i;                                                                      \
  for (i = 0; i < min_size; i++)                                              \
     a_data[i] = a_data[i] op b_data[i];        /*operate on common sets*/    \
  for (; i < b_size; i++)                                                     \
     a_data[i] = excess;                        /*operate on excess b's*/