Translate

Chủ Nhật, 4 tháng 12, 2016

Function pointer and Callback

Created by ThangVu.

Function address in C

Program is a set of binary instruction that computer can understand execute. The executed program is called a process. Each process will be allocated for 4GB virtual memory. In general, there are 4 main parts of memory, that stores different component of a process. 
  • Text segment: stores binary image of the program
  • Data segment: stores static and global variables
  • Heap: allocates dynamic memory
  • Stack: local variables 
Let's look deeper into text segment:

The binary image of a program is a set of instructions. The length of instruction is based on processor architecture. For example we have 4-byte instructions. A function is a subset of instructions, for example, we have a function from instruction #3 to instruction #6 (address 108 to 120). So, we have the address of this function is the smallest address of its instructions (i.e. 108). 

Definition of function pointer

Function pointer is a pointer that points to the address of a function.

Define a function pointer

To define a function pointer, we use following statement

?
1
typename (*function_pointer_name)(arguments)

For example:
?
1
2
Char (*getname)(int ID);
Int (*calculate)(int a, int b);
Dont be confused between pointer function and function returning a pointer.
?
1
2
Char (*getName)(int ID);  //This is a function pointer, return a character
Char *getName(int ID);    //This is a function, return char*

Assign a function address to a function pointer

We can simply assign a function address to a function pointer by its function name, which is the short way (Most of compilers support this assignment) . However, we should use the precise form with '&' operator to get the function address. Be noted that function pointer and function to be pointed should have the same prototype. 

For example: 
?
1
2
3
4
5
6
7
void print_name(char *name){ puts(name); }
 
void main(){
     void (*p_print_name)(char *);
     p_print_name = print_name;  //short form
     p_print_name = &print_name; //precise form
}
In line #6, function pointer p_print_name points to address of function print_name.

Call a function pointer

?
1
2
3
4
5
6
7
int get_double(int a){ return a*2; }
 
void main(){
     int (*p_get_double)(int);
     p_get_double = &get_double;
     int result = *p_get_double(2); //equal get_double(2);
}
After assigning function pointer p_get_double to the address of get_double, we can use the function pointer to pass argument as get_double function.

Return a function pointer

We can also return a function pointer.
For example:
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int add(int a, int b){
     return a + b;
}
 
int sub(int a, int b){
     return a - b;
}
 
int (*get_opcode(char opcode))(int, int){
     if(opcode == '+'){
           return &add;
     }
     else{
           return &subl
     }
}
 
void main(){
     int (*p_get_opcode)(int, int);
     p_get_opcode = get_op_code('+');
     (*p_get_opcode)(1, 2);
}
In line #9 of the above example function get_opcode checks its argument (opcode), and returns address of function add or sub (which have two int argument and return a int value). However this statement is a little messy. We can make it more clearly by using typedef as follows.
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int add(int a, int b){
     return a + b;
}
 
int sub(int a, int b){
     return a - b;
}
 
typedef int (*t_opcode)(int, int)
 
t_opcode get_opcode(char opcode){
     if(opcode == '+'){
           return &add;
     }
     else{
           return &sub
     }
}
 
void main(){
     int (*p_get_opcode)(int, int);
     p_get_opcode = get_opcode('+');
     (*p_get_opcode)(1, 2);
}

Callback

Callback is to use a function pointer as a parameter to pass a function. 
For example: in stdlib.h, a quicksort function is declare with the following prototype:

?
1
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*);
with 

  • base: pointer to the first element of the array to be sort
  • nitems: number of item to be sort pointed by base
  • size: size of each item
  • compar: function that compares two elements
How to use qsort in our work.
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <stdlib.h>
#define N 5
int compare(const void *a, const void *b) {
 return ( *(int*)a  >  *(int*)b);
}
int main() {
 int i = 0;
 int arr[N] = {2, 6, 4, 3, 5};
 qsort(arr, N, sizeof(int), compare);
 for(i = 0; i < N; i++){
  printf("%d\t", arr[i]);
 }
 return 0;
}
Output: 2 3 4 5 6

To understand how to implement Callback, following example illustrates a bubble sort algorithm with two selections of order (increase and decrease). 
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void swap(int *a, int *b) {
 int c = *a;
 *a = *b;
 *b = c;
}
 
int* bubble_sort(int *number, int count, int (*sort_order)(int a, int b)) {
 int i = 0, j = 0;
 int *result = (int *)malloc(count * sizeof(int));
 memcpy(result, number, count * sizeof(int));
 
 
 for (i = 0; i < count; i++) {
  for (j = i + 1; j < count; j++)
  {
   if (sort_order(result[i], result[j]) > 0) {
    swap(&result[i], &result[j]);
   }
  }
 }
 return result;
}
 
int increase_order(int a, int b) {
 return a - b;
}
int decrease_order(int a, int b) {
 return b - a;
}
 
void print_result(int *result, int count) {
 int i;
 for (i = 0; i < count; i++) {
  printf("%d\t", result[i]);
 }
 printf("\n");
}
 
int main(int argc, char *argv[]) {
 int count = argc - 1;
 int *number = (int *) malloc(count * sizeof(int));
 int i;
 for (i = 0; i < count; i++) {
  number[i] = atoi(argv[i + 1]);
 }
 int *result = (int *) malloc(count * sizeof(int));
 result = bubble_sort(number, count, increase_order);
 print_result(result, count);
 result = bubble_sort(number, count, decrease_order);
 print_result(result, count);
 return 0;
}
Explanation: 
  • swap() function: swaps two elements
  • bubble_sort() function: sorts an integer array, its order is controlled by a function pointer *sort_order(int a, int b). This function pointer returns true (returned value >0) or false (returned value <= 0) based on the comparison between its argument (a, b).
  • increase_order() and decrease_order() functions return the comparison between their arguments.
  • print_result() function: print the sorted array.
  • At main function, we pass increase_order and decrease_order as arguments for the bubble_sort function. 
Output:  
?
1
2
3
$/sort 5 1 4 6 2
$ 1 2 4 5 6
$ 6 5 4 2 1

Discussion: 
Obviously, the selection of order in bubble sort can be implemented by the other way. We can use an integer flag to represent the order. However, the advantage of using callback is that our work can be extended and maintained more easily. The reason is we can write another function as a criterion of order, we do not have to modify inside content of bubble sort function as using a integer flag. Especially, when we work with library, we might not have permission to enter source file of a function. 
Good instruction for this topic: 
Function pointer
Người đăng:

Không có nhận xét nào:

Đăng nhận xét

Đăng ký: Đăng Nhận xét (Atom)