AutoHashTable.h   [plain text]

/*
 * Copyright (c) 2004-2008 Apple Inc. All rights reserved.
 *
 * @APPLE_APACHE_LICENSE_HEADER_START@
 * 
 * Licensed 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.
 * 
 * @APPLE_APACHE_LICENSE_HEADER_END@
 */

#pragma once
#ifndef __AUTO_HASHTABLE__
#define __AUTO_HASHTABLE__

#include "AutoConfiguration.h"
#include "AutoDefs.h"
#include "AutoRange.h"


namespace Auto {

    //----- HashTable -----//
    
    //
    // Manages a closed hash table of ranges.
    //
    
    class HashTable {
    
      private:
      
        enum {
            initial_size_log2 = 8,                          // initial length log2
            maximum_depth     = 8,                          // maximum search depth
        };
        
        Range    **_ranges;                                 // array of range pointers
        usword_t _length_log2;                              // ilog2(length), length = 1 << _length_log2;
        
        
        //
        // next
        //
        // Return the next slot in array.
        //
        inline Range **next(Range **slot) const { return _ranges + ((slot - _ranges + 1) & mask(_length_log2)); }
        
        
        //
        // hash
        // 
        // Return the hash of a specified range.
        //
        inline const usword_t hash(register void *address) const {
            usword_t addr = (uintptr_t)address;
            // rotation choices based on empirical study
            usword_t hash = rotate_bits_right(addr, 6);
            hash ^= rotate_bits_right(addr, 9);
            hash ^= rotate_bits_right(addr, 16);
            hash ^= rotate_bits_right(addr, 24);
            return hash & mask(_length_log2);
        }
      
      
        //
        // rehash
        //
        // Rehash all the entries of the table.
        //
        bool rehash(Range **ranges, usword_t length);

        
        //
        // grow 
        // 
        // Grow hash table to accommodate more ranges.
        //
        void grow();
                
        
        //
        // find_slot
        //
        // Find the slot the range should reside.
        //
        Range **find_slot(void *address);
        

        //
        // insert
        //
        // Inserts an entry if there is a slot.
        //
        bool insert(Range *range);


      public:

        HashTable() : _ranges(NULL), _length_log2(0) {}

        //
        // initialize
        //
        // Set up the hash table.
        //
        void initialize();

        
        //
        // dispose
        //
        // Release memory allocated for the hash table.
        //
        void dispose();
        
        
        //
        // add
        //
        // Add a range to the hash table.
        //
        void add(Range *range);

        
        //
        // find
        //
        // Return the entry corresponding to the specified address
        //
        inline Range *find(void *address) {
            // find the slot
            Range **slot = find_slot(address);
            
            // if the slot is found it is either NULL or the object else return NULL
            return slot ? *slot : NULL;
        }


        //
        // is_member
        //
        // Returns true if the range is in the hash table.
        //
        inline const bool is_member(void *address) { return find(address) != NULL; }
        
        
        //
        // remove
        //
        // Remove an entry from the table.
        //
        void remove(Range *range);
        
        
        //
        // clear
        //
        // Remove all entries from the table
        //
        inline void clear() { if (_ranges) bzero(_ranges, (1 << _length_log2) * sizeof(Range *)); }
        
        
    };


};


#endif // __AUTO_HASHTABLE__