aboutsummaryrefslogtreecommitdiffstats
path: root/include/linux/compiler.h
Commit message (Expand)AuthorAge
* rcu: define __rcu address space modifier for sparsePaul E. McKenney2010-08-19
* rcu: add __rcu API for later sparse checkingPaul E. McKenney2010-06-14
* Merge branch 'master' into percpuTejun Heo2010-01-04
|\
| * Merge branch 'x86-asm-for-linus' of git://git.kernel.org/pub/scm/linux/kernel...Linus Torvalds2009-12-05
| |\
| | * x86: Add a Kconfig option to turn the copy_from_user warnings into errorsArjan van de Ven2009-10-02
| | * x86: Turn the copy_from_user check into an (optional) compile time warningArjan van de Ven2009-10-01
| | * x86: Use __builtin_object_size() to validate the buffer size for copy_from_us...Arjan van de Ven2009-09-26
| * | Merge branch 'tracing-core-for-linus' of git://git.kernel.org/pub/scm/linux/k...Linus Torvalds2009-12-05
| |\ \
| | * | compiler: Introduce __always_unusedLi Zefan2009-11-02
| | |/
| * / Add support for GCC-4.5's __builtin_unreachable() to compiler.h (v2)David Daney2009-12-05
| |/
* / percpu: add __percpu for sparse.Rusty Russell2009-10-29
|/
* module_param: add __same_type convenience wrapper for __builtin_types_compati...Rusty Russell2009-06-12
* branch tracer, intel-iommu: fix build with CONFIG_BRANCH_TRACER=yLinus Torvalds2009-04-07
* branch tracer: Fix for enabling branch profiling makes sparse unusableBart Van Assche2009-04-07
* tracing: optimization of branch tracerWitold Baryluk2009-03-17
* Sanitize gcc version header includesLinus Torvalds2009-01-02
* trace: profile all if conditionalsSteven Rostedt2008-11-23
* trace: consolidate unlikely and likely profilerSteven Rostedt2008-11-23
* trace: remove extra assign in branch checkSteven Rostedt2008-11-23
* trace: rename unlikely profiler to branch profilerSteven Rostedt2008-11-12
* tracing: branch tracer, fix vdso crashIngo Molnar2008-11-12
* tracing: profile likely and unlikely annotationsSteven Rostedt2008-11-12
* ftrace: move notrace to compiler.hSteven Rostedt2008-10-14
* rcu: remove redundant ACCESS_ONCE definition from rcupreempt.cPaul E. McKenney2008-08-18
* Move ACCESS_ONCE() to <linux/compiler.h>Linus Torvalds2008-05-10
* add noinline_for_stackAndrew Morton2008-03-04
* remove __attribute_used__Adrian Bunk2008-01-28
* compiler.h: introduce __section()Sam Ravnborg2008-01-28
* Permit silencing of __deprecated warnings.Jeff Garzik2007-10-25
* Replace __attribute_pure__ with __pureRalf Baechle2007-10-18
* make __chk_{user,io}_ptr() accept pointers to volatileAl Viro2007-07-26
* x86: Support __attribute__((__cold__)) in gcc 4.3Andi Kleen2007-07-21
* x86_64: Support gcc 5 properlyAndi Kleen2007-05-21
* compiler: introduce __used and __maybe_unusedDavid Rientjes2007-05-09
* [PATCH] Add const to pointer qualifiers for __chk_user_ptr and __chk_io_ptr.Russ Cox2007-03-26
* include/linux/compiler.h: reject gcc 3 < gcc 3.2Alistair John Strachan2006-12-12
* [PATCH] Pass sparse the lock expression given to lock annotationsJosh Triplett2006-10-01
* [PATCH] Pass a lock expression to __cond_lock, like __acquire and __releaseJosh Triplett2006-09-29
* add CONFIG_ENABLE_MUST_CHECKAndrew Morton2006-09-26
* Restore __attribute_const__ to user-visibility in linux/compiler.h...for nowDavid Woodhouse2006-05-03
* Guard some of linux/compiler.h with #ifdef __KERNEL__David Woodhouse2006-05-02
* [PATCH] Abandon gcc-2.95.xAndrew Morton2006-01-08
* [PATCH] Add deprecated_for_modulesPaul E. McKenney2005-05-01
* Linux-2.6.12-rc2v2.6.12-rc2Linus Torvalds2005-04-16
generated by cgit v1.2.2 (git 2.25.0) at 2026-05-14 10:49:16 -0400

                                                
                                                         
 

                                                                  


                                    

                                                       

                                                                                
                                          
                                                              
                                      
                                                            



                  
                                              
                                                

                                                      

                                                                                
                                          
                                                              
                                      
                                                            















                                        
                         

























                                                    
/*
 * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
 *
 * Jan 23 2005  Matt Mackall <mpm@selenic.com>
 */

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/sort.h>
#include <linux/slab.h>

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);
}

/**
 * sort - sort an array of elements
 * @base: pointer to data to sort
 * @num: number of elements
 * @size: size of each element
 * @cmp_func: pointer to comparison function
 * @swap_func: pointer to swap function or NULL
 *
 * This function does a heapsort on the given array. You may provide a
 * swap_func function optimized to your element type.
 *
 * Sorting time is O(n log n) both on average and worst-case. While
 * qsort is about 20% faster on average, it suffers from exploitable
 * O(n*n) worst-case behavior and extra memory requirements that make
 * it less suitable for kernel use.
 */

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);
		}
	}
}

EXPORT_SYMBOL(sort);

#if 0
/* a simple boot-time regression test */

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

static int sort_test(void)
{
	int *a, i, r = 1;

	a = kmalloc(1000 * sizeof(int), GFP_KERNEL);
	BUG_ON(!a);

	printk("testing sort()\n");

	for (i = 0; i < 1000; i++) {
		r = (r * 725861) % 6599;
		a[i] = r;
	}

	sort(a, 1000, sizeof(int), cmpint, NULL);

	for (i = 0; i < 999; i++)
		if (a[i] > a[i+1]) {
			printk("sort() failed!\n");
			break;
		}

	kfree(a);

	return 0;
}

module_init(sort_test);
#endif
generated by cgit v1.2.2 (git 2.25.0) at 2026-05-14 10:49:15 -0400