CODEWITHSUNDEEP
objective-ccarrays
RL2000
RL2000

Reputation: 1011

C memory management with 2D arrays

I'm starting to play around with some C code within Objective-C programs. The function I'm trying to write sorts all of the lat/long coordinates from a KML file into clusters based on 2D arrays.

I'm using three 2D arrays to accomplish this:

NSUInteger **bucketCounts refers to the number of CLLocationCoordinate2Ds in a cluster.

CLLocationCoorindate2D **coordBuckets is an array of arrays of coordinates

NSUInteger **bucketPointers refers to an index in the array of coordinates from coordBuckets

Here's the code that is messing me up:

//Initialize C arrays and indexes
int n = 10;
bucketCounts = (NSUInteger**)malloc(sizeof(NSUInteger*)*n);
bucketPointers = (NSUInteger**)malloc(sizeof(NSUInteger*)*n);
coordBuckets = (CLLocationCoordinate2D **)malloc(sizeof(CLLocationCoordinate2D*)*n);

for (int i = 0; i < n; i++) {
    bucketPointers[i] = malloc(sizeof(NSUInteger)*n);
    bucketCounts[i] = malloc(sizeof(NSUInteger)*n);
}
NSUInteger nextEmptyBucketIndex = 0;
int bucketMax = 500;

Then for each CLLocationCoordinate2D that needs to be added:

//find location to enter point in matrix
int latIndex = (int)(n * (oneCoord.latitude - minLat)/(maxLat-minLat));
int lonIndex = (int)(n * (oneCoord.longitude - minLon)/(maxLon-minLon));

//see if necessary bucket exists yet. If not, create it.
NSUInteger positionInBucket = bucketCounts[latIndex][lonIndex];
if (positionInBucket == 0) {
    coordBuckets[nextEmptyBucketIndex] = malloc(sizeof(CLLocationCoordinate2D) * bucketMax);
    bucketPointers[latIndex][lonIndex] = nextEmptyBucketIndex;
    nextEmptyBucketIndex++;
}

//Insert point in bucket.
NSUInteger bucketIndex = bucketPointers[latIndex][lonIndex];
CLLocationCoordinate2D *bucketForInsert = coordBuckets[bucketIndex];
bucketForInsert[positionInBucket] = oneCoord;
bucketCounts[latIndex][lonIndex]++;
positionInBucket++;

//If bucket is full, expand it.
if (positionInBucket % bucketMax == 0) {
    coordBuckets[bucketIndex] = realloc(coordBuckets[bucketIndex], (sizeof(CLLocationCoordinate2D) * (positionInBucket + bucketMax)));
}

Things seem to be going well for about 800 coordinates, but at the same point a value in either bucketCounts or bucketPointers gets set to an impossibly high number, which causes a reference to a bad value and crashes the program. I'm sure this is a memory management issue, but I don't know C well enough to troubleshoot it myself. Any helpful pointers for where I'm going wrong? Thanks!

Upvotes: 0

Views: 147

Answers (2)

uesp
uesp

Reputation: 6204

Two problems I see:

  • You don't initialize bucketCounts[] in the given code. It may well happen to all 0s but you should still initialize it with calloc() or memset():

    bucketCounts[i] = calloc(n, sizeof(NSUInteger));

  • if oneCoord.latitude == maxLat then latIndex == n which will overflow your arrays which have valid indexes from 0 to n-1. Same issue with lonIndex. Either allocate n+1 elements and/or make sure latIndex and lonIndex are clamped from 0 to n-1.

In code using raw arrays like this you can solve a lot of issues with two simple rules:

  1. Initialize all arrays (even if you technically don't need to).
  2. Check/verify all array indexes to prevent out-of-bounds accesses.

Upvotes: 1

David K
David K

Reputation: 3132

It seems to me each entry in bucketPointers can potentially have its own "bucket", requiring a unique element of coordBuckets to hold the pointer to that bucket. The entries in bucketPointers are indexed by bucketPointers[latIndex][lonIndex], so there can be n*n of them, but you allocated only n places in coordBuckets.

I think you should allocate for n*n elements in coordBuckets.

Upvotes: 1

Related Questions