On Fri, Nov 11, 2016 at 10:30 PM, nick <[email protected]> wrote:
> Greetings Gcc Folks,
> Either this is me doing something very simple in a school assignment for
> creating a basic hashtable
> or a compiler bug. I am currently seeing this error during my tables run on
> copy constructor call during
> the tester and have set to find out why it doesn't work. After some googling
> it seems either I am doing
> string pointer to string swaps.
This should have gone to gcc-help@ rather than here. This mailing
list is more for the automated emails from bugzilla.
Anyways I think the problem is you assume:
new Record*[N];
Will NULL out the array. It does not.
Thanks,
Andrew
> or it's a compiler bug. This is the error I am getting after running in gdb
> with backtrace:
> Program received signal SIGSEGV, Segmentation fault.
> 0x00007ffff7b769bb in std::__cxx11::basic_string<char,
> std::char_traits<char>, std::allocator<char>
> >::basic_string(std::__cxx11::basic_string<char, std::char_traits<char>,
> std::allocator<char> > const&) ()
> from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
> (gdb) backtrace
> #0 0x00007ffff7b769bb in std::__cxx11::basic_string<char,
> std::char_traits<char>, std::allocator<char>
> >::basic_string(std::__cxx11::basic_string<char, std::char_traits<char>,
> std::allocator<char> > const&) ()
> from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
> #1 0x00000000004067f6 in HashTable<int>::Record::getKey() const ()
> #2 0x00000000004060ee in HashTable<int>::HashTable(HashTable<int> const&) ()
> #3 0x0000000000403cab in main ()
> This is the complete code for the project:
> #include <string>
> #include <utility>
> #include<iostream>
> using namespace std;
> /*The functions I updated for Simple Table are
> 1.search
> 2.grow
> 3.update
> 4.Both Copy Constructor and Copy Assignment
> 5.Destructor
> */
> template <class TYPE>
> class Table {
> public:
> Table() {}
> virtual bool update(const string& key, const TYPE& value) = 0;
> virtual bool remove(const string& key) = 0;
> virtual bool find(const string& key, TYPE& value) = 0;
> virtual ~Table() {}
> };
>
> template <class TYPE>
> class SimpleTable :public Table<TYPE> {
>
> struct Record {
> TYPE data_;
> string key_;
> Record(const string& key, const TYPE& data) {
> key_ = key;
> data_ = data;
> }
>
> };
>
> Record** records_; //the table
> int max_; //capacity of the array
> int size_; //current number of records held
> int search(const string& key);
> void sort();
> void grow();
> public:
> SimpleTable(int maxExpected);
> SimpleTable(const SimpleTable& other);
> SimpleTable(SimpleTable&& other);
> virtual int numRecords();
> virtual bool isEmpty();
> virtual bool update(const string& key, const TYPE& value);
> virtual bool remove(const string& key);
> virtual bool find(const string& key, TYPE& value);
> virtual const SimpleTable& operator=(const SimpleTable& other);
> virtual const SimpleTable& operator=(SimpleTable&& other);
> virtual ~SimpleTable();
> };
>
>
> //returns index of where key is found.
> template <class TYPE>
> int SimpleTable<TYPE>::search(const string& key) {
> int rc = -1;
> for (int i = 0; i<size_; i++) {
> if (records_[i]->key_ == key) {
> rc = i;
> break;
> }
> }
> return rc;
> }
> //checks if array is empty
> template <class TYPE>
> bool SimpleTable<TYPE>::isEmpty(){
> return size_==0;
> }
> template <class TYPE>
> //return size of array
> int SimpleTable<TYPE>::numRecords(){
> return size_;
> }
> //sort the according to key in table
> template <class TYPE>
> void SimpleTable<TYPE>::sort() {
> int minIdx = 0;
> for (int i = 0; i<size_; i++) {
> minIdx = i;
> for (int j = i + 1; j<size_; j++) {
> if (records_[j]->key_ < records_[minIdx]->key_) {
> minIdx = j;
> }
> }
> Record* tmp = records_[i];
> records_[i] = records_[minIdx];
> records_[minIdx] = tmp;
> }
> }
>
> //grow the array by one element
> template <class TYPE>
> void SimpleTable<TYPE>::grow() {
> Record** newArray = new Record*[max_ + 1];
> max_ = max_ + 1;
> for (int i = 0; i<size_; i++) {
> newArray[i] = records_[i];
> }
> records_ = std::move(newArray);
> }
>
> /* none of the code in the function definitions below are correct. You can
> replace what you need
> */
> template <class TYPE>
> SimpleTable<TYPE>::SimpleTable(int maxExpected) : Table<TYPE>() {
> records_ = new Record*[maxExpected];
> max_ = maxExpected;
> size_ = 0;
> }
>
> template <class TYPE>
> SimpleTable<TYPE>::SimpleTable(const SimpleTable<TYPE>& other) {
> records_ = new Record*[other.max_];
> max_ = other.max_;
> size_ = 0;
> for (int i = 0; i<other.size_; i++) {
> update(other.records_[i]->key_, other.records_[i]->data_);
> }
> }
> template <class TYPE>
> SimpleTable<TYPE>::SimpleTable(SimpleTable<TYPE>&& other) {
> size_ = swap(other.size_);
> max_ = swap(other.max_);
> records_ = swap(other.records_);
> }
>
> template <class TYPE>
> bool SimpleTable<TYPE>::update(const string& key, const TYPE& value) {
> int idx = search(key);
> if (idx == -1) {
> if (size_ == max_) {
> grow();
> }
> records_[size_++] = new Record(key, value);
> for(int i=0;i<size_;i++) {
> if(records_[i]->key_ > records_[size_-1]->key_) {
> Record* tmp = records_[i];
> records_[i] = records_[size_-1];
> records_[i] = tmp;
> }
> }
> }
> else {
> records_[idx]->data_ = value;
> }
> return true;
> }
> template <class TYPE>
> bool SimpleTable<TYPE>::remove(const string& key) {
> int idx;
> idx=search(key);
> if(idx!=-1){
> delete records_[idx];
> for(int i=idx;i<size_-1;i++){
> records_[i]=records_[i+1];
> }
> size_--;
> return true;
> } else {
> return false;
> }
> }
> template <class TYPE>
> bool SimpleTable<TYPE>::find(const string& key, TYPE& value) {
> int idx = search(key);
> if (idx == -1) {
> return false;
> } else {
> value = records_[idx]->data_;
> return true;
> }
> }
>
> template <class TYPE>
> const SimpleTable<TYPE>& SimpleTable<TYPE>::operator=(const
> SimpleTable<TYPE>& other) {
> if (this != &other) {
> if(records_){
> delete[] records_;
> }
> records_ = new Record*[other.max_];
> max_ = other.max_;
> size_ = 0;
> for (int i = 0; i<other.size_; i++) {
> update(other.records_[i]->key_,
> other.records_[i]->data_);
> }
>
> }
> return *this;
> }
> template <class TYPE>
> const SimpleTable<TYPE>& SimpleTable<TYPE>::operator=(SimpleTable<TYPE>&&
> other) {
> swap(records_, other.records_);
> swap(size_, other.size_);
> swap(max_, other.max_);
> return *this;
> }
> template <class TYPE>
> SimpleTable<TYPE>::~SimpleTable() {
> if (records_) {
> int sz=size_;
> for(int i=0;i<sz;i++){
> remove(records_[0]->key_);
> }
> }
> }
>
> template <class TYPE>
> class HashTable :public Table<TYPE> {
> // This is the internal structure for array elements for hastable
> struct Record {
> TYPE data_; // data per array element
> string key_;//key to lookup for data element
> Record* next_; // next record to create linkly linked
> list for bucketing
> // Constructor to set values of Record
> Record(const string key, const TYPE data) {
> key_ = key;
> data_ = data;
> next_=nullptr;
> }
> //empty Constructor that sets values to empty safe
> state
> Record(){
> key_="";
> data_=0;
> next_=nullptr;
> }
> //Returns key of Record
> string getKey() const {
> return key_;
> }
> //Sets key of Record
> string setKey(string key) {
> key_=key;
> }
> //Returns data member of Record
> TYPE getData() const {
> return data_;
> }
> //Sets data member of Record
> void setData(TYPE data) {
> data_=data;
> }
> //Gets next element in linked list for bucketing
> Record *getNext() const {
> return next_;
> }
> //Sets next element in linked list for bucketing
> void setNext(Record *next) {
> next_ = next;
> }
>
> };
>
> Record** table_; //the table
> int size_;//size_
> int cap;//max number of records allowed in table
> std::hash<std::string> hash;//hash function used
>
> public:
> HashTable(int maxExpected);
> HashTable(const HashTable& other);
> HashTable(HashTable&& other);
> int numRecords();
> bool isEmpty();
> virtual bool update(const string& key, const TYPE& value);
> virtual bool remove(const string& key);
> virtual bool find(const string& key, TYPE& value);
> virtual const HashTable& operator=(const HashTable& other);
> virtual const HashTable& operator=(HashTable&& other);
> virtual ~HashTable();
> };
> /* none of the code in the function definitions below are correct. You can
> replace what you need
> */
> //returns size of table
> template <class TYPE>
> int HashTable<TYPE>::numRecords() {
> return size_;
> }
> //returns if hashtable has no records been inserted
> template <class TYPE>
> bool HashTable<TYPE>::isEmpty(){
> return size_==0;
> }
> //Constructor that allocates memory equal to passed amount in maxExpected and
> sets hashtable to empty state
> template <class TYPE>
> HashTable<TYPE>::HashTable(int maxExpected) : Table<TYPE>() {
> int size_=0;
> table_=new Record*[maxExpected]();
> cap=maxExpected;
> }
> //Copy Constructor that creates a copy of passed hashtable as argument to
> create a new copy of including memory allocations
> template <class TYPE>
> HashTable<TYPE>::HashTable(const HashTable<TYPE>& other) {
> table_ = new Record*[other.cap];
> size_=other.size_;
> hash = other.hash;
> cap=other.cap;
> for(int i=0;i<cap;i++){
> if(other.table_==nullptr){
> continue;
> }
> string key=other.table_[i]->getKey();
> table_[i]->key_=key;
> TYPE data=other.table_[i]->getData();
> table_[i]->setData(data);
> }
> }
> //Move constructor that moves the hashtable passed into the current table
> being constructed
> template <class TYPE>
> HashTable<TYPE>::HashTable(HashTable<TYPE>&& other) {
> swap(size_,other.size_);
> swap(cap,other.cap);
> swap(table_,other.records_);
> swap(hash,other.hash);
> }
> //Updates record with the string passed to the new data for the record's data
> element and returns true if found/updated otherwise false
> template <class TYPE>
> bool HashTable<TYPE>::update(const string& key, const TYPE& value) {
> int hashvalue=hash(key)%cap;
> Record* prev=nullptr;
> Record* entry=table_[hashvalue];
>
> while (entry != nullptr && entry->getKey() != key) {
> prev=entry;
> entry=entry->getNext();
> }
>
> if (entry == nullptr) {
> entry = new Record(key, value);
> if (prev == nullptr) {
> // insert as first bucket
> table_[hashvalue] = entry;
> } else {
> prev->setNext(entry);
> }
> } else {
> // just update the value
> entry->setData(value);
> }
> size_++;
> return true;
> }
> //Removes the record with the string passed for the key value and returns
> true if removed otherwise false if not found
> template <class TYPE>
> bool HashTable<TYPE>::remove(const string& key) {
> int hashValue = hash(key)%cap;
> Record *prev = nullptr;
> Record *entry = table_[hashValue];
>
> while (entry != nullptr && entry->getKey() != key) {
> prev = entry;
> entry = entry->getNext();
> }
>
> if (entry == nullptr) {
> // key not found
> return false;
> }
> else {
> if (prev == nullptr) {
> // remove first bucket of the list
> table_[hashValue] = entry->getNext();
> } else {
> prev->setNext(entry->getNext());
> }
> delete entry;
> }
> size_--;
> return true;
> }
> //Finds value in table and updates with the value passed if found returns
> true otherwise false
> template <class TYPE>
> bool HashTable<TYPE>::find(const string& key, TYPE& value) {
> int hashValue = hash(key)%cap;
> Record* entry =table_[hashValue];
> while (entry != nullptr) {
> if (entry->getKey() == key) {
> value=entry->getData();
> return true;
> }
> entry = entry->getNext();
> }
> return false;
> }
> //Copy Assignment Operator creates copy of hashtable passed into current
> hashtable
> template <class TYPE>
> const HashTable<TYPE>&HashTable<TYPE>::operator=(const HashTable<TYPE>&
> other) {
> if (table_) {
> delete[] table_;
> }
> table_ = new Record*[other.cap];
> size_=other.size_;
> hash = other.hash;
> cap=other.cap;
> for(int i=0;i<cap;i++){
> if(other.table_==nullptr){
> continue;
> }
> string key=other.table_[i]->getKey();
> table_[i]->key_=key;
> TYPE data=other.table_[i]->getData();
> table_[i]->setData(data);
> }
> return *this;
> ;
>
> }
> //Moves Assignment Operator which moves passed hashtable into current
> hashtable
> template <class TYPE>
> const HashTable<TYPE>& HashTable<TYPE>::operator=(HashTable<TYPE>&& other) {
> swap(size_,other.size_);
> swap(table_,other.table_);
> swap(hash,other.hash);
> swap(cap,other.cap);
> return *this;
>
> }
> //Destructor this destroys the hashtable when it goes out of scope or is
> called directly
> template <class TYPE>
> HashTable<TYPE>::~HashTable() {
> // destroy all buckets one by one
> for (int i = 0; i < cap; ++i) {
> Record *entry = table_[i];
> while (entry != nullptr) {
> Record *prev = entry;
> entry = entry->getNext();
> delete prev;
> }
> table_[i] = nullptr;
> }
> // destroy the hash table
> delete [] table_;
> }
> G++ Version/Toolchain used as with gcc -v:
> Using built-in specs.
> COLLECT_GCC=/usr/bin/g++
> COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/5/lto-wrapper
> Target: x86_64-linux-gnu
> Configured with: ../src/configure -v --with-pkgversion='Ubuntu
> 5.4.0-6ubuntu1~16.04.4' --with-bugurl=file:///usr/share/doc/gcc-5/README.Bugs
> --enable-languages=c,ada,c++,java,go,d,fortran,objc,obj-c++ --prefix=/usr
> --program-suffix=-5 --enable-shared --enable-linker-build-id
> --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix
> --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu
> --enable-libstdcxx-debug --enable-libstdcxx-time=yes
> --with-default-libstdcxx-abi=new --enable-gnu-unique-object
> --disable-vtable-verify --enable-libmpx --enable-plugin --with-system-zlib
> --disable-browser-plugin --enable-java-awt=gtk --enable-gtk-cairo
> --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-5-amd64/jre --enable-java-home
> --with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-5-amd64
> --with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-5-amd64
> --with-arch-directory=amd64 --with-ecj-jar=/usr/share/java/eclipse-ecj.jar
> --enable-objc-gc --enable-multiarch --disable-werror --with-arch-32=i686
> --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib
> --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu
> --host=x86_64-linux-gnu --target=x86_64-linux-gnu
> Thread model: posix
> gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.4)
> Huge Thanks for any help,
> Nick
