Home    News    Components    Get ViTooKi    Documentation    Community    Developers    @sf.net  

Info

Last update:
12 Feb 2007

Documentation

Doxygen LXR

FastPointerHashTable.hpp

 /***********************************************************************
 *                                                                      *
 * ViTooKi                                                              *
 *                                                                      *
 * title:       FastPointerHashTable.hpp                                *
 *                                                                      *
 *                                                                      *
 *                                                                      *
 * ITEC institute of the University of Klagenfurt (Austria)             *
 * http://www.itec.uni-klu.ac.at                                        *
 *                                                                      *
 *                                                                      *
 * For more information visit the ViTooKi homepage:                     *
 * http://ViTooKi.sourceforge.net                                       *
 * vitooki-user@lists.sourceforge.net                                   *
 * vitooki-devel@lists.sourceforge.net                                  *
 *                                                                      *
 * This file is part of ViTooKi, a free video toolkit.                  *
 * ViTooKi is free software; you can redistribute it and/or             *
 * modify it under the terms of the GNU General Public License          *
 * as published by the Free Software Foundation; either version 2       *
 * of the License, or (at your option) any later version.               *
 *                                                                      *
 * This program is distributed in the hope that it will be useful,      *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of       *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the         *
 * GNU General Public License for more details.                         *
 *                                                                      *
 * You should have received a copy of the GNU General Public License    *
 * along with this program; if not, write to the Free Software          *
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,               *
 * MA  02111-1307, USA.                                                 *
 *                                                                      *
 ***********************************************************************/

 /***********************************************************************
 *                                                                      *
 *  REVISION HISTORY:                                                   *
 *                                                                      *
 *                                                                      *
 *                                                                      *
 ***********************************************************************/
#ifndef VITOOKI_PS_FASTPOINTERHASHTABLE_HPP
#define VITOOKI_PS_FASTPOINTERHASHTABLE_HPP

#include <assert.h>
template<class T> class FastPointerHashTable 
{
        T invalid;
        T* data;
        unsigned int size;
        unsigned int* keys;

public:
        FastPointerHashTable(unsigned int siz) {
                invalid=NULL;
                size=siz;
                data=new T[size];
                memset(data,0,sizeof(T)*size); // init to NULL
                keys=new unsigned int[size];
                memset(keys,0u,sizeof(unsigned int)*size); // init to 0
                // 0 is an invalid key for all elements but the first (due to the modulo mapping)
                keys[0]=1u;
        };

        ~FastPointerHashTable() {
                freeAllElements();
                delete[] data; delete[] keys;
        };

        void put(T& elem,unsigned int key) {
                unsigned int pos=key%size;
                assert(elem != NULL);
                if(elem==NULL)
                        return;
                // if we receive another element that maps to the same pos but has
                // a different key then we delete it!
                if(data[pos]) 
                        delete data[pos];
                data[pos]=elem;
                keys[pos]=key;
        };
        
        T& get(unsigned int key) {
                unsigned int pos=key%size;
                if(keys[pos]==key)
                        return data[pos];
                return invalid; 
        };
        
        void freeElement(const unsigned int key) {
                unsigned int pos=key%size;
                if(keys[pos]==key) {
                        keys[pos]=key+1; // invalid key which can never be found at this position due to modulo operation
                        if(data[pos])
                                delete data[pos];
                        data[pos]=NULL;
                }
        };

        void freeAllElements() {
                for(unsigned int i=0;i<size;i++) {
                        if(data[i]) {
                                delete data[i];
                                data[i]=NULL;
                        }
                        keys[i]=i+1;
                }
        };

        void unlinkElement(const unsigned int key) {
                unsigned int pos=key%size;
                if(keys[pos]==key) {
                        keys[pos]=key+1; // invalid key which can never be found at this position due to modulo operation
                        data[pos]=NULL;
                }
        };
};
#endif

© ViTooKi 2003 :: [Lite version] Created with Doxygen