一年十二月谁主春秋关注：基础系统工程密码学人工智能

摘要: 信号量是一种用于并发环境同步手段的原语，分为无名信号量和有名信号量两种，前者只能用于线程间同步，而后者还可用于进程间同步。它包括创建、等待、挂出、取值和销毁5种基本操作。与互斥锁不同的是： ● 信号量拥有一个计数值，表示可用的资源数量，仅当该值为0或1时，则相当于互斥锁。 &... 阅读全文

posted @ 2012-07-20 10:52 春秋十二月阅读(2156) | 评论 (0) | 编辑收藏

一种简单的跨平台互斥锁

摘要: 互斥锁，用来保证任一时刻只有单个线程或进程拥有对共享资源的互斥访问权，在这里将posix thread中的互斥体、win32中的互斥体和临界区，统称为互斥锁，其特点如下： ● 范围：线程锁和进程锁，前者仅用于同一进程内多线程间，而后者用于进程间，显然，它也能用于同一进程内多线程间，但效率较低。posix的互斥体既可以是线程锁，... 阅读全文

posted @ 2012-06-23 00:08 春秋十二月阅读(3564) | 评论 (2) | 编辑收藏

一种简单的跨平台套接字管道

摘要: socket pair，也称套接字管道，主要用来实现进程内或进程间的一对一的全双工或半双工通信，在IO复用模型（如select,poll,epoll等）中起到通知中断退出循环的作用，在类UNIX系统中已经有现成的实现，API为socketpair，但在Windows系统中没有，因此本文主要讲述Windows平台下soketpair的实现及应用，支持IPv4和I... 阅读全文

posted @ 2012-06-17 03:02 春秋十二月阅读(3005) | 评论 (3) | 编辑收藏

一种简单的跨平台用户态自旋锁

自旋锁作为一种并发同步的手段，特别适用于竞争少和锁时间短的情况，在驱动及内核代码中经常被用到，本文讲述一种适合用户态程序的自旋锁，支持Windows和Linux（GCC>=4.1.2）平台，并提供了C语言的接口和实现。

接口
spin_trylock如果获取成功返回1，否则返回0；spin_is_lock如果已加锁，返回1，否则返回0。

typedef struct
2

{
3

volatile long flag_;
4

volatile long* spin_;
5

}spin_lock_t;
6

void spin_init(spin_lock_t* lock,long* flag);
8

void spin_lock(spin_lock_t* lock);
10

int spin_trylock(spin_lock_t* lock);
12

void spin_unlock(spin_lock_t* lock);
14

int spin_is_lock(spin_lock_t* lock);

实现

#ifdef _MSC_VER
2

#include <windows.h>
3

#elif defined(__GNUC__)
4

#if __GNUC__<4 || (__GNUC__==4 && __GNUC_MINOR__<1)
5

#error GCC version must be greater or equal than 4.1.2
6

#endif
7

#include <sched.h>
8

#else
9

#error Currently only windows and linux os are supported
10

#endif
11

void spin_init(spin_lock_t* lock,long* flag)
13

{
14

#ifdef _MSC_VER
15

InterlockedExchange((volatile long*)&lock->flag_,0);
16

InterlockedExchange((volatile long*)&lock->spin_,flag?(long)flag:(long)&lock->flag_);
17

#elif defined(__GNUC__)
18

__sync_and_and_fetch((long*)&lock->flag_,0);
19

__sync_lock_test_and_set((long*)&lock->spin_,flag?(long)flag:(long)&lock->flag_);
20

#endif
21

}
22

void spin_lock(spin_lock_t* lock)
24

{
25

#ifdef _MSC_VER
26

for (;0!=InterlockedExchange((volatile long*)lock->spin_,1);)
27

{
28

Sleep(1);
29

}
30

#elif defined(__GNUC__)
31

for (;0!=__sync_fetch_and_or(lock->spin_,1);)
32

{
33

sched_yield();
34

}
35

#endif
36

}
37

int spin_trylock(spin_lock_t* lock)
39

{
40

#ifdef _MSC_VER
41

return !InterlockedExchange((volatile long*)lock->spin_,1);
42

#elif defined(__GNUC__)
43

return !__sync_fetch_and_or(lock->spin_,1);
44

#endif
45

}
46

void spin_unlock(spin_lock_t* lock)
48

{
49

#ifdef _MSC_VER
50

InterlockedExchange((volatile long*)lock->spin_,0);
51

#elif defined(__GNUC__)
52

__sync_and_and_fetch(lock->spin_,0);
53

#endif
54

}
55

int spin_is_lock(spin_lock_t* lock)
57

{
58

#ifdef _MSC_VER
59

return InterlockedExchangeAdd((volatile long*)lock->spin_,0);
60

#elif defined(__GNUC__)
61

return __sync_add_and_fetch(lock->spin_,0);
62

#endif
63

}

posted @ 2012-06-13 21:02 春秋十二月阅读(3046) | 评论 (3) | 编辑收藏

GCC原子操作类模板

摘要: 主类模板 gcc从4.1.2版本开始提供了__sync_*系列的内置API，用于加减和逻辑运算，可以对1，2，4，8字节长度的数值或指针类型进行原子操作，为方便使用，笔者对这些API作了简单的封装。 Code highlighting produced by Actipro CodeHighlighter (freeware) http://... 阅读全文

posted @ 2012-06-08 00:19 春秋十二月阅读(4562) | 评论 (1) | 编辑收藏

模板元编程（3）：类型选择

摘要: 类型选择是一种编译时的类型计算技术，也就是根据条件判断来匹配对应的类型，功能形如运行时的if else和switch case控制结构。在这里仿真运行时的条件语句，实现了类型选择，包括if单分支、if多分支和switch case三种结构，关于其原理及细节就不多讲了，直接看如下代码（1）if单分支 Code ... 阅读全文

posted @ 2012-06-06 13:49 春秋十二月阅读(2063) | 评论 (1) | 编辑收藏

基于特定小范围关键字的原位统计排序

摘要: 基本原理在数据输入随机分布的情况下，快速排序具有较好的性能表现，但当元素个数比其关键字的取值范围大，而这个范围相对较小时，使用一种关键字索引统计排序会快很多，因为它的时间复杂度是线性的，基本原理是使用数组（为描述方便，特称统计数组），其下标对应关键字的值，存储元素按待排序关键字的值统计的出现次数，然后再按元素关键字的值，结合统计数组，放回到最终位置上。常规的实现... 阅读全文

posted @ 2012-05-31 12:11 春秋十二月阅读(1801) | 评论 (0) | 编辑收藏

模板元编程（2）：计算最值

本文就Loki编译期技术中的类型列表Typelist作了一些扩展，增加了以下几个方法：
• 获取最大和最小长度，即求取Typelist中长度最大和最小的值
• 获取最大和最小类型，即求取Typelist中长度最大和最小的类型

实现
   位于Loki::TL命名空间，利用递归计算最值结果，使用宏生成主类模板和特化类模板，其中后缀为DEFN(N为正整数)形式的宏中N表示特化类模板所带的模板参数数量，使用DEF1宏定义对应的特化类模板的原因在于：当Typelist中存在非NullType类型时，保证结果的正确性。当N为2时参数取值：name为Max则b为true；name为Min则b为false。
   主类模板
   用于定义MaxSize、MinSize和MaxType、MinType主类模板，使用宏LOKI_TYPELIST_METHOD_DEF生成。

#define LOKI_TYPELIST_METHOD_DEF(name)\
2

template <class TList>\
3

struct name;\
4

LOKI_TYPELIST_METHOD_DEF(MaxSize)
6

LOKI_TYPELIST_METHOD_DEF(MinSize)
7

LOKI_TYPELIST_METHOD_DEF(MaxType)
8

LOKI_TYPELIST_METHOD_DEF(MinType)

最大(小)长度
对应类主模板分别为MaxSize和MinSize，每种有3个特化模板，使用宏LOKI_TYPELIST_SIZE_SPEC_DEFN生成（N为0、1、2）。

#define LOKI_TYPELIST_SIZE_SPEC_DEF0(name)\
2

template<>\
3

struct name##Size<NullType>\
4

{\
5

enum { value = 0 };\
6

};\
7

#define LOKI_TYPELIST_SIZE_SPEC_DEF1(name)\
9

template<class T>\
10

struct name##Size<Typelist<T,NullType> >\
11

{\
12

enum { value = sizeof(T) };\
13

};\
14

#define LOKI_TYPELIST_SIZE_SPEC_DEF2(name,b)\
16

template<class T,class U>\
17

struct name##Size<Typelist<T,U> >\
18

{\
19

enum { tmp = name##Size<U>::value };\
20

enum { value = (b ? sizeof(T) > tmp : sizeof(T) < tmp) ? sizeof(T) : tmp };\
21

};\
22

LOKI_TYPELIST_SIZE_SPEC_DEF0(Max)
24

LOKI_TYPELIST_SIZE_SPEC_DEF0(Min)
25

LOKI_TYPELIST_SIZE_SPEC_DEF1(Max)
26

LOKI_TYPELIST_SIZE_SPEC_DEF1(Min)
27

LOKI_TYPELIST_SIZE_SPEC_DEF2(Max,true)
28

LOKI_TYPELIST_SIZE_SPEC_DEF2(Min,false)
29

#undef LOKI_TYPELIST_SIZE_SPEC_DEF0
31

#undef LOKI_TYPELIST_SIZE_SPEC_DEF1
32

#undef LOKI_TYPELIST_SIZE_SPEC_DEF2

最大(小)类型
对应类主模板分别为MaxType和MinType，每种有3个特化模板，使用宏LOKI_TYPELIST_TYPE_SPEC_DEFN生成（N为0、1、2）。

#define LOKI_TYPELIST_TYPE_SPEC_DEF0(name)\
2

template<>\
3

struct name##Type<NullType>\
4

{\
5

typedef NullType type;\
6

};\
7

#define LOKI_TYPELIST_TYPE_SPEC_DEF1(name)\
9

template<class T>\
10

struct name##Type<Typelist<T,NullType> >\
11

{\
12

typedef T type;\
13

};\
14

#define LOKI_TYPELIST_TYPE_SPEC_DEF2(name,b)\
16

template<class T,class U>\
17

struct name##Type<Typelist<T,U> >\
18

{\
19

typedef typename name##Type<U>::type R;\
20

typedef typename Select< b ? (sizeof(T)>sizeof(R)) : (sizeof(T)<sizeof(R)),T,R>::Result type;\
21

};\
22

LOKI_TYPELIST_TYPE_SPEC_DEF0(Max)
24

LOKI_TYPELIST_TYPE_SPEC_DEF0(Min)
25

LOKI_TYPELIST_TYPE_SPEC_DEF1(Max)
26

LOKI_TYPELIST_TYPE_SPEC_DEF1(Min)
27

LOKI_TYPELIST_TYPE_SPEC_DEF2(Max,true)
28

LOKI_TYPELIST_TYPE_SPEC_DEF2(Min,false)
29

#undef LOKI_TYPELIST_TYPE_SPEC_DEF0
31

#undef LOKI_TYPELIST_TYPE_SPEC_DEF1
32

#undef LOKI_TYPELIST_TYPE_SPEC_DEF2

这里用到了Loki中的Select组件来选择类型。

示例
使用LOKI中的LOKI_STATIC_CHECK宏来做编译期诊断结果正确性。

#define LOKI_TL4 LOKI_TYPELIST_4(double,int,short,char)
2

int main(int argc,char *argv[])
4

{
5

static const int max_val = Loki::TL::MaxSize<LOKI_TL4 >::value;
6

LOKI_STATIC_CHECK(max_val==sizeof(double),max_val_should_be_sizeof_double)
7

static const int min_val = Loki::TL::MinSize<LOKI_TL4 >::value;
9

LOKI_STATIC_CHECK(min_val==sizeof(char),min_val_should_be_sizeof_char)
10

typedef Loki::TL::MaxType<LOKI_TL4 >::type max_type;
12

LOKI_STATIC_CHECK((Loki::IsSameType<max_type,double>::value),max_type_should_be_double)
13

typedef Loki::TL::MinType<LOKI_TL4 >::type min_type;
15

LOKI_STATIC_CHECK((Loki::IsSameType<min_type,char>::value),min_type_should_be_char)
16

return 0;
18

}

posted @ 2012-05-29 01:03 春秋十二月阅读(1890) | 评论 (2) | 编辑收藏

三路划分快速排序--针对重复关键字的改进

基本原理
   快速排序算法是一种分治排序算法，影响其性能的因素有划分元素的选择、小的子文件的处理、重复关键字等，本文论述针对重复关键字的改进实现。首先来回顾下一般的算法实现，其流程如下：
   a. 选择一个划分元素，这个元素在划分后将在最终的位置上，通常是选择最右端元素作为划分点。
   b. 从左端开始扫描，直到找到大于划分元素的元素；同时从右端开始扫描，直到找到小于划分元素的元素，再交换使扫描停止的这两个元素。
   c. 继续步骤b，直到左指针不小于右指针，最后再交换左指针元素和划分元素。
   d. 在左指针左侧和右侧区间(区间不包括左指针元素)重复以上过程，直至元素个数为0或1。
   在划分的过程中，位于左指针左侧的元素都比划分元素小，右侧的元素都比划分元素大，如下图所示

   由上述可见，一般的算法实现针对大量重复关键字的输入情况，其性能表现很差，例如如果一个文件完全由相等的值(只有一个值)组成，那么它就不需要再进行任何排序，但前面的算法依然划分直至得到小的子文件，无论文件有多大。针对这一情况，可以作实质性的改进，从而避免处理元素相同的子区间，提高效率。改进的算法实现主要问题在于如何处理与划分元素相等的情况，这里的基本思想是将区间划分为三个部分，左部分小于划分元素，中间部分等于划分元素，右部分大于划分元素，然后再在左右两部分进行子处理，具体的流程如下：
   a'. 选择左端元素、中间元素和右端元素的中值作为划分元素，也就是三者取中划分，这样能有效避免划分区间的最坏情况。
   b'. 从左端开始扫描，直到找到不小于划分元素的元素；同时从右端开始扫描，直到找到不大于划分元素的元素，再交换使扫描停止的这两个元素。如果左指针元素等于划分元素，那么与左端的元素交换，并递增左端位置(初始化为文件最左位置)；如果右指针元素等于划分元素，那么与右端元素交换，并递减右端位置(初始化为文件最右位置)。
   c'. 继续步骤b'，直到左指针不小于右指针。
   d'. 交换最左端区间和左指针左侧区间(不包括左指针元素)，这一过程会递减左端位置；交换最右端区间和左指针右侧区间(包括左指针元素)，这一过程会递增右端位置。
   e'. 在最左端和最右端区间重复以上过程，直至元素个数为0或1。
   在划分的过程中，与划分元素相等的元素分布在最左端和最右端，如下图所示

在划分完成后处理子文件前，需要对调区间，如步骤d'所述，结果如下图所示

代码实现
上面所有图中的v代表划分元素，最后列出代码清单，函数quick_sort有两个版本，一个是支持operator < 的默认实现，另一个是支持带谓词的自定义比较实现。在其中用到了实现三者取中值的__median函数，对应的也有两个版本实现，如下所示

template<class _RandIt>
2

void quick_sort(_RandIt _first,_RandIt _last)
3

{
4

typedef typename std::iterator_traits<_RandIt>::value_type _ValType;
5

if (!(_first<_last-1)) return;
6

_RandIt i = _first,j = _last-1,p = i,q = j,k;
8

_ValType pivot = __median(*_first,*(_last-1),*(_first+(_last-_first)/2));
9

while(true)
11

{
12

while(*i < pivot) ++i;
13

while(pivot < *j) --j;
14

if (!(i < j)) break;
15

std::iter_swap(i,j);
16

if (!(*i < pivot) && !(pivot < *i))
18

std::iter_swap(p++,i);
19

if (!(*j < pivot) && !(pivot < *j))
20

std::iter_swap(q--,j);
21

++i; --j;
22

}
23

j = i - 1;
25

for(k = _first;k<p;--j,++k) std::iter_swap(k,j);
26

for(k = _last-1;k>q;++i,--k) std::iter_swap(k,i);
27

quick_sort(_first,j+1);
29

quick_sort(i,_last);
30

}
31

template<class _RandIt,class _Compare>
33

void quick_sort(_RandIt _first,_RandIt _last,_Compare _comp)
34

{
35

typedef typename std::iterator_traits<_RandIt>::value_type _ValType;
36

if (!(_first < _last - 1)) return;
37

_RandIt i = _first,j = _last-1,p = i, q = j, k;
39

_ValType pivot = __median(*_first,*(_last-1),*(_first+(_last-_first)/2),_comp);
40

while(true)
42

{
43

while(_comp(*i,pivot)) ++i;
44

while(_comp(pivot,*j)) --j;
45

if (!(i < j)) break;
46

std::iter_swap(i,j);
47

if (!_comp(*i,pivot) && !_comp(pivot,*i))
49

std::iter_swap(p++,i);
50

if (!_comp(*j,pivot) && !_comp(pivot,*j))
51

std::iter_swap(q--,j);
52

++i; --j;
53

}
54

j = i - 1;
55

for(k = _first;k < p;++k,--j)
56

std::iter_swap(k,j);
57

for(k = _last - 1;k > q;--k,++i)
58

std::iter_swap(k,i);
59

quick_sort(_first,j+1,_comp);
61

quick_sort(i,_last,_comp);
62

}

从上面实现可看出，与一般的实现相比，划分过程多了两个if及for循环，if测试用来将找到的重复元素放在左右两端；for循环用来交换区间，将重复元素再放在中间，这额外的工作量只与找到的重复关键字的个数成线性，因此，即使在没有重复关键字的情况下，它也运行得很好，平均时间复杂度为O(NlgN)。

posted @ 2012-05-19 14:48 春秋十二月阅读(2693) | 评论 (1) | 编辑收藏

模板元编程（1）：选择API

摘要: C与C++ API的比较在c语言中，API体现为c函数，如操作系统提供的一系列API，在c++中，API体现为自由函数，这里的自由函数是指除普通成员函数、静态成员函数、友元函数外的能在某命名空间作用域或全局空间内直接访问的函数，而这更多地体现为函数模板，如stl提供的一系列算法swap、count和sort等。相对于c API，c++ API具有类型安全和封... 阅读全文

posted @ 2011-12-24 19:08 春秋十二月阅读(2950) | 评论 (2) | 编辑收藏

仅列出标题

常用链接

留言簿(73)

随笔分类(156)

随笔档案(157)

文章分类(30)

关注的开源项目

最新随笔

积分与排名

最新评论

阅读排行榜

评论排行榜