AlphabetMap.cpp

Go to the documentation of this file.

// AlphabetMap.cpp
//
//
// Copyright (c) 2002 Iain Murray
//

#include "AlphabetMap.h"

using namespace Dasher;
using namespace std;

alphabet_map::alphabet_map(unsigned int InitialTableSize)
        : HashTable(InitialTableSize<<1), Undefined(0) 
{
        Entries.reserve(InitialTableSize);
}


void alphabet_map::Add(const string& Key, symbol Value)
{
        RecursiveAdd(Key, Value, false);
}


void alphabet_map::RecursiveAdd(const string& Key, symbol Value, bool PrefixFlag)
{
        Entry*& HashEntry = HashTable[Hash(Key)];
        
        // Loop through Entries with the correct Hash value.
        for (Entry* i = HashEntry; i; i=i->Next) {
                if (i->Key==Key) {
                        if (PrefixFlag) {
                                // Just tagging - don't change symbol. Recurse if necessary
                                i->KeyIsPrefix = true;
                                if (Key.size()>1)
                                        RecursiveAdd(Key.substr(Key.size()-1), Undefined, true);
                        } else {
                                // Add symbol and leave
                                i->Symbol = Value;
                        }
                        return;
                }
        }
        
        // When hash table gets 1/2 full...
        // (no I haven't optimised when to resize)
        if (Entries.size()<<1 >= HashTable.size()) {
                // Double up all the storage
                HashTable.clear();
                HashTable.resize(Entries.size()<<2);
                Entries.reserve(Entries.size()<<1);
                
                // Rehash as the pointers will all be mangled.
                for (uint j=0; j<Entries.size(); j++) {
                        Entry*& HashEntry2 = HashTable[Hash(Entries[j].Key)];
                        Entries[j].Next = HashEntry2;
                        HashEntry2 = &Entries[j];
                }
                
                // Have to recall this function as the key's hash needs recalculating
                RecursiveAdd(Key, Value, PrefixFlag);
                return;
        }
        
        Entries.push_back(Entry(Key, Value, HashEntry));
        HashEntry = &Entries.back();
}


symbol alphabet_map::Get(const string& Key, bool* KeyIsPrefix) const
{
        // Loop through Entries with the correct Hash value.
        for (Entry* i = HashTable[Hash(Key)]; i; i=i->Next) {
                if (i->Key==Key) {
                        if (KeyIsPrefix!=0)
                                *KeyIsPrefix = i->KeyIsPrefix;
                        return i->Symbol;
                }
        }
        
        if (KeyIsPrefix!=0)
                *KeyIsPrefix = false;
        return Undefined;
}

---