- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Directories
- Examples

# PtexImporter/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