This is the 12th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Pointers continue further

Continuation of “Advanced C: Advanced Pointers”

The callback function

Callback function definition

Callback functions: A function called through a function pointer, or a mechanism that calls a function using a function pointer, is called a callback function. Callbacks are not called directly by the implementor, but in response to special conditions.

The concept doesn’t matter, it’s more important to understand and skillfully use the method.

Quick sortqsort

qsortThe function logic
void qsort(void* base, size_t num, size_t width, int (*cmp)(const void* e1, const void* e2));
Copy the code

Qsort has no return value and takes four arguments. Base: start address, num: number of elements, width: size of elements, and compare: function. Can be compared with bubble sort.

// Bubble sort
void Bubble_sort(int arr[], int sz) {
	for (int i = 0; i < sz - 1; i++) { 
		for (int j = 0; j < sz - 1 - i; j++) { 
			// Compare functions
			if (arr[j] > arr[j + 1]) {
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp; }}}}Copy the code

Compared with bubble sort, bubble sort only needs the starting address and the number of elements, which implies other information. Because of excessive externalization, bubble sort can only sort integer arrays, and the comparison function is too simple to list separately.

Because qsort can be applied to various types of data such as floating point, character and custom type, it is impossible to specify the specific type, so it requires multiple parameters to describe the basic information of the element.

Qsort can accommodate multiple types of data because the void* base argument, along with num and width, describes any type.

Why is the base argument typed as void*? As shown in the following code.

char* p1 = &a;
// Types from int* to char* are incompatible
char* p2 = &f;
// Types from float* to char* are incompatible
void* p1 = &a;
void* p2 = &f;
Copy the code

Direct assignments between addresses of certain types indicate type incompatibilities, and forced conversions may result in loss of accuracy.

Therefore, void*, also known as the universal type, can receive any type of pointer, but cannot perform pointer operations (dereferencing, ±±± integer, etc.).

p1++;   *p1;   p1 - p2;   p1 > p2;// The expression must be a pointer to the full object type
Copy the code

  1. Base: start address for storing data. The type is defined as void* and can accept Pointers of any type.

  2. Num: number of elements to be sorted.

  3. Width: element width, in bytes.

We specify the starting position, number of elements, and size of elements, which seems to be enough. But you can’t sort all types, so you have to define an abstract comparison function that specifies how elements are compared.

  1. CMP: Comparison function that specifies how elements are compared.

    • elem1Less thanelem2, the return value is less than 0
    • elem1Is greater thanelem2, returns a value greater than 0
    • elem1Is equal to theelem2, the return value is 0

  2. Field 1, field 2: specifies the addresses of the two elements to be compared.

Qsort is half library and half custom. The last parameter of the function is the comparison function. The function is free internally, but the return value must return the corresponding value according to the stipulation.

summary

You need qsort to sort various types of data,

  • Therefore,baseThe start address cannot be a fixed pointer typevoid*.
  • Since this is a generic type, we need to explicitly compare the number and size of elements.
  • Finally, to sort the core of the comparison size, special comparison functions must be customized to accommodate different types of elements.
qsortImplement bubble sort
// Comparison function: integer
#include <stdlib.h>
int int_cmp(const void* e1, const void* e2) {
	return* (int*)e1 - *(int*)e2;
}
int main(a) {
	int arr[10] = { 9.8.7.6.5.4.3.2.1.0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), int_cmp);
	return 0;
}
Copy the code

The comparison function int_com takes no arguments and is called directly by qsort as a callback function. The parameter passing process of the comparison function is implemented internally by QSORT.

qsortImplement structure sorting
#include <stdlib.h>
struct stu {
	char* name;
	short age;
	float score;
};
// Sort by grade
int score_cmp(const void* e1, const void* e2) {
	/ / 1. Ascending
    return ((struct stu*)e1)->score - ((struct stu*)e2)->score;
	/ / 2. Descending order
    return ((struct stu*)e2)->score - ((struct stu*)e1)->score;
}
// Sort by name
int name_cmp(const void* e1,const void* e2) {
	return strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
}
int main(a) {
	struct stu s[3] ={{"Zhang".22.99.5 f}, {"Bill".21.66.4 f}, {"Fifty".18.80.1 f}};int sz = sizeof(s) / sizeof(s[0]);
	/ / 1.
    qsort(s, sz, sizeof(s[0]), name_cmp);
	/ / 2.
    qsort(s, sz, sizeof(s[0]), score_cmp);
	return 0;
}
Copy the code

As a result, a comparison function is extracted, and the specific exchange mode is implemented internally by QSORT.

Analog implementationqsort

Use qsort function logic to achieve bubble sort.

// Print the function
void print_arr(int arr[],int sz) {
	for (int i = 0; i < sz; i++) {
		printf("%d ", arr[i]); }}// Swap functions
void Swap(char* buf1, char* buf2, size_t width) {
	for (size_t i = 0; i < width; i++) {/ / width
		chartmp = *buf1; *buf1 = *buf2; *buf2 = tmp; buf1++; buf2++; }}// Compare functions
int cmp(const void* e1, const void* e2) {
	return* (int*)e1 - *(int*)e2;
}
// Sort function
void my_bubble_sort(void* base, size_t num, size_t width, int(*cmp)(const void* e1, const void* e2)) {
	for (size_t i = 0; i < num - 1; i++) {
		for (size_t j = 0; j < num - 1 - i; j++) {
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0) {// In bytes
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width); }}}}int main(a) {
	int arr[10] = { 9.8.7.6.5.4.3.2.1.0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	my_bubble_sort(arr, sz, sizeof(arr[0]), cmp);
	print_arr(arr, sz);

	return 0;
}
Copy the code

The address is strongly converted to char*, which is compared and exchanged in the smallest unit of a byte, making the code more universal.

If you need a sort structure, just replace my_qsort in the main function and Name_cmp in the comparison function in the previous code.

/ / 1.
my_qsort(s, sz, sizeof(s[0]), name_cmp);
/ / 2.
my_qsort(s, sz, sizeof(s[0]), score_cmp);
Copy the code

 

Pointer and array pen test parsing

Array discrimination

Pay attention to the point. The array name represents the entire array:

  1. Sizeof (array name)
  2. & array name

Otherwise, array names represent the address of the first element.

A one-dimensional array
int a[] = { 1.2.3.4 };
printf("%d\n".sizeof(a));/ / 16
printf("%d\n".sizeof(a + 0));/ / 4/8
printf("%d\n".sizeof(*a));/ / 4
printf("%d\n".sizeof(a + 1));/ / 4/8
printf("%d\n".sizeof(a[1]));/ / 4
printf("%d\n".sizeof(&a));/ / 4/8
printf("%d\n".sizeof(*&a));/ / 16
printf("%d\n".sizeof(&a + 1));/ / 4/8
printf("%d\n".sizeof(&a[0]));/ / 4/8
printf("%d\n".sizeof(&a[0] + 1));/ / 4/8
Copy the code

  1. The entire array is only as long as its name is inside sizeof.

    A plus 0 inside sizeof is the address of the first element plus 0.

  2. As long as it’s an address, it doesn’t matter what type of address it is it’s 4/8, right

    Sizeof (&a)=sizeof(int(*)[4])=4. Sizeof () evaluates the number of bytes taken up by a pointer rather than the sizeof dereference access.

  3. * and ampersand together cancel out.

    Sizeof (*&a), &a is the address type of the entire array int(*)[4], dereferenced int[4] is 16.

A character array
char arr[] = { 'a'.'b'.'c'.'d'.'e'.'f' };
printf("%d\n".sizeof(arr));/ / 6
printf("%d\n".sizeof(arr + 0));/ / 4/8
printf("%d\n".sizeof(*arr));/ / 1
printf("%d\n".sizeof(arr[1]));/ / 1
printf("%d\n".sizeof(&arr));/ / 4/8
printf("%d\n".sizeof(&arr + 1));/ / 4/8
printf("%d\n".sizeof(&arr[0] + 1));/ / 4/8

printf("%d\n".strlen(arr));// random value x
printf("%d\n".strlen(arr + 0));// random value x
printf("%d\n".strlen(*arr));/ / an error
printf("%d\n".strlen(arr[1]));/ / an error
printf("%d\n".strlen(&arr));// random value x
printf("%d\n".strlen(&arr + 1));// random value x-6
printf("%d\n".strlen(&arr[0] + 1));// random value x-1
Copy the code

  1. Sizeof (*arr), *arr dereferences the address of the first element and calculates the space occupied by the first element.

    Strlen (arr) *, * arr is still the first element, strlen take a 97 as address, access to illegal memory error.

2. Strlen (&arr) is the address of the entire array, but it still starts at the first element, so strlen still starts at the first element.

Strlen (&arr+1), evaluates &arr+1 and then passes it, so you skip the whole array.

sizeofandstrlenThe difference between

  • sizeof– Operator – Finds the space occupied by a variable or type, in bytes

Sizoef is not a function and must be evaluated with a type specifier (). The sizoef content does not participate in the calculation and is transformed at compile time.

  • strlen– Library function – Find the length of the string, that is, the number of characters\ 0Stop.

Library function that evaluates the length of the string until it encounters \0. Return type size_t, char* STR, and the received content is assumed to be an address of type CHAR *.

The space taken up by a variable and the size of a string are irrelevant, but there is always someone tying them together to “confuse the public”.

String array

First, clarify the difference between the two:

//1. The character initializes the array
char arr[] = { 'a'.'b'.'c'.'d'.'e'.'f' };//[a] [b] [c] [d] [e] [f]
//2. String initializes array
char arr[] = "abcdef";//[a] [b] [c] [d] [e] [f] [\0]
Copy the code

The character initializes the array, storing whatever element is in the array. A string initializes an array, in addition to the visible characters in the string, with the implied \0 at the end of the string. \0 exists at the end of the string and is built-in. It is not the content of the string, but the character in the string.

char arr[] = "abcdef";
printf("%d\n".sizeof(arr));/ / 7
printf("%d\n".sizeof(arr + 0));/ / 4/8
printf("%d\n".sizeof(*arr));/ / 1
printf("%d\n".sizeof(arr[1]));/ / 1
printf("%d\n".sizeof(&arr));/ / 4/8
printf("%d\n".sizeof(&arr + 1));/ / 4/8
printf("%d\n".sizeof(&arr[0] + 1));/ / 4/8

printf("%d\n".strlen(arr));/ / 6
printf("%d\n".strlen(arr + 0));/ / 6
printf("%d\n".strlen(*arr));/ / an error
printf("%d\n".strlen(arr[1]));/ / an error
printf("%d\n".strlen(&arr));/ / 6
printf("%d\n".strlen(&arr + 1));/ / random value
printf("%d\n".strlen(&arr[0] + 1));/ / 5
Copy the code
  1. sizeofCalculates the length of a variable, which can be an array, an array element, or a pointer. An array is the size of the entire array, an array element is the size of an array element, and Pointers are all 4/8.
  2. strlenTake all the parameters passed as addresses, and if they are addresses, traverse backwards from that address\ 0If the address is an invalid address, an error is reported.
Constant string
char* p = "abcdef";
Copy the code

“Abcdef” is a constant string that is pointed to by a character pointer P, which is essentially the address of the first character A. Since strings are continuously stored in memory, this feature allows you to iterate over the entire string.

char* p = "abcdef";
printf("%d\n".sizeof(p));/ / 4/8
printf("%d\n".sizeof(p + 1));/ / 4/8
printf("%d\n".sizeof(*p));/ / 1
printf("%d\n".sizeof(p[0]));/ / 1
printf("%d\n".sizeof(&p));/ / 4/8
printf("%d\n".sizeof(&p + 1));/ / 4/8
printf("%d\n".sizeof(&p[0] + 1));/ / 4/8

printf("%d\n".strlen(p));/ / 6
printf("%d\n".strlen(p + 1));/ / 5
printf("%d\n".strlen(*p));/ / an error
printf("%d\n".strlen(p[0]));/ / an error
printf("%d\n".strlen(&p));/ / random value
printf("%d\n".strlen(&p + 1));/ / random value
printf("%d\n".strlen(&p[0] + 1));/ / 5
Copy the code

  1. P,p+1,&p,&p+1,&p[0]+1 are all addresses. We get 4/8 for sizeof, *p, where p[0] is an element in the array, and sizeof measures the sizeof the element.

  2. P,p+1,&p,&p+1,&p[0]+1 are all addresses. For addresses, strlen traverses backwards looking for \0, *p,p[0] is an array element that accesses illegal memory as an address for ASCII values.

    P,p+1,&p[0]+1 are the addresses of string characters,&p,&p+1 are the addresses of pointer variables p or after them.

2 d array

Array elements are accessed by the array name +[j]. If each row of a two-dimensional array can be treated as a one-dimensional array, then a[0],a[1], and a[2] can be treated as the array names of “each row”, which have the same effect as the array names of a one-dimensional array.

  1. The array name is placed separatelysizeof()The inside represents the entire array
  2. &The array name also represents the entire array (the array name for each row also works)

int a[3] [4] = { 0 };
printf("%d\n".sizeof(a));//12X4=48
printf("%d\n".sizeof(a[0] [0]));/ / 4
printf("%d\n".sizeof(a[0]));/ / 16
printf("%d\n".sizeof(a[0] + 1));/ / 4/8
printf("%d\n".sizeof(*(a[0] + 1)));/ / 4
printf("%d\n".sizeof(a + 1));//4/8 - The second line address does not represent the second line array name
printf("%d\n".sizeof(*(a + 1)));/ / 16
printf("%d\n".sizeof(&a[0] + 1));//4/8 - The second line address does not represent the second line array name
printf("%d\n".sizeof(*(&a[0] + 1)));//16 - The second line of the array address is dereferenced to the array name
printf("%d\n".sizeof(*a));/ / 16
printf("%d\n".sizeof(a[3]));/ / 16
Copy the code
  • For a two-dimensional array,sizeof(a[0])Find the entire array size for the first row. ifsizeof(a[0]+1)The name of the array representing the first line is not placed separatelysizeof()Inside,a[0]Degraded to the address of the first element.
  • sizeof(a+1)The address representing the second line is only the address, but not the name of the second line of the “one-dimensional array” arraysizeof(a[1])Confusion.&a[1]Is equivalent toa+1.
  • sizeof(*(a+1))Dereference the address in the second linesizeof(int[4]).
  • *(&a[0]+1)The second line dereferences the array address to the array name.Array address dereference represents the entire array, equivalent to the array name. Never confuse an array address with an array name.(*&arr=arr)

conclusion

To make sense of a two-dimensional array name, you must make sense of the following variables.

a[0]// First line array name
a[0] + 1// The first element address +1 is the second element address
&a[0] + 1// First line address +1 is the second line array address (a+1)
a// The name of the two-dimensional array
a + 1// The first line address +1 is the second line array address
&a + 1Array address +1 is the second array address
*(a + 1) <=> *(&a[0] + 1)// The second line of the array address is dereferenced to the array name
Copy the code
  1. aIs the name of a two-dimensional array,a[0]Is the first line array name.
  2. After participating in the operationaDegenerates the first address,a[0]Degenerates the address of the first element.
  3. &a+1Skip a two-dimensional array,&a[0]+1Skip a one-dimensional array.

 

Pointer pen test paper
Example 1
int main(a)
{
	int a[5] = { 1.2.3.4.5 };
	int* ptr = (int*)(&a + 1);
	printf("%d,%d", *(a + 1), *(ptr - 1));
	return 0;
}
// What is the result of the program?
Copy the code

A +1 skips the length of int[4]. The pointer is converted to int* by the address of int[4], and +1 skips only one int.

The type of pointer determines the length of pointer ± integer.

Example 2
// Since we haven't learned the structure yet, we are told that the structure size is 20 bytes
struct Test
{
	int Num;
	char* pcName;
	short sDate;
	char cha[2];
	short sBa[4];
}*p;
// Assume p is 0x100000. What are the values of the following table expressions?
int main(a)
{
    p = 0x10000000;
	printf("%p\n",  (struct Test*)p + 0x1);
	printf("%p\n", (unsigned long)p + 0x1);
	printf("%p\n", (unsigned int*)p + 0x1);
	return 0;
}
Copy the code

Unsigned long and unsigned int* * * * * * * * * * * * * * * * * * * * * * * * * * Pointer +1 to struct Test* skips a struct Test byte length. An unsigned long is an integer of type +1 and is not a pointer operation.

Example 3
int main(a)
{
	int a[4] = { 1.2.3.4 };
	int* ptr1 = (int*)(&a + 1);
	int* ptr2 = (int((*)int)a + 1);
	printf("%x,%x", ptr1[- 1], *ptr2);
	return 0;
}
Copy the code

Ptr1 and ptr2 both convert variables of different meanings into addresses of type int*. The last four bytes of the address are read after a series of operations.

&a is int(*)[4] so +1 skips 1 array; A converts the address of the first element into an int integer and then adds integers by +1. Since memory is expressed in bytes, each byte has an address, +1 equals the address of the next byte. Both end up casting to Pointers to int*, and both are accessed four bytes backward.

Because the system is a small end storage scheme, it reads data in a small way. It’s printed as %x so we don’t need to convert it to decimal. The answers are 2000000000, 4.

Example 4
#include <stdio.h>
int main(a)
{
	int a[3] [2] = {(0.1), (2.3), (4.5)};int* p;
	p = a[0];
	printf("%d", p[0]);
	return 0;
}
Copy the code

This is relatively simple, but notice that () is a comma expression, so the array elements are 1,3,5,0,0,0.

Example 5
int main(a)
{
	int a[5] [5];
	int(*p)[4];
	p = a;
	printf("%p,%d\n", &p[4] [2] - &a[4] [2], &p[4] [2] - &a[4] [2]);
	return 0;
}	
Copy the code

Int (*)[5]; int(*)[5]; int(*)[5]

You can actually see that arrays are stored consecutively in memory, so it’s up to us to view a row of data as a row of three columns, a row of four columns, a row of five columns, or even a row of ten columns. So the array pointer size only determines how many elements are accessed at a time, or the number of columns in the array to refer to.

A change in the number of columns does not affect the two-dimensional array per se, only how the compiler views the array.

It can be seen that the pointer ptr1-ptr2 is -4, so %d is printed as -4. If it is printed as %p, since the complement of -4 is stored in the memory, it is printed as an unsigned hexadecimal number:

10000000 00000000 00000000 00000100
11111111 11111111 11111111 11111011
11111111 11111111 11111111 11111100
FF FF FF FC
Copy the code
Example 6
int main(a)
{
	int aa[2] [5] = { 1.2.3.4.5.6.7.8.9.10 };
	int* ptr1 = (int*)(&aa + 1);
	int* ptr2 = (int*)(*(aa + 1));
	printf("%d,%d", *(ptr1 - 1), *(ptr2 - 1));
	return 0;
}
Copy the code

&aa takes the address of the array and +1 skips the entire array. Aa equals the address of the first line and +1 is the address of the second line and dereference the name of the array.

Aa +1 gets the address of the array in the second row, and then dereference the address of the array, and you get the entire array which is the name of the array, *(&arr)=arr.

Example 7
#include <stdio.h>
int main(a)
{
	char* a[] = { "work"."at"."alibaba" };
	char** pa = a;
	pa++;
	printf("%s\n", *pa);
	return 0;
}
Copy the code

Pointer array A stores the first character addresses of “work”,”at”, and “alibaba” respectively. The name of the pointer array, i.e. the address of the first element, is stored in the secondary pointer variable. The pointer ++ accesses the second element, a, and then %s prints the entire string.

Example 8
int main(a)
{
	char* c[] = { "ENTER"."NEW"."POINT"."FIRST" };
	char** cp[] = { c + 3,c + 2,c + 1,c };
	char*** cpp = cp;
    / / 1.
	printf("%s\n", **++cpp);
	/ / 2.
    printf("%s\n", *-- * ++cpp + 3);
	/ / 3.
    printf("%s\n", *cpp[2 -] + 3);
	/ / 4.
    printf("%s\n", cpp[- 1] [- 1] + 1);
	return 0;
}
Copy the code

The char pointer array c holds the first address of the string. The char pointer array cp holds the second level pointer “related to pointer C”. The third level pointer CPP points to the second level pointer cp.

The pointer ++ is an increment or a decrement that affects this value.

  1. cppPlus one points to the arraycpThe second element, and dereference is obtainedc+2. And then we dereference that"POINT"The first address of.

  1. cpp+1 points to the arraycpAnd dereference the third element ofc+1.(c+1)--After the arraycpThe third element of is modified toc, dereference access arraycThe first element of is"ENTER"+3 to print the first address ofER.

  1. cp[-2]=*(cp-2)namelycppTwo elements are pointed to and accessedc+3And dereference the arraycAnd you have the fourth element of alpha"FIRST"+3, access toSTAnd print.

Cpp-1 is not CPP –, which has the same effect, but has a different meaning for CPP. (CPP-2) does not change CPP, so CPP still refers to the third element of CP.

  1. cpp[-1][-1]Is equivalent to*(*(cpp-1)-1)namelycpp-1 Dereference accessc+2-1 then dereferences the arraycThe second element of +1 is printedEW.

It’s really easy to look back at the code after you’ve studied it. First, look at the relationship between CPP and CP and C: both are Pointers pointing left to right once, and then look at the related operations.

**++cpp;
*--*++cpp+3;
*cpp[2 -] +3;
cpp[- 1] [- 1] +1;
Copy the code

These four lines of code are essentially the same; they are all 1. CPP ± integers and dereferenced; 2. Cp element ± integer and dereference; 3. C element ± integer and dereferenced. As shown in the figure: