core/sql/executor/ExBitMapTable.cpp

/**********************************************************************
// @@@ START COPYRIGHT @@@
//
// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License.  You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied.  See the License for the
// specific language governing permissions and limitations
// under the License.
//
// @@@ END COPYRIGHT @@@
**********************************************************************/
/* -*-C++-*-
******************************************************************************
*
* File:         ExBitMapTable.cpp
* RCS:          $Id
* Description:  ExBitMapTable class Implementation
* Created:      7/1/97
* Modified:     $Author
* Language:     C++
* Status:       $State
*
*
*
*
******************************************************************************
*/

// ExBitMapTable.cpp - Implementation for the ExBitMapTable class.
//

// Includes
//
#include "ex_ex.h"
#include "ExBitMapTable.h"

// ExBitMapTable::ExBitMapTable
//
// Constructs an ExBitMapTable.
//
// IN     : keySize  - The size of the key in bytes.
// IN     : dataSize - The size of a data row in bytes.
// IN     : memSize  - The amount of memory requested for the table.
// IN     : heap     - The memory allocator.
// EFFECTS: Constructs an ExBitMapTable object.
//
ExBitMapTable::ExBitMapTable(Int32 keySize, Int32 dataSize, Int32 countOffset,
			     Int32 memSize, CollHeap *heap) 
  : keySize_(keySize), dataSize_(dataSize), countOffset_(countOffset),
    memSize_(memSize), 

    // row layout:
    //  data: 
    //  key:  
    //  filler: so nextPtr could be aligned at 4
    //  next ptr: 
    // total length a multiple of 8 so row could be aligned.
    rowSize_(ROUND8(dataSize_ + ROUND4(keySize) + sizeof(char *))),
    heap_(heap), memory_(NULL), maximumNumberGroups_(0), 
    numberHashBuckets_(0), numberGroups_(0), returnGroup_(0),
    buckets_(0), groups_(0)
{

  
  // Attempt to allocate the requested memory. If that fails, try to at
  // least allocate enough memory for a few tuples. Otherwise, simply
  // return and the caller will check getMaximumNumberTuples and realize
  // that the table cannot store any tuples.
  //
  // Memory layout
  //
  // Hash Bucket Pointer Array - NumberHashBuckets
  //   [sizeof(void*)] - pointer to first group in bucket 0
  //   [sizeof(void*)] - pointer to first group in bucket 1
  //       . . .
  //   [sizeof(void*)] - pointer to first group in bucket NumberHashBuckets-1
  // Group Memory - NumberGroups
  //   [rowSize] - data, key, and next for group 0
  //   [rowSize] - data, key, and next for group 1
  //   [rowSize] - data, key, and next for group NumberGroups-1
  //
  const Int32 minimumMemorySize = 32 * (sizeof(char*) + rowSize_);
  memSize_ *= 2;
  while(!memory_ && (memSize_ >= 2 * minimumMemorySize)) {
    memSize_ /= 2;
    memory_ = (char *)heap_->allocateMemory((size_t) memSize_, FALSE);
  }
  if(!memory_) 
    {
      return;
    }

  // Save room for as many hash buckets as there are groups.
  //
  numberHashBuckets_ = ROUND2(memSize_ / (sizeof(char*) + rowSize_));


  // Compute the maximum number of groups that can be stored in the table. 
  //
  maximumNumberGroups_ = (memSize_ - sizeof(char*) * numberHashBuckets_)
    / rowSize_;

  // The buckets 
  // BitMap at memory_. To start there is only one BitMap.
  //
  buckets_ = (char**)memory_;
  groups_ = memory_ + sizeof(char*) * numberHashBuckets_;

  // Initialize the hash buckets.
  //
  for(Int32 i=0; i<numberHashBuckets_; i++)
    buckets_[i] = 0;
}

// ExBitMapTable::~ExBitMapTable
//
// Destructs an ExBitMapTable.
//
// EFFECTS: Destructs an ExBitMapTable object. Releases the memory
//          allocated in the constructor and sets the referencing
//          pointer to NULL.
//
ExBitMapTable::~ExBitMapTable() {
  if(memory_) heap_->deallocateMemory(memory_);
  memory_ = NULL;
}

// ExBitMapTable::reset
//
// Resets an ExBitMapTable
//
// EFFECTS: Resets all of the bitmaps and number of groups in the table.
//
void ExBitMapTable::reset() {
  // Initialize the hash buckets_.
  //
  for(Int32 i=0; i<numberHashBuckets_; i++)
    buckets_[i] = 0;

  // Reset the number of groups.
  //
  numberGroups_ = 0;

  // Also reset the return group.
  //
  returnGroup_ = 0;
}

// ExBitMapTable::findOrAdd
//
// Attemps to find an existing group in the table with the same key 
// as _key_. If a group cannot be found, attempts to add a new group
// to the table given sufficient memory resources. Sets the member data_
// to reference the found or added group, or NULL if no match.
//
// IN     : key   - Pointer to the key for incoming group.
// EFFECTS: A group may be added to the table. The member data_ points 
//          to the matching group. 
//
Int32 ExBitMapTable::findOrAdd(char *key) {
  unsigned char *ukey = (unsigned char*)key;

  // Compute the hash 
  //
  UInt32 hash = 0;
  Int32 i=0;
  for(; i<keySize_; i++)
    {
      hash ^= ukey[i];
      hash <<= 3;
    }
  hash = hash % numberHashBuckets_;

  // If the bucket is empty, try to add a new group.
  //
  char *row = buckets_[hash];
  if(!row)
    {
      // If no more groups can be added, return 0.
      //
      if(numberGroups_ >= maximumNumberGroups_) return 0;

      // Set data_ and the bucket to point to the new group and
      // increment the number of groups.
      //
      data_ = buckets_[hash] = getGroup(numberGroups_++);

      // Initialize the key
      //
      row = getKey(data_);
      for(i=0; i<keySize_; i++)
	row[i] = key[i];

      // Initialize the next pointer
      //
      *getNextPtr(data_) = 0;

      // Initialize any table aggregates.
      //
      initAggregates();
      applyAggregates();

      // Return -1 to indicate that a new group was added. The 
      // initialization is done externally.
      //
      return -1;
    }

  char *lastRow;
  while(row)
    {
      lastRow = row;

      // Test for matching keys.
      //
      Int32 match = 1;
      row = getKey(lastRow);
      for(i=0; match && i<keySize_; i++)
	if(row[i] != key[i]) match = 0;

      // If a matching row is found, set data_ to point to it and 
      // return 0 to indicate a match.
      //
      if(match)
	{
	  data_ = lastRow;

	  // Apply any table aggregates.
	  //
	  applyAggregates();

	  // Return 1 to indicate the group was matched/added.
	  //
	  return 1;
	}

      // Get the pointer to the next row in this hash chain.
      //
      row = *getNextPtr(lastRow);
    }

  // No matching groups were found so try to add another group.
  //
  // If no more groups can be added, return 0.
  //
  if(numberGroups_ >= maximumNumberGroups_) return 0;

  // Set data_ and the next row pointer to point to the new group and
  // increment the number of groups.
  //
  *getNextPtr(lastRow) = data_ = getGroup(numberGroups_++);

  // Initialize the key
  //
  row = getKey(data_);
  for(i=0; i<keySize_; i++)
    row[i] = key[i];

  // Initialize the next pointer
  //
  *getNextPtr(data_) = 0;

  // Initialize any table aggregates.
  //
  initAggregates();
  applyAggregates();

  // Return -1 to indicate that a new group was added. The 
  // initialization is done externally.
  //
  return -1;
}