C++博客-#ant

strlen源码剖析

蚂蚁终结者 — Fri, 12 Oct 2007 05:19:00 GMT

摘要: 学习高效编程的有效途径之一就是阅读高手写的源代码，CRT(C/C++ Runtime Library)作为底层的函数库，实现必然高效。恰好手中就有glibc和VC的CRT源代码，于是挑了一个相对简单的函数strlen研究了一下，并对各种实现作了简单的效率测试。strlen的函数原形如下： size_t strlen(const char *str);strlen返回str中字符的个数，其... 阅读全文

蚂蚁终结者 2007-10-12 13:19 发表评论

TEA加密算法的C/C++实现

蚂蚁终结者 — Fri, 12 Oct 2007 05:17:00 GMT

摘要: TEA(Tiny Encryption Algorithm) 是一种简单高效的加密算法，以加密解密速度快，实现简单著称。算法真的很简单，TEA算法每一次可以操作64-bit(8-byte)，采用128-bit(16-byte)作为key，算法采用迭代的形式，推荐的迭代轮数是64轮，最少32轮。目前我只知道QQ一直用的是16轮TEA。没什么好说的，先给出C语言的源代码(默认是32轮)： 1 v... 阅读全文

蚂蚁终结者 2007-10-12 13:17 发表评论

Win32 Service的简单封装

蚂蚁终结者 — Mon, 24 Sep 2007 05:01:00 GMT

前段时间学习Windows程序设计，刚好学到Win32 Service，于是写了两个简单的类：BaseService和ServiceCtrl。虽然功能比较简单，但是也能适用于大多数情况。下面介绍一下简单用法，如果你刚好需要写一些简单的服务程序，这两个类也许能派上用场：

1. BaseService
BaseService.h

1 #ifndef BASE_SERVICE_H
2 #define BASE_SERVICE_H
3
4 class BaseService {
5 public :
6     explicit BaseService(LPCTSTR szServiceName,
7                 DWORD dwServiceType = SERVICE_WIN32_OWN_PROCESS,
8                 DWORD dwStartType = SERVICE_AUTO_START);
9     virtual ~ BaseService() {}
10     bool ParseStandardArgs(int argc, char* argv[]);
11     bool IsInstalled();
12     bool Install();
13     bool Uninstall();
14     bool Start();
15 private :
16     virtual void Run() = 0 ;
17     virtual bool OnInitialize() { return true ; }
18     virtual void OnStop() {}
19     virtual void OnPause() {}
20     virtual void OnContinue() {}
21     virtual void OnInterrogate() {}
22     virtual void OnShutdown() {}
23     virtual void OnUserControl(DWORD dwControl) {}
24     ...
25 };
26
27 #endif/*BASE_SERVICE_H*/

要实现自己的服务类只需从BaseService继承并且Override相关的virtual函数即可，下面示范一个BeepService类，该服务只是简单地每隔2秒beep一下，为了简单所有代码均放在.h文件中：
BeepService.h

1 #ifndef BEEP_SERVICE_H
2 #define BEEP_SERVICE_H
3
4 #include "BaseService.h"
5
6 class BeepService : public BaseService {
7 public :
8     BeepService(LPCTSTR szServiceName)
9         :BaseService(szServiceName)
10         ,m_bPaused(false )
11         ,m_bRunning(false ) {}
12
13     virtual void OnStop() { m_bRunning = false ; }
14     virtual void OnPause() { m_bPaused = true ; }
15     virtual void OnContinue() { m_bPaused = false ; }
16     virtual void Run() {
17         m_bRunning = true ;
18         while (m_bRunning) {
19             if (! m_bPaused)
20                 Beep(800, 800 );
21             Sleep(2000 );
22         }
23     }
24 private :
25     volatile bool m_bPaused;
26     volatile bool m_bRunning;
27 };
28
29 #endif/*BEEP_SERVICE_H*/

通常来说只须要Override上面的4个virtual函数就OK了：
在Run()中进行实际的工作，OnStop(),OnPause(),OnContinue()则是为了响应Service Control Manager的控制。

test.cpp

1 #include <windows.h>
2 #include <tchar.h>
3 #include <stdio.h>
4 #include "BeepService.h"
5
6 int main(int argc, char * argv[]) {
7
8     BeepService beepService(_T("BeepService" ));
9     if (! beepService.ParseStandardArgs(argc, argv)) {
10         if (beepService.IsInstalled()) {
11             if (! beepService.Start())
12                 printf("The service can not run from command line.\n" );
13         } else {
14             printf("The service is not installed, "
15                 "use \"%s -i\" to install.\n", argv[0 ]);
16         }
17     }
18     return 0 ;
19 }

假设编译后生成的exe文件为beep.exe，则在命令行中可以如下使用：
(1). beep -i 安装service(安装以后系统运行时会自动启动)
(2). beep -u 卸载service(如果service正在运行，则先停止service再卸载)
BaseServiced 的ParseStandardArgs正是用来解析上述两个命令。

2. ServiceCtrl
虽然Windows自带的Service Control Manager可以控制服务程序，但是很多时候我们都需要用代码控制，这就用到ServiceCtrl类，该类的接口如下：
ServiceCtrl.h

1 #ifndef SERVICE_CTRL_H
2 #define SERVICE_CTRL_H
3
4 class ServiceCtrl {
5 public :
6     ServiceCtrl(LPCTSTR szServiceName);
7     ~ ServiceCtrl();
8     bool Start();
9     bool Pause();
10     bool Continue();
11     bool Stop();
12     bool Interrogate();
13     bool UserControl(DWORD dwControl);
14     DWORD State() const ;
15     ...
16 };
17
18 #endif/*SERVICE_CTRL_H*/

接口比较直观没什么好说的，看下面的示例代码：
test.cpp

1 #include <windows.h>
2 #include <tchar.h>
3 #include <stdio.h>
4 #include <exception>
5 #include "BeepService.h"
6 #include "ServiceCtrl.h"
7
8 int main(int argc, char * argv[]) {
9
10     try {
11         ServiceCtrl servCtrl(_T("BeepService" ));
12         if (servCtrl.State() != SERVICE_STOPPED) {
13             printf("Service already started.\n" );
14         } else {
15             servCtrl.Start();
16             printf("Start.\n" );
17             Sleep(6000 );
18             servCtrl.Pause();
19             printf("Pause.\n" );
20             Sleep(6000 );
21             servCtrl.Continue();
22             printf("Continue.\n" );
23             Sleep(6000 );
24             servCtrl.Stop();
25             printf("Stop.\n" );
26         }
27     } catch (std::exception & e) {
28         printf("%s\n" , e.what());
29     }
30     return 0 ;
31 }

源代码：点击下载

蚂蚁终结者 2007-09-24 13:01 发表评论

MD5算法的C++实现

蚂蚁终结者 — Tue, 11 Sep 2007 04:20:00 GMT

摘要: 1. Introduction MD5算法是一种消息摘要算法(Message Digest Algorithm)，此算法以任意长度的信息(message)作为输入进行计算，产生一个128-bit(16-byte)的指纹或报文摘要(fingerprint or message digest)。两个不同的message产生相同message digest的几率相当小，从一个给定的message ... 阅读全文

蚂蚁终结者 2007-09-11 12:20 发表评论

非完美C++ Singleton实现[2]

蚂蚁终结者 — Fri, 07 Sep 2007 15:22:00 GMT

4.解决多线程问题
上一篇实现的Singleton只能在单线程环境中使用，在多线程环境中会出现很多问题，看Instance()实现代码：

1 static Singleton& Instance() {
2     if (0 == _instance) { //1
3         _instance = new Singleton(); //2
4         atexit(Destroy);
5     }
6     return *_instance; //3
7 }

考虑如下情况：线程一调用Instance()，进入//1，0 == _instance 返回true，线程一于是进入//2。这时候线程一被挂起，线程二开始执行，线程二调用Instance()，进入//1，发现0 == _instance 仍然返回true，线程二于是也进入//2，线程二继续执行到//3直到返回。这时候线程一被唤醒，继续从//2开始执行，这将会覆盖线程二创建的_instance，线程一继续执行到//3直到返回...

解决方法很简单，引入相关同步对象(synchronization object)就行了，例如在win32平台下可以如下实现：
synobj.h

1 #ifndef SYNOBJ_H
2 #define SYNOBJ_H
3
4 #include <windows.h>
5
6 #define CLASS_UNCOPYABLE(classname) \
7     private: \
8     classname(const classname&); \
9     classname& operator=(const classname&);
10
11 class Mutex {
12     CLASS_UNCOPYABLE(Mutex)
13 public:
14     Mutex() :_cs() { InitializeCriticalSection(&_cs); }
15     ~Mutex() { DeleteCriticalSection(&_cs); }
16     void lock() { EnterCriticalSection(&_cs); }
17     void unlock() { LeaveCriticalSection(&_cs); }
18 private:
19     CRITICAL_SECTION _cs;
20 };
21
22 class Lock {
23     CLASS_UNCOPYABLE(Lock)
24 public:
25     explicit Lock(Mutex& cs) :_cs(cs) { _cs.lock(); }
26     ~Lock() { _cs.unlock(); }
27 private:
28     Mutex& _cs;
29 };
30
31 #endif/*SYNOBJ_H*/

有了同步对象很容易就能够写出如下代码：
singleton.h

1 #ifndef SINGLETON_H
2 #define SINGLETON_H
3
4 #include "synobj.h"
5
6 class Singleton {
7 public:
8     static Singleton& Instance() { // Unique point of access
9         Lock lock(_mutex);
10         if (0 == _instance) {
11             _instance = new Singleton();
12             atexit(Destroy); // Register Destroy function
13         }
14         return *_instance;
15     }
16     void DoSomething(){}
17 private:
18     static void Destroy() { // Destroy the only instance
19         if ( _instance != 0 ) {
20             delete _instance;
21             _instance = 0;
22         }
23     }
24     Singleton(){} // Prevent clients from creating a new Singleton
25     ~Singleton(){} // Prevent clients from deleting a Singleton
26     Singleton(const Singleton&); // Prevent clients from copying a Singleton
27     Singleton& operator=(const Singleton&);
28 private:
29     static Mutex _mutex;
30     static Singleton *_instance; // The one and only instance
31 };
32
33 #endif/*SINGLETON_H*/

singleton.cpp

1 #include "singleton.h"
2
3 Mutex Singleton::_mutex;
4 Singleton* Singleton::_instance = 0;

现在的Singleton虽然多线程安全，性能却受到了影响。从Instance()中可以看到，实际上仅仅当0 == _instance为true时才需要Lock。你很容易就写出如下代码：

1 static Singleton& Instance() {
2     if (0 == _instance) {
3         Lock lock(_mutex);
4         _instance = new Singleton();
5         atexit(Destroy);
6     }
7     return *_instance;
8 }

但是这样还是会产生竞争条件(race condition)，一种广为人知的做法是使用所谓的Double-Checked Locking：

1 static Singleton& Instance() {
2     if (0 == _instance) {
3         Lock lock(_mutex);
4         if (0 == _instance) {
5             _instance = new Singleton();
6             atexit(Destroy);
7         }
8     }
9     return *_instance;
10 }

Double-Checked Locking机制看起来像是一个完美的解决方案，但是在某些条件下仍然不行。简单的说，编译器为了效率可能会重排指令的执行顺序(compiler-based reorderings)。看这一行代码：

_instance = new Singleton();

在编译器未优化的情况下顺序如下：
1.new operator分配适当的内存；
2.在分配的内存上构造Singleton对象；
3.内存地址赋值给_instance。

但是当编译器优化后执行顺序可能如下：
1.new operator分配适当的内存；
2.内存地址赋值给_instance；
3.在分配的内存上构造Singleton对象。

当编译器优化后，如果线程一执行到2后被挂起。线程二开始执行并发现0 == _instance为false，于是直接return，而这时Singleton对象可能还未构造完成，后果...

上面说的还只是单处理器的情况，在多处理器(multiprocessors)的情况下，超线程技术必然会混合执行指令，指令的执行顺序更无法保障。关于Double-Checked Locking的更详细的文章，请看：
The "Double-Checked Locking is Broken" Declaration

5.使用volatile关键字
为了说明问题，请先考虑如下代码：

1 class MyThread : public Thread {
2 public:
3     virtual void run() {
4         while (!_stopped) {
5             //do something
6         }
7     }
8     void stop() {
9         _stopped = true;
10     }
11 private:
12     bool _stopped;
13 };
14
15 ...
16
17 MyThread thread;
18 thread.start();

上面用thread.start()开启了一个线程，该线程在while循环中检测bool标记_stopped，看是否该继续执行。如果想要结束这个线程，调用thread.stop()应该没问题。但是需要注意的是编译器很有可能对_stopped的存取进行优化。如果编译器发现_stopped被频繁存取(_stopped在while循环中)，编译器可能会考虑将_stopped缓存到寄存器中，以后_stopped将会直接从寄存器存取。这时候如果某个线程调用了thread.stop()，对_stopped的修改将不会反映到寄存器中，thread将会永远循环下去...

为了防止编译器优化，用volatile关键字就OK了，volatile跟const的用法几乎一样，能用const的地方也都能用volatile。对Singleton来说，修改如下两处即可：

1 //singleton.h中
2 static Singleton *_instance;
3 //改为
4 static Singleton * volatile _instance;
5
6 //singleton.cpp中
7 Singleton* Singleton::_instance = 0;
8 //改为
9 Singleton* volatile Singleton::_instance = 0;

6.将Singleton泛化为模板
singleton.h

1 #ifndef SINGLETON_H
2 #define SINGLETON_H
3
4 #include "synobj.h"
5
6 template<class T>
7 class Singleton {
8     CLASS_UNCOPYABLE(Singleton)
9 public:
10     static T& Instance() { // Unique point of access
11         if (0 == _instance) {
12             Lock lock(_mutex);
13             if (0 == _instance) {
14                 _instance = new T();
15                 atexit(Destroy);
16             }
17         }
18         return *_instance;
19     }
20 protected:
21     Singleton(){}
22     ~Singleton(){}
23 private:
24     static void Destroy() { // Destroy the only instance
25         if ( _instance != 0 ) {
26             delete _instance;
27             _instance = 0;
28         }
29     }
30     static Mutex _mutex;
31     static T * volatile _instance; // The one and only instance
32 };
33
34 template<class T>
35 Mutex Singleton<T>::_mutex;
36
37 template<class T>
38 T * volatile Singleton<T>::_instance = 0;
39
40 #endif/*SINGLETON_H*/

测试代码：
test.cpp

1 #include "singleton.h"
2
3 class A : public Singleton<A> {
4     friend class Singleton<A>;
5 protected:
6     A(){}
7     ~A(){}
8 public:
9     void DoSomething(){}
10 };
11
12 int main() {
13
14     A &a = A::Instance();
15     a.DoSomething();
16
17     return 0;
18 }

7.Singleton的析构问题
到此Singleton已经算比较完善了，但是依然算不上完美，因为到现在只是解决了多线程问题，加入了模板支持，对于KDL problem(The Dead Reference Problem)依然没法解决，可以说在实现Singleton模式时，最大的问题就是多个有依赖关系的Singleton的析构顺序。虽然Modern C++ Design中给出了解决方案，但是Loki的实现太过复杂，在此就不详细说明了，有兴趣的可以看看Modern C++ Design，当然了，Loki库中用策略模式实现的Singleton也很不错！

蚂蚁终结者 2007-09-07 23:22 发表评论

非完美C++ Singleton实现[1]

蚂蚁终结者 — Fri, 07 Sep 2007 06:49:00 GMT

Singleton模式是一种非常简单的设计模式，这种模式很常用也很容易被滥用。当你设计应用程序的时候，经常会遇到某些对象在整个程序的生命周期应该仅有一个实例的情况，比如File System，Graphic System，Logging Utility，这时候就可以用到Singleton模式。Singleton模式在GOF中描述如下：

Ensure a class only has one instance, and provide a global point of access to it.

Singleton模式的定义很简单，实现也有N多种，但是却很难找到一个称得上“完美”的。实现一个完美的Singleton比想象中要难的多，下面探索性的来实现一个非完美的。

1.典型实现
在C++中，Singleton模式的典型实现如下：

1 // Header file Singleton.h
2 class Singleton {
3 public :
4     static Singleton& Instance() { // Unique point of access
5         if (0 == _instance)
6             _instance = new Singleton();
7         return * _instance;
8     }
9     void DoSomething();
10 private :
11     Singleton(); // Prevent clients from creating a new Singleton
12     ~Singleton(); // Prevent clients from deleting a Singleton
13     Singleton(const Singleton&); // Prevent clients from copying a Singleton
14     Singleton& operator=(const Singleton& );
15 private :
16     static Singleton *_instance; // The one and only instance
17 };
18
19 // Implementation file Singleton.cpp
20 Singleton* Singleton::_instance = 0;

通过将Singleton的构造函数设为private可以禁止客户代码直接创建Singleton对象，除此之外，Singleton的copy constructor和copy assignment operator都为private且仅有声明没有实现，禁止了客户代码拷贝Singleton对象。唯一可以创建Singleton对象的是Singleton自己的静态成员函数Instance，这样就在编译器保证了Singleton实例的唯一性。上面这些是在C++中实现Singleton模式最基本的要点。

Instance方法保证只有在第一次调用时才会生成Singleton对象，以后的调用只是简单返回唯一的已存在的实例。Instance方法实际上实现的是懒惰初始化(lazy initialize)，如果程序中根本没有用到Singleton对象，也就根本不会产生Singleton的实例，这在Singleton对象很少使用且创建Singleton对象开销比较大的情况下特别有用。

客户代码现在可以这样使用Singleton：

1 Singleton &s = Singleton::Instance();
2 s.DoSomething();

还需要说明的是Singleton的析构函数，析构函数也为private可以禁止客户写出如下代码。如果某个客户写出了如下代码，随后的对Singleton的访问就会导致为定义行为，因为Singleton对象已经不存在。

1 Singleton *p = & Singleton::Instance();
2 delete p;

2.引入smart pointer
上面的实现算是一个好的实现吗？当然不是，或许连一个正确的实现都算不上。如果你想凑合，当然没问题，上面的代码大多数情况下可以工作的很好。也许你已经注意到了一些问题，比如说在上面的代码中只有new没有delete。是的，你说会发生memory leak对吧，其实memory leak都不是主要的问题，所有的现代操作系统在进程结束的时候都会对内存很好的进行回收。比memory leak更值得让人担忧的是resource leak，如果Singleton在构造函数中请求了某些资源：网络连接，文件句柄，数据库连接等。这些资源将得不到释放。

唯一修正resource leak的方法就是在程序结束的时候delete _instance。当然了，用smart pointer再好不过，在这里用auto_ptr就可以满足需要了(如果你还不知道smart_ptr是什么，花点时间熟悉C++标准库吧)，修改后的代码如下：

1 // Header file Singleton.h
2 class Singleton {
3 public :
4     static Singleton& Instance() { // Unique point of access
5         if (0 == _instance.get())
6             _instance.reset(new Singleton());
7         return * (_instance.get());
8     }
9     void DoSomething(){}
10 private :
11     Singleton(){} // Prevent clients from creating a new Singleton
12     ~Singleton(){} // Prevent clients from deleting a Singleton
13     Singleton(const Singleton&); // Prevent clients from copying a Singleton
14     Singleton& operator=(const Singleton& );
15 private :
16     friend auto_ptr<Singleton> ;
17     static auto_ptr<Singleton> _instance; // The one and only instance
18 };
19
20 // Implementation file Singleton.cpp
21 auto_ptr<Singleton> Singleton::_instance;

3.用atexit替换smart pointer
C++并没有规定不同编译单元(translation unit，简单说就是一个可编译的cpp文件)中static对象的初始化顺序。如果一个程序中有多个Singleton对象，那么这些Singleton对象的析构顺序也将是任意的。很显然，当多个Singleton对象有依赖关系时，smart pointer根本无法保证Singleton的析构顺序。

msdn中对atexit描述如下：

The atexit function is passed the address of a function (func) to be called when the program terminates normally. Successive calls to atexit create a register of functions that are executed in last-in, first-out (LIFO) order. The functions passed to atexit cannot take parameters. atexit use the heap to hold the register of functions. Thus, the number of functions that can be registered is limited only by heap memory.

需要说明的是atexit并不比smart pointer好多少，LIFO的保证对于有复杂依赖关系的多个Singleton依然束手无力，但是用atexit替换smart pointer却是必须的，它是设计完美Singleton的基础。

#如果你疑惑atexit为什么还是不行，请考虑下面的情况：
NOTE：下面的情况在Modern C++ Design中叫做KDL(Keyboard,Display,Log)problem。

某个程序中使用了如下3个Singleton：Keyboard，Display，Log。Keyboard和Display分别对应于计算机的键盘和显示器，Log用来记录错误信息。假设当Keyboard和Display的构造函数和析构函数出现错误时会调用Log记录错误信息，并且构造和析构导致的任何错误都会终止程序。

在程序启动时，如果Keyboard构造成功，Display构造失败，很显然在Display的构造函数中将会构造Log而且失败信息会被Log记录，根据假设这时候程序准备退出，atexit注册的函数将会按LIFO的顺序被调用。因为Keyboard先于Log构造，所以Log先于Keyboard析构，但是当由于某种原因Keyboard在析构时失败，想要调用Log记录错误信息时，Log早已被销毁，则Log::Instance()将会导致未定义行为。

#atexit的严重问题：
从上面的例子可以看出，atexit和smart pointer相比仅仅是有LIFO的保证而已，这样的保证貌似也不怎么有效，因为atexit跟smart pointer一样也无法解决KDL probleam。

atexit由于LIFO带来了另外的问题，看下面的代码：

1 #include <cstdlib>
2 void Bar() {
3     ...
4 }
5 void Foo() {
6     std::atexit(Bar);
7 }
8 int main() {
9     std::atexit(Foo);
10     return 0 ;
11 }

上面的小段代码用atexit注册了Foo，Foo调用了std::atexit(Bar)。当程序退出时，根据atexit的LIFO保证，Bar在Foo之后注册，因此Bar应该在Foo之前调用，但是当Bar注册的时候Foo已经调用了，Bar根本就没有机会能够在Foo之前调用。这明显自相矛盾对吧，没办法，C++标准好像忽视了这一点，因此如果类似代码被调用，肯定不会有什么好的结果，好一点是resource leak，差一点估计程序就崩溃了！！！

atexit的这个问题跟Singleton有关系吗？当然有，如果在一个Singleton的析构函数中调用atexit就会出现上述问题。即在KDL problem中，如果Keyboard和Display都构造成功，当Keyboard或Display任意一个析构失败时，Keyboard或Display在析构函数中会构造Log，Log的构造函数会间接调用atexit。oops!!!，可怕的未定义行为。

看到这里你一定对atexit相当失望，貌似它带来的好处多于坏处。但是请你相信，如果适当设计，atexit在后面的Singleton改造中会起到很重要的作用。

用atexit后的代码：

1 // Header file Singleton.h
2 class Singleton {
3 public :
4     static Singleton& Instance() { // Unique point of access
5         if (0 == _instance) {
6             _instance = new Singleton();
7             atexit(Destroy); // Register Destroy function
8         }
9         return * _instance;
10     }
11     void DoSomething(){}
12 private :
13     static void Destroy() { // Destroy the only instance
14         if ( _instance != 0 ) {
15             delete _instance;
16             _instance = 0 ;
17         }
18     }
19     Singleton(){} // Prevent clients from creating a new Singleton
20     ~Singleton(){} // Prevent clients from deleting a Singleton
21     Singleton(const Singleton&); // Prevent clients from copying a Singleton
22     Singleton& operator=(const Singleton& );
23 private :
24     static Singleton *_instance; // The one and only instance
25 };
26
27 // Implementation file Singleton.cpp
28 Singleton* Singleton::_instance = 0;

你有没有仔细考虑过Destroy中的_instance = 0;这一行代码，上述代码实际上实现的是不死鸟模式(The Phoenix Singleton)，所谓不死鸟，就跟一辉一样可以死而复生。上面的代码可以解决本文最早提出的KDL problem，即如果Keyboard析构失败，虽然Log已经析构，但是由于Destroy中的_instance = 0;这一行代码，Log::Instance()将会创建一个新的Log对象，程序将会表现良好。当然了，Phoenix Singleton仅能用于无状态的Singleton，如果Log需要保存某些状态，Phoenix Singleton也不会带来任何好处。你当然可以用某些方法维持Phoenix Singleton的状态，但是在做之前先想想看是否值得，维持状态可能会使Singleton变得特别复杂。

上面的Phoenix Singleton已经可以满足大部分需要，如果你的Singleton没有涉及到多线程，多个Singleton之间也没有依赖关系，你大可以放心使用。但是如果你用到多线程，或者你的Singleton关系如KDL般复杂，或者你觉得对每一个Singleton都敲同样的代码让你厌烦。在后面几篇会有一个多线程安全的，能够解决多个Singleton依赖关系的，基于模板的Singleton实现。

蚂蚁终结者 2007-09-07 14:49 发表评论

从Win32 API封装Thread类[2]

蚂蚁终结者 — Fri, 31 Aug 2007 03:58:00 GMT

在上一篇中介绍了创建Thread的两种方法：从Thread类继承或者实现Runnable接口。有时候这并不是特别方便，我们需要的是更灵活的方法，比如像boost库中的Thread一样可以用普通函数和函数对象
(functor and function object)作为构造函数参数。如果你熟悉STL，你应该熟悉bind1st和bind2nd这两个函数配接器(function adapter)，bind1st和bind2nd可以将一个二元函数(binary function)转换成一元函数(unary function)。为了使Thread类能够用普通函数和函数对象作为参数，我们需要一个bind将一元函数转换成无参函数：
bind.h

1 #ifndef BIND_H
2 #define BIND_H
3
4 template <class _Result>
5 struct trivial_function {
6     typedef _Result result_type;
7 };
8
9 template <class _Operation>
10 class binder : public trivial_function<typename _Operation::result_type> {
11 public:
12     binder(const _Operation& x, const typename _Operation::argument_type& y)
13         :op(x), value(y) {}
14     typename _Operation::result_type operator()() const {
15         return op(value);
16     }
17 protected:
18     _Operation op;
19     typename _Operation::argument_type value;
20 };
21
22 template <class _Operation, class _Tp>
23 inline binder<_Operation>
24 bind(const _Operation& __fn, const _Tp& __x)
25 {
26     typedef typename _Operation::argument_type _Arg_type;
27     return binder<_Operation>(__fn, _Arg_type(__x));
28 }
29
30 #endif/*BIND_H*/

有了bind我们还需要修改Thread类的构造函数，显然我们必须将构造函数声明为成员模板(还有一种方法也可以达到同样的目的，就是把Thread类声明为模板，但是这样的设计好像不太好)，这样才能够让Thread类的构造函数可以接受各种类型的参数，修改后的构造函数应该能够使用如下三种类型的参数：
1.Runnable *
2.no argument function
3.no argument functor
下面是修改后的头文件：
runnable.h

1 #ifndef RUNNABLE_H
2 #define RUNNABLE_H
3
4 struct Runnable {
5     virtual void run() = 0;
6     virtual ~Runnable() {}
7 };
8
9 template <class T>
10 class RunnableFunctor : public Runnable {
11 public:
12     RunnableFunctor(const T& f) :_func(f) {}
13     virtual void run() { _func(); }
14 private:
15     T _func;
16 };
17
18 //base template for no argument functor
19 template <class T>
20 struct FuncImpl {
21     static Runnable* transfer(const T& t) {
22         return new RunnableFunctor<T>(t);
23     }
24 };
25
26 //partial specialization for T*
27 template <class T>
28 struct FuncImpl<T*> {
29     static Runnable* transfer(T* t) {
30         return t;
31     }
32 };
33
34 //partial specialization for no argument function
35 template <class T>
36 struct FuncImpl<T (*)()> {
37     static Runnable* transfer(T (*t)()) {
38         return new RunnableFunctor<T (*)()>(t);
39     }
40 };
41
42 template <class T>
43 inline Runnable* transfer(const T& t) {
44     return FuncImpl<T>::transfer(t);
45 }
46
47 #endif/*RUNNABLE_H*/

thread.h

1 #ifndef THREAD_H
2 #define THREAD_H
3
4 #include <windows.h>
5 #include "bind.h"
6 #include "runnable.h"
7
8 #define CLASS_UNCOPYABLE(classname) \
9     private: \
10     classname(const classname&); \
11     classname& operator=(const classname&);
12
13 class Thread : public Runnable {
14     CLASS_UNCOPYABLE(Thread)
15 public:
16     Thread()
17         :_target(0)
18         ,_handle(0) {
19
20     }
21     template <class T>
22     explicit Thread(const T& op)
23         :_target(transfer(op))
24         ,_handle(0) {
25
26     }
27     virtual ~Thread();
28     virtual void run() {}
29     void start();
30     void join();
31 private:
32     static unsigned __stdcall threadProc(void* param);
33 private:
34     Runnable* _target;
35     HANDLE _handle;
36 };
37
38 #endif/*THREAD_H*/

thread.cpp和前一篇的几乎一样，唯一的不同是去掉了构造函数Thread(Runnable *)，因为现在的构造函数改成了成员模板，实现也放在thread.h中了。现在的构造函数能够接受各种类型的参数，主要归功于模板函数transfer，实现代码在runnable.h中，主要技巧是用类的偏特化模拟函数模板的偏特化，不明白的请看为什么不要特化函数模版。

下面是测试代码：
test.cpp

1 #include "thread.h"
2 #include <iostream>
3 #include <functional>
4
5 using namespace std;
6
7 //no argument function
8 void print() {
9     cout << "print" << endl;
10 }
11
12 //unary function
13 void print1(int n) {
14     cout << "print1" << endl;
15 }
16
17 //binary function
18 void print2(int m, int n) {
19     cout << "print2" << endl;
20 }
21
22
23 //no argument functor
24 struct PrintFunctor {
25     void operator()() const {
26         cout << "PrintFunctor" << endl;
27     }
28 };
29
30 //unary functor
31 struct PrintFunctor1 : public unary_function<int, void> {
32     void operator()(int n) const {
33         cout << "PrintFunctor1" << endl;
34     }
35 };
36
37 //binary functor
38 struct PrintFunctor2 : public binary_function<int, int, void> {
39     void operator()(int m, int n) const {
40         cout << "PrintFunctor2" << endl;
41     }
42 };
43
44 int main() {
45
46     //construct Thread with no argument function
47     Thread thread1(&print);
48     thread1.start();
49
50     //construct Thread with unary function
51     Thread thread2(bind(ptr_fun(print1), 5));
52     thread2.start();
53
54     //construct Thread with binary function
55     Thread thread3(bind(bind1st(ptr_fun(print2), 1), 2));
56     thread3.start();
57
58
59     //construct Thread with no argument functor
60     Thread thread4((PrintFunctor()));
61     thread4.start();
62
63     //construct Thread with unary functor
64     Thread thread5(bind(PrintFunctor1(), 5));
65     thread5.start();
66
67     //construct Thread with binary functor
68     Thread thread6(bind(bind1st(PrintFunctor2(), 1), 2));
69     thread6.start();
70
71     thread1.join();
72     thread2.join();
73     thread3.join();
74     thread4.join();
75     thread5.join();
76     thread6.join();
77
78     return 0;
79 }

当然了，上面的并不是全部，修改后的Thread类不仅能够使用原先的从Thread类继承或者实现Runnable接口的方法，还可以使用任何无参函数或无参函数对象。除了test.cpp里示范的，你甚至可以用bind,bind1st,bind2st,mem_fun,mem_fun_ref的组合来用某个类的成员函数作为参数，具有超强的灵活性。

目前实现的这些都是Thread类最基本的功能，其他功能如设置线程优先级，挂起或恢复线程，异常处理等具体实现都比较简单，这这里就不一一实现了。
源代码下载：点击下载

蚂蚁终结者 2007-08-31 11:58 发表评论

C++&Win32写的空当接龙

蚂蚁终结者 — Thu, 30 Aug 2007 13:37:00 GMT

上学期做课程设计，老师让我做windows自带的空当接龙游戏，写了一个礼拜，完全仿windows的呵呵。
不过也不全一样，有一些细节一直没有时间弄，没办法最近比较懒...

与windows下的相比，我做的这个加入了AI(快捷键F6)，可以开启移牌提示(快捷键F7)，不过撤销一直没有做，可能哪天突然想做了会加上去。另外改进了废牌回收算法，非法移牌的提示直接去掉了，还有一些小的细节作了改进。
感兴趣的可以下载：点击下载
源代码下载：点击下载
顺便发几张截图：

蚂蚁终结者 2007-08-30 21:37 发表评论

为什么不要特化函数模版

蚂蚁终结者 — Thu, 30 Aug 2007 05:55:00 GMT

Overloading vs. Specialization

在C++中有class templates 和function templates，这两种模版有很多区别，最重要的区别就是重载(overloading)：
普通的C++类不能重载，当然类模版也不能重载；相反，普通函数可以重载，函数模版也能重载。这再正常不过，看下面的代码：

1 // Example 1: Class vs. function template, and overloading
2 //
3
4 // A class template
5 template<class T> class X { /*...*/ }; // (a)
6
7 // A function template with two overloads
8 template<class T> void f( T ); // (b)
9 template<class T> void f( int, T, double ); // (c)
10

像上面未特化的模板通常叫做base templates。当然，base templates能够被特化，在特化这一点上
class templates 和function templates有很大的区别：一个class template 能够被partially specialized and/or
fully specialized，一个function template只能被fully specialized，但是由于function templates能够重载我们可以通过重载来实现和partially specialized 相当的功能。下面的代码说明了这些区别：

1 // Example 1, continued: Specializing templates
2 //
3
4 // A partial specialization of (a) for pointer types
5 template<class T> class X<T*> { /*...*/ };
6
7 // A full specialization of (a) for int
8 template<> class X<int> { /*...*/ };
9
10 // A separate base template that overloads (b) and (c)
11 // -- NOT a partial specialization of (b), because
12 // there's no such thing as a partial specialization
13 // of a function template!
14 template<class T> void f( T* );             // (d)
15
16 // A full specialization of (b) for int
17 template<> void f<int>( int );              // (e)
18
19 // A plain old function that happens to overload with
20 // (b), (c), and (d) -- but not (e), which we'll
21 // discuss in a moment
22 void f( double );                           // (f)
23

根据函数重载解析规则：

1 // Example 1, continued: Overload resolution
2 //
3 bool b;
4 int i;
5 double d;
6
7 f( b );        // calls (b) with T = bool
8 f( i, 42, d ); // calls (c) with T = int
9 f( &i );       // calls (d) with T = int
10 f( i );        // calls (e)
11 f( d );        // calls (f)

上面说的这些其实都是很简单的情况，大多数人很容易就能明白，下面的才是容易让人弄混的：

1.考虑如下代码：

1 // Example 2: Explicit specialization
2 //
3 template<class T> // (a) a base template
4 void f( T );
5
6 template<class T> // (b) a second base template, overloads (a)
7 void f( T* );     //      (function templates can't be partially
8                   //     specialized; they overload instead)
9
10 template<>        // (c) explicit specialization of (b)
11 void f<>(int* );
12
13 // ...
14
15 int * p;
16 f( p );           // calls (c)

最后一行的结果像大多数人所期望的一样，问题是：为什么期望是这个结果？
如果你期望的原因是错误的，接下来的一定会让你好奇。也许你会说："我为int*写了一个特化版本，f(p)当然会调用c"，不幸的是，这正是错误的原因!!!

2.再考虑下面的代码：

1 // Example 3
2 //
3 template<class T> // (a) same old base template as before
4 void f( T );
5
6 template<>        // (c) explicit specialization, this time of (a)
7 void f<>(int* );
8
9 template<class T> // (b) a second base template, overloads (a)
10 void f( T* );
11
12 // ...
13
14 int * p;
15 f( p );           // calls (b)! overload resolution ignores
16                   // specializations and operates on the base
17                   // function templates only

如果这个结果让你感到惊奇，那就对了！很多人都会感到惊奇！
理解这个的关键是：Specializations don't overload,only the base templates overload.

重载解析仅仅选择base template(或者nontemplate function，如果有的话)，只有当编译器已经决定了哪个
base template将会被选择，编译器才会继续往下寻找适合的特化版本，如果找到了就使用那个特化版本。

最后，应当避免特化函数模板，也要避免重载函数模板(nontemplate function的重载当然没问题)。如果一定要这样，可以使用如下方法模拟函数模板的偏特化：

1 //base template class,
2 template <class T>
3 struct FuncImpl {
4     //users, go ahead and specialize this
5     static int apply(const T & t) {
6         return 0 ;
7     }
8 };
9
10 //partial specialazation for int
11 template <>
12 struct FuncImpl<int> {
13     static int apply(int t) {
14         return 1 ;
15     }
16 };
17
18 //partial specialazation for T*
19 template <class T>
20     struct FuncImpl<T *> {
21     static int apply(T * t) {
22         return 2 ;
23     }
24 };
25
26 //users, don't touch this!
27 template <class T>
28 int func(const T & t) {
29     return FuncImpl<T> ::apply(t);
30 }
31
32 int i = 10 , r;
33 r = func('c'); //r = 0
34 r = func(8); //r = 1
35 r = func(&i); //r = 2

蚂蚁终结者 2007-08-30 13:55 发表评论

从Win32 API封装Thread类[1]

蚂蚁终结者 — Thu, 30 Aug 2007 02:18:00 GMT

前几天在学Windows多线程程序设计，发现Win32 API用起来确实不怎么方便，特别是对于C++程序员。于是实现了一个简单的封装，技术含量当然不高，不过用起来还是比较方便的。如果你熟悉Java，你会发现这个实现有点像Java的Thread，在Java中有两种方法可以创建一个Thread：

1.从Thread类继承并实现run方法：

1 class MyThread extends Thread {
2     public void run() {
3         ...
4     }
5 };
6
7 //开启线程
8 MyThread thread = new MyThread;
9 thread.start();

2.声明一个类实现Runnable接口并实现run方法：

1 class MyRunnable implements Runnable {
2     public void run() {
3         ...
4     }
5 };
6
7 // 开启线程
8 MyThread thread = new MyThread(new MyRunnable);
9 thread.start();

具体实现
Java的实现方式还算优雅，我们也可以在C++中模拟，由于篇幅所限，在这里我们只关注基本功能的实现：
thread.h

1 #ifndef THREAD_H
2 #define THREAD_H
3
4 #include <windows.h>
5
6 #define CLASS_UNCOPYABLE(classname) \
7     private: \
8     classname(const classname&); \
9     classname& operator=(const classname&);
10
11 struct Runnable {
12     virtual void run() = 0;
13     virtual ~Runnable() {}
14 };
15
16 class Thread : public Runnable {
17     CLASS_UNCOPYABLE(Thread)
18 public:
19     explicit Thread(Runnable* target = 0);
20     virtual ~Thread();
21     virtual void run() {}
22     void start();
23     void join();
24 private:
25     static unsigned __stdcall threadProc(void* param);
26 private:
27     Runnable* _target;
28     HANDLE _handle;
29 };
30
31 #endif/*THREAD_H*/

在上面的代码中我们先定义一个Runnable类，并为Runnable类添加纯虚函数run，需要特别注意的是Runnable类的虚析构函数，任何想要成为基类的class都应该声明析构函数为virtual。
Thread类直接继承自Runnable，CLASS_UNCOPYABLE(Thread) 这一行用宏声明Thread类不可拷贝，具体细节请看考虑用Macro替换Uncopyable 。start成员函数和Java中的一样，用来开启一个线程，join成员函数用来阻塞当前线程直到开启的线程执行完毕。threadProc作为静态成员函数用来传递给_beginthreadex，至于为什么用_beginthreadex代替CreateThread请问Google。初步的实现都比较简单，直接贴上代码：
thread.cpp

1 #include "thread.h"
2 #include <process.h> // for _beginthreadex
3
4 Thread::Thread(Runnable* target /*= 0*/)
5 :_target(target)
6 ,_handle(0) {
7
8 }
9
10 Thread::~Thread() {
11     if (_handle != 0)
12         CloseHandle(_handle);
13     if (_target != 0)
14         delete _target;
15 }
16
17 void Thread::start() {
18     if (_handle != 0)
19         return;
20     unsigned id;
21     _handle = reinterpret_cast<HANDLE>(
22         _beginthreadex(0, 0, threadProc, this, 0, &id)
23         );
24 }
25
26 void Thread::join() {
27     if(_handle != 0) {
28         WaitForSingleObject(_handle, INFINITE);
29         CloseHandle(_handle);
30         _handle = 0;
31     }
32 }
33
34 unsigned __stdcall Thread::threadProc(void* param) {
35     Thread* p = static_cast<Thread*>(param);
36     if (p->_target != 0)
37         p->_target->run();
38     else
39         p->run();
40     return 0;
41 }

下面是测试代码：
test.cpp

1 #include "thread.h"
2 #include <iostream>
3
4 using namespace std;
5
6 //第一种方法，从Thread类继承
7 struct MyThread : public Thread {
8     virtual void run() {
9         for (int i = 0; i < 5; ++i) {
10             cout << "MyThread Running..." << i << endl;
11             Sleep(100);
12         }
13     }
14 };
15
16 //第二种方法，“实现”Runnable接口
17 struct MyRunnable : public Runnable {
18     virtual void run() {
19         for (int i = 0; i < 5; ++i) {
20             cout << "MyRunnable Running..." << i << endl;
21             Sleep(300);
22         }
23     }
24 };
25
26 int main() {
27
28     MyThread thread1;
29     Thread thread2(new MyRunnable());
30     thread1.start();
31     thread2.start();
32     thread1.join();
33     thread2.join();
34
35     return 0;
36 }

可能的运行结果：
MyThread Running...0
MyRunnable Running...0
MyThread Running...1
MyThread Running...2
MyRunnable Running...1
MyThread Running...3
MyThread Running...4
MyRunnable Running...2
MyRunnable Running...3
MyRunnable Running...4

如果你熟悉boost库，你会知道boost库的Thread构造函数可以接受普通函数和函数对象作为参数，如果你觉得从Thread类继承或者实现Runnable接口还不够简洁，下一篇会有一个比较好的改进。

蚂蚁终结者 2007-08-30 10:18 发表评论

考虑用Macro替换Uncopyable

蚂蚁终结者 — Mon, 27 Aug 2007 00:11:00 GMT

看过Effective C++的人都知道，为了防止一个class被copying，而且将错误提前到编译期，基本有两种方法：
1. 将这个类的copy构造函数和copy assignment操作符都声明为private而且没有定义。示例代码如下：

1 class SomeClass {
2     ...
3 private:
4     //只有声明
5     SomeClass(const SomeClass&);
6     SomeClass& operator=(const SomeClass&);
7 };

2. 专门设计一个为了阻止copying动作而设计的base class，这个base class相当简单：

1 Uncopyable {
2 protected: //允许derived对象构造和析构
3     Uncopyable() {}
4     ~Uncopyable() {}
5 private: //阻止copying
6     Uncopyable(const Uncopyable&);
7     Uncopyable& operator=(const Uncopyable&);
8 };

为了阻止某个对象如SomeClass被copying，我们唯一需要做的就是继承自Uncopyable：

1 SomeClass : private Uncopyable {
2 ...
3 };

第2种方案貌似很完美，在大多数情况下也工作的很好，甚至boost库也广泛采用了(boost库中的叫noncopyable)。当然了，因为Uncopyable不含任何数据，符合EBO(empty base class optimization，空白基类最优化)资格，但由于它总是扮演base class，因此有可能导致多重继承，而EBO一般只在单继承下才可行，编译器通常不会对有多个base class的derived classes施行EBO。

如果你不想导致多重继承，不管是从性能上还是书写代码上，比如SomeClass继承自某个base class，你可能会写如下代码：

1 class SomeClass : public BaseClass, private Uncopyable {
2 ...
3 };

这让人很不爽，要是你跟我一样懒，你肯定也不会愿意采用第一种方案，因为那意味着你会在每一个不想被copying的class里都加上那三行代码。

如果用Macro就很简单了，即灵活又方便：

1 #define CLASS_UNCOPYABLE(classname) \
2     private: \
3     classname(const classname&); \
4     classname& operator=(const classname&);

现在SomeClass只需写成这样：

1 class SomeClass {
2 CLASS_UNCOPYABLE(SomeClass)
3 ...
4 };

不仅省事而且灵活！！！

蚂蚁终结者 2007-08-27 08:11 发表评论