linux内核中的排序接口--sort函数

简介:

linux内核中的sort函数,其实跟我们所说的qsort函数很像,我们来看看qsort:

qsort 的函数原型是
void qsort(void*base,size_t num,size_t width,int(__cdecl*compare)(const void*,const void*));
参数: 
1 、待排序数组首地址
2 、数组中待排序元素数量
3 、各元素的占用空间大小
4 、指向函数的指针,用于确定排序的顺序。
其中compare函数应写为:
1
2
3
4
int  comp( const  void *a, const  void *b)
{
return  *( int *)a-*( int *)b;
}
其实qsort是一个典型的快速排序的接口函数。

  接下来我们来看看linux内核中的排序接口函数sort:

void sort(void *base, size_t num, size_t size,
 int (*cmp_func)(const void *, const void *),
 void (*swap_func)(void *, void *, int size)) ;
同样的:

        1、待排序的数组首地址

2、数组中待排序元素的数量

  3、各元素的占用空间大小

  4、指向函数的指针,用于确定排序的顺序。

5、指向函数的指针,用于交换元素的顺序(其实这可有可无,一般可以设置为NULL(空)值)。

接下来,我们来看看它的实现:

跟qsort函数的源码其实大致相似:

void sort(void *base, size_t num, size_t size,
	  int (*cmp_func)(const void *, const void *),
	  void (*swap_func)(void *, void *, int size))
{
	/* pre-scale counters for performance */
	int i = (num/2 - 1) * size, n = num * size, c, r;

	if (!swap_func)
		swap_func = (size == 4 ? u32_swap : generic_swap);

	/* heapify */
	for ( ; i >= 0; i -= size) {
		for (r = i; r * 2 + size < n; r  = c) {
			c = r * 2 + size;
			if (c < n - size &&
					cmp_func(base + c, base + c + size) < 0)
				c += size;
			if (cmp_func(base + r, base + c) >= 0)
				break;
			swap_func(base + r, base + c, size);
		}
	}

	/* sort */
	for (i = n - size; i > 0; i -= size) {
		swap_func(base, base + i, size);
		for (r = 0; r * 2 + size < i; r = c) {
			c = r * 2 + size;
			if (c < i - size &&
					cmp_func(base + c, base + c + size) < 0)
				c += size;
			if (cmp_func(base + r, base + c) >= 0)
				break;
			swap_func(base + r, base + c, size);
		}
	}
}
接下来我们看一个实例程序:

将代码从linux内核中抠出来,然后编写程序:

#include <stdio.h>
#include <stdlib.h>
typedef int u32 ; 

/*
	fri : sort array
	sec : array num 
	thr : array only num size
	function:
	function:
*/
void sort(void *base, size_t num, size_t size,
	  int (*cmp_func)(const void *, const void *),
	  void (*swap_func)(void *, void *, int size)) ;
int cmpint(const void *a, const void *b) ;
static void u32_swap(void *a, void *b, int size) ; 
static void generic_swap(void *a, void *b, int size); 

int main(void)
{
	int array[10] = {0};
	
	int i = 0 ;
	printf("随机产生10个100以内的数:\n");
	for(i = 0 ; i < 10 ; i++)
	{
		array[i] = rand()%100;
		printf("array[%d]=%d\n",i , array[i]);
	}

	sort(array , 10 , sizeof(int) , cmpint , u32_swap) ;
	putchar('\n');
	printf("排序后的数:\n");
	for(i = 0 ; i < 10 ; i++)
	{
		printf("arr[%d]=%d\n",i , array[i]);
	}

	return 0 ;	
}

	  

void sort(void *base, size_t num, size_t size,
	  int (*cmp_func)(const void *, const void *),
	  void (*swap_func)(void *, void *, int size))
{
	/* pre-scale counters for performance */
	int i = (num/2 - 1) * size, n = num * size, c, r;

	if (!swap_func)
		swap_func = (size == 4 ? u32_swap : generic_swap);

	/* heapify */
	for ( ; i >= 0; i -= size) {
		for (r = i; r * 2 + size < n; r  = c) {
			c = r * 2 + size;
			if (c < n - size &&
					cmp_func(base + c, base + c + size) < 0)
				c += size;
			if (cmp_func(base + r, base + c) >= 0)
				break;
			swap_func(base + r, base + c, size);
		}
	}

	/* sort */
	for (i = n - size; i > 0; i -= size) {
		swap_func(base, base + i, size);
		for (r = 0; r * 2 + size < i; r = c) {
			c = r * 2 + size;
			if (c < i - size &&
					cmp_func(base + c, base + c + size) < 0)
				c += size;
			if (cmp_func(base + r, base + c) >= 0)
				break;
			swap_func(base + r, base + c, size);
		}
	}
}

int cmpint(const void *a, const void *b)
{
	return *(int *)a - *(int *)b;
}

static void u32_swap(void *a, void *b, int size)
{
	u32 t = *(u32 *)a;
	*(u32 *)a = *(u32 *)b;
	*(u32 *)b = t;
}

static void generic_swap(void *a, void *b, int size)
{
	char t;

	do {
		t = *(char *)a;
		*(char *)a++ = *(char *)b;
		*(char *)b++ = t;
	} while (--size > 0);
}
运行结果:

随机产生10个100以内的数,通过排序接口sort排序后得到如下结果,验证成功!



目录
相关文章
|
4天前
|
Linux 调度
Linux 内核源代码情景分析(一)(下)
Linux 内核源代码情景分析(一)
16 1
|
4天前
|
存储 IDE Unix
Linux 内核源代码情景分析(四)(上)
Linux 内核源代码情景分析(四)
10 1
Linux 内核源代码情景分析(四)(上)
|
4天前
|
存储 NoSQL Linux
深度探索Linux操作系统 —— 从内核空间到用户空间3
深度探索Linux操作系统 —— 从内核空间到用户空间
20 9
|
4天前
|
存储 NoSQL Linux
深度探索Linux操作系统 —— 从内核空间到用户空间2
深度探索Linux操作系统 —— 从内核空间到用户空间
18 7
|
4天前
|
Linux Shell 编译器
深度探索Linux操作系统 —— 构建内核
深度探索Linux操作系统 —— 构建内核
10 5
|
4天前
|
存储 安全 Linux
深度探索Linux操作系统 —— 从内核空间到用户空间1
深度探索Linux操作系统 —— 从内核空间到用户空间
19 4
|
4天前
|
存储 Linux 块存储
Linux 内核源代码情景分析(三)(下)
Linux 内核源代码情景分析(三)
16 4
|
4天前
|
存储 Unix Linux
Linux 内核源代码情景分析(四)(下)
Linux 内核源代码情景分析(四)
8 2
|
4天前
|
Linux 人机交互 调度
Linux 内核源代码情景分析(二)(下)
Linux 内核源代码情景分析(二)
12 2
|
4天前
|
存储 Unix Linux
Linux 内核源代码情景分析(二)(上)
Linux 内核源代码情景分析(二)
11 2