Google Git
Sign in
apache / trafodion / refs/tags/2.3.0rc1 / . / core / sql / common / Collections.h
blob: a53e3d4a129de195a41c4f5fce634286b73dcd4e [file] [log] [blame]
/**********************************************************************
// @@@ 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 @@@
**********************************************************************/
#ifndef COLLECTIONS_H
#define COLLECTIONS_H
/* -*-C++-*-
******************************************************************************
*
* File: Collections.h
* Description: Collection type templates
* Created: 4/26/94
* Language: C++
*
*
******************************************************************************
*/
// -----------------------------------------------------------------------
#include <limits.h>
#include "BaseTypes.h"
#include <stdint.h>
/**
*** _m64_popcnt is an instruction-level intrinsic routine supported in the
*** IA64 compiler. It quickly counts the number of bits set in a 64-bit
*** register. Although we define the intrinsics prototype here, we should
*** replace this with an include to "builtin.h" once the intrinsic is
*** officially supported.
**/
// -----------------------------------------------------------------------
// File contents
// -----------------------------------------------------------------------
template <class T> class NACollection;
template <class T> class NASubCollection;
template <class T> class NASet;
template <class T> class NAList;
template <class T> class NAArray;
template <class T> class NASimpleArray;
template <class T> class NASubArray;
template <class K,class V> class NAHashDictionary;
template <class K,class V> class NAHashDictionaryIterator;
template <class K,class V> class NAKeyLookup;
// -----------------------------------------------------------------------
// Collection types implement collections of arbitrary class objects.
// The Noah code uses collection types to implement lists, sets, and
// other collections of classes. We intend the Noah code to be as
// independent as possible from the actual implementation of the
// collection type, although a complete independence is not always
// possible.
//
// Here are some points about how collection types are used:
//
// - Different collections, like SET, LIST, ARRAY, are defined in this
// file. Only if necessary, the methods for those collections are defined
// differently. For example, the entries() method will
// work for all the mentioned collection type templates(although for
// a set the name card() instead of entries() would be more appropriate).
// This makes switching from one collection template to another more
// easy. For example, one might detect that instead of a set one
// wants a list, if it becomes necessary to identify elements by
// position.
//
// - Collection type names are not given using the template syntax
// when they are defined in code outside of this file. Instead, a
// #define is used. This allows more changes in the implementation of
// collection types without changing all the places where collection
// types are defined(for example using the style of "generic.h").
//
// - In order to create a collection of an object of type T, the type
// T must provide the following:
// + a default constructor(sometimes it is necessary to create
// empty entries in a collection)
// + well-defined assignment semantics(copy constructor and
// assignment operator), since objects are copied into the collection
// (see below)
// + a comparison operator
// operator ==(const T &other) const
// for searching an object in a collection
//
// - Policy of ownership: the collection types defined here take ownership
// of all objects that are part of the collection. So, if a collection of
// objects of type X is defined and an object o of type X is inserted
// into that collection, then a copy of o is made and retained in the
// collection. If o is removed from the collection, the implementation
// of the collection is free to delete that copy of o immediately, at
// a later point in time, or never.
//
// In many cases this is not what a user of a collection wants, since
// it wastes space and time. Also, if an object o is part of several
// collections, having multiple copies of it in those collections
// would mean that one would have
// to change all of the copies when o needs to be modified. As a
// solution to this one can define a collection of pointers to X and
// add a pointer to object o to the collection. There is no special
// pointer-based collection, since this can be achieved by defining
// collections on the pointer data type.
//
// When creating the copy of the object to be inserted, the assignment
// operator is used, so a valid operator = and a valid copy constructor
// must be defined for the base type of the collection.
//
// - The SET, LIST, and ARRAY collections are based on an implementation
// that uses a variable-length array. When the array is created, the
// default constructor for all objects is called. However, users of a
// collection must always overwrite array entries explicitly before
// being able to use them. This is to avoid having uninitialized
// entries for datatypes with no explicit constructor.
//
// - The simplest collection type template is that of a set. A set collection
// assures that no two elements of the collection compare equal(as a
// consequence, the operator == must be defined on the base type of the
// set).
//
// - More complicated collections are lists. Neither sets, nor lists
// have a pre-set limit on the number of elements that they can
// contain. While sets avoid duplicate entries by using the == operator
// of the underlying base type, lists allow duplicate entries,
// since they use an index to identify an element.
//
// - To identify a list entry, an integral data type
// CollIndex is defined in this file. The convention is that a value
// of 0 identifies the first position in a collection.
//
// - In a list, entries are always numbered consecutively from 0 to n-1
// where n is the number of entries. If entries are inserted between
// existing elements or entries are deleted that are not at the end of
// the list, then the indexes of other list entries are modified such
// that the list remains contiguous with the first entry having index 0.
//
// - The array collection is intended mainly for performance-critical
// cases where a fast direct and random access through the index operator
// is needed(mostly for lookup tables with an integer key). Also,
// unlike a list, an entry in an array never changes its index. It is
// possible for an array to have "holes" meaning unused entries in
// between used ones.
//
// - The following methods are defined for all collections:
//
// + default constructor(create an empty collection with no limit for
// the number of elements)
//
// + copy constructor(make a new collection from an existing one)
//
// + a method "entries" to determine the number of entries in the
// set, array, or list
//
// + a method "insert" to insert an entry without specifying its position
//
// + a method "remove" to remove an element given by its value
// (all entries with that value ?are removed? if the collection contains
// duplicate values?
// For lists, "remove" removes the first matching element;
// "removeAll" removes all matching elements.)
// Note that collections of pointers to objects will compare as equal
// only if the pointers point to the same object, not if the pointers
// point to different objects that have the "same" value!
//
// + a method "clear" to remove all entries from the collection.
//
// + a(generally non-commutative) method "insert" that allows to insert
// the contents of one collection into another one(it is allowed to insert
// sets into lists, lists into arrays, etc.) without defined positioning
// of the inserted elements
//
// + a method "contains" that checks whether a certain entry is in the
// collection(this uses the == operator of the base type)
// Note that collections of pointers to objects will compare as equal
// only if the pointers point to the same object, not if the pointers
// point to different objects that have the "same" value!
//
// + a method "find" that finds and returns a given entry(using
// the == operator of the base type)
// Note that collections of pointers to objects will compare as equal
// only if the pointers point to the same object, not if the pointers
// point to different objects that have the "same" value!
//
// - The following methods are defined for the list type template:
//
// + index access operators(both as const and non-const versions,
// returning a value or an updatable reference of the object)
//
// + an "insertAt" method to insert an entry at a specified position
//
// + a "removeAt" method that removes an entry with a given index
//
// + a "removeAll" method that removes all matching elements
// (see additional notes above)
//
// + an "index" method to find the index of an element
//
// + "getFirst" and "getLast" methods to implement queues and
// stacks(FIFO and LIFO lists)
//
// - The array template has the following method in addition to the other
// collection templates:
//
// + a method "used" that indicates whether a particular index of the
// array is used or not.
//
// - Sometimes it is important to have very dense representations of sets
// and to be able to perform set operations(union, intersect, add/
// remove elements) very efficiently. Often, many subsets of a given
// set are created and it is important to deal with the subsets very
// efficiently.
//
// This file defines a collection type template designed for this
// special situation: a subset collection is defined on a particular
// instance of a collection(right now this is only used for array
// collections). A subset collection represents each element of the
// super-collection as a bit. The subset collection has a built-in array
// of enough bits to handle small to medium size super-collections.
//
// Set operations between subsets from the same super-collection can
// be done very fast by using bitwise AND and OR operators. Two subsets
// that don't reference the same super-collection are not comparable.
//
// Note that inconsistencies may arise when the super-collection changes
// while subsets are defined for it. With the array collection these
// conflicts are manageable by the user, since a subset merely
// identifies a subset of the index positions of an array, without
// making a statement about the contents of the array. Subsets on list,
// however, may require updates to the list, except replacement of list
// elements with another value and insertions at the end of the list.
//
// Subset collection types don't have union and intersect operators
// defined in the traditional way. This is because such operators
// typically require the creation of a temporary object. The same
// functionality can be achieved with union and intersect operators
// that work in-place, meaning that they modify a subset. This puts
// allocation of temporary objects into the hands of the user and
// makes problems with temporaries more visible.
//
// - Finally, a fast implementation of a hash lookup table is defined,
// using the Tools.h++ library implementation. The lookup table is
// a pointer-based collection. In order to create a hash lookup table
// for an object, a hash function must be defined for it that maps
// the object into a random character string.
//
// - For users who want to control space allocation themselves, special
// constructors for collection templates are provided. The collection
// templates allocate arrays of the collected objects from the heap.
// If the collection is constructed by passing in a pointer to a
// CollHeap object, then the virtual "allocateMemory" and "deallocateMemory"
// methods of the CollectionHeap object is used to allocate the arrays.
// Since that method is virtual, users can define their own classes,
// derived from CollHeap, that override the generic implementation. Note
// that collection classes do NOT have an overloaded "operator new".
// Users can do that for their own classes that are derived from
// collection classes(they will still have to use the constructor form
// that passes in a CollHeap object). A final note: users who can use
// standard allocation from the C runtime heap can ignore all this.
// -----------------------------------------------------------------------
// -----------------------------------------------------------------------
// define a data type for list indexes(the value 0 can be
// used to access the first element in an array or list)
// -----------------------------------------------------------------------
// this definition moved to BaseTypes.h:
// typedef UInt32 CollIndex;
// -----------------------------------------------------------------------
// some constants for internal use of values of CollIndex
// -----------------------------------------------------------------------
const CollIndex FIRST_COLL_INDEX = 0; // first element
const CollIndex NULL_COLL_INDEX = 111111111; // pointer to nothing
const CollIndex UNUSED_COLL_ENTRY = 111111112; // unused array entry
// -----------------------------------------------------------------------
// Limit the growth of a Collections class to MAX_COLL_INDEX elements.
// The bound provided by LONG_MAX ensures that an element can be
// indexed using a vraible of type long. This limit is imposed to
// prevent the proliferation of variables of type unsigned in the
// application code that uses these Collections classes. The C run
// time environments typically interpret a negative value that is
// assigned to an unsigned variable as an unsigned value.
// -----------------------------------------------------------------------
const NAUnsigned MAX_COLL_INDEX = MINOF(100000000,LONG_MAX);
// -----------------------------------------------------------------------
// defines for collection types(avoids hard-coding the template
// syntax in other modules)
// -----------------------------------------------------------------------
#define SET(Type) NASet<Type>
#define LIST(Type) NAList<Type>
#define ARRAY(Type) NAArray<Type>
#define SUBARRAY(Type) NASubArray<Type>
#define HASHDICTIONARY(Key,Value) NAHashDictionary<Key,Value>
#define CollIndexList LIST(CollIndex)
// -----------------------------------------------------------------------
// The generic collection template, base class of other collection types
// -----------------------------------------------------------------------
template <class T> class NACollection : public NABasicObject
{
friend class NASubCollection<T>;
public:
// return the number of entries in the collection
inline CollIndex entries() const { return entries_; }
inline NABoolean isEmpty() const { return(entries_ == 0); }
// return the allocated size
inline CollIndex getSize() const { return maxLength_; }
inline CollIndex getUsedLength() const {return usedLength_; }
//protected:
// default constructor(empty collection)
NACollection(CollIndex initLen = 0) : heap_(NULL)
{ allocate(initLen); }
// constructor for a collection with user-defined heap management
NACollection(CollHeap *heap, CollIndex initLen = 0) : heap_(heap)
{ allocate(initLen); }
// copy ctor
NACollection(const NACollection<T> &other, CollHeap *heap=0)
: heap_( (heap==NULL) ? other.heap_ : heap )
{ copy(other); }
// virtual destructor
virtual ~NACollection();
// copy another collection into this one
// NOTE: this method is called by a constructor and it
// assumes that the collection is in the deallocated state!!!
void copy(const NACollection<T> &other) ;
// assignment operator (deep copy instead of shallow one)
inline NACollection<T> & operator =(const NACollection<T> &other)
{
if ( this != &other) { deallocate(); copy(other); } // avoid copy-self!
return *this;
}
// delete entries from <entry> to usedLength_ in the collection.
void clearFrom( CollIndex entry );
// return entry ix(create entry, if it doesn't exist already)
T & rawEntry(CollIndex ix);
// overloaded operator [] to access elements of the collection
T & usedEntry(CollIndex ix)
{
#if defined(_DEBUG)
if((ix >= usedLength_) OR
(usages_[ix] == UNUSED_COLL_ENTRY))
ABORT("referencing an unused element of a collection");
#endif
return arr_[ix];
}
// the const version of usedEntry
const T & constEntry(CollIndex ix) const
{
#if defined(_DEBUG)
if((ix >= usedLength_) OR
(usages_[ix] == UNUSED_COLL_ENTRY))
{
ABORT("referencing an unused element of a collection");
}
#endif
return arr_[ix];
}
// get the usage info for an entry
inline CollIndex getUsage(CollIndex pos) const
{
if(pos < usedLength_)
return usages_[pos];
else
return UNUSED_COLL_ENTRY;
}
// find a particular usage in the array and return its position or
// NULL_COLL_INDEX
CollIndex findUsage(const CollIndex &toFind);
// return byte size of this collection
Lng32 getByteSize() const
{ return sizeof(*this) + (maxLength_ * (sizeof(T)+sizeof(CollIndex))); }
// Resize the arrays to a new size(return new size)
CollIndex resize(CollIndex newSize);
inline void setUsage(CollIndex pos, CollIndex newUsage)
{
if ((pos < usedLength_) AND
(usages_[pos] != UNUSED_COLL_ENTRY) AND
(newUsage != UNUSED_COLL_ENTRY))
usages_[pos] = newUsage;
}
// allocate the arrays(used in constructor, don't assume
// that the data members except "heap_" are initialized yet)
void allocate(CollIndex initLen);
//inline void deallocate()
virtual void deallocate()
{
// NOTE: dirty deallocate, no cleanup!!!
if ( heap_ == NABasicObject::systemHeapPtr() )
{
// default: use global ::operator delete()
if (arr_ != NULL) delete [] arr_;
if (usages_ != NULL) delete [] usages_;
}
else
{
// user-specified delete operator
// Note : this won't call the destructor of each arr_ element.
// after the compiler supports delete[] operator to be supprted,
// it should be changed to
//if (arr_) delete [] arr_;
//if (usages_) delete [] usages_;
if (arr_ != NULL) heap_->deallocateMemory(arr_);
if (usages_ != NULL) heap_->deallocateMemory(usages_);
}
arr_ = NULL;
usages_ = NULL;
}
inline void clear()
{
for (CollIndex i = FIRST_COLL_INDEX; i < usedLength_; i++)
usages_[i] = UNUSED_COLL_ENTRY;
entries_ = 0;
usedLength_ = 0;
}
inline CollIndex freePos() const
{
// is there space in the unused but allocated portion?
if (usedLength_ < maxLength_)
return usedLength_;
// now search the allocated portion for free entries
for (CollIndex i = FIRST_COLL_INDEX; i < usedLength_; i++)
{
if (usages_[i] == UNUSED_COLL_ENTRY)
return i;
}
// no free positions in the allocated part
return maxLength_;
}
inline void remove(CollIndex posToDelete)
{
if ((posToDelete < usedLength_) &&
(usages_[posToDelete] != UNUSED_COLL_ENTRY))
{
// set the usage field to indicate an unused entry
usages_[posToDelete] = UNUSED_COLL_ENTRY;
entries_--;
// change the usedLength_, if we deleted the last entry
if (posToDelete == usedLength_ - 1)
{
while (usedLength_ > 0 AND
usages_[usedLength_ - 1] == UNUSED_COLL_ENTRY)
usedLength_--;
// resize, if we gained back a substantial part of the array
if (maxLength_ > 10 AND
usedLength_ < maxLength_/4)
resize(usedLength_);
}
}
return;
}
void insert(CollIndex posToInsert,
const T &newElement,
CollIndex newUsage = NULL_COLL_INDEX);
inline CollIndex find(const T &toFind) const
{
for (CollIndex i = FIRST_COLL_INDEX; i < usedLength_; i++)
{
if ((usages_[i] != UNUSED_COLL_ENTRY) &&
(arr_[i] == toFind))
return i;
}
// return a "not found" indicator
return NULL_COLL_INDEX;
}
inline void setHeap(CollHeap *heap)
{
heap_ = heap;
}
private:
CollIndex maxLength_; // how many array entries are allocated?
CollIndex usedLength_; // how many entries of adm_ are initialized?
CollIndex entries_; // caches number of entries
T *arr_; // array for the members of the collection
CollIndex *usages_; // array for administrative information
CollHeap *heap_; // user-defined heap object or NULL
}; // NACollection
// ***********************************************************************
// NASubCollection: A subset of a NACollection
//
// A NASubCollection is an array of bits. The array contains 512 bits
// initially but it grows from and shrinks to this inital allocation
// on demand. Each bit is addressed using its bit position as
// illustrated in the figure below:
//
// |...............|...............|...............|...............|......
// 0 32 64 96 128
//
// The array is implemented in units of 32 bit "words". Bits 0 through
// 31 are in word 0, bits 32 through 63 are in word 1, and so on.
//
// The ON/OFF state of each bit indicates the presence/absence
// respectively of corresponding elements in the NACollection.
//
// An NASubCollection object with no superset can also be used as a
// bit vector.
//
// ***********************************************************************
const Int32 BuiltinSubsetWords = 8; // size of the built-in array
typedef uint64_t DblWordAsBits;
typedef ULng32 WordAsBits;
// typedef change will affect clearFast, nextUsedFast and addElementFast.
const UInt32 BitsPerWord = 32;
const UInt32 LogBitsPerWord = 5; // 0...31 can be expressed in 5 bits
const UInt32 LogBytesPerWord = 2;
const WordAsBits BitPortion = 0x1F; // the 5 least significant bits
const WordAsBits AllBitsSet = 0xFFFFFFFF;
const WordAsBits SingleBitArray[BitsPerWord] = {
0x80000000, 0x40000000, 0x20000000, 0x10000000,
0x08000000, 0x04000000, 0x02000000, 0x01000000,
0x00800000, 0x00400000, 0x00200000, 0x00100000,
0x00080000, 0x00040000, 0x00020000, 0x00010000,
0x00008000, 0x00004000, 0x00002000, 0x00001000,
0x00000800, 0x00000400, 0x00000200, 0x00000100,
0x00000080, 0x00000040, 0x00000020, 0x00000010,
0x00000008, 0x00000004, 0x00000002, 0x00000001
};
const Lng32 bitsSet[] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
// ***********************************************************************
//
// firstOne
//
// Returns the ordinal position of the first bit set in the unsigned long
// passed as an argument.
//
// NOTE: It is assumed (for performance reasons) that there is at least
// one bit set in the argument.
//
// ***********************************************************************
inline Lng32 firstOne( ULng32 x )
{
#define FIRSTHALFWORDBITS 0xFFFF0000
#define FIRSTQUARTERWORDBITS 0xFF000000
#define FIRSTEIGHTHWORDBITS 0xF0000000
#define FIRSTSIXTEENTHWORDBITS 0xC0000000
#define THIRDSIXTEENTHWORDBITS 0x0C000000
#define THIRDEIGHTHWORDBITS 0x00F00000
#define FIFTHSIXTEENTHWORDBITS 0x00C00000
#define SEVENTHSIXTEENTHWORDBITS 0x000C0000
#define THIRDQUARTERWORDBITS 0x0000FF00
#define FIFTHEIGHTHWORDBITS 0x0000F000
#define NINTHSIXTEENTHWORDBITS 0x0000C000
#define ELEVENTHSIXTEENTHWORDBITS 0x00000C00
#define SEVENTHEIGHTHWORDBITS 0x000000F0
#define THIRTEENTHSIXTEENTHWORDBITS 0x000000C0
#define FIFTEENTHSIXTEENTHWORDBITS 0x0000000C
#define BIT31 0x80000000
#define BIT29 0x20000000
#define BIT27 0x08000000
#define BIT25 0x02000000
#define BIT23 0x00800000
#define BIT21 0x00200000
#define BIT19 0x00080000
#define BIT17 0x00020000
#define BIT15 0x00008000
#define BIT13 0x00002000
#define BIT11 0x00000800
#define BIT9 0x00000200
#define BIT7 0x00000080
#define BIT5 0x00000020
#define BIT3 0x00000008
#define BIT1 0x00000002
if (x & FIRSTHALFWORDBITS)
{
if (x & FIRSTQUARTERWORDBITS)
{
if (x & FIRSTEIGHTHWORDBITS)
{
if (x & FIRSTSIXTEENTHWORDBITS)
{
if (x & BIT31)
return( 0 );
else // Bit 30.
return( 1 );
}
else // Second sixteenth bits.
{
if (x & BIT29)
return( 2 );
else // Bit 28.
return( 3 );
}
}
else // Second eighth bits.
{
if (x & THIRDSIXTEENTHWORDBITS)
{
if (x & BIT27)
return( 4 );
else // Bit 26.
return( 5 );
}
else // Fourth sixteenth bits.
{
if (x & BIT25)
return( 6 );
else // Bit 24.
return( 7 );
}
}
}
else // Second quarter.
{
if (x & THIRDEIGHTHWORDBITS)
{
if (x & FIFTHSIXTEENTHWORDBITS)
{
if (x & BIT23)
return( 8 );
else // Bit 22
return( 9 );
}
else // Second sixteenth bits.
{
if (x & BIT21)
return( 10 );
else // Bit 20.
return( 11 );
}
}
else // Fourth eighth bits.
{
if (x & SEVENTHSIXTEENTHWORDBITS)
{
if (x & BIT19)
return( 12 );
else // Bit 18.
return( 13 );
}
else // Eighth sixteenth bits.
{
if (x & BIT17)
return( 14 );
else // Bit 16.
return( 15 );
}
}
}
}
else // Second half
{
if (x & THIRDQUARTERWORDBITS)
{
if (x & FIFTHEIGHTHWORDBITS)
{
if (x & NINTHSIXTEENTHWORDBITS)
{
if (x & BIT15)
return( 16 );
else // Bit 14.
return( 17 );
}
else // Tenth sixteenth bits.
{
if (x & BIT13)
return( 18 );
else // Bit 12.
return( 19 );
}
}
else // Sixth eighth bits.
{
if (x & ELEVENTHSIXTEENTHWORDBITS)
{
if (x & BIT11)
return( 20 );
else // Bit 10.
return( 21 );
}
else // Twelveth sixteenth bits.
{
if (x & BIT9)
return( 22 );
else // Bit 8.
return( 23 );
}
}
}
else // Fourth quarter.
{
if (x & SEVENTHEIGHTHWORDBITS)
{
if (x & THIRTEENTHSIXTEENTHWORDBITS)
{
if (x & BIT7)
return( 24 );
else // Bit 6.
return( 25 );
}
else // Fourteenth sixteenth bits.
{
if (x & BIT5)
return( 26 );
else // Bit 4.
return( 27 );
}
}
else // Eighth eighth bits.
{
if (x & FIFTEENTHSIXTEENTHWORDBITS)
{
if (x & BIT3)
return( 28 );
else // Bit 2.
return( 29 );
}
else // Sixteenth sixteenth bits.
{
if (x & BIT1)
return( 30 );
else // Bit 0.
return( 31 );
}
}
}
}
}
// ***********************************************************************
//
// lastOne
//
// Returns the ordinal position of the last bit set in the unsigned long
// passed as an argument.
//
// NOTE: It is assumed (for performance reasons) that there is at least
// one bit set in the argument.
//
// NOTE2: If this routine ever gets extensively used, replace with call
// to compiler intrinsic _m64_popcnt - much *MUCH* faster.
//
// ***********************************************************************
inline Lng32 lastOne( ULng32 x )
{
#define LASTHALFWORDBITS 0x0000FFFF
#define LASTQUARTERWORDBITS 0x000000FF
#define LASTEIGHTHWORDBITS 0x0000000F
#define LASTSIXTEENTHWORDBITS 0x00000003
#define FOURTEENTHSIXTEENTHWORDBITS 0x00000030
#define SIXTHEIGHTHWORDBITS 0x00000F00
#define TWELVETHSIXTEENTHWORDBITS 0x00000300
#define TENTHSIXTEENTHWORDBITS 0x00003000
#define SECONDQUARTERWORDBITS 0x00FF0000
#define FOURTHEIGHTHWORDBITS 0x000F0000
#define EIGHTHSIXTEENTHWORDBITS 0x00030000
#define SIXTHSIXTEENTHWORDBITS 0x00300000
#define SECONDEIGHTHWORDBITS 0x0F000000
#define FOURTHSIXTEENTHWORDBITS 0x03000000
#define SECONDSIXTEENTHWORDBITS 0x30000000
#define BIT30 0x40000000
#define BIT28 0x10000000
#define BIT26 0x04000000
#define BIT24 0x01000000
#define BIT22 0x00400000
#define BIT20 0x00100000
#define BIT18 0x00040000
#define BIT16 0x00010000
#define BIT14 0x00004000
#define BIT12 0x00001000
#define BIT10 0x00000400
#define BIT8 0x00000100
#define BIT6 0x00000040
#define BIT4 0x00000010
#define BIT2 0x00000004
#define BIT0 0x00000001
if (x & LASTHALFWORDBITS)
{
if (x & LASTQUARTERWORDBITS)
{
if (x & LASTEIGHTHWORDBITS)
{
if (x & LASTSIXTEENTHWORDBITS)
{
if (x & BIT0)
return( 0 );
else
return( 1 ); // Bit 1.
}
else // Fifteenth sixteenth bits.
{
if (x & BIT2)
return( 2 );
else // Bit 3.
return( 3 );
}
}
else // Seventh eighth bits.
{
if (x & FOURTEENTHSIXTEENTHWORDBITS)
{
if (x & BIT4)
return( 4 );
else
return( 5 ); // Bit 5.
}
else // Thirteenth sixteenth bits.
{
if (x & BIT6)
return( 6 );
else // Bit 7.
return( 7 );
}
}
}
else // Third quarter.
{
if (x & SIXTHEIGHTHWORDBITS)
{
if (x & TWELVETHSIXTEENTHWORDBITS)
{
if (x & BIT8)
return( 8 );
else // Bit 9
return( 9 );
}
else // Eleventh sixteenth bits.
{
if (x & BIT10)
return( 10 );
else // Bit 11.
return( 11 );
}
}
else // Fifth eighth bits.
{
if (x & TENTHSIXTEENTHWORDBITS)
{
if (x & BIT12)
return( 12 );
else // Bit 13.
return( 13 );
}
else // Eighth sixteenth bits.
{
if (x & BIT14)
return( 14 );
else // Bit 15.
return( 15 );
}
}
}
}
else // First half
{
if (x & SECONDQUARTERWORDBITS)
{
if (x & FOURTHEIGHTHWORDBITS)
{
if (x & EIGHTHSIXTEENTHWORDBITS)
{
if (x & BIT16)
return( 16 );
else // Bit 17.
return( 17 );
}
else // Seventh sixteenth bits.
{
if (x & BIT18)
return( 18 );
else // Bit 19.
return( 19 );
}
}
else // Third eighth bits.
{
if (x & SIXTHSIXTEENTHWORDBITS)
{
if (x & BIT20)
return( 20 );
else // Bit 10.
return( 21 );
}
else // Fifth sixteenth bits.
{
if (x & BIT22)
return( 22 );
else // Bit 23.
return( 23 );
}
}
}
else // First quarter.
{
if (x & SECONDEIGHTHWORDBITS)
{
if (x & FOURTHSIXTEENTHWORDBITS)
{
if (x & BIT24)
return( 24 );
else // Bit 25.
return( 25 );
}
else // Third sixteenth bits.
{
if (x & BIT26)
return( 26 );
else // Bit 27.
return( 27 );
}
}
else // First eighth bits.
{
if (x & SECONDSIXTEENTHWORDBITS)
{
if (x & BIT28)
return( 28 );
else // Bit 29.
return( 29 );
}
else // First sixteenth bits.
{
if (x & BIT30)
return( 30 );
else // Bit 31.
return( 31 );
}
}
}
}
}
// ***********************************************************************
//
// ones
//
// Returns the number of bits set in the unsigned long passed as an
// argument.
//
// ***********************************************************************
inline Lng32 ones( ULng32 x )
{
unsigned char * px = (unsigned char *) &x;
return( bitsSet[ px[ 0 ] ]
+
bitsSet[ px[ 1 ] ]
+
bitsSet[ px[ 2 ] ]
+
bitsSet[ px[ 3 ] ]
);
}
template <class T> class NASubCollection : public NABasicObject
{
// protected: doesn't work for NT nor C89
public:
// constructor
NASubCollection(NACollection<T> *superset, CollHeap * heap=0);
// copy ctor and destructor
NASubCollection(const NASubCollection<T> &other, CollHeap * heap=0);
virtual ~NASubCollection();
// set heap after constructor has been called but before object is used
void setHeap(CollHeap *heap);
inline CollIndex resize( CollIndex newSize )
{
if (newSize > maxLength_)
{
CollIndex i = wordSize_ - 1;
WordAsBits * newBits;
WordAsBits * pBits = &pBits_[ i ];
maxLength_ = newSize << 1;
if (heap_)
newBits = new (heap_) WordAsBits[ maxLength_ ];
else
newBits = new WordAsBits[ maxLength_ ];
newBits = &newBits[ i ];
do
{
*newBits-- = *pBits--;
}
while (--i);
*newBits = *pBits;
for (i = wordSize_; i < maxLength_; i++)
newBits[ i ] = 0x0;
if (!builtin_)
deallocateBits();
else
builtin_ = FALSE;
pBits_ = newBits;
wordSize_ = newSize;
}
else
{
CollIndex i = wordSize_ - newSize;
if ((Lng32) i > 0)
{
WordAsBits * pBits = &pBits_[ newSize ];
do
{
*pBits++ = 0x0;
}
while (--i);
}
wordSize_ = newSize;
if (wordSize_ == 0)
entries_ = 0;
}
return( wordSize_ * BitsPerWord );
}
CollIndex getWordSize () const { return( wordSize_ ); }
CollIndex getLastStaleBit() const { return( lastStaleBit_ ); }
inline void extendWordSize( CollIndex minWordSize )
{
// resize the array
resize( minWordSize );
}
inline void clear()
{
CollIndex i = wordSize_;
if (i && entries_)
{
WordAsBits * pBits = pBits_;
do
{
*pBits++ = 0x0;
}
while (--i);
}
entries_ = 0;
lastStaleBit_ = 0;
}
// Fast clear if bit 1 entries are probably in the first few words.
inline void clearFast();
// quick check whether the collection is empty
inline NABoolean isEmpty() const { return( entries_ == 0 ); }
// word() performs a bounds check.
inline WordAsBits & word( CollIndex i )
{
assert(i < wordSize_);
return( pBits_[ i ] );
}
// word() const performs a bounds check.
inline WordAsBits word( CollIndex i ) const
{
assert(i < wordSize_);
return( pBits_[ i ] );
}
// ---------------------------------------------------------------------
// wordNo() : Given a bit position, it returns an index to the
// word in which the bit is contained
// For bits 0 through 31 returns 0
// 32 63 1
// 64 95 2 ... and so on
// It is equivalent to(b / 32), where b is the bit position.
// ---------------------------------------------------------------------
inline CollIndex wordNo(CollIndex x) const { return x >> LogBitsPerWord; }
// ---------------------------------------------------------------------
// bitNo() : Given a bit position, it returns the position of the
// bit within a 32 bit word
// It is equivalent to(b mod 32), where b is the bit position
// ---------------------------------------------------------------------
inline CollIndex bitNo(CollIndex x) const { return x LAND BitPortion; }
// ---------------------------------------------------------------------
// entries() : Returns the number of entries in the subcollection.
// ---------------------------------------------------------------------
inline CollIndex entries() const { return( entries_ ); }
// ---------------------------------------------------------------------
// testBit() : Given a bit position, check whether the bit is set
// in the given position in the NASubCollection.
// ---------------------------------------------------------------------
inline NABoolean testBit( CollIndex b ) const
{
CollIndex wn = wordNo( b );
if (wn >= wordSize_)
{
// this bit surely isn't part of the subset (although we can't
// return an error, since the superset may have grown beyond the
// allocated limit of the subset)
return( FALSE );
}
else
{
// NOTE: for performance reasons we return arbitrary numbers for TRUE
return( (NABoolean) (pBits_[ wn ] LAND SingleBitArray[ bitNo( b ) ]) );
}
}
// ---------------------------------------------------------------------
// access a particular element of the superset, specified by the index
// ---------------------------------------------------------------------
const T & element(CollIndex e) const
{ assert(testBit(e)); return superset_->constEntry(e); }
// ---------------------------------------------------------------------
// subset() : Check whether another set is a subset of this one
// ---------------------------------------------------------------------
NABoolean contains(const NASubCollection<T> & other) const;
// ---------------------------------------------------------------------
// prevUsed() : Given a starting bit position, find the previous bit that
// is set.
// Returns: TRUE if a bit that is set is found; decrements start
// FALSE if all bits < start are reset; start is undefined
//
// e.g. in a for-loop: for(CollIndex i = lastStaleBit; prevUsed(i); i--) ...
// ---------------------------------------------------------------------
inline CollIndex prevUsed(CollIndex start) const;
CollIndex prevUsedSlow(CollIndex start) const;
// Fast path when prevUsed is probably in the first two words.
inline CollIndex prevUsedFast(CollIndex start) const;
// ---------------------------------------------------------------------
// nextUsed() : Given a starting bit position, find the next bit that
// is set.
// Returns: TRUE if a bit that is set is found; advances start
// FALSE if all bits > start are reset; start is undefined
//
// e.g. in a for-loop: for(CollIndex i = 0; nextUsed(i); i++) ...
// ---------------------------------------------------------------------
inline NABoolean nextUsed( CollIndex & start ) const
{
CollIndex limit = wordSize_ << LogBitsPerWord;
if (start >= limit || entries_ == 0)
return( FALSE );
else
{
CollIndex startOffset = bitNo( start );
CollIndex firstDWord = pBits_[ wordNo( start ) ]
&
((~0u) >> startOffset);
if (firstDWord)
{
start = start + firstOne( firstDWord ) - startOffset;
return( TRUE );
}
else
{
start = start + (BitsPerWord - startOffset);
CollIndex dWordsRemaining = (limit - start) >> LogBitsPerWord;
if (dWordsRemaining == 0)
return( FALSE );
WordAsBits * pBits = &pBits_[ wordNo( start ) - 1 ];
do
{
pBits++;
}
while (--dWordsRemaining && !*pBits);
start = ((((char *) pBits) - ((char *) pBits_)
) >> LogBytesPerWord
) << LogBitsPerWord;
if (*pBits)
{
start = start + firstOne( *pBits );
return( TRUE );
}
else
{
start = limit;
return( FALSE );
}
}
}
}
// Fast path when nextUsed is probably in the first two words.
inline NABoolean nextUsedFast(CollIndex &start) const;
// ---------------------------------------------------------------------
// lastUsed() : Find the last bit that is set.
// Returns: TRUE if a bit that is set is found; sets lastBit
// FALSE if no bits are set; no change to lastBit.
//
// e.g. in an if:
// CollIndex lastBit = 0;
// if (lastUsed(lastBit))
// {
// ... ok to make use of lastBit...
// };
// ---------------------------------------------------------------------
NABoolean lastUsed(CollIndex &lastBit) const;
NABoolean operator ==(const NASubCollection<T> & other) const;
inline NASubCollection<T> & operator = (const NASubCollection<T> & other)
{
if (this != &other) // avoid copy-self!
{
CollIndex i;
WordAsBits * pBits;
WordAsBits * pOtherBits = other.pBits_;
entries_ = other.entries_;
superset_ = other.superset_;
lastStaleBit_ = other.lastStaleBit_;
if (other.wordSize_ > maxLength_)
{
maxLength_ = other.wordSize_;
wordSize_ = maxLength_;
if (!builtin_)
deallocateBits();
if (wordSize_ > BuiltinSubsetWords)
{
pBits_ = allocateBits( wordSize_ );
builtin_ = FALSE;
}
else
{
pBits_ = (WordAsBits *)(&sbits_[ 0 ]);
builtin_ = TRUE;
}
pBits = pBits_;
i = wordSize_;
if (i)
{
do
{
*pBits++ = *pOtherBits++;
}
while (--i);
}
}
else
{
i = other.wordSize_;
//If maxLength_ is greater than the other.wordSize_, it implies that
//entries are on the builtin array. In this case we cannot assume that
//pBits_ is pointing to its sbits_. Because structures like LIST(ValueIdSet)
//cannot guarantee that each of its ValueIdSet is properly initialized.
//In the future when we have the use of overloaded new[] we can change
//NACollection::allocate to have each member properly initialized.
//CR#10-011003-6224
if(builtin_) //sometimes we come here for builtin_ false.
pBits_ = (WordAsBits*)(&sbits_[ 0 ]);
pBits = pBits_;
if (i)
{
do
{
*pBits++ = *pOtherBits++;
}
while (--i);
}
i = wordSize_ - other.wordSize_;
if ((Lng32) i > 0)
{
do
{
*pBits++ = 0x0;
}
while (--i);
}
wordSize_ = other.wordSize_;
}
}
return( *this );
}
// ---------------------------------------------------------------------
// Set-oriented operators on subcollections.
// ---------------------------------------------------------------------
NASubCollection<T> & addSet(const NASubCollection<T> & other);
NASubCollection<T> & intersectSet(const NASubCollection<T> & other);
NASubCollection<T> & subtractSet(const NASubCollection<T> & other);
inline NASubCollection<T> & addElement( CollIndex elem )
{
CollIndex wordNumber = wordNo( elem );
assert( superset_ == NULL
OR
(superset_->getUsage( elem ) != UNUSED_COLL_ENTRY)
);
if ( wordNumber >= wordSize_ )
{
extendWordSize( wordNumber + 1 );
pBits_[ wordNumber ] |= SingleBitArray[ bitNo( elem ) ];
entries_++;
}
else
{
WordAsBits originalWord = pBits_[ wordNumber ];
if (originalWord != (pBits_[ wordNumber ] |= SingleBitArray[ bitNo( elem ) ]))
entries_++;
}
// Record the last bit ever set.
if (elem > lastStaleBit_)
lastStaleBit_ = elem;
return( *this );
}
// Fast path when elem is probably less than 64.
inline NASubCollection<T> & addElementFast(CollIndex elem);
inline NASubCollection<T> & subtractElement( CollIndex elem )
{
CollIndex wordNumber = wordNo( elem );
if (wordNumber < wordSize_)
{
WordAsBits originalWord = pBits_[ wordNumber ];
if (originalWord != (pBits_[ wordNumber ] &= LNOT SingleBitArray[ bitNo( elem ) ]))
entries_--;
}
return( *this );
}
NASubCollection<T> & complement();
// ---------------------------------------------------------------------
// Overloaded variants of some of the above.
// ---------------------------------------------------------------------
inline NASubCollection<T> & operator +=(const NASubCollection<T> & other)
{ return addSet(other); }
inline NASubCollection<T> & operator -=(const NASubCollection<T> & other)
{ return subtractSet(other); }
inline NASubCollection<T> & operator +=(CollIndex elem)
{ return addElement(elem); }
inline NASubCollection<T> & operator -=(CollIndex elem)
{ return subtractElement(elem); }
WordAsBits hash() const;
private:
CollIndex maxLength_; // Allocated size in dwords.
CollIndex wordSize_; // Dwords in use.
Lng32 entries_; // Number of bits set (or -1 if don't know).
NABoolean builtin_; // TRUE if using builtin array.
// sbits_ is defined as an array of double words instead of an array of
// words so that we ensure it starts on an 8-byte boundary. This is
// important for routines like prevUsedFast() so that an unalignment trap
// doesn't occur whenever we read an Int64 from the start of the array.
// Also, there is no problem if we don't use the builtin words since any
// dynamic allocation done will start the allocated buffer on a 16-byte
// boundry
DblWordAsBits sbits_[ BuiltinSubsetWords ];// Automatically allocated bits.
WordAsBits *pBits_; // Points to the bit vector,
// wherever it may be.
NACollection<WordAsBits> *longBits_; // used if more bits are needed
NACollection<T> *superset_; // the superset
CollHeap *heap_; // heap used for longBits_
CollIndex lastStaleBit_; // rightmost bit ever set to 1.
// Any method setting bit 1 must
// remember to maintain this var.
// initialized to 0.
// allocate and deallocate the pBits_ vector
inline WordAsBits * allocateBits( CollIndex words )
{
return( heap_ ?
(new( heap_ ) WordAsBits[ words ])
:
(new WordAsBits[ words ])
);
}
inline void deallocateBits()
{
if (heap_)
heap_->deallocateMemory( pBits_ );
else
delete [] pBits_;
}
}; // NASubCollection
// Fast path if bit 1 entries are probably in the first few words.
// If it is not the case, the regular clear will be called.
// Assume WordAsBits is 32 bit unsigned integer.
// Note it is not required to call clearFast, nextUsedFast, and
// addElementFast together.
template <class T>
inline void NASubCollection<T>::clearFast()
{
if (lastStaleBit_ >= 128)
{ // call the regular clear.
clear();
return;
}
*pBits_ = 0; // clear 1st word
entries_ = 0;
if (lastStaleBit_ < 32)
{
lastStaleBit_ = 0;
return;
}
WordAsBits *pW = pBits_;
*++pW = 0; // clear 2nd word
if (lastStaleBit_ < 64)
{
lastStaleBit_ = 0;
return;
}
*++pW = 0; // clear 3rd word
if (lastStaleBit_ < 96)
{
lastStaleBit_ = 0;
return;
}
*++pW = 0; // clear 4th word
lastStaleBit_ = 0;
return;
}
// Fast path when prev used is probably in the first 2 words.
template <class T>
inline CollIndex NASubCollection<T>::prevUsed(CollIndex start) const
{
if (start > lastStaleBit_)
return NULL_COLL_INDEX;
if (start >= 64)
return prevUsedSlow(start);
return prevUsedFast(start);
}
// Returns the ordinal position of the last bit set in the uint64_t passed as
// an argument.
inline ULng32 FindLastOne(uint64_t x)
{
// Set bits right of, and clear bits left of, last bit set.
uint64_t y = x ^ (x - 1);
// Return count of all bits set in the computed value. Fast version
// implemented for each targetted OS.
ULng32 result;
ULng32* ptr = ((ULng32*)&y);
ULng32 z;
// Quickly count the number of set bits in the first word using a well known
// population count algorithm
z = ptr[0];
z -= ((z >> 1) & 0x55555555);
z = (((z >> 2) & 0x33333333) + (z & 0x33333333));
z = (((z >> 4) + z) & 0x0f0f0f0f);
z += (z >> 8);
z += (z >> 16);
result = (z & 0x0000003f);
// Quickly count the number of set bits in the second word using a well known
// population count algorithm
z = ptr[1];
z -= ((z >> 1) & 0x55555555);
z = (((z >> 2) & 0x33333333) + (z & 0x33333333));
z = (((z >> 4) + z) & 0x0f0f0f0f);
z += (z >> 8);
z += (z >> 16);
return (result + (z & 0x0000003f));
}
// Slower path for calculating previous set bit. We can make this routine
// twice as fast if we access 64-bits at a time - no need to implement now.
template <class T>
CollIndex NASubCollection<T>::prevUsedSlow(CollIndex start) const
{
Lng32 startWordBucket;
ULng32 startWord;
ULng32 shiftAmount;
startWordBucket = (Lng32)(start >> 5); // word bucket to start search in
shiftAmount = 32 - (start & 0x1f) - 1; // used to calculate prev bit position
startWord = pBits_[startWordBucket] >> shiftAmount; // portion of bit vector
// with start bit as the
// least significant bit.
// If start bit is set, return it
if (startWord & 1)
return start;
// Search all words from startWord down to the 0th word in the bit vector in
// search for a set bit.
do {
if (startWord) {
// First calculation the ordinal position of the 1st set bit in the
// next word. Then subtract off the shiftAmount and the position of the
// last set bit in the word. This will give the ordinal position of the
// last bit set.
return ((startWordBucket+1) << 5) - shiftAmount - FindLastOne(startWord);
}
// Move on down to the next word bucket.
startWordBucket--;
// Set shiftAmount to 0 since start bit will now already be in the least
// significant bit position.
shiftAmount = 0;
// Get the next word to process *if* we're not passed the edge.
if (startWordBucket >= 0)
startWord = pBits_[startWordBucket];
} while (startWordBucket >= 0);
// If we haven't returned already, we must not have found a prev set bit.
return NULL_COLL_INDEX;
}
// Fast path when prev used is probably in the first 2 words.
template <class T>
inline CollIndex NASubCollection<T>::prevUsedFast(CollIndex start) const
{
uint64_t startDoubleWord;
ULng32 shiftAmount;
// Amount to shift start bit to least significant bit position.
shiftAmount = 64 - start - 1;
// Get portion of bit vector with start bit in least signifcant bit position.
// On NT, we have to byte-swap 64-bit value to big-endian.
startDoubleWord =
(((uint64_t)(*pBits_) << 32) | (uint64_t)(*(pBits_+ 1))) >> shiftAmount;
// If double word is 0, no bits are set, so return.
if (!startDoubleWord)
return NULL_COLL_INDEX;
// Return start bit if it is set. Otherwise calculate ordinal position of
// last bit set and return it.
return ((startDoubleWord & 1)
? start
: 64 - shiftAmount - FindLastOne(startDoubleWord));
}
const WordAsBits FirstOneLookup[16] = {
4, 3, 2, 2, // 0, 1, 2, 3
1, 1, 1, 1, // 4, 5, 6, 7
0, 0, 0, 0, // 8, 9, 10, 11
0, 0, 0, 0 // 12, 13, 14, 15
};
// Fast path when next used is probably in the first two words.
// If it is not the case, the regular nextUsed will be called.
//
// TRUE if found next used and update start to the nextUsed position.
// FALSE otherwise and start value is undefined.
// Assume WordAsBits is 32 bit unsigned integer.
// For each 4 bits, do a lookup.
// Use lastStaleBit_ to limit the search.
template <class T>
inline NABoolean NASubCollection<T>::nextUsedFast(CollIndex &start) const
{
if (start > lastStaleBit_) // no bit 1 entry after lastStaleBit_.
return FALSE;
if (start >= 64)
return nextUsed(start); // call the regular nextUsed.
WordAsBits w;
if (start >= 32)
// truncate bits before starting bit in word 1.
w = (pBits_[1] << (start - 32));
else
{ // truncate bits before starting bit in word 0.
w = ((*pBits_) << start);
if (!w)
{
if (lastStaleBit_ < 32)
return FALSE; // lastStaleBit_ is in word 0.
// check next word.
w = pBits_[1];
start = 32;
}
}
if (w >> 31)
return TRUE; // starting bit is set
ULng32 j, k;
// Do a lookup for each 4 bits.
// first 8 bits.
if (j = (w >> 24))
{
if (k = (j >> 4))
start += FirstOneLookup[k]; // bit 0..3
else
start += (4 + FirstOneLookup[j & 0xf]); // bit 4..7
return TRUE;
}
// 2nd 8 bits.
if (j = (w & 0xff0000))
{
if (k = (j >> 20)) // bit 8..11
start += (8 + FirstOneLookup[k]);
else
start += (12 + FirstOneLookup[(j >> 16) & 0xf]); // bit 12..15
return TRUE;
}
// 3rd 8 bits
if (j = (w & 0xff00))
{
if (k = (j >> 12)) // bit 16..19
start += (16 + FirstOneLookup[k]);
else
start += (20 + FirstOneLookup[(j >> 8) & 0xf]); // bit 20..23
return TRUE;
}
// 4th 8 bits
if (j = (w & 0xff))
{
if (k = (j >> 4)) // bit 24..27
start += (24 + FirstOneLookup[k]);
else
start += (28 + FirstOneLookup[j & 0xf]); // bit 28..31
return TRUE;
}
// Not found in first two words.
if (lastStaleBit_ < 64)
return FALSE; // lastStaleBit_ is in the first two words.
// Start from bit 64 to look for next used.
start = 64;
return nextUsed(start);
}
// Fast path when elem is probably less than 64.
// If it is not the case, the regular addElement will be called.
template <class T>
inline NASubCollection<T> & NASubCollection<T>::addElementFast(CollIndex elem)
{
if (elem >= 64)
return addElement(elem);
WordAsBits *w = pBits_;
CollIndex j = elem;
if (j >= 32)
{
w = &pBits_[1];
j -= 32;
}
if (((*w) << j) >> 31)
return (*this); // already set.
if (elem > lastStaleBit_)
lastStaleBit_ = elem;
(*w) |= SingleBitArray[j];
entries_++;
return (*this);
}
// -----------------------------------------------------------------------
// A set type template
//(NOTE: this is implemented as an array where used entries have usage
// NULL_COLL_INDEX and free entries have UNUSED_COLL_ENTRY usage)
// -----------------------------------------------------------------------
template <class T> class NASet : public NACollection<T>
{
public:
// constructor with user-defined heap
NASet(CollHeap *heap,
CollIndex initSize = 0) : NACollection<T>(heap,initSize)
{ invalidateCache(); }
// copy ctor
NASet(const SET(T) &other, CollHeap * heap) : NACollection<T>(other, heap)
{ invalidateCache(); }
// virtual destructor
virtual ~NASet();
// assignment operator (deep copy instead of shallow one)
inline NASet<T> & operator =(const NASet<T> &other)
{
if ( this != &other) { this->deallocate(); NACollection<T>::copy( (const NACollection<T>&) other); } // avoid copy-self!
return *this;
}
// remove all entries from the set
inline void clear() { NACollection<T>::clear(); invalidateCache(); }
// check whether an element is in the collection
inline NABoolean contains(const T &elem) const
{ return(NACollection<T>::find(elem) != NULL_COLL_INDEX); }
// find a given element in the collection and return it
inline NABoolean find(const T &elem, T &returnedElem) const
{
CollIndex ix = NACollection<T>::find(elem);
if(ix != NULL_COLL_INDEX)
{
returnedElem = this->constEntry(ix);
return TRUE;
}
else
return FALSE;
}
// index access(both reference and value) to be used as an iterator
// over the set elements, not for determining any order of the set!!!
T & operator [](CollIndex i);
const T & operator [](CollIndex i) const;
NABoolean operator==(const NASet<T> &other) const;
inline T & at(CollIndex i) { return operator [](i); }
inline const T & at(CollIndex i) const { return operator [](i); }
// return byte size of this collection
Lng32 getByteSize() const
{ return NACollection<T>::getByteSize() + sizeof(*this) -
sizeof(NACollection<T>); }
inline NABoolean insert(const T &elem)
{
invalidateCache();
if (NACollection<T>::find(elem) == NULL_COLL_INDEX)
{
NACollection<T>::insert(this->freePos(),elem);
return TRUE;
}
else
return FALSE;
}
// A dumb but easy implementation for insert one SET into another
inline NABoolean insert(const NASet<T> &other)
{
CollIndex count = other.entries();
for (CollIndex i = 0; i < count; i++)
{
insert(other[i]);
} // for loop for iterating over members of the set
return TRUE;
} // insert(SET(T))
inline NABoolean remove(const T &elem)
{
CollIndex ix = NACollection<T>::find(elem);
invalidateCache();
if (ix != NULL_COLL_INDEX)
{
NACollection<T>::remove(ix);
return TRUE;
}
else
return FALSE;
}
// A dumb but easy implementation for remove one SET from another
inline NABoolean remove(const NASet<T> &other)
{
CollIndex count = this->entries();
for (CollIndex i = 0; i < count; i++)
{
if ( contains(other[i]) )
remove(other[i]);
// else
// raise an exception?
} // for loop for iterating over members of the set
return TRUE;
} // removeSET(T))
private:
inline void invalidateCache()
{ userIndexCache_ = arrayIndexCache_ = NULL_COLL_INDEX; }
CollIndex userIndexCache_; // cache of last accessed element # with []
CollIndex arrayIndexCache_; // where to find the last accessed element
}; // NASet
// -----------------------------------------------------------------------
// a list type template
// -----------------------------------------------------------------------
template <class T> class NAList : public NACollection<T>
{
public:
// constructor with user-defined heap
NAList(CollHeap * heap,
CollIndex initLen = 0) : NACollection<T>(heap,initLen)
{ first_ = last_ = userIndexCache_ = arrayIndexCache_ = NULL_COLL_INDEX; }
// copy ctor
NAList(const NAList<T> &other, CollHeap * heap) : NACollection<T>(other, heap)
{
first_ = other.first_;
last_ = other.last_;
userIndexCache_ = other.userIndexCache_;
arrayIndexCache_ = other.arrayIndexCache_;
}
// virtual destructor
virtual ~NAList();
// assignment
NAList<T> & operator =(const NAList<T> &other);
// comparison
NABoolean operator ==(const NAList<T> &other) const;
// insert a new entry
inline void insert(const T &elem) { this->insertAt(this->entries(),elem); }
// insert a set, array, or list
// void insert(const SET(T) &other);
void insert(const LIST(T) &other);
// remove an element(the first that matches) that is given by its value
//(returns whether the element was found and removed)
inline NABoolean remove(const T &elem)
{ return removeCounted(elem, 1) > 0; }
// remove elements(all that match) given by value
//(returns the number of elements removed)
inline CollIndex removeAll(const T &elem)
{ return removeCounted(elem, 0); }
// remove at most "desiredCount" matching elements
//(returns the number of elements removed)
CollIndex removeCounted(const T &elem, const CollIndex desiredCount);
// remove all entries from the list
inline void clear()
{
NACollection<T>::clear();
first_ = last_ = userIndexCache_ = arrayIndexCache_ = NULL_COLL_INDEX;
}
// check whether an element is in the collection
inline NABoolean contains(const T &elem) const
{ return(NACollection<T>::find(elem) != NULL_COLL_INDEX); }
// find a given element in the collection and return it
NABoolean find(const T &elem, T &returnedElem) const;
// find the index of a given element or return NULL_COLL_INDEX if not found
inline CollIndex index (const T &elem) const
{
CollIndex currEntry = first_;
CollIndex result = FIRST_COLL_INDEX;
while (currEntry != NULL_COLL_INDEX)
{
if (this->constEntry(currEntry) == elem)
return result;
else
{
// advance to the next entry
result++;
currEntry = this->getUsage(currEntry);
}
}
// not found
return NULL_COLL_INDEX;
}
// index access(both reference and value), zero based
T & operator [](CollIndex i);
const T & operator [](CollIndex i) const;
inline T & at(CollIndex i) { return operator [](i); }
const T & at(CollIndex i) const { return operator [](i); }
// for the RAlist
CollIndex findArraysIndex(CollIndex i);
CollIndex findArraysIndex(CollIndex i) const;
// remove the last entry from the list and store it in "elem"
//(returns FALSE if the list is empty and no value is returned)
NABoolean getLast(T &elem);
// return byte size of this collection
Lng32 getByteSize() const
{ return NACollection<T>::getByteSize() + sizeof(*this) -
sizeof(NACollection<T>); }
// remove the index'th element from the list
//(returns TRUE if list[index] was found, FALSE if index was out of bounds)
inline NABoolean removeAt(const CollIndex index)
{
// check whether index is legal
if (index >= this->entries())
return FALSE;
if (index == 0)
{
// special case of removing the first list element
CollIndex elemToRemove = first_;
first_ = this->getUsage(elemToRemove);
NACollection<T>::remove(elemToRemove);
if (elemToRemove == last_)
last_ = first_;
}
else
{
// second or later entry
CollIndex pred = first_;
CollIndex predIx = 0;
CollIndex elemToRemove;
// find the predecessor in the list
while (++predIx < index)
{
pred = this->getUsage(pred);
}
// knowing the predecessor, unlink the element to remove from the list
elemToRemove = this->getUsage(pred);
this->setUsage(pred,this->getUsage(elemToRemove));
if (elemToRemove == last_)
last_ = pred;
NACollection<T>::remove(elemToRemove);
}
invalidateCache();
return TRUE;
}
// insert a new entry at a given position(new element becomes element # i,
// the rest of the list moves 1 entry up)
// use i = entries() to insert at the end, i = 0 to insert at the front
inline CollIndex insertAt(CollIndex i, const T &elem)
{
CollIndex newIndex = this->freePos();
CollIndex newUsage;
// handle special cases i=0, i=entries_
if (i == 0)
{
// add the new element to the front of the list
newUsage = first_;
first_ = newIndex;
if (last_ == NULL_COLL_INDEX)
last_ = first_;
}
else if (i == this->entries())
{
// add the new element at the tail of the list
if (last_ != NULL_COLL_INDEX)
this->setUsage(last_,newIndex);
newUsage = NULL_COLL_INDEX;
last_ = newIndex;
}
else
{
CollIndex pred = first_;
CollIndex predIx = 0;
// neither the new first nor the new last entry
while (predIx < i-1)
{
pred = this->getUsage(pred);
predIx++;
if (pred == NULL_COLL_INDEX)
ABORT("Insert position in list is invalid");
}
newUsage = this->getUsage(pred);
this->setUsage(pred,newIndex);
}
// do the actual insert (common for all three cases)
NACollection<T>::insert(newIndex,
elem,
newUsage);
// Invalidate the cache upon an insert.
if (userIndexCache_ >= i)
invalidateCache();
return newIndex;
}
// remove the first entry from the list and store it in "elem"
//(returns FALSE if the list is empty and no value is returned)
inline NABoolean getFirst(T &elem)
{
if (this->entries() > 0)
{
CollIndex oldFirst = first_;
// copy first element from the list
elem = this->usedEntry(oldFirst);
// set the new first element
first_ = this->getUsage(oldFirst);
// adjust the pointer to the last, if necessary
if (last_ == oldFirst)
last_ = NULL_COLL_INDEX;
// actually remove the first element
NACollection<T>::remove(oldFirst);
// invalidate the cache
invalidateCache();
return TRUE;
}
else
return FALSE;
}
private:
inline void invalidateCache()
{ userIndexCache_ = arrayIndexCache_ = NULL_COLL_INDEX; }
CollIndex first_; // index of fist element in list or NULL
CollIndex last_; // index of last element in list or NULL
CollIndex userIndexCache_; // cache of last accessed element # with []
CollIndex arrayIndexCache_; // where to find the last accessed element
}; // NAList
// -----------------------------------------------------------------------
// Array collection type template: this is similar to a list, except
// that it stores the list elements in order. Insertions in the middle
// are not allowed, but "holes" in the array(unused elements) are.
// Access to array elements by index is very fast. Beware of accessing
// uninitialized elements of the array(this will give you a core file).
// -----------------------------------------------------------------------
template <class T> class NAArray : public NACollection<T>
{
public :
// constructor with user-defined heap
NAArray(CollHeap *heap, CollIndex initialElements = 0) :
NACollection<T>(heap,initialElements) {}
// copy ctor
NAArray(const NAArray & other, CollHeap * heap) :
NACollection<T>(other, heap) {}
// Resize the array to a new size(return new size)
inline CollIndex resize(CollIndex newSize)
{ return NACollection<T>::resize(newSize); }
// access a used entry(warning: accessing unused entries aborts!!)
inline T & operator [](CollIndex index) { return this->usedEntry(index); }
inline const T & operator [](CollIndex index) const
{ return this->constEntry(index); }
inline T & at(CollIndex i) { return operator [](i); }
inline const T & at(CollIndex i) const { return operator [](i); }
// check whether a certain entry is used(prior to using operator [])
inline NABoolean used(CollIndex index) const
{ return(this->getUsage(index) != UNUSED_COLL_ENTRY); }
// find an unused position in the array(not necessarily the first one)
inline CollIndex unusedIndex() const { return this->freePos(); }
// delete all entries in the collection
inline void clear() { NACollection<T>::clear(); }
// comparison
NABoolean operator ==(const NAArray<T> &other) const;
inline NABoolean operator!= (const NAArray<T> &other) const
{ return NOT operator==(other); };
// assignment operator (deep copy instead of shallow one)
inline NAArray<T> & operator =(const NAArray<T> &other)
{
if ( this != &other) { this->deallocate(); NACollection<T>::copy( (const NACollection<T>&) other); } // avoid copy-self!
return *this;
}
// find a particular element in the array and return its position or
// NULL_COLL_INDEX
inline CollIndex find(const T &toFind) const
{ return NACollection<T>::find(toFind); }
// insert or overwrite array entry at a specified position
inline void insertAt(CollIndex index, const T &newEntry)
{ NACollection<T>::insert(index, newEntry); }
// make an array entry unused(caution: no destructor is called)
inline NABoolean remove(CollIndex index)
{ if(used(index)) { NACollection<T>::remove(index); return TRUE; }
else return FALSE; }
}; // NAArray
// -----------------------------------------------------------------------
// A subarray is a subset of an array, stored as a bit vector
// -----------------------------------------------------------------------
template <class T> class NASubArray : public NASubCollection<T>
{
public:
NASubArray(NAArray<T> *superset, CollHeap* heap) :
NASubCollection<T>(superset, heap) {}
NASubArray(const NASubArray<T> &other, CollHeap * heap) :
NASubCollection<T>(other, heap) {}
virtual ~NASubArray();
inline CollIndex resize(CollIndex newSize)
{ return NASubCollection<T>::resize(newSize); }
inline void clear() { NASubCollection<T>::clear(); }
inline NABoolean operator ==(const NASubArray<T> & other) const
{ return NASubCollection<T>::operator ==(other); }
inline NABoolean operator !=(const NASubArray<T> & other) const
{ return(NOT operator ==(other)); }
inline NASubArray<T> & operator =(const NASubArray<T> & other)
{ NASubCollection<T>::operator =(other); return *this; }
// check whether a particular entry is part of the subarray
inline NABoolean contains(CollIndex elem) const
{ return NASubCollection<T>::testBit(elem); }
inline NABoolean contains(const NASubArray<T> & other) const
{ return NASubCollection<T>::contains(other); }
// find the next used entry in the array or return false
// e.g. in a for-loop:
// for(CollIndex i = 0; nextUsed(i); i++) ...element(i)...
inline NABoolean nextUsed(CollIndex &start) const
{ return NASubCollection<T>::nextUsed(start); }
inline NASubArray<T> & insert(const NASubArray<T> & other)
{ NASubCollection<T>::addSet(other); return *this; }
inline NASubArray<T> & intersectSet(const NASubArray<T> & other)
{ NASubCollection<T>::intersectSet(other); return *this; }
inline NASubArray<T> & remove(const NASubArray<T> & other)
{ NASubCollection<T>::subtractSet(other); return *this; }
inline NASubArray<T> & insert(CollIndex elem)
{ NASubCollection<T>::addElement(elem); return *this; }
inline NASubArray<T> & remove(CollIndex elem)
{ NASubCollection<T>::subtractElement(elem); return *this; }
inline NASubArray<T> & complement()
{ NASubCollection<T>::complement(); return *this; }
inline NASubArray<T> & operator +=(const NASubArray<T> & other)
{ return insert(other); }
inline NASubArray<T> & operator -=(const NASubArray<T> & other)
{ return remove(other); }
inline NASubArray<T> & operator +=(CollIndex elem)
{ return insert(elem); }
inline NASubArray<T> & operator -=(CollIndex elem)
{ return remove(elem); }
inline WordAsBits hash() const { return NASubCollection<T>::hash(); }
inline const T & element(CollIndex e) const
{ return NASubCollection<T>::element(e); }
}; // NASubArray
// For bit vectors, NASubArray without a superset, source in
// file NABitVector.h
/* For these arrays, we want to be able to append, access a particular */
/* element, and be able to iterate over and tell the size. Destroying */
/* would be a welcome method as well. */
/* */
template <class T> class NASimpleArray : private NAArray<T>
{
public:
NASimpleArray (CollHeap * h) : NAArray<T>(h) {}
// copy ctor
NASimpleArray (const NASimpleArray & orig, CollHeap * h)
: NAArray<T>(orig, h) {}
void clearAndDestroy()
{
CollIndex i;
CollIndex last = entries();
for(i=0;i!=last;i++) {
delete(*this)[i];
}
this->clear();
}
T& operator [](CollIndex index)
{ return NAArray<T>::operator [](index); };
void append( T newItem)
{
this->insertAt( entries(), newItem);
}
CollIndex entries() const
{
return NAArray<T>::entries();
}
// operator s new and delete get inherited from private base class,
// make them publicly available by the following inline functions
static inline void * operator new(size_t size, CollHeap* h)
{ return NAArray<T>::operator new(size, h); }
static inline void operator delete(void *buffer)
{ NAArray<T>::operator delete(buffer); }
inline void setHeap(CollHeap *heap)
{
NAArray<T>::setHeap(heap);
}
}; // NASimpleArray
// ----------------------------------------------------------------------
// A NAHashDictionary is a pointer-based collection of keys and values.
// It is implemented by a hash table. The keys are represented by the
// class K and the values are represented by the class V.
//
// The hash table is an array of hash buckets. Each hash bucket is
// a list of hash bucket entries. Each hash bucket entry contains a
// key value pair.
//
// The application that uses this hash dictionary must provide a
// hash function that accepts a key instance as an argument and
// returns an integer that is the hash value, i.e., an index for
// a hash bucket in the hash table.
//
// The initial number of hash buckets is specified in the
// initialHashSize. If data skew causes many values to be clustered
// within a few hash buckets, then the size of the hash table can be
// changed by means of the resize() function. Note that resize()
// is usually an expensive operation since it involves the creation
// of a new hash table and the rehashing of all the keys that are
// contained in the dictionary.
//
// If the application wants to enforce that exactly one instance of
// a certain key can be inserted in this dictionary, it can specify
// such a requirement when the hash dictionary is created. The
// insertion of a duplicate key will fail when enforceUniqueness is
// set to TRUE. The first key value pair that is inserted in the hash
// table will persist after the failure in inserting a duplicate key.
// $$$$ In the future, the insertion of a duplicate key should
// $$$$ cause an exception.
//
// In general, the hash table can contain duplicate keys or even
// duplicate key value pairs. The application must initialize an iterator
// for retrieving mutiple instances of a given key or a given key
// value pair that are stored in the hash dictionary.
// In general, the hash table can contain duplicate keys or even duplicate
// key value pairs. The application must create an iterator object for
// retrieving mutiple instances of a given key or a given key value pair
// that are stored in the hash dictionary. See NAHashDictionaryIterator<K,V>
// below for how to create iterator objects.
//
// Requirement:
// ***********
// The classes K and V must each support well-defined equality semantics.
// It must be implemented by overloading the operator "==". This means,
// an implementation must exist for K::operator ==() as well as for
// V::operator ==(). The implementation of the hash dictionary invokes
// these operator s in order to compare stored keys and values with a
// a given key and value.
// ----------------------------------------------------------------------
// -----------------------------------------------------------------------
// class NAHashBucketEntry - A hash bucket entry.
// -----------------------------------------------------------------------
template <class K, class V>
class NAHashBucketEntry : public NABasicObject
{
public:
// --------------------------------------------------------------------
// Constructor function
// --------------------------------------------------------------------
NAHashBucketEntry(K* key, V* value) : key_(key), value_(value)
{ }
// copy ctor
NAHashBucketEntry(const NAHashBucketEntry<K,V>& other)
: key_(other.key_), value_(other.value_)
{ }
// --------------------------------------------------------------------
// Destructor function
// --------------------------------------------------------------------
virtual ~NAHashBucketEntry();
// --------------------------------------------------------------------
// Accessor functions for a NAHashBucket
// --------------------------------------------------------------------
inline K* getKey() const { return key_; }
inline V* getValue() const { return value_; }
// If deleteContents is set, then the key and the value that are
// contained in this hash bucket entry are also deleted.
void clear(NABoolean deleteContents = FALSE);
void display() const;
Int32 printStatistics(char *buf);
// return byte size of this object
Lng32 getByteSize() const { return sizeof(*this); }
private:
K* key_;
V* value_;
}; // class NAHashBucketEntry
// -----------------------------------------------------------------------
// class NAHashBucket - A hash bucket.
// -----------------------------------------------------------------------
template <class K, class V>
class NAHashBucket : public NABasicObject
{
public:
// --------------------------------------------------------------------
// Constructor function
// --------------------------------------------------------------------
NAHashBucket(CollHeap * heap): bucket_(heap), heap_(heap) {}
// copy ctor
NAHashBucket(const NAHashBucket<K,V>& other, CollHeap * heap);
// --------------------------------------------------------------------
// Destructor function
// --------------------------------------------------------------------
virtual ~NAHashBucket();
// --------------------------------------------------------------------
// Accessor functions for a NAHashBucket
// --------------------------------------------------------------------
// Check whether this hash bucket contains a given key, or a given
// key value pair.
NABoolean contains(const K* key) const;
NABoolean contains(const K* key, const V* value) const;
// The number of entries contained in this hash bucket.
inline CollIndex entries() const { return bucket_.entries(); }
// Get the first value that is encountered that corresponds to the
// given key. If no such key exists, getFirstValue() returns a NULL.
V* getFirstValue(const K* key) const;
// Get all key value pairs that correspond to the given key or
// given key value pair. If both key and value are NULL, then
// return all the key value pairs contained in this bucket.
// The qualifying key value pairs are returned in the container.
void getKeyValuePair(const K* key, const V* value,
NAHashBucket<K,V>& container) const;
// Overload the array index operator to access a particular entry.
inline const NAHashBucketEntry<K,V>* operator [](Lng32 index) const
{ return bucket_[index]; }
// --------------------------------------------------------------------
// Mutator functions for a NAHashBucket
// --------------------------------------------------------------------
// Delete all hash bucket entries. If deleteContents is set, then
// the contents of each hash bucket entry are also deleted.
void clear(NABoolean deleteContents = FALSE);
// Insert a given key value pair into this hash bucket.
inline void insert(K* key, V* value)
{ bucket_.insertAt(0,new(heap_) NAHashBucketEntry<K,V>(key, value)); }
// Remove the first hash bucket entry that contains the given key.
K* remove(K* key);
void display() const;
Int32 printStatistics(char *buf);
// return byte size of this object
Lng32 getByteSize() const
{ return sizeof(*this) + (bucket_ ? bucket_->getByteSize() : 0); }
private:
// --------------------------------------------------------------------
// A hash bucket contains a number of entries.
// --------------------------------------------------------------------
NAList<NAHashBucketEntry<K,V> *> bucket_;
// -----------------------------------------------------------------------
// A CollHeap* for memory allocation within NAHashBucket.
// -----------------------------------------------------------------------
CollHeap * heap_;
}; // class NAHashBucket
// -----------------------------------------------------------------------
// class NAHashDictionary - The hash dictionary.
// -----------------------------------------------------------------------
template <class K, class V>
class NAHashDictionary : public NABasicObject
{
public:
friend class NAKeyLookup<K,V>;
friend class NAHashDictionaryIterator<K,V>;
#define NAHashDictionary_Default_Size 11
// --------------------------------------------------------------------
// Constructor functions.
// --------------------------------------------------------------------
// Previously the code was ugly -- it used a hash function that was defined
// in the scope of the file using the NAHashDictionary template. New
// compilers produce an error ("undeclared variable" ) in case the template
// gets defined (i.e., Collections.h is included) but not instantiated!
// Solution: The hash function should be a method of the "key" class K !!
// Thus: we fixed the NAHashDictionary code.
// Problem: The code using NAHashDictionary has to be fixed as well (turn
// those hash functions into hash() methods). This code is mainly compiler
// code, and we don't have the time to do and test those changes; thus we
// left the old ugly way under the #else clause, until someone finishes
// this work.
// NAHashDictionary(
//#else // the old way
NAHashDictionary(ULng32(*hashFunction)(const K&),
//#endif
ULng32 initialHashSize = NAHashDictionary_Default_Size,
NABoolean enforceUniqueness = FALSE,
CollHeap * heap=0 /* where to allocate memory */ );
// copy ctor
NAHashDictionary(const NAHashDictionary<K,V>& other, CollHeap * heap);
// --------------------------------------------------------------------
// Destructor function
// --------------------------------------------------------------------
virtual ~NAHashDictionary();
// --------------------------------------------------------------------
// Accessor functions for a NAHashDictionary.
// --------------------------------------------------------------------
// Check whether this dictionary contains a certain key, or a
// certain key value pair.
inline NABoolean contains(const K* key) const
{ return(*hashTable_)[getHashCode(*key)]->contains(key); }
inline NABoolean contains(const K* key, const V* value) const
{ return(*hashTable_)[getHashCode(*key)]->contains(key,value); }
// The number of key value pairs that are contained in this dictionary.
inline Lng32 entries() const { return entries_; }
// Find the first value corresponding to the given key.
// This method is especially useful(and effcient) when the hash
// dictionary enforces uniqueness.
V* getFirstValue(const K* key) const
{ return(*hashTable_)[getHashCode(*key)]->getFirstValue(key); }
// Returns TRUE if the dictionary contains no key value pairs.
// FALSE otherwise.
inline NABoolean isEmpty() const { return(entries_ == 0); }
// --------------------------------------------------------------------
// NB: iterator functions for this class (which were previously
// described here) have been taken over by the friend class
// NAHashDictionaryIterator<K,V> (see below).
// --------------------------------------------------------------------
// --------------------------------------------------------------------
// Mutator functions for a NAHashDictionary
// --------------------------------------------------------------------
// Remove all key value pairs.
void clear(NABoolean deleteContents = FALSE);
// Delete all key and value pairs. Does not check whether they are unique.
// Delete all entries in the hash buckets.
// Delete all hash buckets.
// Delete the hash table and the dictionary.
void clearAndDestroy() { clear(TRUE); }
// Insert a key value pair.
// Returns the given value if the insertion is successful.
// Returns a NULL if the insertion fails, such as when a
// duplicate key is inserted into a dictionary that enforces
// uniqueness on keys.
K* insert(K* key, V* value);
// Remove one key value pair corresponding to the given key.
// Returns the given key value if the removal is successful.
// Returns NULL if the given key value is not found in the dictionary.
K* remove(K* key);
// Change the number of hash buckets in an attempt to distribute the
// keys and values uniformly over all the hash buckets.
void resize(ULng32 newHashSize);
virtual void display() const;
Int32 printStatistics(char *buf);
// return byte size of this object
Lng32 getByteSize() const
{ return sizeof(*this) + (hashTable_ ? hashTable_->getByteSize() : 0); }
// return byte size of one NAHashBucketEntry
static Lng32 getBucketEntrySize() { return sizeof(NAHashBucketEntry<K,V>); }
ULng32 getNumBuckets() { return hashSize_; }
private:
// --------------------------------------------------------------------
// Helper function for creating a hash table
// --------------------------------------------------------------------
void createHashTable(ULng32 hashSize);
// --------------------------------------------------------------------
// Private method for generating a hash code.
// --------------------------------------------------------------------
ULng32 getHashCode(const K& key) const;
private:
// Needed only for the old way of NAHashDictionary -- see comment above
// --------------------------------------------------------------------
// The hash function that is applied to the key for determining the
// bucket to which it belongs.
// --------------------------------------------------------------------
ULng32(*hash_)(const K&);
// --------------------------------------------------------------------
// The hash table is an array of hash buckets.
// --------------------------------------------------------------------
NAArray<NAHashBucket<K,V>*>* hashTable_;
// --------------------------------------------------------------------
// The hashSize is stored here for improving efficiency.
// --------------------------------------------------------------------
ULng32 hashSize_;
// --------------------------------------------------------------------
// The number of key value pairs existing in the hash dictionary are
// cached here.
// --------------------------------------------------------------------
Lng32 entries_;
// --------------------------------------------------------------------
// The application is allowed to insert only one instance of a key
// if uniqueness is to be enforced. An attempt to insert another
// instance causes an exception to be raised.
//($$$ Presently this exception is not implemented!)
// --------------------------------------------------------------------
NABoolean enforceUniqueness_;
// -----------------------------------------------------------------------
// The CollHeap* for memory allocation within NAHashDictionary
// -----------------------------------------------------------------------
CollHeap * heap_;
}; // class NAHashDictionary
// -----------------------------------------------------------------------
// class NAHashDictionaryIterator - iterator class for NAHashDictionary
// -----------------------------------------------------------------------
// --------------------------------------------------------------------
// An iterator for the NAHashDictionary.
//
// The iterator is a mechanism that allows an application to iterate
// over a set of key value pairs that are stored in the hash dictionary.
// The set is constructed according to one of the following three
// specifications.
// 1) The application does not provide either a key or a value, i.e.,
// both are NULL. Such an iterator is used for iterating over
// all the key value pairs that are stored in the hash dictionary.
// 2) The application provides a key but not a value, i.e., value is
// NULL. Such an iterator can be used for iterating over all
// those key value pairs in the hash dictionary whose keys are
// equal to(the same as) the given key.
// 3) The application provides a key as well as a value. Such an
// iterator can be used for iterating over all those key value
// pairs that are equal to(the same as) the given key value pair.
//
// --------------------------------------------------------------------
// -----------------------------------------------------------------------
// Iterators are easy to use!
//
// ( given the existence of 'NAHashDictionary<int,double> bob' )
//
// --> create an iterator for bob for key-value 3
// int * key ;
// double * value ;
// NAHashDictionaryIterator<int,double> bobIter (bob, 3) ;
//
// --> loop over and print out everything in the iterator
// for ( int i = 0 ; i < bobIter.entries() ; i++)
// {
// bobIter.getNext (key,value) ;
// cout << key << " : " << value << endl ;
// }
//
// --> another way to loop over it (taste preference)
// bobIter.getNext (key,value) ;
// while ( key && value )
// {
// cout << key << " : " << value << endl ;
// bobIter.getNext (key,value) ;
// }
//
// --> create a copy of this iterator
// bobIter2 (bobIter) ;
//
// --> reset this copied iterator to loop from the beginning
// bobIter2.reset() ;
//
// --> destroying the iterator : just let it go out of scope!
// -----------------------------------------------------------------------
template <class K, class V>
class NAHashDictionaryIterator : public NABasicObject
{
public:
// basic ctor
NAHashDictionaryIterator<K,V> (const NAHashDictionary<K,V> & dict,
const K* key = NULL,
const V* value = NULL) ;
// copy ctor
NAHashDictionaryIterator<K,V> (const NAHashDictionaryIterator<K,V> & other,
CollHeap * heap) ;
// dtor
~NAHashDictionaryIterator<K,V>() ;
// The number of key value pairs that can be accessed using this
// iterator.
inline CollIndex entries() const { return iterator_.entries(); }
// Our current position within the list
inline Lng32 position() const { return iteratorPosition_; }
// Reset the counter so we can iterate again from the start
inline void reset()
{
if ( entries() > 0 )
iteratorPosition_ = FIRST_COLL_INDEX ;
else
iteratorPosition_ = NULL_COLL_INDEX ;
}
// Advances the iterator and returns a new key value pair.
// Both key and value are set to NULL after all the key value pairs
// have been iterated over.
void getNext(K*& key, V*& value) ;
private:
NAHashDictionaryIterator<K,V>() ; // never create an uninitialized iterator!
// --------------------------------------------------------------------
// The iterator for the hash dictionary is implemented by an
// empty hash bucket which is initialized with pointers to hash
// bucket entries when the iterator is created.
// --------------------------------------------------------------------
NAHashBucket<K,V> iterator_;
Lng32 iteratorPosition_; // where in iterator_ we currently are
};
// **********************************************************************
// gcc requires these definitions be seen before the hashKey is used in
// NAKeyLookup. This may be a bug in gcc that could be fixed in a
// newer release. The other solution to this problem involves reordering
// include files.
// **********************************************************************
class QualifiedName;
class ExtendedQualName;
class CorrName;
class ColRefName;
class NAString;
class NARoutineDBKey;
ULng32 hashKey(const QualifiedName&);
ULng32 hashKey(const ExtendedQualName&);
ULng32 hashKey(const CorrName&);
ULng32 hashKey(const ColRefName&);
ULng32 hashKey(const NAString&);
ULng32 hashKey(const NARoutineDBKey&);
// **********************************************************************
// NAKeyLookup : A Descriptor Store
// (a storage area for a given class of descriptors)
//
// The descriptor store is an associative storage for object descriptors.
// It is implemented by a hash table in which the name of the object
// is used as the hash key. The hash table provides a fast associative
// lookup through the association of a name(as a key) with each object
// descriptor. Each descriptor store imposes a uniqueness constraint
// on the names that are used as keys.
//
// Consumers need to support:
// - a V.getKey() function that returns a value of type K*
// - well-defined equality semantics, i.e. K::operator ==(const K&)
// - an external unsigned long hashKey(const K&) function
// (must be external because NAString, i.e. RWCString, does not have
// a static function of this signature)
// - a K::K(const K &, CollHeap * h), i.e., a copy ctor that takes a
// CollHeap* as a 2nd parameter
// e.g., NAString::NAString (const NAString & other, CollHeap * h=0) ;
// **********************************************************************
class NAKeyLookupEnums // not a template, just a namespace for enum
{
public:
enum KeyProvenance { KEY_INSIDE_VALUE, KEY_OUTSIDE_VALUE };
};
template <class K, class V>
class NAKeyLookup : public NAHashDictionary<K,V>
{
public:
// --------------------------------------------------------------------
// Constructor functions
// --------------------------------------------------------------------
NAKeyLookup(short initSize,
NAKeyLookupEnums::KeyProvenance keyProvenance,
CollHeap * heap) :
NAHashDictionary<K,V>(&hashKey, initSize, TRUE,heap),
keyProvenance_(keyProvenance)
{}
// copy ctor
NAKeyLookup (const NAKeyLookup & nakl, CollHeap * heap) :
NAHashDictionary<K,V>(nakl, heap),
keyProvenance_(nakl.keyProvenance_)
{}
// --------------------------------------------------------------------
// Destructor functions
// --------------------------------------------------------------------
~NAKeyLookup() {}
// --------------------------------------------------------------------
// Methods for a NAKeyLookup.
// 'Const' is used on method signatures where it makes sense
//(thus allowing the methods to be called more easily, and safely).
// --------------------------------------------------------------------
void clearAndDestroy()
{
// Frees memory for BOTH K AND V for all such pairs,
// plus internal RW data structures.
NAHashDictionary<K,V>::clearAndDestroy();
}
inline V* get(const K* kk) const // retrieve a tuple
{
return this->getFirstValue(kk);
}
inline void insert(const V* vv) // insert a tuple
{
// K and V must point to distinct regions of memory
// in order for clearAndDestroy() to work
//(i.e. not free same mem twice)!
const K* kk;
if(keyProvenance_ == NAKeyLookupEnums::KEY_INSIDE_VALUE)
kk = new(this->heap_) K(*vv->getKey(), this->heap_);
else
kk = vv->getKey();
K* rv = NAHashDictionary<K,V>::insert((K*)kk,(V*)vv); //(cast away constness)
if ( rv == NULL && keyProvenance_ == NAKeyLookupEnums::KEY_INSIDE_VALUE )
delete kk ; // avoid memleak!
}
void remove(const K* kk)
{
// insert creates a key object and here we undo this operation. We collect
// keys and values that match the key in the iterator. Because of unique-
// ness constraints, there should only be one element. The uniqueness is
// asserted during insert operation
V* vv=NULL;
NAHashDictionaryIterator<K,V> iter (*this, kk, vv);
K* rv = NAHashDictionary<K,V>::remove((K*)kk);
if (keyProvenance_ == NAKeyLookupEnums::KEY_INSIDE_VALUE && rv!= NULL)
{
K* key;
V* value;
iter.getNext(key, value);
delete key;
}
}
void dump(NAList<V *>& vv) const // dump contents to list
{
NAHashDictionaryIterator<K,V> iter (*this) ;
K* key;
V* value;
iter.getNext(key,value);
while(key)
{
vv.insert(value);
iter.getNext(key,value);
}
}
void dumpKeys (NAList<K *>& kk) const // dump the keys to a list
{
NAHashDictionaryIterator<K,V> iter (*this) ;
K* key;
V* value;
iter.getNext(key,value);
while(key)
{
kk.insert(key);
iter.getNext(key,value);
}
}
// NAKeyLookup::insert() may have allocated memory to insert the key
// part of the <key,value> pairs that were put into the NAKeyLookup.
// However, since we didn't allocate the value parts, we might now
// want to deallocate them.
//
// This method can be called as an alternative to clearAndDestroy(),
// when the user only wants to delete the memory that NAKeyLookup itself
// allocated.
void clearAndDestroyKeysOnly ()
{
// no-op if NAKeyLookup couldn't possibly allocate any memory
if ( keyProvenance_ != NAKeyLookupEnums::KEY_INSIDE_VALUE ) return ;
NAList<K *> keys (this->heap_);
dumpKeys (keys) ;
CollIndex entries = keys.entries() ;
for ( CollIndex i = 0 ; i < entries ; i++ )
delete keys[i] ;
this->clear() ;
}
private:
const NAKeyLookupEnums::KeyProvenance keyProvenance_;
}; // NAKeyLookup
// -----------------------------------------------------------------------
// This is done similarly to Tools.h++: if we want to instantiate
// templates at compile time, the compiler needs to know the
// implementation of the template functions. Do this by setting the
// preprocessor define NA_COMPILE_INSTANTIATE.
// -----------------------------------------------------------------------
#if defined(NA_COMPILE_INSTANTIATE)
#include "Collections.cpp"
#endif
#endif /* COLLECTIONS_H */