Soft Binary

map hash_map unordered_map 性能测试

2012年1月8日 | by zieckey | 标签: hash_map, map, STL, unordered_map, 关联容器, 性能比较, 用法示例

by zieckey

测试条件：

gcc version 4.2.1 20070719 [FreeBSD]

FreeBSD 7.2-RELEASE #0: Fri May 1 07:18:07 UTC 2009 root@driscoll.cse.buffalo.edu:/usr/obj/usr/src/sys/GENERIC amd64
Intel(R) Xeon(R) CPU E5620 @ 2.40GHz 16核

测试程序说明：

先准备好n个字符串随机的MD5字符串做为key，然后分别对3个容器进行插入、遍历、查找、删除操作。

例如，n=100的时候，插入是指插入100个随机MD5 key；遍历是指对容器遍历一次；查找是指分别对这个100个随机的MD5 key做查找操作（即查找100次）；删除是指挨个删除这个100个随机MD5 key。

测试数据如下表：

插入，单位us	100	1K	10K	100K	1M	10M
std::map	241	2833	35888	381214	4439088	62233380
std::ext/hash_map	97	1667	16466	146025	1788446	18512639
std::tr1::unordered_map	77	772	8052	53094	658312	7429297

遍历，单位us	100	1K	10K	100K	1M	10M
std::map	11	76	842	11603	155700	1771906
std::ext/hash_map	47	430	4218	39880	470344	4781575
std::tr1::unordered_map	1	1	2	1	2	1

查找，单位us	100	1K	10K	100K	1M	10M
std::map	156	2111	30456	258709	4100260	59064394
std::ext/hash_map	77	774	8056	56974	660231	7705527
std::tr1::unordered_map	77	772	8051	54456	659537	7600263

删除，单位us	100	1K	10K	100K	1M	10M
std::map	291	3641	49584	472414	6675897	92491113
std::ext/hash_map	89	869	9068	86524	964767	10372650
std::tr1::unordered_map	49	480	4879	33087	395098	4369617

结论：

1. std::tr1::unordered_map 与 std::ext/hash_map

任何情况下，如果要在这两个容器之间选择的话，我们毫不犹豫应该选择 unordered_map。因为他的性能在上述4中操作中均优于 hash_map，甚至可以说远远优于 hash_map。

2. std::tr1::unordered_map 与 std::map

map的性能总体来说是最差的。但是，当我们需要一个有序的关联容器的时候，我们必须选择std::map，因为 unordered_map 内部元素不是有序的，这一点从名字都可以看出来。除此之外都应该选择 unordered_map 。

3. 上述测试中，unordered_map 的遍历性能几乎是常数级别的，与常识不太相符，需要再研究研究。

附录：贴上源代码

说明：与测试程序稍有区别，这里的源码里没有MD5相关的代码以确保其他人能比较方便的直接拿去编译运行。

如有错误还请跟帖指出，非常感谢。

#include <iostream>
#include <string>
#include <sstream>
#include <list>
#include <map>
#include <sys/time.h>
#include <ext/hash_map>
#include <tr1/unordered_map>
namespace zl
{ //{{{
struct equal_to
{
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) == 0;
}
};
struct hash_string
: public std::unary_function<std::string, std::size_t>
{
std::size_t
operator()(const std::string& __s) const
#ifdef __linux__
{ return std::tr1::Fnv_hash<>::hash(__s.data(), __s.length()); }
#else
{ return std::tr1::_Fnv_hash<>::hash(__s.data(), __s.length()); }
#endif
};
struct hash_charptr
: public std::unary_function<const char*, std::size_t>
{
std::size_t
operator()(const char* __s) const
#ifdef __linux__
{ return std::tr1::Fnv_hash<>::hash(__s, strlen(__s)); }
#else
{ return std::tr1::_Fnv_hash<>::hash(__s, strlen(__s)); }
#endif
};
}//}}}
typedef std::list<std::string> string_list;
typedef std::map<std::string, int> string_map;
typedef __gnu_cxx::hash_map<std::string, int, zl::hash_string> string_hash_map;
typedef std::tr1::unordered_map<std::string, int> string_unordered_map;
void fill_list(string_list& slist, size_t count);
uint64_t current_usec();
int main( int argc, char* argv[] )
{
if (argc != 2 && argc != 3)
{
fprintf(stderr, “Usage:%s test_count rehash\n”, argv[0]);
fprintf(stderr, “For example:%s 10000 rehash\n”, argv[0]);
return -1;
}
size_t count = atoi(argv[1]);
bool rehash = false;
if (argc == 3)
{
rehash = true;
}
string_map smap;
string_hash_map shash_map;
string_unordered_map sunordered_map;
if (rehash)
{
sunordered_map.rehash(count);
}
string_list slist;
fill_list(slist, count);
uint64_t start = 0;
uint64_t end = 0;
uint64_t map_insert_us = 0;
uint64_t hash_map_insert_us = 0;
uint64_t unordered_map_insert_us = 0;
uint64_t map_traverse_us = 0;
uint64_t hash_map_traverse_us = 0;
uint64_t unordered_map_traverse_us = 0;
uint64_t map_find_us = 0;
uint64_t hash_map_find_us = 0;
uint64_t unordered_map_find_us = 0;
uint64_t map_delete_us = 0;
uint64_t hash_map_delete_us = 0;
uint64_t unordered_map_delete_us = 0;
// Insert test
{//{{{
string_list::iterator it(slist.begin());
string_list::iterator ite(slist.end());
//map insert
start = current_usec();
for (int i = 0; it != ite; ++it, ++i)
{
smap[*it] = i;
}
end = current_usec();
map_insert_us = end - start;
//hash_map insert
it = slist.begin();
start = current_usec();
for (int i = 0; it != ite; ++it, ++i)
{
shash_map[*it] = i;
}
end = current_usec();
hash_map_insert_us = end - start;
//unordered_map insert
it = slist.begin();
start = current_usec();
for (int i = 0; it != ite; ++it, ++i)
{
shash_map[*it] = i;
}
end = current_usec();
unordered_map_insert_us = end - start;
}//}}}
// Traverse test
{//{{{
//map traverse
{
string_map::iterator it(smap.begin());
string_map::iterator ite(smap.end());
start = current_usec();
for (int i = 0; it != ite; ++it)
{
i++;
}
end = current_usec();
map_traverse_us = end - start;
}
//hash_map traverse
{
string_hash_map::iterator it(shash_map.begin());
string_hash_map::iterator ite(shash_map.end());
start = current_usec();
for (int i = 0; it != ite; ++it)
{
i++;
}
end = current_usec();
hash_map_traverse_us = end - start;
}
//unordered_map traverse
{
string_unordered_map::iterator it(sunordered_map.begin());
string_unordered_map::iterator ite(sunordered_map.end());
start = current_usec();
for (int i = 0; it != ite; ++it)
{
i++;
}
end = current_usec();
unordered_map_traverse_us = end - start;
}
}//}}}
// Find test
{//{{{
string_list::iterator it(slist.begin());
string_list::iterator ite(slist.end());
//map find
start = current_usec();
for (int i = 0; it != ite; ++it, ++i)
{
smap[*it] = i;
}
end = current_usec();
map_find_us = end - start;
//hash_map find
it = slist.begin();
start = current_usec();
for (int i = 0; it != ite; ++it, ++i)
{
shash_map[*it] = i;
}
end = current_usec();
hash_map_find_us = end - start;
//unordered_map find
it = slist.begin();
start = current_usec();
for (int i = 0; it != ite; ++it, ++i)
{
shash_map[*it] = i;
}
end = current_usec();
unordered_map_find_us = end - start;
}//}}}
// Delete test
{//{{{
string_list::iterator it(slist.begin());
string_list::iterator ite(slist.end());
//map delete
start = current_usec();
for (int i = 0; it != ite; ++it, ++i)
{
smap.erase(*it);
}
end = current_usec();
map_delete_us = end - start;
//hash_map delete
it = slist.begin();
start = current_usec();
for (int i = 0; it != ite; ++it, ++i)
{
shash_map.erase(*it);
}
end = current_usec();
hash_map_delete_us = end - start;
//unordered_map delete
it = slist.begin();
start = current_usec();
for (int i = 0; it != ite; ++it, ++i)
{
shash_map.erase(*it);
}
end = current_usec();
unordered_map_delete_us = end - start;
}//}}}
//stat output
std::cout << ” insert, count “ << count << std::endl;
std::cout << ” std::map “ << map_insert_us << ” us\n”;
std::cout << ” std::ext/hash_map “ << hash_map_insert_us << ” us\n”;
std::cout << “std::tr1::unordered_map “ << unordered_map_insert_us << ” us\n”;
std::cout << “\n”;
std::cout << ” traverse, count “ << count << std::endl;
std::cout << ” std::map “ << map_traverse_us << ” us\n”;
std::cout << ” std::ext/hash_map “ << hash_map_traverse_us << ” us\n”;
std::cout << “std::tr1::unordered_map “ << unordered_map_traverse_us << ” us\n”;
std::cout << “\n”;
std::cout << ” find, count “ << count << std::endl;
std::cout << ” std::map “ << map_find_us << ” us\n”;
std::cout << ” std::ext/hash_map “ << hash_map_find_us << ” us\n”;
std::cout << “std::tr1::unordered_map “ << unordered_map_find_us << ” us\n”;
std::cout << “\n”;
std::cout << ” delete, count “ << count << std::endl;
std::cout << ” std::map “ << map_delete_us << ” us\n”;
std::cout << ” std::ext/hash_map “ << hash_map_delete_us << ” us\n”;
std::cout << “std::tr1::unordered_map “ << unordered_map_delete_us << ” us\n”;
return 0;
}
void fill_list(string_list& slist, size_t count)
{
for (size_t i = 0; i < count; ++i)
{
std::ostringstream oss;
oss << i;
//slist.push_back(MD5::getHexMD5(oss.str().c_str(), oss.str().length()));
slist.push_back(oss.str());
}
}
uint64_t current_usec()
{
struct timeval tv;
gettimeofday( &tv, NULL );
return tv.tv_sec * 1000 * 1000 + tv.tv_usec;
}

没有评论 (0 views)

UI技术简介

2011年10月20日 | by luckzj | 标签:

1. 本文简介
开发一款桌面应用软件，界面设计往往需要占据较大部分的工作量。界面设计的好坏，直接决定了软件的客户体验。然而界面设计是一门专业的技术，需要对Windows界面绘制技术有较深的理解，才可以制作出美观大方的界面效果。
本文主要介绍当前主流的界面设计技术DirectUI，将DirectUI技术与传统的界面设计技术进行比较，最后介绍当前DirectUI技术在国内的发展现状。

2. 传统的UI设计模式
2.1 Windows窗体
        Windows界面程序中，最重要的概念是窗体的概念。窗体是Windows程序中，消息派发的单位，每个窗体都有自己的窗口过程，用于处理Windows派发来的消息，这些消息中，比较容易让人理解的，即是WM_ERASEBKGND消息和WM_PAINT消息。
        当窗体需要重新绘制背景时，系统就会向窗体发送WM_ERASEBKGND消息，窗体接收到这个消息以后，将会调用OnEraseBkgnd函数，刷新窗体的背景。
       当窗体需要被重新绘制时，系统会向窗体发送WM_PAINT消息，则窗体的OnPaint函数将会被调用，以达到重新绘制整个窗体的作用。
        我们不需要纠结于绘制背景和绘制窗体的区别，只需要知道窗体大概就是这样展现出来的即可，而两个消息的响应函数，也并非一定是OnEraseBkgnd和OnPaint，我们可以根据需要自行决定函数名称。
       我们将某个窗体从后台移动到前台时，则该窗体将会依次收到WM_ERASEBKGND和WM_PAINT消息。

2.2 使用Windows API来制作界面
如果纯粹使用Windows API来开发程序界面，则我们需要做的工作大致如下：
1. 设置一个WNDCLASSEX结构，使用这个结构来注册一个新的窗体类别。
2. 创建刚注册的窗口类别的一个窗体实例。
3. 编写一个窗体过程函数，响应第2步中创建的窗体的各种消息。对于不需要特殊处理的消息，则直接调用DefWindowProc处理。
后续的界面处理，有两种选择，一种是再创建子窗体，放在主窗体上，而后子窗体可以有自己的窗体过程函数，以此实现将界面划分不同模块，分开处理。另外一种选择则是将主窗体划分为不同的区域，在OnPaint函数中，根据不同的区域，调用不同的绘制模块，来实现复杂的界面处理。前者可以认为是MFC的雏形，而后者则是DirectUI的思想。

2.3 MFC框架
      MFC是微软提供的一套界面开发工具库，其全称是Microsoft Foundation Classes。早期的界面开发很多是基于MFC框架。
      MFC将对窗体操作的一系列Windows API函数封装成一个CWnd类。封装窗口过程处理函数，提供消息映射机制。即不再需要编写窗口过程，而是直接使用消息映射宏ON_MESSAGE(msg, handler)来映射msg与handler。
      框架提供从CWnd类派生的诸多其他控件类，例如CButton, CStatic, CListCtrl, CCombox, CProgressCtrl等等。每一个界面控件的实例，都包含一个窗体，可以响应发送给该窗体的消息，多个界面控件，以父子控件的层级关系，搭建在一起，就组成了复杂的界面。
MFC框架中提供的基础控件，往往难以满足复杂界面的需求，通常情况下，软件公司会对MFC库进行扩展，并建造自己的界面控件库，以满足不同的需求。
阅读全文…

评论关闭 (0 views)

C++ STL 学习：自己写仿函数(functor)（三）

2011年10月11日 | by zieckey | 标签: compose, for_each, functor

C++ STL 学习：自己写仿函数(functor)（三）

我们从最简单的visitor入手，看下面的定义：

// TEMPLATE STRUCT unary_function

template<class _Arg, class _Result>

struct unary_function

{ // base class for unary functions

typedef _Arg argument_type;

typedef _Result result_type;

};

template< class _Ty >

struct visitor : public std::unary_function<_Ty, void>

{

void operator()( const _Ty& x )

{

std::cout << x << "\t";

}

};

这个visitor定义足够简单，我们就不多说了。前文说过for_each的定义，这里再给出来：

template<typename InputIterator, typename Function>

Function for_each( InputIterator beg, InputIterator end, Function f ) {

while ( beg != end )

f( *beg++ );

}

看下面的测试代码:

void test_for_each()

{

typedef std::list<int> intlist;

intlist il;

for ( int i = 0; i < 10; i++ )

{

il.push_back(i);

}

std::for_each( il.begin(), il.end(), visitor<int>() );

}

这里对一个list进行遍历，对每一个元素调用visitor仿函数。

下面，我们来实现一个复杂点的任务，遍历一个map，对每一个key/value对中value调用visitor仿函数。

首先我们需要一个选择器仿函数select2nd_t来选择key/value对的value：

/**

* select the second parameter from a std::pair

*/

template< class _Pair >

struct select2nd_t

: public std::unary_function< _Pair, typename _Pair::second_type >

{

const typename _Pair::second_type& operator()( const _Pair& _x )

{

return _x.second;

}

};

在遍历过程中，通过select2nd_t把value选出来，然后调用visitor。

为了实现这个功能，我们需要下面这个组合仿函数：

/**

* compose _Func1 and _Func2

* use the return value of _Func1 as the parameter of the _Func2 and return the return value of _Func2

*/

template< class _Func1, class _Func2 >

struct compose_t

: public std::unary_function< typename _Func1::argument_type, typename _Func2::result_type >

{

_Func1 __func1;

_Func2 __func2;

compose_t( const _Func1& f1, const _Func2& f2 ) : __func1(f1), __func2(f2) {}

typename _Func2::result_type operator()( const typename _Func1::argument_type& _x )

{

return __func2( __func1( _x ) );

}

};

func1是select2nd_t，func2是visitor。

__func2( __func1( _x ) ) 可以知道，如果 _x 是map里面的单个元素（key/value对，std::pair类型），

先用select2nd_t作用于这个pair得到value,然后做参数传入visitor。

最后，看我们的遍历map中value的函数：

template< class _Map, class _Func >

void for_each_2nd( const _Map& _map, const _Func& _func )

{

compose_t< select2nd_t< typename _Map::value_type>, _Func > _f( select2nd_t<typename _Map::value_type>(), _func );

std::for_each( _map.begin(), _map.end(), _f );

};

通过前面的铺垫，这个函数就比较容易理解了，直接给出使用示例：

void tset_for_each_2nd()

{

typedef std::map<int, int> intmap;

intmap im;

for ( int i = 0; i < 10; ++i )

{

im.insert( intmap::value_type(i, i * 100) );

}

for_each_2nd( im, visitor<int>() );

}

总结：本文介绍了for_each的用法，进而更深入的介绍了如何写一个复杂点的组合仿函数。

评论关闭 (1 views)

MFC中用配置文件实现界面布局的方式

2011年7月3日 | by luckzj | 标签:

最近看了下android程序设计，发现其界面布局是采用一个layout配置文件，以xml的形式配置UI，然后通过android框架对这个layout进行解析，动态生成界面控件。这种界面设计模式，简化了UI的编码，使得我们可以像写HTML页面一样，设计应用程序的UI。

这种UI设计的方式，实际上在CSharp中也比较容易做到。我们可以轻易设计出一种控制器，来读入界面配置文件，并动态生成界面布局配置扎文件中定义的各种控件，最典型的如Button, Label之类。而后在控制器中添加控件事件响应函数，实现应用程序的业务逻辑。

采用CSharp语言实现这种动态UI配置比较容易，控件的生成，可以通过反射来实现。从配置文件指定的dll中，寻找到指定名称的控件，并动态生成即可。

那么使用C++语言进行界面设计时，可以实现这种动态界面布局么？答案是可以的，只是会有一些麻烦。下面我将对在MFC中实现动态界面布局的问题以及解决方案作出分析。

动态界面布局有两大基础要素，一个是动态创建控件，一个是动态的为控件指定事件响应函数。

1. 动态创建控件
我们知道在CSharp中，可以使用反射的方式，通过类名动态创建类的实例。而在C++中，并没有反射的概念。这个问题可以通过巧妙的方式来解决，在MFC中有运行时类的概念，我们可以通过RUNTIME_CLASS(classname)获取一个CRuntimeClass的指针，进而通过CRuntimeClass类来动态地创建。对于需要使用CRuntimeClass动态创建的类，需要在类的定义中添加DECLARE_DYNCREATE的声明，并在实现文件中，添加 IMPLEMENT_DYCREATE。

我们使用CRuntimeClass动态创建一个类的实例时，首先需要使用宏 RUNTIME_CLASS来获取到CRuntimeClass的实例，RUNTIME_CLASS宏的定义如下：

  #define RUNTIME_CLASS(class_name) (class_name::GetThisClass())

而 class_name::GetThisClass() 已经在IMPLEMENT_DYNCREATE中定义，最终定义为返回如下成员：

AFX_COMDAT CRuntimeClass class_name::class##class_name = {
		#class_name, sizeof(class class_name), wSchema, pfnNew,
			&class_name::_GetBaseClass, NULL, class_init };

通过查看CRuntimeClass，发现其为一个结构体，声明如下：

struct CRuntimeClass
{
// Attributes
	LPCSTR m_lpszClassName;
	int m_nObjectSize;
	UINT m_wSchema; // schema number of the loaded class
	CObject* (PASCAL* m_pfnCreateObject)(); // NULL => abstract class
#ifdef _AFXDLL
	CRuntimeClass* (PASCAL* m_pfnGetBaseClass)();
#else
	CRuntimeClass* m_pBaseClass;
#endif

// Operations
	CObject* CreateObject();
	BOOL IsDerivedFrom(const CRuntimeClass* pBaseClass) const;

	// dynamic name lookup and creation
	static CRuntimeClass* PASCAL FromName(LPCSTR lpszClassName);
	static CRuntimeClass* PASCAL FromName(LPCWSTR lpszClassName);
	static CObject* PASCAL CreateObject(LPCSTR lpszClassName);
	static CObject* PASCAL CreateObject(LPCWSTR lpszClassName);

// Implementation
	void Store(CArchive& ar) const;
	static CRuntimeClass* PASCAL Load(CArchive& ar, UINT* pwSchemaNum);

	// CRuntimeClass objects linked together in simple list
	CRuntimeClass* m_pNextClass;       // linked list of registered classes
	const AFX_CLASSINIT* m_pClassInit;
};

由此我们知道RUNTIME_CLASS宏实际上最后获取到了一个CRuntimeClass结构体，并对结构体中的各个域进行了赋值。之后我们即可以调用获取到的CRuntimeClass实例的成员函数CreateObject来创建实例。

阅读全文…

评论关闭 (1 views)

Nginx 模块开发（1）—— 一个稍稍能说明问题模块开发 Step By Step 过程

2011年4月23日 | by zieckey | 标签: C++, nginx, 高性能服务器

By zieckey

1. Nginx 介绍

Nginx 是俄罗斯人编写的十分轻量级的HTTP服务器,它的发音为“engine X”，是一个高性能的HTTP和反向代理服务器，同时也是一个IMAP/POP3/SMTP 代理服务器．Nginx是由俄罗斯人 Igor Sysoev为俄罗斯访问量第二的 Rambler.ru站点开发的，从2004年开始它已经在该站点运行了七八年了。Igor Sysoev在建立的项目时,使用基于BSD许可。
英文主页：http://nginx.org.
阅读全文…

评论关闭 (1 views)

一句话解说内存屏障 Memory barrier

2011年3月17日 | by zieckey | 标签:

内存屏障，可以保证在此之前的代码全部执行完才开始执行在此之后的代码

参考wikipedia的定义：
Memory barrier, also known as membar or memory fence or fence instruction, is a type of barrier and a class of instruction which causes a central processing unit (CPU) or compiler to enforce an ordering constraint on memory operations issued before and after the barrier instruction.

阅读全文…

评论关闭 (1 views)

[转载]Windows路径探究

2010年11月3日 | by luckzj | 标签:

原文地址： http://www.cnblogs.com/zplutor/archive/2010/08/21/1805335.html

Windows路径是我们经常使用的东西，它看似简单，实际上隐含许多细节，这些都是在平常的使用过程中注意不到的。下面让我们来看看各种各样的Windows路径。

提起路径，我们都会想到“绝对路径”和“相对路径”，实际上绝对路径是一个广泛的概念，它表示的是可以唯一定位一个文件或文件夹的路径，有多种形式的路径都属于绝对路径的范畴，例如：

完整路径（Full path）

我们平时所说的“绝对路径”通常就是指完整路径，它的格式如下：
C:\Windows\System32\calc.exe

UNC（Universal Naming Convention通用命名规范）路径

UNC路径用于在局域网上定位文件或文件夹，在通过网上邻居访问其它系统上的共享文件时使用的就是UNC路径。UNC路径的格式如下：
\\PC101\ShareFiles\job.doc
其中PC101是目标系统的计算机名，ShareFiles是目标系统上的共享文件夹名称。

以\\?\开头的路径

在某些手工辅助杀毒的工具中可以看到以\\?\开头的路径，这种路径我还找不到正式的名称。完整路径和UNC路径都可以以\\?\开头：
\\?\C:\Windows\System32\calc.exe
\\?\UNC\PC101\ShareFiles\job.doc

相对路径（Relative path）

上面四种路径都可以在本地或网络上绝对定位一个文件，因此属于绝对路径。另一种我们常常使用的是相对路径，这种路径需要与进程的当前文件夹（Current directory）一起合作才可以定位一个文件或文件夹。进程的当前文件夹并不是指EXE文件所在的文件夹，它是每个进程都有的一个属性。例如在命令提示符中显示的路径就是这个cmd.exe进程的当前文件夹，使用cd命令可以改变当前文件夹，无论当前文件夹如何改变，cmd.exe文件所在的文件夹总是不变的。在进程启动的时候可以指定它的当前文件夹，例如在快捷方式的属性中有一个“起始位置”输入框，这个就是进程启动后的当前文件夹。如果在启动时不指定进程的当前文件夹（直接双击EXE文件的情况），那么EXE文件的所在文件夹就会作为它的当前文件夹。

纯粹的相对路径格式如下：

Windows\System32\calc.exe
要注意的是相对路径的开头不能有\，很多人以为有没有\都是一样的，其实不然，以\开头的路径是另外一种路径，下文会详细介绍这种路径。

如果在进程中操作文件时传递一个相对路径，那么进程会将当前文件夹的路径与这个相对路径合并，得到一个完整路径。例如命令提示符的当前文件夹是C:\Windows，如果执行start System32\calc.exe命令，程序就会将两个路径合并得到C:\Windows\System32\calc.exe。
由于这样的特性，当前文件夹又称为工作文件夹，因为进程使用相对路径时都是针对该文件夹的。

除了上面所说的纯粹的相对路径，还有两种特殊的相对路径，为了不至于混淆，不再将它们称为相对路径。

以\开头的路径

上面说过相对路径不能以\开头，一旦如此，它就表示相对于当前文件夹根目录的路径。例如进程的当前文件夹是C:\Windows，那么\System32\calc.exe就表示C:\System32\calc.exe。不论当前文件夹的路径有多深，只取根目录进行合并。可以在命令提示符中进行验证：首先将C:\Windows设置为当前文件夹，然后执行start \System32\calc.exe命令，将会提示错误，所找不到文件。再执行start \Windows\System32\calc.exe命令，这时计算器程序成功启动了，证明了上面的说法。

以盘符和冒号开头的路径

这种路径就像是拼写错误的完整路径，它的格式如下：
C:System32\calc.exe

盘符加冒号是一种特殊的表示法，表示的是进程在“该分区上的当前文件夹”。这里又蹦出来了一个当前文件夹，这与上文的当前文件夹是不同的。简单来说，对于每一个分区，进程都会保存在这个分区上最后使用的当前文件夹。可能解析的不够好，那么可以使用命令提示符来操作一遍以加深理解。
阅读全文…

评论关闭 (1 views)

pinvoke中的字符串

2010年9月1日 | by luckzj | 标签:

我们编写C#程序时，有时候会用到一些C封装的函数，例如Windows API之类。我们可以使用IntPtr解决几乎所有参数封送的问题，但毕竟使用IntPtr读写内存非常麻烦，实际上微软为我们提供了许多简易的操作方式，这篇文章要介绍的就是字符串在pinvoke中的使用方式。

建立测试环境

测试环境的建立，请参考soft-bin.com上之前的文章 “P/INVOKE使用方法万惊油”，查看C#文章分类即可找到这篇文章。

在建立了测试环境以后，我们可以编写C的程序供C#调用，我们还可以开启 Unmanaged Code Debugging来对C#传入到C中的参数进行调试查看。

字符串作为传入参数

很多函数要求将字符串传入其中，例如FindWindow函数。我们可以编写自己的C++测试函数：

void TestString(char* strIn)
{
    cout << strIn << endl;
}

这几乎是最简单的字符串测试了，在C#中作如下声明即可使用这个函数：

public static extern TestString(
    [MarshalAs(UnmanagedType.LPStr)]
    string strIn
);

为了简便起见，我将函数声明前的DllImport属性省去不写。

阅读全文…

评论关闭 (4 views)

C#端口扫描

2010年8月31日 | by luckzj | 标签:

最近公司断网，不让访问外网，于是写了个网络代理扫描程序。

端口扫描的概念

我们知道，每一个网络服务程序都会绑定一个端口，客户端可以通过将数据发送到这个端口，从而获得服务。这种获取服务的活动，是我们在已知某一IP上开启了某种服务后，通过端口与服务器通信的活动。我们也可以逆向考虑这个问题，即，可以通过尝试给某一IP发送数据，通过响应情况来判断这个IP上是否存在这一服务，而连续向某一段IP地址发送网络数据，以测试服务是否存在的情况，就被称为端口扫描。

我们已知的默认端口列表如下：

HTTP网站服务：80 （很多人喜欢把端口改为8080，如果想扫描HTTP服务，建议扫描80和8080端口）

FTP服务： 21

TELNET服务：23

反恐精英服务器（CS）：27015 （本科的时候见到有人扫这个端口，然后加入别人建立的CS游戏）

网络代理软件ccProxy默认端口： 808(http)， 1080(sockV5)

其他的端口就不列了，想要扫什么服务，直接查其端口即可。

C#简单的端口扫描

简单的端口扫描其实没什么好说的，就是在界面上指定IP范围，程序通过死循环来不断尝试连接指定的IP。这里需要注意几个地方：

1. 输入的IP是string类型的，我们可以通过IPAddress.Parse方法，将其转换成IPAddress类的实例。

2. 为了扫描一个范围的IP地址，我们需要能够对IP地址实现加1，比较的功能。

以下的讨论中，只考虑IPV4的处理。IP通常被表示为10.1.2.3的形式，但实际上在内存中，其使用4个字节的空间存储，每个字节存储0到255，也就是使用字符串表示的值变为数字，例如 10.1.2.3 在内存中存储为4个字节，分别为：

b[0] = 10;
b[1] = 1;
b[2] = 2;
b[3] = 3;

在此基础上，我们需要编写两个函数来实现IP地址的自增和比较，废话不多，源码如下：
阅读全文…

评论关闭 (3 views)

Windows下使用内核对象进行线程同步

2010年8月30日 | by luckzj | 标签:

在多线程编程时，线程间的同步操作是非常重要，也是非常麻烦的。关于windows下的进程和线程，谈得比较多的是线程同步和进程间通信，而进程间的同步，其实和线程同步是有些类似的。对于线程间的通信，如果线程属于同一个进程，则可以直接通过共享进程资源的方式进行通信，如果两个线程从属于不同的进程，则线程通信实际上变成了进程间通信了。

因此，我们谈到多线程编程时，通常只说线程的同步以及进程的通信。

线程同步方式概述

线程的同步可以分为用户态同步和内核态同步。

用户态同步的方式即是使用互锁函数和临界区两种方式进行线程同步，这两种方式在前一篇文章使用互锁函数和临界区(CriticalSection)实现线程同步中已经做过介绍。在用户态下进行线程同步的好处在于速度快，使用方便。

内核态同步则是这篇文章要介绍的重点，即使用内核对象进行线程同步。使用内核对象进行线程同步，速度会比使用互锁函数和临界区要慢一些，但好处在于内核对象可以用于跨进程的同步。原因很简单，内核对象是独立于进程存在的，由系统进行维护，我们可以创建一个内核对象，并在不同的进程中打开它，那么我们就可以使用这个内核对象进行跨进程的同步了。

在另外一个进程中打开内核对象，我们可以有两种思路，一种是利用父子进程间的继承关系，让子进程继承父进程的内核对象。另外一种思路则是创建内核对象时，为起指定一个名称，在另外一个进程中，只需要根据这个名称打开相应的内核对象即可。关于内核对象的更多操作，可以参考 Windows内核对象一文。

有的内核对象会有两种状态，一种叫做已通知状态，一种叫做未通知状态。对于这种内核对象，我们可以使用等待函数，来等待其从未通知状态变为已通知状态。我们可以通过选择不同的等待函数以及不同的内核对象，来实现线程的同步。

等待函数

最常见的等待函数莫过于 WaitForSingleObject，其原型如下：

DWORD WaitForSingleObject(
    HANDLE hObject,    // 要等待的内核对象句柄
    DWORD dwMilliseconds);  // 等待时间，可以设置为 INFINITE表示永久等待

阅读全文…

评论关闭 (4 views)

Linux 信号处理

2010年8月21日 | by dingshi | 标签: signal, 信号处理

Linux编程中信号处理部分知识比较庞杂，鉴于此本文不会全面讲解，而是力争讲明白为后续的服务器开发做铺垫的知识。

信号的种类：
可以从两个不同的分类角度对信号进行分类：
（1）可靠性方面：可靠信号与不可靠信号；
（2）与时间的关系上：实时信号与非实时信号。

本文以常用的不可靠信号、非实时信号为主讲解。

1可靠信号与不可靠信号

“不可靠信号”
Linux 信号机制基本上是从Unix系统中继承过来的。早期Unix系统中的信号机制比较简单和原始，后来在实践中暴露出一些问题，因此，把那些建立在早期机制上的信号叫做”不可靠信号”，信号值小于SIGRTMIN(Red hat 7.2中，SIGRTMIN=32，SIGRTMAX=63)的信号都是不可靠信号。这就是”不可靠信号”的来源。它的主要问题是：
•进程每次处理信号后，就将对信号的响应设置为默认动作。在某些情况下，将导致对信号的错误处理；因此，用户如果不希望这样的操作，那么就要在信号处理函数结尾再一次调用signal()，重新安装该信号。
•信号可能丢失。
因此，早期unix下的不可靠信号主要指的是进程可能对信号做出错误的反
应以及信号可能丢失。
Linux支持不可靠信号，但是对不可靠信号机制做了改进：在调用完信号处理函数后，不必重新调用该信号的安装函数（信号安装函数是在可靠机制上的实现）。因此，Linux下的不可靠信号问题主要指的是信号可能丢失。
阅读全文…

1 条评论 (56 views)

C#链接mysql数据库

2010年8月13日 | by luckzj | 标签:

mysql数据库是目前世界上应用得最为广泛的几种数据库之一，mysql的开发团队为其开发了多个编程语言版本的驱动程序，使得mysql可以支持目前流行的多种编程语言，C#作为当前最为流行的几种编程语言之一，当然也被mysql所支持。

mysql的开发团队为mysql开发了C#版本的驱动，我们可以从mysql的官方网站下载到完整的程序，示例以及文档。或者也可以从本站直接下载：

mysql-connector-net-5.0.8.1-noinstall

将上述zip文件下载到本地后，对其进行解压缩，则可以在bin下找到驱动dll，名字为：Mysql.data.dll。我们在自己的工程中，添加对这个dll的引用，然后在cs文件中引入名字空间 using MySql.Data.MySqlClient。

我们可以在解压缩后的 Docs 文件夹中找到此版本驱动的开发文档，具体使用方法可以参阅此文档。

我们在连接其他类型数据库时，已经熟知了XXConnection, XXCommand, XXReader等与数据库相关的类，而在MySql中，情形也非常类似。

我们可以使用 MySqlConnection 类来管理与数据库的链接，使用 MySqlCommand 来执行命令，MySqlDataReader 来读取数据， MySqlDataAdapter 对数据进行适配。

以下是我在试验时，写的使用测试代码：

阅读全文…

评论关闭 (5 views)

使用互锁函数和临界区(CriticalSection)实现线程同步

2010年8月12日 | by luckzj | 标签:

线程同步是多线程编程中比较重要的操作。在多个线程同时访问某个资源时，如果没有做好同步操作，则轻可以导致程序运行无法实现预定的目标，重则可能导致程序异常崩溃。

例如对于 i++ 这么一个简单的操作，实际上在执行时，也是分为多步的：
MOVE EAX, [i] INC EAX MOVE [i], EAX

假设现在有两个线程同时执行i++，且其执行顺序为：
Thread 1: MOVE EAX, [i]
Thread 1: INC EAX
Thread 2: MOVE EAX, [i]
Thread 2: INC EAX
Thread 1: MOVE[i], EAX
Thread 2: MOVE[i], EAX

经过这种执行方式，i的值将被少加一次，这不会是我们希望的结果。

我们需要使用线程同步，线程同步的方式有很多，但多数需要使用到内核对象，这些同步方式速度会比较慢。用户模式的线程同步方式包括互锁函数家族和临界区，我将分别对这两种同步方式进行介绍。

互锁函数家族

互锁函数家族的操作都是原子操作，也就是可以保证此函数在执行过程中，不会被其他线程打断。使用互锁家族函数，需要包含Windows.h，几个主要的互锁家族函数如下：

阅读全文…

评论关闭 (7 views)

异或指针双向连表(XOR Linked list)

2010年8月11日 | by luckzj | 标签:

链表是我们最常用的一种数据结构之一，除了单向链表外，有些时候为了可以逆向遍历链表，我们也会需要使用到双向链表。通常情况下的双向链表是如下形式：

 ...  A       B         C         D         E  ...
          –>  next –>  next  –>  next  –>
          <–  prev <–  prev  <–  prev  <–

我们在一个节点上，使用两个指针，一个名为next，指向下一个节点，而另一个名为prev，指向前一个节点。这种传统的双向链表结构需要使用两个额外的指针才能实现对链表的正向和逆向遍历。异或指针双向链表(Xor Linked List)提供了另外的一种方式。

异或链表利用异或操作的特性，将一个节点前后两个节点的地址进行异或操作，然后将这个操作的结果保存起来，则我们可以根据本节点的上一个节点地址，获得下一个节点的地址。

异或操作的特性是，假设：

c = a ^ b;

则：
a = c ^ b;
b = c ^ a;

即，我们知道了异或操作的三个数值中的任意两个，就可以求出第三个数值。在C++中，指针表示内存空间地址，而在Win32系统中，指针用4个字节表示，可以被转换成unsigned int的数值类型。

阅读全文…

评论关闭 (4 views)

regsvr32.exe 的的使用方法及实现

2010年8月10日 | by luckzj | 标签:

regsvr32.exe 是微软提供的注册和反注册COM的工具。我们使用这个工具进行注册的时候，可能会遇到注册失败的情况，这篇文章介绍regsvr32的实现流程，以帮助大家对regsvr32有一个更好的理解，在注册出错时，也可以更加方便地排除错误。

regsvr32使用方法

regsvr32.exe 的使用方法如下：

regsvr32.exe [/u] [/n] [/i[:cmdline]] dllname

/u – 反注册
/s – 安静模式，注册时不弹出对话框提示
/i – 给DllInstall或者DllUnInstall传入参数，通常情况下不会使用这个命令行
/n -不使用 DllRegisterServer，在不使用DllRegisterServer时，必须指定/i参数，这个也可以忽略掉

我们可以直接在命令行里手工输入regsvr32命令注册DLL，也可以在程序或者脚本中调用regsvr32.exe注册COM。在使用后者进行操作时，regsvr32.exe 的返回值会告诉我们执行结果。我没有找到官方的关于regsvr32.exe的返回值的介绍，只能列出我测试出来的结果：

0：执行成功
3：无法接在DLL（通常是因为找不到DLL文件或者DLL文件依赖项缺失）
-1：regsvr32.exe 不可用，可能是这个程序已经被删除

regsvr32.exe的实现流程

regsvr32.exe 会依次调用以下Windows函数

OleInitialize
LoadLibrary
DllRegisterServer或者DllUnregisterServer
FreeLibrary
OleUninitialize

阅读全文…

评论关闭 (4 views)

Soft Binary

map hash_map unordered_map 性能测试

UI技术简介

C++ STL 学习：自己写仿函数(functor)（三）

MFC中用配置文件实现界面布局的方式

Nginx 模块开发（1）—— 一个稍稍能说明问题模块开发 Step By Step 过程

一句话解说内存屏障 Memory barrier

[转载]Windows路径探究

完整路径（Full path）

UNC（Universal Naming Convention通用命名规范）路径

以\\?\开头的路径

相对路径（Relative path）

以\开头的路径

以盘符和冒号开头的路径

pinvoke中的字符串

C#端口扫描

Windows下使用内核对象进行线程同步

Linux 信号处理

C#链接mysql数据库

使用互锁函数和临界区(CriticalSection)实现线程同步

异或指针双向连表(XOR Linked list)

regsvr32.exe 的的使用方法及实现

Notice

Recent Posts

Tags

Category

Recent Comments

链接表