0

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!

kyle k
  • 5,134
  • 10
  • 31
  • 45
RL2000
  • 913
  • 10
  • 20
  • These are **not** 2D arrays but only a simulation of them. C has just simple 2D arrays as a builtin feature. Why don't you use them? You seem to make your life artificially complicated. – Jens Gustedt Jun 27 '14 at 18:53
  • I've never seen a 2D array in C that could be allocated to a size determined at runtime. Admittedly the line `n = 10;` determines the size at compile time, but it hints that a runtime allocation is eventually desired. – David K Jun 27 '14 at 19:00
  • @DavidK - C89 did not, but C99 makes provision for this. ***[Look Here](http://stackoverflow.com/a/1677180/645128)*** – ryyker Jun 27 '14 at 19:08
  • If this were my code, however, I don't think I'd allocate n arrays of n elements each to make a single 2D array. I might allocate a single array of n*n elements to hold all the data, and then either allocate a single array of n pointers to access the individual rows within the n*n block of memory (analogous to the built-in 2D arrays) or write a function that I could call like tihs: `getSubscriptedElement(bucketCounts,i,j)`. – David K Jun 27 '14 at 19:08
  • 1
    It would help if this were a ***[short self contained correct example](http://www.sscce.org/)*** – ryyker Jun 27 '14 at 19:11
  • @ryyker: Good to hear about how C99 fixed this. Scratch all that old-style code from my last comment. It just goes to show how long ago I switched over to Java and C++ (after years of C experience, but all of it before C99). – David K Jun 27 '14 at 19:12

2 Answers2

1

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.

David K
  • 3,147
  • 2
  • 13
  • 19
  • I was trying to save some memory space by allocating the `coordBuckets` only when they were first called-- in the `if (positionInBucket == 0)` call. Maybe I'll try changing that. Thanks for the pointers-- clearly I have a lot to learn still about C. – RL2000 Jun 27 '14 at 20:39
  • The part with `if (positionInBucket == 0)` was OK as far as I saw--it is not the _buckets_ that you needed to allocate more of, it is just the list of _pointers_ to them--that is, the array `coordBuckets` itself, which you allocated on the fifth line of your posted code. – David K Jun 27 '14 at 20:55
  • Aha! That did it. I will spend a bit more time looking at memory allocation documentation. And cleaning up this code so it's not such a mess :-) – RL2000 Jun 27 '14 at 20:59
1

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.
uesp
  • 6,194
  • 20
  • 15