Extending hash tables - Introduction

4.2.2 Extending hash tables
Assumptions:
-
A hash function, h, exists.
-
If K is a key, then K’ = h(K) is a pseudokey.
File is structured into two levels
-
Leaves: contain (K, I(K)) (I(K) is the information associated with K)
Contains a header that stores the local depth
-
Directory: the record associated with K or a pointer to the record
Contains a header that stores the depth
Contains pointers to leaf pages
Example
The following figures explain the working of extendible hash structures.
Figure 1
Figure 2
Figure 3
4.2.3 Using GDBMCE library
The gdbmce.dll library exports all the functions to do the database operations. In Chapter 2 all the functions of GDBMCE was explained and all functions are ported on Windows CE platform. The .def (definition) file for the gdbmce dynamic link library exports the following functions which can be accessed by the pointers as discussed in the last model.
//GDBMCE .def file
LIBRARY GDBMCE
EXPORTS
gdbm_open
gdbm_close
gdbm_store
gdbm_fetch
gdbm_delete
gdbm_firstkey
gdbm_nextkey
gdbm_reorganize
gdbm_sync
gdbm_exists
gdbm_setopt
gdbm_errno
gdbm_version
Code snippets that are used to do the database operations using gdbmce.dll.
//Database variable
GDBM_FILE dbf;
//Variables to work with the database
datum key, content;
/*
datum is a data structure defined in gdbmce.h which has two important members. The first member of the structure is a pointer to character array while the next member of the character array is an integer which stores the number of elements in the character. Using this data structure the values are stored and retrieved from the database.
*/
//Define the function pointers to call the gdbm functions
typedef GDBM_FILE(*GDBMOpen_ptr)(WCHAR*,int,int,int,void*);
typedef void(*GDBMClose_ptr)(GDBM_FILE);
typedef int(*GDBMStore_ptr)(GDBM_FILE,datum,datum,int);
typedef datum(*GDBMFetch_ptr)(GDBM_FILE,datum);
//Instance to call the dll
HINSTANCE hInst1;
//Loading the engine dll
hInst1 = ::LoadLibrary(L"gdbmce.dll");
//Getting the function pointers of 4 GDBM functions
GDBMOpen_ptr pgdbm_open=(GDBMOpen_ptr)GetProcAddress(hInst1,L"gdbm_open");
GDBMClose_ptr pgdbm_close=(GDBMClose_ptr)GetProcAddress(hInst1,L"gdbm_close");
GDBMStore_ptr pgdbm_store=(GDBMStore_ptr)GetProcAddress(hInst1,L"gdbm_store");
GDBMFetch_ptr pgdbm_fetch=(GDBMFetch_ptr)GetProcAddress(hInst1,L"gdbm_fetch");
If the pointers (pgdbm_open. pgdbm_close, pgdbm_store, pgdbm_fetch) are NULL then the functions are not exported by the dynamic link library. It is always advisable to check whether the function pointers are NULL or not.
//Opening a database
//Database reader
dbf = (*pgdbm_open)(newstring,512,GDBM_READER,777,0);
newstring contains the name of the database to open. 512 specifies the block size in which the data will be accessed from the disc. GDBM_READER specifies that the database is to be opened in read mode. 777 defines the mode of the database file which means read, write and execute permission on the database file thus created. 0 refers to the default value that should be passed to the error function.
//Database writer
dbf = (*pgdbm_open)(newstring,512,GDBM_WRITER,777,0);
GDBM_WRITER specifies that the database is opened for writing. It also requires that the database should be present on the disc.
//Create a database
dbf = (*pgdbm_open)(newstring,512,GDBM_WRCREAT,777,0);
This will create a database if the database doesn’t exist and provide both a reader and writer for the database. *pgdbm_fetch reads the database and retrieves value corresponding to a given key value while *pgdbm_store writes into the database according to the key value thus provided.
//Storing into a database
Suppose there are two strings. The first string contains the key which is the tokenname (“0704” for example) and the second string which is epoch contains the epoch value corresponding to the key (“107” for example). Now to store the information into the database the following function will be used:
//Storing the key and its size into the datum structure
key.dptr = tokenname;
key.dsize = strlen(tokenname);
//Storing the value and its size to datum structure
content.dptr = epoch ;
content.dsize=strlen(epoch);
//Storing into the database after successful opening
(*pgdbm_store)(dbf, key, content, GDBM_INSERT);
Take a look at the GDBM_INSERT option on the function call. GDBM_INSERT parameter inserts the value corresponding to the key. If the key exists then the store operation will fail. GDBM_REPLACE is used in those cases where the key already exists and the value needs to be changed.
//Fetch pairs from the database
Suppose the epoch value corresponding to the token name (“0165179” for example) is to be fetched from a database that is opened successfully in GDBM_READ mode. The following code will be used to fetch the values:
//Storing the key and its size into the datum structure
key.dptr = tokenname;
key.dsize = strlen(tokenname);
//fetch the value corresponding to the key
content = (*pgdbm_fetch)(dbf,key);
//copy the content to a string called epoch
strcpy (epoch,content.dptr);
int epochval = atoi(epoch);
Thus as the operation completes, epochval will contain the integer value of the epoch string that is fetched from the database.
|