The hash storage class
I figured I'd share the storage class I'm using now. Little bit more overhead (2mb more overall) for 6 million tiles. Yet look ups are quicker. Total tiles size in memory is 86 mb (including bloat).
This class has a derived logic class as a higher layer in the program to act as an intermediary between data and SDL pixel drawing functions.
// HashNodeClass.hpp
class HashNodes { private: Sint32 p2b; Uint32 count; Sint32 idlookup; void resize(void); Sint32 const getIndex( Uint32 const & hashlookup ); std::vector<Tile> TileEntry; std::vector<Uint32> Hash; // find on hash, get o(1) lookup on tile. std::vector<Sint8> HasData; // -1 delete, 0 empty, 1 yes public: HashNodes(); virtual ~HashNodes();
bool insert(Tile const & tl,Uint32 const & x , Uint32 const & y ); bool remove (Uint32 const & hashlookup); Uint32 Count(void); Tile const * get (Uint32 const & hashlookup) ; void SortHash(void); };
High level summary:
1. On creation all 3 vectors are initialized to a power of 2 amount of entries in memory (128 to start with). 2. Insert pushes data onto the stack into each of the 3 vectors simultaneously. These entries are on a parallel index (VERY IMPORTANT). So, Tile[0] will always line up with Hash[0] value.
Tile entry - stores the tile class. Right now it just contains a color value and a few extra bytes to mimic the size of what I saw in Terraria memory format on one of those free server mods.
Hash - Value of the 1D location of the converted 2D (x,y). Necessary for binary search look ups.
Has data - This is used by the sort function to erase/ignore or check if data exists for retrieval.
3. Get() performs a binary search lookup on the sorted array against the hash value vector. When it finds a value that matches the 1d location of the tile requested, it returns the index of where the data was stored. Now the program performs an o(1) constant time look up to retrieve the tile and the hasdata.
4. Remove() sets values for deletion on the next sort.
5. SortHash() resorts all 3 vectors based on the hash values and erases any indexes that HasData equals -1.
6. Resize() - When the index amount on an insert surpasses pow(2,p2b) , it resizes all 3 arrays in memory to the next power of 2. Starting at 128 then 256 then 512. Etc.. For faster lookup on the binary searches.
Ran using this data structure last night. It takes about 30 seconds to load all 20,000,000 (2400x8400 map) into the same sized RGBA SDL surface for display.
I'm sure I have some more performance tweaks to make.
Then onto testing if this is faster then using a std::map.