, , , , , , ,

Consider the following function:

Screen Shot 2014-08-19 at 2.57.34 PM

The function takes an array and uses recursion to check if that array is in sorted order.  For example, an array containing: {1, 2, 3, 4} is in sorted (ascending) order.  So is the array: {2, 2}, or an array with only one element, such as: {0}.  But the array: {44, 3, 25, 88} is not.  A pretty simple, elegant, little function, right?  But, there is a potential danger.  Can you spot the problem?

I have been doing a lot of C programming for a project this summer (C is a customer requirement) and I have run across lots of libraries, and functions similar to the one above.  Namely, some function passing in an array, then iterating over the values of that array to print the contents or perform some computation over the elements.  In C, if you pass in an array as a function argument, you must also pass in the number of elements or size of the array.  Why?  In C, array parameters are treated as pointers and with out n, the size or number of elements contained in the array, we have no way of calculating the size of an array given its pointer.

A common mistake made by inexperienced C developers is to do:Screen Shot 2014-08-19 at 3.27.11 PM

That only works if you are dealing with arrays that are NOT received as parameters.  An array passed in as a parameter is treated as a pointer, the sizeof function will return the pointer’s size instead of the array’s.  Not what we want.

The potential danger of the function above, and consequently many functions that take in arrays (at least in C that I have noticed), is the assumption that the caller will do the right thing.   But accidents happen.  What happens when a caller passes in an array that is smaller than the size (e.g. isArrayInSortedOrder(A[2], 5) )?  We wind up exceeding the bounds of the array and crash the program and that belongs in the “bad things” category.

So how does one perform some form of sanity check when passing in an array and a size?  Don’t use C, use C++ or Java where array objects natively “know” their size?  Would if I could but customer constraint, remember?  Must be in C.  Convince the customer not to use C?  Fine, but what if you are developing on an embedded system?

Ok so we are stuck with C, a non-reflective language where objects don’t automatically know about themselves like their sizes.  One solution: we could write a macro to wrap the call, calculate the size of the native array before passing it in as a parameter, then adding our calculated size as a parameter.  That way, the caller would only need to pass in the array and not have to worry about getting the size right.  Something like the following:

Screen Shot 2014-08-19 at 3.55.00 PM

Notice the #define on line 15.  We name our wrapper function with one parameter in terms of our original but slightly modified array checking function.   The size of the native array is calculated first and then passed in as the second parameter, the int n.  One other note:  obviously a developer can see the original function declaration and there is nothing preventing the developer from calling that function directly bypassing my wrapped solution.  We would need to do a better job of “hiding” the original.  But for demonstration purposes, this will suffice.

In our modified implementation, we can add some sanity checks to deal with empty arrays or if n becomes a negative number for some weird reason:

Screen Shot 2014-08-19 at 4.02.30 PM

By wrapping our function in a macro, we simplify the implementation a bit for the user. They only have to pass in an array and the wrapper will calculate the size on behalf of the caller thus potentially minimizing our risk of passing in an incorrect array size.

To test our solution, we can do:

Screen Shot 2014-08-19 at 4.12.21 PM

Since array3 is empty, the above should print that the array is not sorted.  Change the array parameters and you should find that arrays 1, 2, and 4 should print that the arrays are sorted, while array 5 is not sorted.

An interesting little conundrum in C that I never really put much thought into until I started doing more intensive C programming projects.  I would be interested in hearing your thoughts on handling situations like the above, or others gotchas.  Feel free to drop me a line.  Until next time, we’ll C you later.