c++ - Segfault when trying to access a hash in a particular function -
so, i'm trying make simple hash data structure assignment. is, works except when try access remove function when try compare key in hash string passed reference function. segfault on compare , i've tried rewrite keep getting same segfault or compile error. i'm not sure don't have access when trying compare. can assume ->getkey have access in print function right below it.
#ifndef mystringmap_h #define mystringmap_h #include <iostream> #include <string> #include "abstractstringmap.h" using namespace std; const int base_size = 10; template <typename t> class hashentry { private: string m_key; t m_value; public: hashentry( string k , t v ) : m_key( k ), m_value( v ) {} string& getkey() { return m_key; } t& getvalue() { return m_value; } }; template <typename t> class mystringmap { private: hashentry<t> **m_table; int m_size; int hash( const string &s ) const; public: mystringmap() { m_table = new hashentry<t>*[base_size]; m_size = base_size; for( int = 0 ; < m_size ; ++i ) { m_table[i] = null; } } int size() const; bool isempty() const { return ( size() == 0 ); } const t& valueof( const string& key ) const; void clear(); void insert( const string& key , const t& val ); void remove( const string& k ); void print() const; }; template <typename t> int mystringmap<t>::hash( const string &s ) const { int hashval = 0; for( unsigned int = 0 ; < s.length() ; ++i ) { char c = s.at(i); hashval += int(c); } return hashval; } template <typename t> int mystringmap<t>::size() const { int s = 0; for( int = 0 ; < m_size ; ++i ) { if( m_table[i] != null ) { ++s; } } return s; } template <typename t> const t& mystringmap<t>::valueof( const string& key ) const { int hashval = hash( key ); hashval = hashval % m_size; while( m_table[hashval] != null && hash( m_table[hashval]->getkey() ) != hash( key ) ) { hashval = ( hashval + 1 ) % m_size; } if( m_table[hashval] == null ) { string err = "error [valueof] key not found."; throw err; } else { return m_table[hashval]->getvalue(); } } template <typename t> void mystringmap<t>::clear() { for( int = 0 ; < m_size ; ++i ) { if( m_table[i] != null ) { delete m_table[i]; } } delete m_table; m_table = new hashentry<t>*[base_size]; m_size = base_size; for( int = 0 ; < m_size ; ++i ) { m_table[i] = null; } return; } template <typename t> void mystringmap<t>::insert( const string& key , const t& val ) { if( size() >= m_size ) { int tempsize = m_size * 2; hashentry<t>** temp; temp = new hashentry<t>*[( m_size * 2 )]; for( int = 0 ; < m_size ; ++i ) { temp[i] = m_table[i]; } clear(); m_table = temp; m_size = tempsize; } int hashval = hash( key ); hashval = hashval % m_size; while( m_table[hashval] != null && hash( m_table[hashval]->getkey() ) != hash( key ) ) { hashval = ( hashval + 1 ) % m_size; } if( m_table[hashval] != null ) { delete m_table[hashval]; } m_table[hashval] = new hashentry<t>( key, val ); return; } template <typename t> void mystringmap<t>::remove( const string& k ) { int removeindex = -1; for( int = 0 ; < m_size ; ++i ) { if( hash( m_table[i]->getkey() ) == hash( k )) { removeindex = i; } } if( removeindex >= 0 ) { delete m_table[removeindex]; m_table[removeindex] = null; } return; } template <typename t> void mystringmap<t>::print() const { for( int = 0 ; < m_size ; ++i ) { if( m_table[i] != null ) { cout << endl << "< " << m_table[i]->getkey() << ", " << m_table[i]->getvalue() << " > "; } } cout << endl; return; } #endif as tester given:
#include <iostream> #include <string> #include "mystringmap.h" using namespace std; // -------------------------------------------------------------- void test0() { mystringmap<char> grades; cout << endl; cout << "--- test 0 ----" << endl; cout << "is empty? " << boolalpha << grades.isempty() << endl; cout << "size = " << grades.size() << endl; grades.insert("nate",'a'); grades.insert("george",'c'); grades.insert("karl",'f'); grades.insert("john",'b'); grades.insert("will",'b'); cout << endl; cout << "is empty? " << boolalpha << grades.isempty() << endl; cout << "size = " << grades.size() << endl; grades.print(); return; } // -------------------------------------------------------------- void test1() { mystringmap<string> thelist; cout << endl; cout << "--- test 1 ----" << endl; cout << "is empty? " << boolalpha << thelist.isempty() << endl; cout << "size = " << thelist.size() << endl; thelist.insert("fry","naughty"); thelist.insert("leela","naughty"); thelist.insert("hermes","naughty"); thelist.insert("qubert","naughty"); thelist.insert("zoidberg","nice"); thelist.insert("scruffy","naughty"); thelist.insert("bender","naughty"); thelist.insert("zapp","naughty"); thelist.insert("kiff","naughty"); thelist.insert("leela","nice"); cout << endl; cout << "is empty? " << boolalpha << thelist.isempty() << endl; cout << "size = " << thelist.size() << endl; thelist.print(); cout << endl; cout << "testing remove" << endl; cout << "removing non-humans" << endl; thelist.remove("leela"); thelist.remove("zoidberg"); thelist.remove("bender"); thelist.remove("kiff"); thelist.remove("nixon"); thelist.print(); cout << endl; cout << "testing lookup" << endl; try { cout << "fry? " << thelist.valueof("fry") << endl; cout << "hermes? " << thelist.valueof("hermes") << endl; cout << "qubert? " << thelist.valueof("qubert") << endl; cout << "nixon? "; cout << thelist.valueof("nixon") << endl; } catch (string s) { cout << "error : " << s << endl; } cout << endl; //cout << "end of test #1" << endl; return; } // -------------------------------------------------------------- // -------------------------------------------------------------- // -------------------------------------------------------------- int main () { cout << "map tester!!" << endl; test0(); test1(); //cout << "q?"; //cin.ignore(); //cin.get(); return 0; } the .h is:
#ifndef abstractstringmap_h #define abstractstringmap_h #include <iostream> #include <string> using namespace std; template < typename t > class abstractstringmap { public: /*** ---- accessor operations ---- */ // purpose: accessor function number of elements in map // returns: number of elements in map virtual int size() const = 0; // purpose: checks if map empty // returns: 'true' if map empty // 'false' otherwise virtual bool isempty() const = 0; // purpose: returns value associated key. // parameters: key of value found // returns: // if map contains key return value associated key. // if map not contains key throw something!!! virtual const t& valueof(const string& key) const = 0; /*** ---- mutator operations ---- */ // purpose: clears map // postconditions: empty map virtual void clear() = 0; // purpose: inserts element map // parameters: key , value added map // postconditions: map contains pair < key, value > // if map contains value associated key, // replace parameter val virtual void insert(const string& key, const t& val) = 0; // purpose: removes element map // parameters: k, key remove // postconditions: map not contains pair k key virtual void remove(const string& k) = 0; /*** ---- output operations ---- */ // purpose: prints map pretty formatting // no partucular order required. virtual void print() const = 0; /*** ---- utility functions operations ---- */ // purpose: hashes string integer. // shall use function hash-table. private: virtual int hash(const string &s) const = 0; }; #endif
the bug when resize table in insert copy pointers old table new table after call clear deletes same pointers.
the resize code in insert has bug because doesn't rehash entries, instead copies them same slots before though table size has changed. means after resizing table many of entries occupy wrong slots.
another bug in remove
if( hash( m_table[i]->getkey() ) == hash( k )) should be
if(m_table[i] != null && hash( m_table[i]->getkey() ) == hash( k )) but still leaves 'not comparing keys bug' (see comments), should be
if(m_table[i] != null && m_table[i]->getkey() == k) but yet bug version of remove makes no use of hashing, linear search through entire table.
i think there's bit of work on code.
Comments
Post a Comment