Operationen auf einer Linked List - Reallocation vom Speicherbereich

[hell-student]

Hallo Zusammen,

ich versuche gerade eine Doppelt verkette Liste zu implementieren, indem ich ein dynamisches Array verwende, wobei jedes Element einen Zeiger auf Vor- und Nachfolger hat. Dies hat den Zweck, dass ich nicht zur Laufzeit jedesmal malloc/calloc machen muss (aus Performance Gründen)

Hier mal mein Code:

TaskObj *task_objs = NULL;
unsigned int no_task_obj = 0;
#define INIT_NO_TASK_OBJ 10
static pthread_mutex_t unused_task_obj_mutex = PTHREAD_MUTEX_INITIALIZER;
TaskObj *unused_task_obj_h = NULL;
TaskObj *task_obj_h = NULL;
TaskObj *task_obj_t = NULL;

void init_task_objs() {
	task_objs = calloc(INIT_NO_TASK_OBJ, sizeof(TaskObj));
	no_task_obj = INIT_NO_TASK_OBJ;

	task_objs[0].successor = &task_objs[1];
	task_objs[0].predecessor = NULL;
	task_objs[0].id = 0;

	/* initialize all jobs */
	for (unsigned int i = 1; i < INIT_NO_TASK_OBJ - 1; i++) {
		task_objs[i].successor = &task_objs[i + 1];
		task_objs[i].predecessor = &task_objs[i - 1];
		task_objs[i].id = i;
	}

	task_objs[INIT_NO_TASK_OBJ - 1].successor = NULL;
	task_objs[INIT_NO_TASK_OBJ - 1].predecessor = &task_objs[INIT_NO_TASK_OBJ - 2];
	task_objs[INIT_NO_TASK_OBJ - 1].id = INIT_NO_TASK_OBJ - 1;

	/* set up list headers */
	unused_task_obj_h = &task_objs[0];
}

TaskObj* get_unused_task_obj() {
	/* extend task object array if the unused list is empty */
	pthread_mutex_lock(&unused_task_obj_mutex);
	if (!unused_task_obj_h) {
		unsigned int no_task_obj_tmp = no_task_obj;
		no_task_obj *= 2;
		task_objs = realloc(task_objs, sizeof(TaskObj) * no_task_obj);

		/* initialize all jobs */
		for (unsigned int i = no_task_obj_tmp; i < no_task_obj - 1; i++) {
			task_objs[i].successor = &task_objs[i + 1];
			task_objs[i].predecessor = &task_objs[i - 1];
			task_objs[i].id = i;
		}

		task_objs[no_task_obj - 1].successor = NULL;
		task_objs[no_task_obj - 1].predecessor = &task_objs[no_task_obj - 2];
		task_objs[no_task_obj - 1].id = no_task_obj - 1;

		unused_task_obj_h = &task_objs[no_task_obj_tmp];
		TaskObj *task_obj = unused_task_obj_h;
		unused_task_obj_h = unused_task_obj_h->successor;
		pthread_mutex_unlock(&unused_task_obj_mutex);
		return task_obj;
	}
	/* return first unused task object */
	else {
		TaskObj *task_obj = unused_task_obj_h;
		unused_task_obj_h = unused_task_obj_h->successor;
		pthread_mutex_unlock(&unused_task_obj_mutex);
		return task_obj;
	}

	return NULL;
}

TaskObj* get_task_obj(unsigned int id) {
	TaskObj *task_obj = unused_task_obj_h;
	if (task_obj) {
		if (task_obj->id == id) {
			return task_obj;
		}
		else {
			task_obj = task_obj->successor;
		}
	}

	return NULL;
}

void add_task_obj(TaskObj *task_obj) {
	if (!task_obj_h) {
		task_obj_h = task_obj;
		task_obj_t = task_obj;
		task_obj->successor = NULL;
		task_obj->predecessor = NULL;
	}
	else {
		task_obj_t->successor = task_obj;
		task_obj->predecessor = task_obj_t;
		task_obj->successor = NULL;
		task_obj_t = task_obj;
	}
}

Wenn ich nun folgendes aufrufe, würde ich gerne jedesmal einen "unbenutzes" Object aus dem Pool aller unbenutzen bekommen, dessen ID printen, sowie diesen in eine allgemeine double LL einfügen. Dies funktioniert sowohl beim einfügen am Ende (_h = Head, _t = TAIL). Jedoch habe ich das Problem bei einer Reallocation, also bei realloc().:

TaskObj *task_obj = get_unused_task_obj();
		printf("TASK_OBJ: %i of %i task objects\n", task_obj->id, no_task_obj);
		add_task_obj(task_obj);
		TaskObj *task_obj_tmp = task_obj_h;
		while (task_obj_tmp) {
			printf("%i ", task_obj_tmp->id);
			task_obj_tmp = task_obj_tmp->successor;
		}
		printf("\n");

Wenn nun also alle (initial 10) unbenutzte Tasks des Pool in meine double LL eingefügt wurden und somit der Pointer unused_task_obj_h = NULL ist, müsste sich die Array-Größe verdoppeln. Dies tut sie auch, jedoch ist mein TaskObjmit der ID 0 dann nicht mehr korrekt:

bei einfügen am TAIL:

0 1 2 3 4 5 6 7 8 9 -> 539989880 1 2 3 4 5 6 7 8 9 10

bei einfügen am HEAD:

9 8 7 6 5 4 3 2 1 0 -> 10 9 8 7 6 5 4 3 2 1 -2111113352

Irgendwie geht mir hier mein Pointer verloren.

Danke

EDIT:

Ich habe mir nun vor der Reallokation die ID des Head-Pointers gemerkt und nach der Reallokation wieder auf das entsprechende Element gesetzt. Ich denke durch die Reallokation bleibt mein Pointer des Heads ja immer noch auf dem Speicherbereich, auch wenn mein Array wo ganz anders im Speicher abgelegt wird. Könnte das stimmen?

also bisher funktioniert es nun und ich bekomme wie gewollt:

bei einfügen am TAIL:

0 1 2 3 4 5 6 7 8 9 -> 0 1 2 3 4 5 6 7 8 9 10