Bus Error

[deiwid]

Hallo

ich muss ein programm online abgeben. lokal funktioniert alles jedoch wenn ich es online abgebe und der ein unit test durchgeführt wird kommt der fehler bus error. und ich kann diesen fehler nicht finden. bitte um hilfe.

#ifndef EXTHASHING_H
#define EXTHASHING_H

#include <iostream>
#include <cmath>
#include "Container.h"

template<typename E>
class ExtHashing: public Container<E> {

	class Bucket {
	public:
		int noKeys;
		int bucketDepth;
		E** keys;
		bool visited;

		Bucket(int size) {
			noKeys = 0;
			bucketDepth = 0;
			keys = new E*[size];
			visited = false;
		}

		~Bucket() {
			for (int i = 0; i < noKeys; i++) {
				delete keys[i];
			}

			delete[] keys;
		}
	};

	int directoryDepth;
	int bucketSize;
	size_t noKeys;

	Bucket ** directory;

	void init(int directoryDepth, int bucketSize);
	void add_(const E& key);
	void moveKeys(Bucket * oldBucket, Bucket * newBucket);
	void doubleDirectory();
	unsigned long calculatePosition(const E& key, int depth) const;
	E* getKeys() const;
	void mergeSort(E keys[], size_t n, Order order) const;
public:
	class Exception;

	ExtHashing<E> ();
	ExtHashing<E> (int depth, int bucketsize);
	virtual ~ExtHashing<E> ();

	using Container<E>::add;
	virtual void add(const E keys[], size_t size);

	using Container<E>::remove;
	virtual void remove(const E keys[], size_t size);

	virtual bool member(const E& key) const;
	virtual size_t size() const;
	virtual bool empty() const;

	virtual size_t apply(const Functor<E>& f, Order order = dontcare) const;

	virtual E min() const;
	virtual E max() const;

	virtual std::ostream& print(std::ostream &o) const;
};

template<typename E>
ExtHashing<E>::ExtHashing() {
	init(1, 4);
}

template<typename E>
ExtHashing<E>::ExtHashing(int depth, int bucketSize) {
	init(depth, bucketSize);
}

template<typename E>
ExtHashing<E>::~ExtHashing() {
	int size = (int) pow(2, directoryDepth);

	Bucket * tmpBucket;

	// alle buckets löschen
	for (int i = 0; i < size; i++) {
		if (directory[i]) {
			tmpBucket = directory[i];

			for (int j = i; j < size; j++) {
				if (directory[j] == tmpBucket) {
					directory[j] = 0;
				}
			}

			delete tmpBucket;
		}
	}

	// directory löschen
	delete[] directory;
}

template<typename E>
void ExtHashing<E>::init(int depth, int bucketSize) {
	this->directoryDepth = depth;
	this->bucketSize = bucketSize;

	int size = (int) pow(2, depth);

	// directory erstellen
	directory = new Bucket*[size];

	// leeren bucket erstellen
	Bucket * newBucket = new Bucket(bucketSize);

	// directory einträge auf leeren bucket zeigen lassen
	for (int i = 0; i < size; i++) {
		directory[i] = newBucket;
	}

	noKeys = 0;
}

template<typename E>
unsigned long ExtHashing<E>::calculatePosition(const E& key, int depth) const {
	// position im directory berechnen (dafür werden depth-anzahl bits verwendet)
	return hashValue(key) % (1 << depth);
}

template<typename E>
void ExtHashing<E>::moveKeys(Bucket * oldBucket, Bucket * newBucket) {
	int newIndex = 0;
	oldBucket->bucketDepth++;

	for (int i = 0; i < oldBucket->noKeys; i++) {

		// ungerade keys in neuen bucket verschieben
		if (hashValue(*oldBucket->keys[i]) & (1 << oldBucket->bucketDepth - 1)) {
			newBucket->keys[newIndex] = oldBucket->keys[i];
			oldBucket->keys[i] = 0;
			newIndex++;
		}
	}

	newBucket->noKeys = newIndex;
	newBucket->bucketDepth = oldBucket->bucketDepth;

	// lücken im alten bucket füllen
	for (int i = 0, flag = 0; i < bucketSize && flag == 0; i++) {
		if (oldBucket->keys[i] == 0) {
			int j;

			for (j = i + 1; j < bucketSize; j++) {
				if (oldBucket->keys[j] != 0) {
					break;
				}
			}

			if (j < bucketSize) {
				oldBucket->keys[i] = oldBucket->keys[j];
				oldBucket->keys[j] = 0;
			} else {
				flag = 1;
			}
		}
	}

	oldBucket->noKeys -= newIndex;
}

template<typename E>
void ExtHashing<E>::add_(const E& key) {
	Bucket * tmpBucket = directory[calculatePosition(key, directoryDepth)];

	if (tmpBucket->noKeys < bucketSize) {
		// platz ist frei => key kann eingefügt werden
		tmpBucket->keys[tmpBucket->noKeys] = new E(key);
		tmpBucket->noKeys++;
	} else {
		if (tmpBucket->bucketDepth == directoryDepth) {
			// directory muss verdoppelt werden
			doubleDirectory();
		}

		Bucket * newBucket = new Bucket(bucketSize);

		// bucket splitten
		moveKeys(tmpBucket, newBucket);

		// neuen bucket ins directory hängen
		directory[calculatePosition(*newBucket->keys[0], directoryDepth)]
				= newBucket;

		// ziel bucket für neuen key suchen
		tmpBucket = directory[calculatePosition(key, directoryDepth)];

		// key einfügen
		tmpBucket->keys[tmpBucket->noKeys] = new E(key);
		tmpBucket->noKeys++;
	}
}

template<typename E>
void ExtHashing<E>::doubleDirectory() {
	int size = (int) pow(2, directoryDepth);

	Bucket **tmpDirectory = new Bucket*[size];

	// altes directory kopieren
	for (int i = 0; i < size; i++) {
		tmpDirectory[i] = directory[i];
	}

	// altes directory löscehn
	delete[] directory;

	// neues vergrößertes directory erstellen
	directory = new Bucket*[size * 2];

	// zeiger in neues directory kopieren
	for (int i = 0; i < size; i++) {
		directory[i] = tmpDirectory[i];
		directory[size + i] = tmpDirectory[i];
	}

	// globale tiefer erhöhen
	directoryDepth++;

	// temporäres directory löschen
	delete[] tmpDirectory;
}

template<typename E>
void ExtHashing<E>::add(const E keys[], size_t size) {
	for (size_t i = 0; i < size; i++) {
		if (!member(keys[i])) {
			add_(keys[i]);
			noKeys++;
		}
	}
}

template<typename E>
void ExtHashing<E>::remove(const E keys[], size_t size) {
	int directorySize = (int) pow(2, directoryDepth);

	Bucket *tmpBucket = 0;

	for (size_t i = 0; i < size; i++) {

		if (member(keys[i])) {

			for (int d = 0; d < directorySize; d++) {
				tmpBucket = directory[d];

				for (int j = 0; j < tmpBucket->noKeys; j++) {
					if (*tmpBucket->keys[j] == keys[i]) {
						delete tmpBucket->keys[j];

						// lücken im bucket füllen
						for (int k = j; k < (tmpBucket->noKeys - 1); k++) {
							tmpBucket->keys[k] = tmpBucket->keys[k + 1];
						}

						tmpBucket->noKeys--;
						noKeys--;
						break;
					}
				}
			}
		}
	}
}

template<typename E>
bool ExtHashing<E>::member(const E& key) const {
	int size = (int) pow(2, directoryDepth);

	Bucket *tmpBucket = 0;

	for (int i = 0; i < size; i++) {
		tmpBucket = directory[i];

		for (int j = 0; j < tmpBucket->noKeys; j++) {
			if (*tmpBucket->keys[j] == key) {
				return true;
			}
		}
	}

	return false;
}

template<typename E>
bool ExtHashing<E>::empty() const {
	return noKeys == 0;
}

template<typename E>
size_t ExtHashing<E>::size() const {
	return noKeys;
}

template<typename E>
E ExtHashing<E>::min() const {
	if (size() == 0) {
		throw typename Container<E>::Exception("ExtHashing::min(): empty");
	}

	E* keys = getKeys();
	mergeSort(keys, size(), ascending);

	// kleinster key an erster stelle
	E minKey = keys[0];

	delete[] keys;

	return minKey;
}

template<typename E>
E ExtHashing<E>::max() const {
	if (size() == 0) {
		throw typename Container<E>::Exception("ExtHashing::min(): empty");
	}

	E* keys = getKeys();
	mergeSort(keys, size(), descending);

	// größter key an erster stelle
	E maxKey = keys[0];

	delete[] keys;

	return maxKey;
}

template<typename E>
std::ostream& ExtHashing<E>::print(std::ostream &o) const {
	int size = (int) pow(2, directoryDepth);

	Bucket *tmpBucket = 0;

	for (int i = 0; i < size; i++) {

		o << i << ": ";

		tmpBucket = directory[i];

		for (int j = 0; j < tmpBucket->noKeys; j++) {
			if (tmpBucket->keys[j] != 0) {
				o << *tmpBucket->keys[j] << " ";
			}
		}

		o << std::endl;
	}

	return o;
}

template<typename E>
size_t ExtHashing<E>::apply(const Functor<E>& f, Order order) const {

	size_t cnt = 0;

	E* keys = getKeys();

	if (order != dontcare) {
		// keys sortieren
		mergeSort(keys, size(), order);
	}

	// functor für alle keys aufrufen
	for (size_t i = 0; i < size(); i++) {
		cnt++;

		if (f(keys[i]) == false) {
			break;
		}
	}

	delete[] keys;

	return cnt;
}

/**
 * Alle Keys als Array holen
 */
template<typename E>
E* ExtHashing<E>::getKeys() const {
	E* keys = new E[size()];

	int size = (int) pow(2, directoryDepth);
	size_t cnt = 0;
	Bucket * tmpBucket;

	for (int i = 0; i < size; i++) {
		directory[i]->visited = false;
	}

	for (int i = 0; i < size; i++) {
		tmpBucket = directory[i];

		// jeder bucket darf nur einmal durchlaufen werden
		if (tmpBucket->visited == false) {

			for (int j = 0; j < tmpBucket->noKeys; j++) {
				if (tmpBucket->visited == false) {
					keys[cnt] = *tmpBucket->keys[j];
					cnt++;
				}
			}

			tmpBucket->visited = true;
		}
	}

	return keys;
}

template<typename E>
void ExtHashing<E>::mergeSort(E keys[], size_t n, Order order) const {
	size_t i, j, k;

	if (n < 2) {
		return;
	}

	// elemente in erste hälfte
	size_t f = n / 2;

	// beide hälfte rekursiv sortieren
	mergeSort(keys, f, order);
	mergeSort(keys + f, n - f, order);

	// mergen

	// temp array für sortierte keys
	E *s = new E[n];

	for (i = 0, j = f, k = 0; i < f && j < n;) {
		s[k++] = (((order == ascending) && !(keys[i] > keys[j])) || ((order
				== descending) && (keys[i] > keys[j]))) ? keys[i++] : keys[j++];
	}

	while (i < f) {
		s[k++] = keys[i++];
	}

	while (j < n) {
		s[k++] = keys[j++];
	}

	for (i = 0; i < n; i++) {
		keys[i] = s[i];
	}

	delete[] s;
}

[knivil]

Vielleicht liegt es nicht an dir ...

[Dravere]

1. Was heisst "online abgeben"? Ich verstehe darunter irgendwie nichts, was einen Unit-Test auslöst und dann einen Bus Error.
2. Du erwartest nicht wirklich, dass wir deinen ganzen Quellcode durchgehen und einen Fehler suchen, den du nicht mal richtig beschreibst? Und das alles ohne Bezahlung? Ja wo sind wir hier denn? lol

Grüssli

[SeppJ]

Ich schließe mich meinen Vorrednern an, dass sich das niemand durchlesen wird. Aber zumindest den Begriff "bus error" kann ich erklären: Es wird auf eine nicht existierende Speicheraddresse zugegriffen. Das hat im Prinzip die gleiche Ursache wie ein segmentation fault: Es wird ein falsch gesetzter (oder ungesetzter) Pointer dereferenziert. Nur dass dieser beim segmentation fault auf eine existierende aber verbotene Adresse verweist, beim bus error aber zufällig auf eine nicht existierende.

Zur Ursachenforschung: Verwende ein Speicheranalysewerkzeug (z.B. valgrind) oder einen Debugger und suche damit den Ort des Fehlers. Wenn du den Ort des Fehlers hast und immer noch nicht weiterweißt, dann kann man dir hier weiterhelfen.