bit_set.c

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

//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
//
// Created: MBN 06/13/89 -- Initial implementation
// Updated: MBN 09/31/89 -- Added conditional exception handling
// Updated: MBN 10/07/89 -- Changed operator[-~^&|] to allocate on stack
//                          Bit_Set::find(int) returns state of indicated bit
// Updated: MBN 10/12/89 -- Changed "current_position" to "curpos" and added
//                          the current_position() method for Iterator<Type>
// Updated: MBN 10/13/89 -- Changed from bit field to preprocessor bit macros
// Updated: LGO 11/09/89 -- Major changes to every method
// Updated: MBN 01/10/90 -- Fixed size-check bug in operator=
// Updated: MJF 03/12/90 -- Added group names to RAISE
// Updated: DLS 03/26/91 -- New lite version
// Updated: VDN 05/01/92 -- Copying by bytes only, to avoid out of bounds.
// Updated: JAM 08/12/92 -- removed DOS specifics, stdized #includes
// Updated: JAM 08/19/92 -- added static data def
//
// This file contains member and  friend function implementation  code for  the
// Bit Set class defined in the  Bit_Set.h header file.  Where  appropriate and
// possible,  interfaces to, and  us  of, existing system   functions  has been
// incorporated.  An overview of the structure of the CoolBit_Set class, along with
// a synopsis of each member and friend function, can be found in the Bit_Set.h
// header file.
//

#ifndef BIT_SET_H                               // If no class definition
#include <cool/Bit_Set.h>                       // Include class specification
#endif

#include <string.h>                             // For strcpy
#include <stdlib.h>                             // For exit()

#define BS_MAKE_POSITION(byte, offset) ((byte << 3) | offset)
#define BS_BYTE_COUNT(n) ((int) (n + 7) >> 3)   // Byte count from bit count

extern int bit_pos[];                           // Lowest/highest bit set masks
extern int bits_set[];                          // Number of bits set in mask
extern int powers_of_2_minus_1[];               // Number of contiguous bits


// alloc_size_s -- Allocation size for growth
int CoolBit_Set::alloc_size_s = BIT_SET_BLK_SZ;         // Set memory block size


// CoolBit_Set -- Simple constructor that takes no arguments and allocates no
//            storage
// Input:     None
// Output:    None

CoolBit_Set::CoolBit_Set () {
  this->data = NULL;                            // Zero initial memory
  this->size = 0;                               // Save number of bytes
  this->number_elements = 0;                    // Save number of elements
  this->curpos = INVALID;                       // Reset current position
  this->growth_ratio = 0.0;                     // Initialize growth ratio
}


// CoolBit_Set -- Constructor that takes an integer argument specifying an initial
//            number of elements for which storage must be allocated
// Input:     Initial number of elements
// Output:    None

CoolBit_Set::CoolBit_Set (int n) {
  int nbyte = BS_BYTE_COUNT(n);
  this->data = new unsigned char[nbyte];        // Allocate storage
  for (int i = 0; i < nbyte; i++) data[i] = 0;  // Initialize bits to zero
  this->size = nbyte;                           // Save number of bytes
  this->number_elements = 0;                    // Save number of elements
  this->curpos = INVALID;                       // Reset current position
  this->growth_ratio = 0.0;                     // Initialize growth ratio
}


// CoolBit_Set -- Constructor that takes a reference to another CoolBit_Set object and
//            duplicates its size and value
// Input:     Reference to Bit_Set object
// Output:    None

CoolBit_Set::CoolBit_Set (const CoolBit_Set& b) {
  this->data = new unsigned char[b.size];         // Allocate storage
  for (int i = 0; i < b.size; i++)                // For each byte in vector
    this->data[i] = b.data[i];                    // Copy value
  this->size = b.size;                            // Maintain number of bytes
  this->number_elements = b.number_elements;      // Save number of elements
  this->curpos = INVALID;                         // Reset current position
  this->growth_ratio = 0.0;                       // Initialize growth ratio
}


// ~CoolBit_Set -- Destructor for CoolBit_Set objects
// Input:      None
// Output:     None

CoolBit_Set::~CoolBit_Set () {
  delete [] this->data;                         // Free up memory allocated
}

// MACRO generate_next(operation=, excess_a=0, excess_b=0) {
//   int index, offset;
//   long pos = this->curpos;
//   if (pos == INVALID) {                      // If invalid current position
//     index = 0;                               // Start at first byte
//     offset = -1;                             // Start at zero'th bit
//   } else {
//     index = BS_BYTE_NUMBER(pos);             // Get current byte index
//     offset = BS_BYTE_OFFSET(pos);            // Get current bit offset
//   }
// 
// #if excess_a || excess_b  
//   int end = min(this->number_elements, b.number_elements);
// #else
//   int end = this->number_elements;
// #endif
//   register int value = (~powers_of_2_minus_1[offset+1]);
//   while(index < end) {
//     value &= this->data[index] operation;
//     if (value != 0) goto found;
//     value = -1;
//     index++;
//   }
// #if excess_a || excess_b  
//   if (index < (end = this->number_elements)) {
// #if excess_a
//     while(index < end) {
//       value &= this->data[index];
//       if (value != 0) goto found;
//       value = -1;
//       index++;
//     }
// #endif
//   } else {
// #if excess_b
//     end = b.number_elements;
//     while(index < end) {
//       value &= b.data[index];
//       if (value != 0) goto found;
//       value = -1;
//       index++;
//     }
// #endif
//   }
// #endif
//   this->curpos = INVALID;                    // Invalidate current position
//   return FALSE;                              // Return failure
//  found:
//   this->curpos = BS_MAKE_POSITION(index, bit_pos[value]); 
//   return TRUE;                               // Indicate success
// }


// next -- Increment the current position index
// Input:  None
// Output: Boolean TRUE/FALSE

Boolean CoolBit_Set::next () {
  //generate_next()                             // take out this 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 = this->number_elements;
  register int value = (~powers_of_2_minus_1[offset+1]);
  while(index < end) {
    value &= this->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);
}


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

Boolean CoolBit_Set::next_intersection (const CoolBit_Set& b) {
  if (this->number_elements > b.number_elements)
    this->number_elements = b.number_elements;
  //generate_next(&b.data[index],0,0)               // 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 = this->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++;
  }
  this->curpos = (-1);
  return (0);
 found:
  this->curpos = ((index << 3) | bit_pos[value]);
  return (1);
}


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

Boolean CoolBit_Set::next_union (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);
}

// next_difference -- Position at the zero-relative integer of the next bit in 
//                    the difference of two bit sets. That is all elements in
//                    "this" that are not in "b"
// Input:             Reference to Bit Set object
// Output:            TRUE/FALSE, current position updated

Boolean CoolBit_Set::next_difference (const CoolBit_Set& b) {
  //generate_next(&~b.data[index],1,0)      // take out macro expansion