symtab_ty Class Reference
[Symtab]

#include <symtab.h>

Public Types
typedef void(*	callback_t )(const symtab_ty *stp, const nstring &key, void *data, void *arg)
typedef void(*	reaper_t )(void *)
Public Member Functions
	~symtab_ty ()
	symtab_ty (int suggested_size=5)
size_t	size () const
bool	empty () const
void	clear (void)
void *	query (string_ty *key) const
void *	query (const nstring &key) const
void *	query (const nstring_list &keys) const
string_ty *	query_fuzzy (string_ty *key) const
nstring	query_fuzzy (const nstring &key) const
void	assign (string_ty *key, void *value)
void	assign (const nstring &key, void *value)
void	assign_push (string_ty *key, void *value)
void	assign_push (const nstring &key, void *value)
void	remove (string_ty *key)
void	remove (const nstring &key)
void	dump (const char *caption) const
void	keys (string_list_ty *result) const
void	keys (nstring_list &result) const
void	walk (callback_t func, void *arg) const
void	set_reap (reaper_t func)
bool	valid () const
Private Member Functions
void	split (void)
	symtab_ty (const symtab_ty &)
symtab_ty &	operator= (const symtab_ty &)
Private Attributes
reaper_t	reap
row_t **	hash_table
str_hash_ty	hash_modulus
str_hash_ty	hash_mask
str_hash_ty	hash_load
Friends
class	symtab_iterator
Data Structures
struct	row_t

---

Detailed Description

The symtab_ty class is used to represent a symbol table. All data is referenced through void pointers. You may wish to use the template wrapper for type safety.

Definition at line 40 of file symtab.h.

---

Member Typedef Documentation

typedef void(* symtab_ty::callback_t)(const symtab_ty *stp, const nstring &key, void *data, void *arg)

typedef void(* symtab_ty::reaper_t)(void *)

---

Constructor & Destructor Documentation

symtab_ty::~symtab_ty

(

)

The destructor.

Note:

it isn't virtual, thou shalt not derive from this class.

symtab_ty::symtab_ty

(

int

suggested_size = 5

)

The constructor.

Parameters:

suggested_size

You are able to suggest how many rows will be in the table. It is better to under estimate than overestimate and waste memory. Optimal resizing happens automagically.

symtab_ty::symtab_ty

(

const symtab_ty &

)

[private]

The copy constructor. Do not use.

---

Member Function Documentation

size_t symtab_ty::size

(

)

const [inline]

The size method may be used to determine how many rows there are in the symbol table.

Definition at line 63 of file symtab.h.

bool symtab_ty::empty

(

)

const [inline]

The empty method may be used to determine if there symbol table is empty (i.e. there are no rows).

Definition at line 69 of file symtab.h.

void symtab_ty::clear

(

void

)

The clear method may be used to discard all rows of the symbol table. It is not an error if the symbol table is already empty.

Note:

This method has O(n) execution time.

void* symtab_ty::query

(

string_ty *

key

)

const

The query method may be used to search for a variable.

Parameters:

key

The row name to search for.

Returns:

If the variable has been defined, this method returns the pointer value assigned. If the variable has not been defined, it returns the NULL pointer.

Note:

This method has O(1) execution time. This method will eventually be DEPRECATED

void* symtab_ty::query

(

const nstring &

key

)

const

The query method may be used to search for a variable.

Parameters:

key

The row name to search for.

Returns:

If the variable has been defined, this method returns the pointer value assigned. If the variable has not been defined, it returns the NULL pointer.

Note:

This method has O(1) execution time.

void* symtab_ty::query

(

const nstring_list &

keys

)

const

The query method may be used to search for a variable.

Parameters:

keys

The row names to search for. The first found will be returned.

Returns:

If the variable has been defined, this method returns the pointer value assigned. If the variable has not been defined, it returns the NULL pointer.

string_ty* symtab_ty::query_fuzzy

(

string_ty *

key

)

const

The query_fuzzy method may be used to search for a variable.

Parameters:

key

The row name to search for.

Returns:

The NULL pointer if there is no row of that name and no row with a similar name, otherwise returns a pointer to the most similar name.

Note:

This method has O(n) execution time. This method will eventually be DEPRECATED

nstring symtab_ty::query_fuzzy

(

const nstring &

key

)

const

The query_fuzzy method may be used to search for a variable.

Parameters:

key

The row name to search for.

Returns:

The NULL pointer if there is no row of that name and no row with a similar name, otherwise returns a pointer to the most similar name.

Note:

This method has O(n) execution time.

void symtab_ty::assign	(	string_ty *	key,
		void *	value
	)

The assign method is used to assign a value to a given variable.

Parameters:

	key	They key (usually a variable name or simialar).
	value	The value to be assigned to that name.

Note:

The key is copied, the value pointed to is not.

If there is already a key of that name, the old data will be discarded, via the reap function, if one has been supplied.

This method has O(1) execution time. This method will eventually be DEPRECATED

void symtab_ty::assign	(	const nstring &	key,
		void *	value
	)

The assign method is used to assign a value to a given variable.

Parameters:

	key	They key (usually a variable name or simialar).
	value	The value to be assigned to that name.

Note:

The key is copied, the value pointed to is not.

If there is already a key of that name, the old data will be discarded, via the reap function, if one has been supplied.

This method has O(1) execution time.

void symtab_ty::assign_push	(	string_ty *	key,
		void *	value
	)

The assign_push function is used to assign a value to a given variable. Any previous value will be obscured until this one is removed with the remove method.

Parameters:

	key	They key (usually a variable name or simialar).
	value	The value to be assigned to that name.

Note:

The key is copied, the value pointed to is not.

This method has O(1) execution time. This method will eventually be DEPRECATED

void symtab_ty::assign_push	(	const nstring &	key,
		void *	value
	)

The assign_push function is used to assign a value to a given variable. Any previous value will be obscured until this one is removed with the remove method.

Parameters:

	key	They key (usually a variable name or simialar).
	value	The value to be assigned to that name.

Note:

The key is copied, the value pointed to is not.

This method has O(1) execution time.

void symtab_ty::remove

(

string_ty *

key

)

The remove method is used to remove a variable from the symbol table.

Parameters:

key

The name of the row to be removed.

Note:

The name is freed, the data is reaped. (By default, reap does nothing.)

This method has O(1) execution time. This method will eventually be DEPRECATED

void symtab_ty::remove

(

const nstring &

key

)

The remove method is used to remove a variable from the symbol table.

Parameters:

key

The name of the row to be removed.

Note:

The name is freed, the data is reaped. (By default, reap does nothing.)

This method has O(1) execution time.

void symtab_ty::dump

(

const char *

caption

)

const

The dump method is used to dump the contents of the symbol table.

Parameters:

caption

The caption will be used to indicate why the symbol table was dumped.

Note:

This function is only available when symbol DEBUG is defined.

This method has O(n) execution time.

void symtab_ty::keys

(

string_list_ty *

result

)

const

The keys method may be used to extract the list of row names from the symbol table.

Parameters:

result

Where to put the row names. It is cleared before any row names are placed in it. It is not sorted.

Note:

If you have used assign_push method, it is possible to have duplicates in they list of keys.

This method has O(n) execution time. This method will eventually be DEPRECATED

void symtab_ty::keys

(

nstring_list &

result

)

const

The keys method may be used to extract the list of row names from the symbol table.

Parameters:

result

Where to put the row names. It is cleared before any row names are placed in it. It is not sorted.

Note:

If you have used assign_push method, it is possible to have duplicates in they list of keys.

This method has O(n) execution time.

void symtab_ty::walk	(	callback_t	func,
		void *	arg
	)			const

The walk method is used to invoke a func tion for every row of the symbol table.

Parameters:

	func	A pointer to the function to be called.
	arg	An extra argument passed to the function.

Note:

This method has O(n) execution time.

void symtab_ty::set_reap

(

reaper_t

func

)

[inline]

The set_reap method is used to set the reaping function to be used on the data of row tables when they are remove()ed or assign()ed over.

Definition at line 332 of file symtab.h.

bool symtab_ty::valid

(

)

const

The valid method determines whether the symbol table's internal values are self consistent. Usually only used for debugging.

void symtab_ty::split

(

void

)

[private]

The split method is used to double the number of buckets in the symbol table, which results in halving the load. The symbols are then redistributed into the new buckets.

Note:

It is only sensable to do this when the symbol table load exceeds some reasonable threshold. A threshold of 80% is used.

The probablity of another split thus halves every time this method is called, resulting in overall O(1) behaviour because (sigma(2 ** -n) == 1).

symtab_ty& symtab_ty::operator=

(

const symtab_ty &

)

[private]

The assignment operator. Do not use.

---

Friends And Related Function Documentation

friend class symtab_iterator [friend]

Definition at line 407 of file symtab.h.

---

Field Documentation

reaper_t symtab_ty::reap [private]

The grim reaper. Default to NULL, i.e. nothing is done.

Definition at line 360 of file symtab.h.

row_t** symtab_ty::hash_table [private]

The hash_table instance variable is used to remember the base address of the array of buckets. On average, there will only be 0.5 to 0.8 rows per bucket.

Definition at line 375 of file symtab.h.

str_hash_ty symtab_ty::hash_modulus [private]

The hash_modulus instance variable is used to remember the size of the array of buckets. It is always a power of two.

Definition at line 381 of file symtab.h.

str_hash_ty symtab_ty::hash_mask [private]

The hash_mask instance variable is used to remember the bit mask used to place rows into buckets. Because hash_modulus is always a power of two, this mask will always be one less than the hash modulus; we cache it for efficiency.

Definition at line 389 of file symtab.h.

str_hash_ty symtab_ty::hash_load [private]

The hash_load instance variable is used to remember how many rows are present in the table.

Definition at line 395 of file symtab.h.

---

The documentation for this class was generated from the following file:

• common/symtab.h