I have a shortestPath () function, which is a modified implementation of Dijkstra's algorithm for use with the game AI game I'm working on for my comp2 class. I made my way through the website and used gdb and valgrind. I know exactly where segfault happens (I actually knew that a few hours ago), but I can’t understand what causes undefined behavior or a logical error.
The function in which the problem occurs is called around 10x and works as expected until it executes GDB: msgstr "read error: cannot access memory" and valgrind: "Invalid read size 8"
Normally this would be enough, but I cannot work with it. Any general tips and advice are also welcome ... thanks!
GDB: https://gist.github.com/mckayryan/b8d1e9cdcc58dd1627ea
Valgrind: https://gist.github.com/mckayryan/8495963f6e62a51a734f
Here is the function in which segfault occurs:
static void processBuffer (GameView currentView, Link pQ, int *pQLen, LocationID *buffer, int bufferLen, Link prev, LocationID cur) { //printLinkIndex("prev", prev, NUM_MAP_LOCATIONS); // adds newly retrieved buffer Locations to queue adding link types appendLocationsToQueue(currentView, pQ, pQLen, buffer, bufferLen, cur); // calculates distance of new locations and updates prev when needed updatePrev(currentView, pQ, pQLen, prev, cur); <--- this line here qsort((void *) pQ, *pQLen, sizeof(link), (compfn)cmpDist); // qsort sanity check int i, qsortErr = 0; for (i = 0; i < *pQLen-1; i++) if (pQ[i].dist > pQ[i+1].dist) qsortErr = 1; if (qsortErr) { fprintf(stderr, "loadToPQ: qsort did not sort succesfully"); abort(); } }
and the function by which, after calling it, everything falls apart:
static void appendLocationsToQueue (GameView currentView, Link pQ, int *pQLen, LocationID *buffer, int bufferLen, LocationID cur) { int i, c, conns; TransportID type[MAX_TRANSPORT] = { NONE }; for (i = 0; i < bufferLen; i++) { // get connection information (up to 3 possible) conns = connections(currentView->gameMap, cur, buffer[i], type); for (c = 0; c < conns; c++) { pQ[*pQLen].loc = buffer[i]; pQ[(*pQLen)++].type = type[c]; } } }
So, I thought the pointer was redefined to the wrong address, but after a lot of printing in GDB, which seems to be wrong. I also spun around reading / writing to the variables in question to see who caused the error, and they all do it after appendLocationsToQueue (), but not earlier (or at the end of this function, for that matter).
Here is the rest of the relevant code: shortestPath ():
Link shortestPath (GameView currentView, LocationID from, LocationID to, PlayerID player, int road, int rail, int boat) { if (!RAIL_MOVE) rail = 0; // index of locations that have been visited int visited[NUM_MAP_LOCATIONS] = { 0 }; // current shortest distance from the source // the previous node for current known shortest path Link prev; if(!(prev = malloc(NUM_MAP_LOCATIONS*sizeof(link)))) fprintf(stderr, "GameView.c: shortestPath: malloc failure (prev)"); int i; // intialise link data structure for (i = 0; i < NUM_MAP_LOCATIONS; i++) { prev[i].loc = NOWHERE; prev[i].type = NONE; if (i != from) prev[i].dist = INF; else prev[i].dist = LAST; } LocationID *buffer, cur; // a priority queue that dictates the order LocationID are checked Link pQ; int bufferLen, pQLen = 0; if (!(pQ = malloc(MAX_QUEUE*sizeof(link)))) fprintf(stderr, "GameView.c: shortestPath: malloc failure (pQ)"); // load initial location into queue pQ[pQLen++].loc = from; while (!visited[to]) { // remove first item from queue into cur shift(pQ, &pQLen, &cur); if (visited[cur]) continue; // freeing malloc from connectedLocations() if (cur != from) free(buffer); // find all locations connected to buffer = connectedLocations(currentView, &bufferLen, cur, player, currentView->roundNum, road, rail, boat); // mark current node as visited visited[cur] = VISITED; // locations from buffer are used to update priority queue (pQ) // and distance information in prev processBuffer(currentView, pQ, &pQLen, buffer, bufferLen, prev, cur); } free(buffer); free(pQ); return prev; }