PtexExtractor/ptex/PtexDict.h

/* 
PTEX SOFTWARE
Copyright 2009 Disney Enterprises, Inc.  All rights reserved

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

  * Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.

  * Redistributions in binary form must reproduce the above copyright
    notice, this list of conditions and the following disclaimer in
    the documentation and/or other materials provided with the
    distribution.

  * The names "Disney", "Walt Disney Pictures", "Walt Disney Animation
    Studios" or the names of its contributors may NOT be used to
    endorse or promote products derived from this software without
    specific prior written permission from Walt Disney Pictures.

Disclaimer: THIS SOFTWARE IS PROVIDED BY WALT DISNEY PICTURES AND
CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS
FOR A PARTICULAR PURPOSE, NONINFRINGEMENT AND TITLE ARE DISCLAIMED.
IN NO EVENT SHALL WALT DISNEY PICTURES, THE COPYRIGHT HOLDER OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND BASED ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
*/
#ifndef PtexDict_h
#define PtexDict_h

template<class T>
class PtexDict
{
    class Entry; 
    
public: // Public Types   
    class iterator;        
    class const_iterator;  
    friend class iterator;
    friend class const_iterator;
    
    typedef const char*    key_type;       
    typedef T              mapped_type;    

    struct value_type {
    public:
    value_type(): first(0), second() {}
    value_type(key_type f, const T& s): first(f), second(s) {}

    const key_type first;  
    T second;              
    };

public:  // Public Member Interfce
    
    PtexDict() :  _numEntries(0), _numBuckets(0), _bucketMask(0), _buckets(0) {}
    virtual ~PtexDict() { clear(); }


    T& operator[](const char* key);

    iterator begin()
    {
    iterator iter;
    iter._d = this;
    for (iter._b = 0; iter._b < _numBuckets; iter._b++) {
        iter._e = &_buckets[iter._b];
        if (*iter._e) return iter;
    }
    iter._e = 0;
    return iter;
    }

    inline iterator end() { return iterator( 0, this, 0 ); }

    const_iterator begin() const
    {
    const_iterator iter;
    iter._d = this;
    for (iter._b = 0; iter._b < _numBuckets; iter._b++) {
        iter._e = &_buckets[iter._b];
        if (*iter._e) return iter;
    }
    iter._e = 0;
    return iter;
    }

    inline const_iterator end() const { return const_iterator( 0, this, 0 ); }
    

    iterator find(const char* key);
    const_iterator find(const char* key) const;
    
    bool erase(const char* key);

    iterator erase(iterator iter);

    void clear();

    int size() const { return _numEntries; }

private: // Private Member Interface
       
    struct Entry {
    public: // Public Member Interface
    Entry() : _next(0), _hashval(0), _keylen(0),
          _val(_key,T()), _pad(0) {}    
    private: // Private Member Interface    
    Entry(const Entry&);
    Entry& operator=(const Entry&);
    
    public:
    Entry*     _next;    
    int        _hashval; 
    int        _keylen;  
    value_type _val;     
    union {
        int  _pad;   
        char _key[1];
    };
    };

    PtexDict(const PtexDict&);
    PtexDict& operator=(const PtexDict&);

    int hash(const char* key, int& keylen) const
    {
    // this is similar to perl's hash function
    int hashval = 0;
    const char* cp = key;
    char c;
    while ((c = *cp++)) hashval = hashval * 33 + c;
    keylen = int(cp-key)-1;
    return hashval;
    }

    Entry** locate(const char* key, int& keylen, int& hashval) const
    {
    hashval = hash(key, keylen);
    if (!_buckets) return 0;
    for (Entry** e = &_buckets[hashval & _bucketMask]; *e; e=&(*e)->_next)
        if ((*e)->_hashval == hashval && (*e)->_keylen == keylen &&
        streq(key, (*e)->_key, keylen)) 
        return e;
    return 0;
    }


    static inline bool streq(const char* s1, const char* s2, int len)
    {
    // first make sure s1 is quad-aligned (s2 is always aligned)
    if (((intptr_t)s1 & 3) == 0) {  
        int len4 = len >> 2;
        while (len4--) {
        if (*(int*)s1 != *(int*)s2) return 0;
        s1 += 4; s2 += 4;
        }
        len &= 3;
    }
    while (len--) if (*s1++ != *s2++) return 0;
    return 1;
    }

    void grow();

private:  // Private Member data

    int _numEntries;  
    int _numBuckets;  
    int _bucketMask;  
    Entry** _buckets; 
};


template<class T>
class PtexDict<T>::iterator {
public:
    iterator() : _d(0), _e(0), _b(0) {}
    
    iterator(const iterator& iter) :
    _d(iter._d), _e(iter._e), _b(iter._b) {}
    inline iterator& operator=(const iterator& iter)
    { _e = iter._e; _d = iter._d; _b = iter._b; return *this; }   
    
    inline value_type& operator*() const { return getValue(); }
    inline value_type* operator->() const { return &getValue(); }

    inline operator bool() { return _e != 0; }
    
    inline bool operator==(const iterator& iter) const
    { return iter._e == _e; }
    inline bool operator!=(const iterator& iter) const
    { return iter._e != _e; }
    inline bool operator==(const const_iterator& iter) const
    { return iter._e == _e; }
    inline bool operator!=(const const_iterator& iter) const
    { return iter._e != _e; }
    iterator& operator++(int);
    
private:  // Private interface

    iterator( Entry** e, const PtexDict* d, int b): _d(d), _e(e), _b(b) {}
    
    inline value_type& getValue() const{
    if (_e) return (*_e)->_val;
    else   return _defaultVal;
    }
    
    friend class PtexDict;
    friend class const_iterator;
    const PtexDict* _d;  
    Entry** _e;      
    int _b;          

    static value_type _defaultVal; 
};

// define the static type for the iterator
template<class T> typename PtexDict<T>::value_type PtexDict<T>::iterator::_defaultVal;

template<class T>
class PtexDict<T>::const_iterator {
public:
    const_iterator() : _d(0), _e(0), _b(0) {}

    const_iterator(const const_iterator& iter) :
    _d(iter._d), _e(iter._e), _b(iter._b) {}
    const_iterator(const iterator& iter) :
    _d(iter._d), _e(iter._e), _b(iter._b) {}
    inline const_iterator& operator=(const const_iterator& iter)
    { _e = iter._e; _d = iter._d; _b = iter._b; return *this; }
    inline const_iterator& operator=(iterator& iter)
    { _e = iter._e; _d = iter._d; _b = iter._b; return *this; }
    
    inline const value_type& operator*() const { return getValue(); }
    inline const value_type* operator->() const { return &getValue(); }
    
    inline operator bool() { return _e != 0; }
    
    inline bool operator==(const iterator& iter) const
    { return iter._e == _e; }
    inline bool operator!=(const iterator& iter) const
    { return iter._e != _e; }
    inline bool operator==(const const_iterator& iter) const
    { return iter._e == _e; }
    inline bool operator!=(const const_iterator& iter) const
    { return iter._e != _e; }
    const_iterator& operator++(int);
    
private:  // Private interface
    
    const_iterator( Entry** e, const PtexDict* d, int b): _d(d),_e(e),_b(b) {}

    inline const value_type& getValue() const{
    if (_e) return (*_e)->_val;
    else   return _defaultVal;
    }
    
    friend class PtexDict;
    friend class iterator;
    const PtexDict* _d;  
    Entry** _e;      
    int _b;          

    static value_type _defaultVal; 
};

// define the static type for the iterator
template<class T> typename PtexDict<T>::value_type PtexDict<T>::const_iterator::_defaultVal;

template<class T>
typename PtexDict<T>::iterator& PtexDict<T>::iterator::operator++(int)
{
    if (_e) {
    // move to next entry
    _e = &(*_e)->_next;
    if (!*_e) {
        // move to next non-empty bucket
        for (_b++; _b < _d->_numBuckets; _b++) {
        _e = &_d->_buckets[_b];
        if (*_e) return *this;
        }
        _e = 0;
    }
    }
    return *this;
}

template<class T>
typename PtexDict<T>::const_iterator& PtexDict<T>::const_iterator::operator++(int)
{
    if (_e) {
    // move to next entry
    _e = &(*_e)->_next;
    if (!*_e) {
        // move to next non-empty bucket
        for (_b++; _b < _d->_numBuckets; _b++) {
        _e = &_d->_buckets[_b];
        if (*_e) return *this;
        }
        _e = 0;
    }
    }
    return *this;
}

template<class T>
typename PtexDict<T>::iterator PtexDict<T>::find(const char* key)
{
    int keylen, hashval;
    Entry** e = locate(key, keylen, hashval);

    if (e) return iterator( e, this, hashval & _bucketMask );
    else   return end();
}

template<class T>
typename PtexDict<T>::const_iterator PtexDict<T>::find(const char* key) const
{
    int keylen, hashval;
    Entry** e = locate(key, keylen, hashval);

    if (e) return const_iterator( e, this, hashval & _bucketMask );
    else   return end();
}

template<class T>
T& PtexDict<T>::operator[](const char* key)
{
    int keylen, hashval;
    Entry** e = locate(key, keylen, hashval);
    if (e) return (*e)->_val.second;

    // create a new entry
    _numEntries++;
    if (_numEntries*2 >= _numBuckets) grow();

    // allocate a buffer big enough to hold Entry + (the key length )
    // Note: the NULL character is already accounted for by Entry::_key's size
    void* ebuf = malloc( sizeof(Entry) + (keylen) * sizeof(char) );
    Entry* ne = new(ebuf) Entry; // note: placement new 

    // Store the values in the Entry structure
    Entry** slot = &_buckets[hashval & _bucketMask];
    ne->_next = *slot; *slot = ne;
    ne->_hashval = hashval;
    ne->_keylen = keylen;
    
    // copy the string given into the new location
    memcpy(ne->_key, key, keylen);
    ne->_key[keylen] = '\0';
    return ne->_val.second;
}


template<class T>
void PtexDict<T>::grow()
{
    if (!_buckets) {
    _numBuckets = 16;
    _bucketMask = _numBuckets - 1;
    _buckets = (Entry**) calloc(_numBuckets, sizeof(Entry*));
    } else {
    int newsize = _numBuckets * 2;
    _bucketMask = newsize - 1;
    Entry** newbuckets = (Entry**) calloc(newsize, sizeof(Entry*));
    for (int i = 0; i < _numBuckets; i++) {
        for (Entry* e = _buckets[i]; e;) {
        Entry* _next = e->_next;
        Entry** slot = &newbuckets[e->_hashval & _bucketMask];
        e->_next = *slot; *slot = e;
        e = _next;
        }
    }
    free(_buckets);
    _buckets = newbuckets;
    _numBuckets = newsize;
    }
}


template<class T>
bool PtexDict<T>::erase(const char* key)
{
    iterator iter = find(key);
    if (!iter) return false;

    erase(iter);
    return true;  // valid entry to remove
}


template<class T>
typename PtexDict<T>::iterator PtexDict<T>::erase(iterator iter)
{
    Entry** eptr = iter._e;
    if (!eptr) return iter;

    // patch around deleted entry
    Entry* e = *eptr;
    Entry* next = e->_next;
    if (!next) iter++;  // advance iterator if at end of chain
    *eptr = next;

    // destroy entry.  This is a strange destroy but is necessary because of
    // the way Entry() is allocated by using malloc above.
    e->~Entry(); // note: explicit dtor call
    free(e);     // free memory allocated.
    _numEntries--;

    return iter;
}


template<class T>
void PtexDict<T>::clear()
{
    for (iterator i=begin(); i != end(); i = erase(i));
    free(_buckets);
    _buckets = 0;
    _numEntries = 0;
    _numBuckets = 0;
}

#endif //PtexDict_h