How to return array from function

We want function which dynamically creates array of integers, so no static declaration is possible because we do not know how big array needs to be.

#include <stdio.h> #include <stdlib.h> int * allocator(int size) { int * array = malloc(size * sizeof(int)); printf ("%p\n", (void*)array); return array; } int main() { int * i = allocator(2); i[0] = 1; i[1] = 2; printf ("%d, %d\n", i[0], i[1]); printf ("%p\n", (void*)i); free(i); return 0; }

We print address of dynamically allocated array in function and in main to be sure it points to the same place and use it to show it is usable. We must use pointer to integer in main because expression

int i[] = allocator(2);

is illegal initializer. It doesn't prevent us from using pointer to integer later as array. Finally we free allocated memory. That what we did is called manual memory allocation and such memory is placed on heap. If we want to use pointer arithmetic we will do something like this:

*i = 1;
*(i + 1) = 2;
printf ("%d, %d\n", *i, *(i+1));

Please note that *(i + 1) is not the same as *i + 1 even if it produces the same output in our example. Dereferencing pointer got higher order of precedence than addition. Because of precedence we are using braces. What if we need two-dimensional array? Two-dimensional array is array of arrays and we will need pointer to pointer.

#include <stdio.h> #include <stdlib.h> int ** allocator(int columns, int rows) { int i; int ** array = malloc(rows * sizeof(int)); printf ("%p\n", (void*)array); for(i = 0; i < columns; i++) array[i] = malloc(columns * sizeof(int)); return array; } int main() { int ** i = allocator(2, 3), j; i[0][0] = 1; i[1][1] = 2; printf ("%d, %d\n", i[0][0], i[1][1]); printf ("%p\n",(void*)i); for(j = 0; j < 3; j++) free(i[j]); free(i); return 0; }

As we see allocating is more complicated and feeing also. It goes in two steps, first we allocate array of rows and after that we allocate arrays of columns. As in previous case we can use array syntax. Now we can go mixing pointer arithmetic and array syntax or go completely pointer arithmetic

*(array+i) = malloc(columns * sizeof(int)); … **i = 1; *(*(i+1)+1) = 2; … *i[0] = 1; *(i[1]+1) = 2; printf ("%d, %d\n", i[0][0], i[1][1]);

Maybe to add that *(*i+1) corresponds to i[0][1]. That was how to do it, now how not to do it. Going heroic and forcing through pointer to array as return type.

typedef int (*array_t)[]; array_t justdont() { static int array[] = { 0, 1}; return &array; } int (*fun())[] { static int array[] = { 0, 1}; return &array; } int main() { int* i = justdont(); printf ("%d, %d\n", i[0], i[1]); printf ("%p\n",(void*)i); i = fun(); printf ("%d, %d\n", i[0], i[1]); printf ("%p\n",(void*)i); return 0; }

This compiles and executes with few warnings, if we change fun return type by adding another pointer int* (*fun())[], that also works. If something looks difficult, like returning address of array, than design needs additional work. For example

int * justdont() { static int array[] = { 0, 1}; return array; }

this is much nicer and easy to understand. Please note that returning static array is perfectly fine and that we do not use free on it. Statically declared variables are allocated automatically and available through execution of program. If we forget to declare array as static than we will return dangling pointer, local variable goes out of scope and returned pointer points to who knows what.

Functions, pointers, nested functions, clojures

While ago GCC introduced nested functions which are allowing easy solution of funargs problem. With funargs problem solved C can accommodate closures and provide everything what different modern languages can, except funny syntax. In order to demonstrate that we need function pointers and they are not part of modern languages derived from C. So, we start with function pointers refresher.

Function pointers

They are more cryptic than other pointers and they scare away younger generations of programmers. We will declare function and pointer to it:

int add( int i, int j) { return i + j; } int main(){ int (*fptr)(int,int) = add; printf("%d\n", fptr(2, 3)); return 0; }

We have return type, variable name in brackets and type list for parameters. We could also use address of operator during assignment. How we pass it as parameter?

int execute(int (*fptr)(int,int), int a, int b) { return fptr(a, b); } printf("%d\n", execute(fptr, 2, 3));

How we return it, write function which is returning function pointer? There is user friendly way, we declare typedef for function pointer:

typedef int (*fptra)(int,int); fptra get() { return add; } printf("%d\n", get()(2, 3));

But there is also user unfriendly way:

int (*fptr2fptr())(int, int) { return add; } int (*fptr)(int,int) = fptr2fptr(); printf("%d\n", fptr(2, 3)); printf("%d\n", (*fptr2fptr())(2, 2));

Return type of return type goes in front, inside first pair of brackets name and own parameters, inside the second pair of brackets list of parameter types of return type. And just for those who value extreme programming above all, pointer to function which returns function which returns function:

int (*(*f2f2f())(void))(int,int){ return fptr2fptr; } int (*(*f2f)())(int,int) = f2f2f(); int (*fadd)(int,int) = f2f(); printf("%d\n",fadd(4, 3));

Nested Functions

Those are GCC specifics and they are just ordinary functions but inside another function. Standard C will not let you define function within function. To demonstrate we can do trampolining of one notoriously recursive function.

int factorial(int i){ int acc = 1; void * f() { if (i < 2) return 0; acc *= i; --i; return f; } while(f()) continue; return acc; } int main() { int i; for(i = 2; i < 14; i++) printf("%d! is %d\n", i, factorial(i)); return 0; }

Here nested function is accessing variables which are host scoped and returns self or NULL. We got whole function back but we are not really using it, except to exit while loop if it is NULL. To remedy that we will dispatch those nested functions out of host function.

struct closure{ int counter; int visited; } data; int (*pgen(int i))(int){ int increase(int k){ data.counter += k; data.visited++; return data.counter; } int decrease(int k){ data.counter -= k; data.visited++; return data.counter; } if(i) return increase; return decrease; } int main(){ data.counter = 4; data.visited = 4; int (*incr)(int) = (*pgen)(1); int (*decr)(int) = (*pgen)(0); printf("counter = %d visited = %d\n", data.counter, data.visited); printf("counter = %d\n", incr(2)); printf("counter = %d\n", decr(1)); printf("counter = %d visited = %d\n", data.counter, data.visited); printf("counter = %d\n", incr(4)); printf("counter = %d\n", decr(1)); printf("counter = %d visited = %d\n", data.counter, data.visited); return 0; }

Here we have struct which is global variable, it is not really closure but just named like that, and one function generator. If we pass zero to generator we get one function back and for non zero the other one. Both nested functions now operating on global variable. In previous example we were working on variables belonging to host function, in this case if we try the same we will have problems since host's variables went out of scope.

Funarg problem

This one is related to functional languages and nested functions. If we pass nested function as argument to another function that is called downward funarg problem. Returning nested function to caller is upwards funarg problem. If any of passed or returned functions references variable from scope of declarer, those must be available to nested function so it can be executed. Passing nested function as argument to another function is not problem in C since all local variables of declarer are alive.

void execute(void(*fptr)(int), int i){ fptr(i); } void print(int(*fptr)(void)){ printf("counter = %d\n", fptr()); } int main(){ int counter = 0; void increase(int k){ counter += k; } void decrease(int k){ counter -= k; } int getter(){ return counter; } execute(increase, 3); print(getter); execute(decrease, 2); print(getter); return 0; }

Returning nested function is more problematic because declarer went out of scope. That could be addressed like in Java, if anonymous function uses some declarer's variable, that variable must be final. In C there is even more options, we can use static variables or allocate them on the heap.

int (*pgen(int i))(int){ static int counter = 0; int increase(int k){ counter += k; return counter; } int decrease(int k){ counter -= k; return counter; } if(i) return increase; return decrease; } int main(){ int (*incr)(int) = (*pgen)(1); int (*decr)(int) = (*pgen)(0); printf("counter = %d\n", incr(2)); printf("counter = %d\n", decr(1)); printf("counter = %d\n", incr(4)); printf("counter = %d\n", decr(1)); return 0; }

It is easier to use static than malloc and free. Removing static from counter declaration will result in exception during execution of program. So, funargs problem is not problem for C in GCC version. This makes C almost functional language, functional with few extras.

Tests, pointers, arrays and GDB

While I was looking for work, actually I am still looking for work, they sent me to do some tests. Those are some “tech check” rubbish tests which are testing how much of man pages you know by hart. Not do you have logic of programmer and real working knowledge but how well have you memorized help files. So let me explain how you are going to deal with those test and real life problems in sensible way. While agile approach is very desirable in project management, memorizing help files is what industry expects from programmers. Everything further happens on Linux and we will do some debugging to find out answers.
About every book teaching C contains story how one can declare array and access array elements via pointer arithmetic. Something like this:

int arr1d[] = {1, 2, 3, 4, 5}, i; for(i=0;i<5;i++) printf("i = %d; %d = %d = %d\n", i, *arr1d+i, *(arr1d+i), arr1d[i]);

Expression *arr1d+i is not really pointer arithmetic since dereferencing will happen before addition, and everybody who worked in C longer than two weeks knows it, but it will also produce desired result. I also omitted array length and gcc managed to read it from initializer. Now we can declare some pointers and assign address of our array to them.

int *p1d = arr1d; for(i=0;i<5;i++) printf("i = %d; %d = %d\n", i, *(p1d+i), p1d[i]);

Array is just pointer to its first element, we got type and everything right. If we now take address of array we will have double pointer? Not really.

int **p1d12 = &arr1d;

Produces this warning:

warning: initialization from incompatible pointer type [enabled by default]

Since we do not know what is wrong, what type for pointer to array we are getting instead double pointer to integer, we will ask GDB. This is the code:

#include <stdio.h> int main(){ int arr1d[] = {1, 2, 3, 4, 5}, i; for(i=0;i<5;i++) printf("i = %d; %d = %d = %d\n", i, *arr1d+i, *(arr1d+i), arr1d[i]); int *p1d = arr1d; for(i=0;i<5;i++) printf("i = %d; %d = %d\n", i, *(p1d+i), p1d[i]); int **p1d12 = &arr1d; /* not really */ int *p1d11 = &arr1d[0]; return 0; }

and we will save it as untitled.c and build using

gcc -g -Wall -o untitled untitled.c
untitled.c: In function ‘main’:
untitled.c:12:16: warning: initialization from incompatible pointer type [enabled by default]
untitled.c:13:7: warning: unused variable ‘p1d11’ [-Wunused-variable]
untitled.c:12:8: warning: unused variable ‘p1d12’ [-Wunused-variable]

This is together with output. Switch -g means that we want debugg info and -Wall that we want all warnings. Now we start interactive session and ask GDB what we want to know:

gdb untitled GNU gdb (Ubuntu/Linaro 7.4-2012.04-0ubuntu2.1) 7.4-2012.04 Copyright (C) 2012 Free Software Foundation, Inc. … more advertising stuff … Reading symbols from ~/workshop/lrhw/untitled...done. (gdb) start Temporary breakpoint 1 at 0x4004fc: file untitled.c, line 4. Starting program: ~/workshop/lrhw/untitled Temporary breakpoint 1, main () at untitled.c:4 4 int arr1d[] = {1, 2, 3, 4, 5}, i; (gdb) info locals arr1d = {-6136, 32767, 4195877, 0, 1} i = 0 p1d = 0x0 p1d12 = 0x400410 p1d11 = 0x7fffffffe7f0 (gdb) next 5 for(i=0;i<5;i++) (gdb) info locals arr1d = {1, 2, 3, 4, 5} i = 0 p1d = 0x0 p1d12 = 0x400410 p1d11 = 0x7fffffffe7f0 (gdb) print arr1d $1 = {1, 2, 3, 4, 5} (gdb) print &arr1d $2 = (int (*)[5]) 0x7fffffffe6d0

It printed few lines of messages about license, where to report bugs and similar and loaded symbols for untitled. On prompt (gdb) we type in start and it starts and breaks on the first possible line. We try info locals and see that array is not initialized yet, so we execute next. Now array is initialized and we print it. Finally we ask it to print &arr1d and we learn what is the type of our “double pointer”.

int (*p1d12)[] = &arr1d;

This is what address of array returns and how “double pointer” should be declared, really ugly question on some idiotic test.
Things are becoming more interesting with multidimensional arrays. For example:

int arr2d[][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}};

We can not omit everything even if we are supplying initializer, just the first square bracket may be empty. How about asking some questions? Start GDB session and ask all what you need to know:

(gdb) print &arr2d $1 = (int (*)[2][4]) 0x7fffffffe630 (gdb) print &arr2d[0] $2 = (int (*)[4]) 0x7fffffffe630 (gdb) print &arr2d[1] $3 = (int (*)[4]) 0x7fffffffe640 (gdb) print *arr2d $4 = {1, 2, 3, 4} (gdb) x 0x7fffffffe640 0x7fffffffe640: 0x00000005 (gdb) print **arr2d $5 = 1 (gdb) print **arr2d+1 $6 = 2 (gdb) print **(arr2d+1) $7 = 5 (gdb) print *(*arr2d+1) $8 = 2

Simple as that. There is one more question left, what will happen with double pointer initialized to address of array, why it not working? Again we are agile and write code:

int arr2d[][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}}; int **p = arr2d; printf("*p = %d \n", *p);

That will execute and print *p = 1?! Start GDB session and check what is happening:

(gdb) p **p Cannot access memory at address 0x200000001 (gdb) p *p $1 = (int *) 0x200000001 (gdb) p sizeof(*p) $2 = 8 (gdb) p p $3 = (int **) 0x7fffffffe6e0 (gdb) x 0x7fffffffe6e0 0x7fffffffe6e0: 0x00000001 (gdb) x 0x7fffffffe6e4 0x7fffffffe6e4: 0x00000002 (gdb) x 0x7fffffffe6e8 0x7fffffffe6e8: 0x00000003 (gdb) p **arr2d $4 = 1 (gdb) p *arr2d $5 = {1, 2, 3, 4} (gdb) p sizeof(*arr2d) $6 = 16

Abbreviated print is p and x will print content of memory at some address. Array is not just pointer, there is size of it what counts. If we have used ld format in printf, we would see slightly bigger output than just one ;-)
That would be such lovely question for test, what would be output if we replace %d with %ld? Naturally it will be *p = 8589934593!
Ask yourself stupid questions for fun and for profit.