GameTools gameHashTable

From Wikiid
Revision as of 21:39, 23 October 2007 by SteveBaker (Talk | contribs) (New page: Hash tables and Checksums are convenient ways to store bulk data in random order and yet retrieve it quickly. == gameHashTable == '''gameHashTable''' supports a table of key/value pairs....)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Hash tables and Checksums are convenient ways to store bulk data in random order and yet retrieve it quickly.


gameHashTable supports a table of key/value pairs. The 'value' can either be a 'void *' pointer or an integer. Use gameHashTable::getFreeKey() to get a guaranteed-unique key - or use gameHashTable::getFreeKeyBlock() to get a number of consecutive, unusued keys - it returns the first of that set. Alternatively, you can just make up your own keys - so long as they are unique. The gameChecksum method is an excellent way to do that. The remaining hash table functions are pretty obvious:

 class gameHashTable
    gameHashTable ( unsigned int size = DEFAULT_HASHTABLE_SIZE ) ;
   ~gameHashTable () ;
   int   getInt       ( unsigned int key ) ;
   void  add          ( unsigned int key, int val ) ;
   void *get          ( unsigned int key ) ;
   void  add          ( unsigned int key, void *data ) ;
   void  remove       ( unsigned int key ) ;
   unsigned int getFreeKeyBlock ( unsigned int numKeys ) ;
   unsigned int getFreeKey   () ;
 } ;


To calculate a virtually unique checksum for a text string, the most convenient method is to call:

 unsigned int getChecksum ( const char *s ) ;

...which is a reasonably fast 32 bit checksum generator for null-terminated strings. If you need to calculate the checksum of some other kind of data, you need to use the underlying class gameChecksum:

 class gameChecksum
   gameChecksum() ;
   void clear() ;
   void add ( const char *s ) ;
   void add ( const unsigned char *b, int length ) ;
   void add ( unsigned char b ) ;
   void add ( int            x ) ;
   void add ( bool           x ) ;
   void add ( short          x ) ;
   void add ( unsigned short x ) ;
   void add ( unsigned int   x ) ;
   void add ( signed char    x ) ;
   void add ( double         x ) ;
   void add ( float          x ) ;
   unsigned int get () ;
 } ;

The idea is to call gameChecksum::clear() (which is automatically done in the constructor function) to 'empty' the checksum generator, then call any of the gameChecksum::add(...) functions in any order and in any combination to add data that you'd like to be included into the check sum. When you are done, call gameChecksum::get() to get the resulting checksum code.

The checksum is guaranteed never to be zero - so you can safely use a zero checksum to flag error conditions in code that uses it. Whilst it is astronomically unlikely that two data structures (or strings or whatever) would generate the same result, it is possible that this could happen - so mission-critical code needs to check for this situation. A probability of one in four billion of a collision is good enough for many applications - but only a perfect checksum algorithm generates all codes with equal probability - so your odds are probably not that good.

Wikiid Pages relating to gameTools (edit)
gameTools - Main page
gameTools - Support Tools :
plb_to_ac3d, mklevel, mktile, mktree, tiled, autogen_java, mk3dgallery
gameTools - File Formats :
title_screen.rgb, ultimate.xml, material.xml, decoration.xml, physics.xml
tiled.xml, tiled_autotiles.xml, Level files, Tile naming scheme, PLB files
gameTools - Source Code :
Game functions: gameCamera, gameClock, gameChecksum/gameHashTable, gameHTTP,
gameIsect, gameJoystick, gameParticleManager, gameScreen/gameMouse,
gameSky, gameStarter, gameStrokeFont, gameUtils
Material database: MatList/MatEntry
Tile map handling: TileObject/MapFlag/MapEntry/Map
Java Interfacing: JavaLink
Image file loading: liImage/liImageFactory
3D Model file loading: loadPLB, PLB exporter
Physics: Sabot, Bullet, gameTools - Use with Blender, PLB exporter
Object management: Object

Wikiid Pages relating to Lemur of Lima (edit)
Lemur of Lima - Main page
Lemur of Lima - Controls
Lemur of Lima - Levels :
List of Levels, Level design, Screen shots, Models
Lemur of Lima - Java Plugins :
Java plugin API, Event handling, Flags, GameInterface API , Alphabetical Index
Lemur of Lima - Source Code Documentation :
Initialisation, Main Loop, gameTools