00001 00002 #include <assert.h> 00003 #include <string.h> 00004 #include <stdio.h> 00005 #include "stdtypes.h" 00006 #include "blockpool.h" 00007 #include "pools.h" 00008 #include "str.h" 00009 #include "list.h" 00010 #include "hash_serv.h" 00011 #include "sparse.h" 00012 #include "strtable.h" 00013 00014 00018 STRING *strtable::chain_elem::search_list( STRING item ) 00019 { 00020 LIST<STRING *>::handle h; 00021 STRING *list_str, *str; 00022 00023 str = NULL; 00024 for (h = list.first(); h != NULL; h = list.next(h)) { 00025 list_str = list.get_item( h ); 00026 if ( strcmp(list_str->GetText(), item.GetText()) == 0 ) { 00027 str = list_str; 00028 break; 00029 } // if 00030 } // for 00031 00032 return str; 00033 } // search_list 00034 00035 00036 00041 STRING *strtable::new_item( STRING str ) 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 00060 00061 00065 STRING strtable::find_string( STRING item, Boolean insert /* = TRUE */) 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 00109 00110 00114 void strtable::pr(FILE *fp) 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 00132 00133 00134 00139 STRING strtable::get_str(void) 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 00168