I didn't look in great detail because there's no explanation of the algorithm you are using, but I did notice that you have several code blocks similar to the following:

    do {
        x = rand()%(maxx-1);
        y = rand()%(maxy-1);
    } while (map[x][y].visited != 0);

That code runs quickly when the map is mostly unvisited, but as the percentage of the map that has been visited increases, thean increasing number of iterations is required to locate an unvisited spot.

If your map is 1000 by 1000, there are 1,000,000 cells.  When you get down to the last 10 cells, you have a 1 in 100,000 chance of locating an empty cell with each guess.  You should devise a method of tracking used and unused cells separately so you can make a random pick in a single step.

**Edit:**
testEndMaze() may be another source of inefficiency.  Instead of searching every cell to see if it has been visited, can you keep count of cells as you visit them?  If so, then testEndMaze() is just comparing your current count of visited cells with the total number of cells in the maze.