Main Page | Class Hierarchy | Compound List | File List | Compound Members | File Members

strtable Class Reference

This class implements a string table. More...

#include <strtable.h>

Inheritance diagram for strtable:

Inheritance graph
[legend]
Collaboration diagram for strtable:

Collaboration graph
[legend]
List of all members.

Public Member Functions

 strtable (unsigned int size, pool *p)
void dealloc ()
 ~strtable ()
STRING find_string (STRING item, Boolean insert=TRUE)
 Search for the string in the string table.

STRING find_string (const char *str, Boolean insert=TRUE)
unsigned int get_percent_alloced (void)
unsigned int get_max_list (void)
void pr (FILE *fp=stdout)
 Print the contents of the string table.

STRING first (void)
 The functions first and get_item are used to iterate through the string table.

STRING get_str (void)
 get_str is used to iterate through the string table.


Private Member Functions

STRING * new_item (STRING str)
 Allocate a new STRING, plus the associated storage for the string.


Private Attributes

unsigned int table_size
unsigned int hash_slot
LIST< STRING * >::handle list_handle
sparse_array< chain_elem > * hash
pool * alloc_pool

Detailed Description

This class implements a string table.

The string table consists of unique strings, which are null terminated. The strings that are managed by the string table are contained in the STRING class.

This class was originally a generic template (HASH) for building hash tables. However, this template uses other templates (e.g., the sparse_array and LIST templates). C++ compilers (especially the HP C++ compiler) tend to have trouble with nested templates. So this class has been changed to be a specific class, instead of a template.

Definition at line 56 of file strtable.h.

Constructor & Destructor Documentation

strtable::strtable (  unsigned int  size,
pool *  p
)  [inline]
 

Definition at line 96 of file strtable.h.

References alloc_pool, sparse_array< chain_elem >::get_total_size(), hash, NULL, and table_size. 

00097     {
00098 
00099         assert( p != NULL );
00100         alloc_pool = p;
00101         hash = new sparse_array<chain_elem>( (const unsigned int)size );
00102         table_size = hash->get_total_size();
00103     }

strtable::~strtable (   )  [inline]
 

Definition at line 110 of file strtable.h.

References dealloc(). 

00111     {
00112         dealloc();
00113     }

Member Function Documentation

void strtable::dealloc (  void   )  [inline]
 

Definition at line 104 of file strtable.h.

References sparse_array< chain_elem >::dealloc(), and hash.

Referenced by ~strtable(). 

00105     {
00106         hash->dealloc();
00107 
00108         delete hash;
00109     }

STRING strtable::find_string (  const char *  str,
Boolean  insert = TRUE
)  [inline]
 

Definition at line 117 of file strtable.h.

References find_string(), and STRING::SetText(). 

00118     {
00119         STRING local_str;
00120         
00121         local_str.SetText( str );
00122         return find_string( local_str, insert );
00123     } // find_item with a char * argument

STRING strtable::find_string (  STRING  item,
Boolean  insert = TRUE
) 
 

Search for the string in the string table.

Definition at line 65 of file strtable.C.

References STRING::GetText(), hash, hash_services::hash_value(), sparse_array< chain_elem >::insert(), new_item(), NULL, sparse_array< chain_elem >::probe(), STRING::SetText(), and table_size.

Referenced by symtable::enter_sym(), find_string(), symtable::find_sym(), and sym_scope::LookupFromScope(). 

00066 {
00067     STRING * pVal;
00068     STRING RetStr;
00069     unsigned int ix, val;
00070 
00071     val = hash_value( item.GetText() );
00072     // table size should always be a power of 2, so
00073     // table_size - 1 is likely to be a prime.
00074     ix = val % (table_size - 1);
00075     if (! insert) {  // insert == FALSE
00076 
00077         if (! hash->probe( ix )) { 
00078             pVal = NULL;
00079         }
00080         else {
00081             pVal =  (*hash)[ ix ].search_list( item );
00082         }
00083     }
00084     else { // insert == TRUE
00085         if (! hash->probe( ix ) ) {
00086 
00087             hash->insert( chain_elem(), ix );
00088 
00089             pVal = new_item( item );
00090             (*hash)[ix].list.add( pVal );
00091         }
00092         else {
00093             pVal = (*hash)[ix].search_list( item );
00094             if ( pVal == NULL) {
00095                 pVal = new_item( item );
00096                 (*hash)[ix].list.add( pVal );
00097             }
00098         }
00099     }
00100 
00101     if (pVal == NULL) {
00102         RetStr.SetText( NULL );
00103     }
00104     else {
00105         RetStr = *pVal;
00106     }
00107     return RetStr;
00108 } // find_item with a STRING argument

STRING strtable::first (  void   )  [inline]
 

The functions first and get_item are used to iterate through the string table.

Note that the strings will be returned in hash order, which is pseudorandom. An example is shown below: 

      
      STRING str;

      for (str = strtab.first(); str.GetText() != NULL; str = strtab.get_str()) {
         printf("%s\n", str.GetText() );
      }

Definition at line 159 of file strtable.h.

References get_str(), hash_slot, list_handle, and NULL. 

00160     {
00161         hash_slot = 0;
00162         list_handle = NULL;
00163         return get_str();
00164     }

unsigned int strtable::get_max_list (  void   )  [inline]
 

Definition at line 128 of file strtable.h.

References hash, sparse_array< chain_elem >::probe(), table_size, and uint. 

00129     {
00130         uint i;
00131         uint max, len;
00132 
00133         max = 0;
00134         for (i = 0; i < table_size; i++) {
00135             if (hash->probe( i )) {
00136                 len = (*hash)[i].list_len();
00137                 if (len > max) {
00138                     max = len;
00139                 }
00140             }
00141         }
00142         return max;
00143     } // get_max_list

unsigned int strtable::get_percent_alloced (  void   )  [inline]
 

Definition at line 126 of file strtable.h.

References sparse_array< chain_elem >::get_percent_alloced(), and hash. 

00126 { return hash->get_percent_alloced(); }

STRING strtable::get_str (  void   ) 
 

get_str is used to iterate through the string table.

See strtable.h.

Definition at line 139 of file strtable.C.

References hash, hash_slot, list_handle, NULL, sparse_array< chain_elem >::probe(), STRING::SetText(), and table_size.

Referenced by first(). 

00140 {
00141     STRING local_str;
00142     STRING * pVal;
00143 
00144     local_str.SetText( NULL );
00145     pVal = &local_str;
00146 
00147     while (list_handle == NULL && hash_slot < table_size) {
00148         if (hash->probe( hash_slot )) {
00149             list_handle = (*hash)[hash_slot].list.first();
00150         }
00151         if (list_handle == NULL) {
00152             hash_slot++;
00153         }
00154     } // for
00155 
00156     if (list_handle != NULL && hash_slot < table_size) {
00157 
00158         pVal = (*hash)[hash_slot].list.get_item( list_handle );
00159 
00160         list_handle = (*hash)[hash_slot].list.next(list_handle);
00161 
00162         if (list_handle == NULL)
00163             hash_slot++;        
00164     }
00165 
00166     return *pVal;
00167 } // get_str

STRING * strtable::new_item (  STRING  str  )  [private]
 

Allocate a new STRING, plus the associated storage for the string.

Definition at line 41 of file strtable.C.

References alloc_pool, pool::GetMem(), STRING::GetText(), NULL, STRING::SetText(), and uint.

Referenced by find_string(). 

00042 {
00043     STRING *pStr;
00044     char *pStrCopy;
00045 
00046     pStrCopy = NULL;
00047     pStr = (STRING *)alloc_pool->GetMem( sizeof(STRING) );
00048 
00049     if (str.GetText() != NULL) {
00050         uint len;
00051 
00052         len = strlen( str.GetText());
00053         pStrCopy = (char *)alloc_pool->GetMem( len + 1 /* char for '\0' */ );
00054         strcpy( pStrCopy, str.GetText() );
00055     }
00056     
00057     pStr->SetText( pStrCopy );
00058     return pStr;
00059 } // new_item

void strtable::pr (  FILE *  fp = stdout  ) 
 

Print the contents of the string table.

Definition at line 114 of file strtable.C.

References hash, LIST< T >::list, NULL, STRING::pr(), sparse_array< chain_elem >::probe(), table_size, and uint. 

00115 {
00116     uint i;
00117 
00118     for (i = 0; i < table_size; i++) {
00119         if (hash->probe( i )) {
00120             LIST<STRING *>::handle h;
00121             STRING * pVal;
00122             
00123             for (h = (*hash)[i].list.first(); h != NULL; h = (*hash)[i].list.next(h)) {
00124                 // fprintf(fp, "hash_label::pr: i = %d, ", i );
00125                 pVal = (*hash)[i].list.get_item( h );
00126                 pVal->pr(fp);
00127                 fprintf(fp, "\n");
00128             } // for
00129         } // if
00130     } // for
00131 } // pr

Member Data Documentation

pool* strtable::alloc_pool [private]
 

Definition at line 90 of file strtable.h.

Referenced by new_item(), and strtable().

sparse_array<chain_elem>* strtable::hash [private]
 

Definition at line 89 of file strtable.h.

Referenced by dealloc(), find_string(), get_max_list(), get_percent_alloced(), get_str(), pr(), and strtable().

unsigned int strtable::hash_slot [private]
 

Definition at line 86 of file strtable.h.

Referenced by first(), and get_str().

LIST<STRING *>::handle strtable::list_handle [private]
 

Definition at line 87 of file strtable.h.

Referenced by first(), and get_str().

unsigned int strtable::table_size [private]
 

Definition at line 85 of file strtable.h.

Referenced by find_string(), get_max_list(), get_str(), pr(), and strtable().

The documentation for this class was generated from the following files:
Generated on Wed Mar 31 21:16:09 2004 for Data Structures for a VHDL Compiler by doxygen 1.3.3