On 2016-11-12 01:37 AM, Andrew Pinski wrote:
> On Fri, Nov 11, 2016 at 10:30 PM, nick <xerofoify@xxxxxxxxx> 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
>
>
Ok I will move it there but makes no sense at least from my understanding of C++. Shouldn't new overwrite that memory
with a null block or is new so stupid that it doesn't do this so I actually new to do this instead:
new Record*[N]():
Thanks,
Nick
>> 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
