代码拉取完成，页面将自动刷新
/*
*
* Copyright (c) 2011, Jue Ruan <ruanjue@gmail.com>
*
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef __SORT_RJ_H
#define __SORT_RJ_H
#include <stdio.h>
#include <stdlib.h>
#define cmp_2nums_proc(a, b) if((a) < (b)) return -1; else if((a) > (b)) return 1;
#define num_cmp_script(e1, e2, obj, val_macro) ((val_macro(e1, obj) == val_macro(e2, obj))? 0 : ((val_macro(e1, obj) < val_macro(e2, obj))? -1 : 1))
#define cmpgt_2nums_proc(a, b) if((a) < (b)) return 0; else if((a) > (b)) return 1;
#define define_bubble_sort(name, e_type, is_greater_func) \
static inline void name(e_type* list, size_t size, void *ref){ \
size_t i, j, n; \
e_type t; \
i = 0; \
while(i < size){ \
n = 0; \
for(j=size-1;j>i;j--){ \
if(is_greater_func(list[j-1], list[j], ref) > 0){ \
t = list[j-1]; list[j-1] = list[j]; list[j] = t; \
n = 1; \
} \
} \
if(n == 0) break; \
i ++; \
} \
if(ref == ref) return; \
}
#define bubble_sort_array(rs, size, e_type, is_a_greater_than_b) \
do { \
size_t bubble_i, bubble_j, bubble_n, bubble_size; \
e_type a, b; \
bubble_size = size; \
for(bubble_i=0;bubble_i<bubble_size;bubble_i++){ \
bubble_n = 0; \
for(bubble_j=bubble_size-1;bubble_j>bubble_i;bubble_j--){ \
a = (rs)[bubble_j - 1]; \
b = (rs)[bubble_j]; \
if((int)(is_a_greater_than_b) > 0){ \
(rs)[bubble_j] = a; (rs)[bubble_j - 1] = b; \
bubble_n = 1; \
} \
} \
if(bubble_n == 0) break; \
} \
} while(0)
#define divide_array(rs_ary, rs_size, e_type, is_a_greater_than_b, ret_val) \
do { \
e_type *_rs; \
_rs = (e_type*)(rs_ary); \
size_t s, e, i, j, m; \
e_type p, t, a, b; \
if((rs_size) < 2){ (ret_val) = 0; break; } \
{ \
s = 0; \
e = (rs_size) - 1; \
m = s + (e - s) / 2; \
a = _rs[s]; b = _rs[m]; \
if(is_a_greater_than_b){ t = _rs[s]; _rs[s] = _rs[m]; _rs[m] = t; } \
a = _rs[m]; b = _rs[e]; \
if(is_a_greater_than_b){ \
t = _rs[e]; _rs[e] = _rs[m]; _rs[m] = t; \
a = _rs[s]; b = _rs[m]; \
if(is_a_greater_than_b){ t = _rs[s]; _rs[s] = _rs[m]; _rs[m] = t; } \
} \
p = _rs[m]; \
i = s + 1; j = e - 1; \
while(1){ \
a = p; \
while(b = _rs[i], (is_a_greater_than_b)) i ++; \
b = p; \
while(a = _rs[j], (is_a_greater_than_b)) j --; \
if(i < j){ \
t = _rs[i]; _rs[i] = _rs[j]; _rs[j] = t; \
i ++; j --; \
} else break; \
} \
if(i == j){ i ++; j --; } \
(ret_val) = i; \
} \
} while(0)
#define sort_array(rs_ary, rs_size, e_type, is_a_greater_than_b) \
do { \
e_type *_rs; \
_rs = (e_type*)(rs_ary); \
size_t _qsort_n; \
_qsort_n = rs_size; \
size_t s, e, i, j, m, stack[64][2], x; \
e_type p, t, a, b; \
if(_qsort_n < 2) break; \
x = 0; \
stack[x][0] = 0; stack[x][1] = _qsort_n - 1; x ++; \
while(x){ \
x --; s = stack[x][0]; e = stack[x][1]; \
m = s + (e - s) / 2; \
a = _rs[s]; b = _rs[m]; \
if(is_a_greater_than_b){ t = _rs[s]; _rs[s] = _rs[m]; _rs[m] = t; } \
a = _rs[m]; b = _rs[e]; \
if(is_a_greater_than_b){ \
t = _rs[e]; _rs[e] = _rs[m]; _rs[m] = t; \
a = _rs[s]; b = _rs[m]; \
if(is_a_greater_than_b){ t = _rs[s]; _rs[s] = _rs[m]; _rs[m] = t; } \
} \
p = _rs[m]; \
i = s + 1; j = e - 1; \
while(1){ \
a = p; \
while(b = _rs[i], (is_a_greater_than_b)) i ++; \
b = p; \
while(a = _rs[j], (is_a_greater_than_b)) j --; \
if(i < j){ \
t = _rs[i]; _rs[i] = _rs[j]; _rs[j] = t; \
i ++; j --; \
} else break; \
} \
if(i == j){ i ++; j --; } \
if(j - s > e - i){ \
if(s + 4 < j){ stack[x][0] = s; stack[x][1] = j; x ++; } \
if(i + 4 < e){ stack[x][0] = i; stack[x][1] = e; x ++; } \
} else { \
if(i + 4 < e){ stack[x][0] = i; stack[x][1] = e; x ++; } \
if(s + 4 < j){ stack[x][0] = s; stack[x][1] = j; x ++; } \
} \
} \
for(i=0;i<_qsort_n;i++){ \
x = 0; \
for(j=_qsort_n-1;j>i;j--){ \
a = _rs[j - 1]; b = _rs[j]; \
if(is_a_greater_than_b){ t = _rs[j - 1]; _rs[j - 1] = _rs[j]; _rs[j] = t; x = 1; } \
} \
if(x == 0) break; \
} \
} while(0)
#define sort_array_adv(rs_size, is_a_greater_than_b, swap_expr) \
do { \
size_t _qsort_n; \
_qsort_n = rs_size; \
size_t s, e, i, j, m, stack[64][2], x, a, b; \
if(_qsort_n < 2) break; \
x = 0; \
stack[x][0] = 0; stack[x][1] = _qsort_n - 1; x ++; \
while(x){ \
x --; s = stack[x][0]; e = stack[x][1]; \
m = s + (e - s) / 2; \
a = s; b = m; \
if(is_a_greater_than_b){ swap_expr; } \
a = m; b = e; \
if(is_a_greater_than_b){ \
swap_expr; \
a = s; b = m; \
if(is_a_greater_than_b){ swap_expr; } \
} \
i = s + 1; j = e - 1; \
while(1){ \
a = m; \
while(b = i, (is_a_greater_than_b)) i ++; \
b = m; \
while(a = j, (is_a_greater_than_b)) j --; \
if(i < j){ \
if(m == i) m = j; \
else if(m == j) m = i; \
a = i; b = j; \
swap_expr; \
i ++; j --; \
} else break; \
} \
if(i == j){ i ++; j --; } \
if(s + 4 < j){ stack[x][0] = s; stack[x][1] = j; x ++; } \
if(i + 4 < e){ stack[x][0] = i; stack[x][1] = e; x ++; } \
} \
for(i=0;i<_qsort_n;i++){ \
x = 0; \
for(j=_qsort_n-1;j>i;j--){ \
a = j - 1; b = j; \
if(is_a_greater_than_b){ swap_expr; x = 1; } \
} \
if(x == 0) break; \
} \
} while(0)
// Must #include "thread.h" and "list.h"
#define psort_array(rs_ary, rs_size, e_type, ncpu, is_a_greater_than_b) \
do { \
thread_beg_def(psrt); \
e_type *rs; \
size_t beg, end, div; \
int divide; \
thread_end_def(psrt); \
thread_beg_func_inline(psrt); \
thread_beg_loop(psrt); \
if(psrt->divide){ \
divide_array(psrt->rs + psrt->beg, psrt->end - psrt->beg, e_type, is_a_greater_than_b, psrt->div); \
psrt->div += psrt->beg; \
} else { \
sort_array(psrt->rs + psrt->beg, psrt->end - psrt->beg, e_type, is_a_greater_than_b); \
} \
thread_end_loop(psrt); \
thread_end_func(psrt); \
thread_preprocess(psrt); \
e_type *_rs; \
_rs = (e_type*)(rs_ary); \
size_t _qsort_n, _min_blk_size; \
_qsort_n = rs_size; \
_min_blk_size = _qsort_n / ncpu / 8; \
if(_min_blk_size < 1024) _min_blk_size = 1024; \
if(_qsort_n < ((uint32_t)(ncpu)) * 32){ \
sort_array(rs_ary, rs_size, e_type, is_a_greater_than_b); \
break; \
} \
thread_beg_init(psrt, (int)(ncpu)); \
psrt->rs = _rs; psrt->beg = psrt->end = psrt->div = 0; psrt->divide = 0; \
thread_end_init(psrt); \
u64list *stacks[2]; \
int x; \
stacks[0] = init_u64list(32); \
stacks[1] = init_u64list(32); \
push_u64list(stacks[0], 0); \
push_u64list(stacks[1], _qsort_n); \
x = 0; \
while(stacks[0]->size || x > 0){ \
thread_waitfor_one_idle(psrt); \
if(psrt->divide){ \
if(psrt->div - psrt->beg <= psrt->end - psrt->div){ \
push_u64list(stacks[0], psrt->beg); \
push_u64list(stacks[1], psrt->div); \
push_u64list(stacks[0], psrt->div); \
push_u64list(stacks[1], psrt->end); \
} else { \
push_u64list(stacks[0], psrt->div); \
push_u64list(stacks[1], psrt->end); \
push_u64list(stacks[0], psrt->beg); \
push_u64list(stacks[1], psrt->div); \
} \
x --; \
psrt->divide = 0; \
} else if(stacks[0]->size){ \
psrt->beg = stacks[0]->buffer[--stacks[0]->size]; \
psrt->end = stacks[1]->buffer[--stacks[1]->size]; \
psrt->divide = (psrt->end - psrt->beg > _min_blk_size); \
if(psrt->divide) x ++; \
thread_wake(psrt); \
} \
} \
thread_waitfor_all_idle(psrt); \
thread_beg_close(psrt); \
thread_end_close(psrt); \
free_u64list(stacks[0]); \
free_u64list(stacks[1]); \
} while(0)
#define quick_median_array(_rs, _rs_size, e_type, expr) \
({ \
e_type key; \
do { \
e_type *rs; \
rs = (e_type*)(_rs); \
size_t size; \
size = (size_t)(_rs_size); \
size_t i, j, beg, mid, end; \
if(size == 0){ \
memset(&key, 0, sizeof(e_type)); \
break; \
} \
beg = 0; \
end = size - 1; \
e_type tmp, a, b; \
while(beg < end){ \
mid = beg + (end - beg) / 2; \
a = rs[beg]; b = rs[mid]; \
if(expr){ tmp = rs[beg]; rs[beg] = rs[mid]; rs[mid] = tmp; } \
a = rs[mid]; b = rs[end]; \
if(expr){ \
tmp = rs[end]; rs[end] = rs[mid]; rs[mid] = tmp; \
a = rs[beg]; b = rs[mid]; \
if(expr){ tmp = rs[beg]; rs[beg] = rs[mid]; rs[mid] = tmp; } \
} \
key = rs[mid]; \
i = beg + 1; j = end - 1; \
while(1){ \
a = key; \
while(b = rs[i], (expr)) i ++; \
b = key; \
while(a = rs[j], (expr)) j --; \
if(i < j){ \
tmp = rs[i]; rs[i] = rs[j]; rs[j] = tmp; \
i ++; j --; \
} else break; \
} \
if(i == j){ i ++; j --; } \
if(i <= size / 2) beg = i; \
else end = j; \
} \
key = rs[size/2]; \
} while(0); \
key; \
})
#define apply_array(rs, rs_size, e_type, expression) \
do { \
size_t _i, _rs_size; \
e_type a; \
_rs_size = rs_size; \
for(_i=0;_i<_rs_size;_i++){ \
a = (rs)[_i]; \
expression; \
} \
} while(0)
#define ref_apply_array(rs, rs_size, e_type, expression) \
do { \
size_t _i, _rs_size; \
e_type *a; \
_rs_size = rs_size; \
for(_i=0;_i<_rs_size;_i++){ \
a = (rs) + _i; \
(expression); \
} \
} while(0)
#define locate_array(rs, rs_size, e_type, expr) \
({ \
size_t _i, _size; \
e_type a; \
_size = rs_size; \
for(_i=0;_i<_size;_i++){ \
a = rs[_i]; \
if(expr) break; \
}; \
_i; \
})
// sort the array according to bool value (true then flase), and return the size of trues
#define apply_xchg_array(rs, rs_size, e_type, expr) \
({ \
size_t _i, _j, _size; \
e_type a; \
_size = rs_size; \
for(_i=_j=0;_i<_size;_i++){ \
a = (rs)[_i]; \
if(!(expr)) continue; \
if(_j < _i){ \
a = (rs)[_j]; \
(rs)[_j] = (rs)[_i]; \
(rs)[_i] = a; \
} \
_j ++; \
} \
_j; \
})
#define define_quick_sort(name, e_type, is_greater_func) \
static inline void name(e_type *rs, size_t n, void *obj){ \
size_t s, e, i, j, m, stack[64][2], x; \
e_type p, t; \
if(n < 2) return; \
x = 0; \
stack[x][0] = 0; stack[x][1] = n - 1; x ++; \
while(x){ \
x --; s = stack[x][0]; e = stack[x][1]; \
m = s + (e - s) / 2; \
if(is_greater_func(rs[s], rs[m], obj) > 0){ t = rs[s]; rs[s] = rs[m]; rs[m] = t; } \
if(is_greater_func(rs[m], rs[e], obj) > 0){ \
t = rs[e]; rs[e] = rs[m]; rs[m] = t; \
if(is_greater_func(rs[s], rs[m], obj) > 0){ t = rs[s]; rs[s] = rs[m]; rs[m] = t; } \
} \
p = rs[m]; \
i = s + 1; j = e - 1; \
while(1){ \
while(is_greater_func(p, rs[i], obj) > 0) i ++; \
while(is_greater_func(rs[j], p, obj) > 0) j --; \
if(i < j){ \
t = rs[i]; rs[i] = rs[j]; rs[j] = t; \
i ++; j --; \
} else break; \
} \
if(i == j){ i ++; j --; } \
if(j - s > e - i){ \
if(s + 4 < j){ stack[x][0] = s; stack[x][1] = j; x ++; } \
if(i + 4 < e){ stack[x][0] = i; stack[x][1] = e; x ++; } \
} else { \
if(i + 4 < e){ stack[x][0] = i; stack[x][1] = e; x ++; } \
if(s + 4 < j){ stack[x][0] = s; stack[x][1] = j; x ++; } \
} \
} \
for(i=0;i<n;i++){ \
x = 0; \
for(j=n-1;j>i;j--){ \
if(is_greater_func(rs[j - 1], rs[j], obj) > 0){ t = rs[j - 1]; rs[j - 1] = rs[j]; rs[j] = t; x = 1; } \
} \
if(x == 0) break; \
} \
if(obj == obj) return; \
}
#define define_merge(name, e_type, cmp_func, output_func) \
static inline void name(e_type *list1, size_t size1, e_type *list2, size_t size2, void *ref){ \
size_t i, j; \
i = j = 0; \
while(i < size1 && j < size2){ \
if(cmp_func(list1[i], list2[j], ref) <= 0){ \
output_func(list1[i], ref); \
i ++; \
} else { \
output_func(list2[j], ref); \
j ++; \
} \
} \
while(i < size1){ output_func(list1[i++], ref); } \
while(j < size2){ output_func(list2[j++], ref); } \
} \
\
static inline size_t name##_files(FILE **files, int n, void *ref){ \
e_type *es; \
int *flags, i, min; \
size_t ret; \
ret = 0; \
es = malloc(sizeof(e_type) * n); \
flags = malloc(sizeof(int) * n); \
for(i=0;i<n;i++) flags[i] = 0; \
while(1){ \
min = -1; \
for(i=0;i<n;i++){ \
if(flags[i] == 0){ \
flags[i] = (fread(es + i, sizeof(e_type), 1, files[i]) == 1)? 1 : 2; \
} \
if(flags[i] == 1){ \
if(min == -1){ \
min = i; \
} else if(cmp_func(es[i], es[min], ref) <= 0){ \
min = i; \
} \
} \
} \
if(min == -1) break; \
output_func(es[min], ref); \
flags[min] = 0; \
ret ++; \
} \
free(es); \
free(flags); \
return ret; \
}
#define define_unique_merge(name, e_type, cmp_func, output_func) \
static inline void name(e_type *list1, size_t size1, e_type *list2, size_t size2, void *ref){ \
size_t i, j; \
i = j = 0; \
while(i < size1 && j < size2){ \
switch(cmp_func(list1[i], list2[j])){ \
case 0: output_func(list1[i++], ref); j ++; break; \
case -1: output_func(list1[i++], ref); break; \
default: output_func(list2[j++], ref); \
} \
} \
while(i < size1){ output_func(list1[i++], ref); } \
while(j < size2){ output_func(list2[j++], ref); } \
}
#define reverse_array(_rs, _rs_size, e_type) \
do { \
size_t i, n; \
n = (_rs_size); \
e_type* __rs = (_rs); \
e_type e; \
for(i=0;i<n>>1;i++){ \
e = __rs[i]; __rs[i] = __rs[n-1-i]; __rs[n-1-i] = e; \
} \
} while(0)
#define define_reverse_array(name, e_type) \
static inline void name(e_type *list, size_t size){ \
size_t i, j; \
e_type t; \
if(size == 0) return; \
i = 0; \
j = size - 1; \
while(i < j){ \
t = list[i]; list[i] = list[j]; list[j] = t; \
i ++; j --; \
} \
}
#define define_apply_array(name, e_type, apply_func) \
static inline size_t name(e_type *list, size_t size, void *ref){ \
size_t i, ret; \
ret = 0; \
for(i=0;i<size;i++){ \
ret += apply_func(list[i], ref); \
} \
return ret; \
ref = NULL; \
}
#define define_search_array(name, e_type, cmp_func) \
static inline long long name(e_type *array, long long size, e_type key, void *ref){ \
long long i, j, m; \
i = 0; \
j = size; \
while(i < j){ \
m = i + (j - i) / 2; \
if(cmp_func(array[m], key, ref) < 0){ \
i = m + 1; \
} else { \
j = m; \
} \
} \
if(i < size && cmp_func(array[i], key, ref) == 0) return i; \
else return - (i + 1); \
if(ref) return 0; \
}
#define bsearch_array(_rs_array, _rs_size, e_type, _bs_ret, is_a_less_than_your) \
\
do { \
e_type*_bs_rs; \
e_type a; \
_bs_rs = (e_type*)(_rs_array); \
size_t _bs_size; \
_bs_size = _rs_size; \
size_t _bs_i, _bs_j, _bs_m; \
_bs_i = 0; \
_bs_j = _bs_size; \
while(_bs_i < _bs_j){ \
_bs_m = _bs_i + (_bs_j - _bs_i) / 2; \
a = _bs_rs[_bs_m]; \
if(is_a_less_than_your){ \
_bs_i = _bs_m + 1; \
} else { \
_bs_j = _bs_m; \
} \
} \
_bs_ret = _bs_i; \
} while(0)
#endif
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手