前缀压缩词典

阅读更多关于《前缀压缩词典》

包含多个固定索引,一个可变索引,

固定索引使用一个内存池和一个数组保存项目在内存中的偏移,并且使用前缀压缩,使用空间最小(每个词条4个字节的索引空间)  

可变索引不压缩,并且可以动态插入词条,占用空间较大(每个词条20个字节的索引空间)

存储 1000 万个词,占用内存 100M 左右,平均每个词10个字节(包括了字符串空间和索引空间)。

接口采用 stl 容器的风格

cpu 的 cache 是很宝贵的——从互相平行的数组看

阅读更多关于《cpu 的 cache 是很宝贵的——从互相平行的数组看》

以前一直想不通,为什么在有些系统中,要把同一个数据结构的不同字段放入 多个互相平行的数组中,而不是放入一个结构中。 继续阅读

未来的 PC 会怎样

阅读更多关于《未来的 PC 会怎样》

是更简化,还是更复杂?我觉得应该是更简化。

网络速度变得越来越快,终究有一天,会光纤入户,最终,或许用不了多久,网络速度已经比我们的硬盘快了。

目前的PC(个人电脑)之所以是现在这个样子,是因为我们的硬盘,相对于网络有两个优势,一个是速度,一个是隐私。当速度已经不是问题,就只剩一个隐私了。而隐私问题实际上只是一个心理问题,人们总觉得把隐私敏感的东西也存储到网上 不安全,容易泄露,而实际上,保存在自己的硬盘上并不比存在网络上更安全,更不容易泄露。如果大家都认识到这个问题,那么,硬盘,对于PC,就已经不重要了。(——除非此时硬盘已被如Flash一类的新产品代替了,并且速度比网络至少快一个数量级,并且大家有那么高的吞吐量需求。)

应该不会太久,我们设想这时的网络速度是50MB/s,那么pc,只需要内存和cpu,操作系统都不需要了,就像现在的电视,一打开就可以用,并且所有的东西都是最新的(根本不需要什么软件更新一类的东西)。仅仅需要的就如同现在和很久以前的旧时代里从终端登录:用户名,密码。不同的是,那时是consol终端,现在是比Vista更强劲的终端。

pc 的cpu也更快,内存也更大了,而同时,网络分布式计算的增长更快。很多计算根本都不需要pc的参与,他只需要向网络发出命令,比如编辑文档,收发邮件,游戏(图象计算密集的除外,现在的网游服务器可以认为是未来全分布式游戏时代的雏形)。

浏览器也泛化了,进入计算机所有的操作都是在“浏览器”中进行,就像我们现在在在图形界面或consol终端进行操作一样。我们个性化的东西就是自己的配置,配置哪些东西是我一步(我的顶级目录)操作就可以得到,那些东西需要两步(二级目录),那些需要三步,……整个世界上所有的东西我们都可以得到,只是得到它的方便程度不同。

这个终极的理想在过去和现在已经有一些雏形,如一些网吧里的机器,一些学校的机房,有windows的,有linux的。现在ubuntu已经在朝这个方向努力了。如果linux最终能在这个方向上走到windows前面,或许微软的日子就到头了,除非他也顺应时代潮流。

用C++的高级模版特性实现一个不需要IDL的RPC

阅读更多关于《用C++的高级模版特性实现一个不需要IDL的RPC》

当然,首要的是为了有用,其次是挑战自己驾驭 C++ 的能力,目前已经全部完成,并且取得了非常好的效果。使用该 RPC 的简短示例代码: 继续阅读

VC++ 6.0 的函数模版解析 bug

阅读更多关于《VC++ 6.0 的函数模版解析 bug》

struct TTT1 { int x; };
struct TTT2 { int x; };

template<class T1, class T2>
void foo(T1& t1, T2& t2)
{
 printf("111111111111/n");
}

template<class T1>
void foo(T1& t1, TTT2& t2)
{
 printf("222222222222/n");
}

void foo2()
{
 TTT1 x;
 TTT2 y;
 foo(x, y);
}

上述代码在 vc6 中编译会出错:

error C2667: ‘foo’ : none of 2 overload have a best conversion
error C2668: ‘foo’ : ambiguous call to overloaded function

在 vc2005 中,gcc 中编译都通过。本来一个好好的库,因为这个原因在 VC6 下不能用了。

按序号索引二叉树的应用

阅读更多关于《按序号索引二叉树的应用》

主要是快速计数。

可以从Index得到相应结点,也就可以从相应结点得到 Index。

如果有两个结点,通过彼此间的 Index 相减,就可以得到他们之间的结点个数。

这种算法可以推广到使用 B+Tree 或其它更复杂的树。

使用" 参数化基类" 和" 成员函数指针" 模拟实现虚函数--在实际中的应用

阅读更多关于《使用" 参数化基类" 和" 成员函数指针" 模拟实现虚函数--在实际中的应用》

// 使用" 参数化基类" " 成员函数指针" 模拟实现虚函数--在实际中的应用。

#include <stdio.h>

#include <string.h>

/*

    病毒或许可以使用这种技术有效地实现,不过这是我在写 Windows PE 文件

    加壳程序的时候总结出来的技术。当然可以被用在恶意程序上,任何事情总有两面性!

 

    ***注意***

    VC 中测试时,必须去掉“启用增量连接”,即(/INCREMENTAL:NO)

    如果在 ShellCode 或者 Virus 中使用该技术,字符串文字量(string literal

    也必须进行地址转化,即:convert_address("string literal").

 

    使用 "参数化基类 " "成员函数指针 "模拟实现虚函数。

    可能大家都以为只有疯子才会这么干,好好的虚函数干吗不用,而偏要拐弯抹角地

    搞得这么复杂,但有时候这可能是最好地选择。举个例子吧,我写 Windows PE 文件

    加壳程序的时候,遇到一个问题:

    1. 我开发了一个框架,可以只用 C++ 来写 "壳程序 ",大家很难想到吧!

    2. 但不能使用一些 C++ 功能:虚函数,异常处理,还有 switch-case 语句

    3. C++ 异常处理可以不用,但是不能使用虚函数可能太过苛刻。

 

    当我看了 "generative programming"以后,觉得 "参数化继承 "

    或许可以满足这个需求,模拟实现虚函数。

    以下是使用 "参数化继承 "实现虚函数的框架,以及要注意的事项。

 

    BaseClass 显然,实际上是 "抽象基类 ",因为如果实例化

    "InstantialClass<ConcreteClass>" 时,ConcreteClass

    必须定义响应的 "虚函数 ",否则编译就报错。如果相应的

    BaseClass InstantialClass 定义正确无误(从代码可以

    看到,这很简单,但比较麻烦,必须注意一些细节)。因此

    ConcreteClass 编译期错误不会被推迟到运行时才发现,

    而使用其它方式模拟,就很难有这个保证。

 

    其实,如果了解 C++ 的底层对象模型,这些需要注意的细节

    很容易理解!

 

    //——-

    另外有一种 C 语言模拟 C++ 虚函数的方法,可以在我以前

    (2002 )一篇文章中看到。

*/

 

struct Context

{

    int (*printf)(const char *, …);

 

    // other external fuctions…

};

 

// construct these codes…

int entry(const Context* context)

{

    int imp_entry(const Context* context);

    return imp_entry(context);

}

 

template< typename AddressType >

AddressType convert_address(AddressType address)

{

    // if used in shell code, this must return another valid address.

#define SUPPORT_RECLOCATION

#ifdef SUPPORT_RECLOCATION

    __asm {

        call LL

LL:     pop eax

        sub eax, offset LL

        add eax, address

        mov address, eax

    }

#endif

    return address;

}

 

class BaseClass

{

#define DEFINE_VIRTUAL(ret , name, param_list, call_list ) /

protected :  /

    typedef ret (BaseClass ::*T## name) param_list ;   /

    T## name p ##name;     /

public :                 /

    ret name param_list /

    { return ( this->*this ->p## name)call_list ; }

 

//////////////////////////////////////////////////////////////////////////

// expansion of :

/*  DEFINE_VIRTUAL(int, Func1,

        (int x1, int x2),

        (   x1,    x2)

        );

*/

protected :

    typedef int (BaseClass ::*TFunc1)( int x1 , int x2);

    TFunc1 pFunc1;

public :

    int Func1(int x1, int x2 )

    {

        return ( this->*this ->pFunc1)( x1, x2 );

    //  return (this->*pFunc1)(x1, x2); // can be simplified as this line.

    }

// end expansion

//////////////////////////////////////////////////////////////////////////

 

    DEFINE_VIRTUAL( int, Func2 ,

        (int x1, int x2, int x3 ),

        (   x1 ,    x2 ,    x3 )

        );

 

public :

    template< typename BaseFuncType , typename ConcreteFuncType>

    void assign(BaseFuncType & x, ConcreteFuncType y )

    {

    // if use C Style cast like "(BaseFunType)(y)", it is danger!!

    // any member function can be assigned to x!!

    //  x = convert_address((BaseFuncType)(y)); // danger!!

        x = convert_address(static_cast <BaseFuncType>(y));

    }

    BaseClass()

    {

        pFunc1 = 0;

        pFunc2 = 0;

    }

};

 

class ConcreteClass1

{

private :

    const Context* context;

    int x1, x2 , x3;

public :

    ConcreteClass1(const Context* context)

    {

        this->context = context;

    }

    int Func1(int x1, int x2)

    {

        this-> x1 = x1 ;

        this-> x2 = x2 ;

        context->printf("ConcreteClass1::Func1/n");

        context->printf("x1=%d, x2=%d/n/n", x1, x2);

        return 0;

    }

    int Func2(int x1, int x2 , int x3)

    {

        this-> x1 = x1 ;

        this-> x2 = x2 ;

        this-> x3 = x3 ;

        context->printf("ConcreteClass1::Func2/n");

        context->printf("x1=%d, x2=%d, x3=%d/n/n", x1, x2, x3);

        return 0;

    }

};

 

class ConcreteClass2

{

private :

    const Context* context;

    int x1, x2 , x3;

public :

    ConcreteClass2(const Context* context)

    {

        this->context = context;

    }

    int Func1(int x1, int x2 )

    {

        this-> x1 = x1 ;

        this-> x2 = x2 ;

        context->printf("ConcreteClass2::Func1/n");

        context->printf("x1=%d, x2=%d/n/n", x1, x2);

        return 0;

    }

    int Func2(int x1, int x2 , int x3)

    {

        this-> x1 = x1 ;

        this-> x2 = x2 ;

        this-> x3 = x3 ;

        context->printf("ConcreteClass2::Func2/n");

        context->printf("x1=%d, x2=%d, x3=%d/n/n", x1, x2, x3);

        return 0;

    }

};

 

template <class ConcreteClass>

class InstantialClass :

    // "BaseClass" must be first base class, otherwise,

    // function pointer convert in "BaseClass::assign()" may be not valid!

    public BaseClass, // interface inherit, multi inherit is not allowed!!

    protected ConcreteClass // implementation inherit, multi inherit is allowed

{

    // it is a guide line that do not hold any data member in this class!!

    //

    // if ‘BaseClass’ is not the first base class for ‘this’ class,

    // and data member is defined here,

    // and these data member will be modified,

    // it will error at runtime!

    // you can reverse the inherit order of

    // BaseClass and ConcreteClass, and try!!

    //

    int x1, x2 , x3;

public :

    // must delegate these member functions…

    int Func1(int x1, int x2 ) { return ConcreteClass::Func1 (x1, x2); }

    int Func2(int x1, int x2 , int x3)

    {

        this-> x1 = x1 ;

        this-> x2 = x2 ;

        this-> x3 = x3 ;

        return ConcreteClass::Func2 (x1, x2, x3 );

    }

 

    InstantialClass(const Context* context)

        : ConcreteClass(context)

    {

    // must assign these member function pointers…

    //  BaseClass::pFunc1 = (TFunc1)(Func1);

    //  int v = _MSC_VER;

#if _MSC_VER >= 1310 // vc2003

        assign(pFunc1, Func1);

        assign(pFunc2, Func2);

#else // in vc6, vc6 template support is not perfect!!

        pFunc1 = (TFunc1)Func1;

        pFunc2 = (TFunc2)Func2;

#endif

    // if use C Style cast in assign, follow line can be compiled,

    // but will error at runtime, because pointer to ConcreteClass

    // is different from to ‘this’!!

    // pointer to ‘BaseClass’ is equal to ‘this’..

    // so, do not write such code,

    // must delegate ‘ConcreteClass::Func2’ to ‘this->Func2’.

    // assign(pFunc2, ConcreteClass::Func2);

    }

};

 

template InstantialClass<ConcreteClass1>;

template InstantialClass<ConcreteClass2>;

 

int imp_entry(const Context* context)

{

    InstantialClass<ConcreteClass1> v1(context);

    InstantialClass<ConcreteClass2> v2(context);

    BaseClass* p1 = &v1;

    BaseClass* p2 = &v2;

 

    p1-> Func1(1111 , 2222);

    p2-> Func1(1111 , 2222);

    p1-> Func2(1111 , 2222, 3333);

    p2-> Func2(1111 , 2222, 3333);

 

    p1-> Func1(1111 , 2222);

    p2-> Func1(1111 , 2222);

    p1-> Func2(1111 , 2222, 3333);

    p2-> Func2(1111 , 2222, 3333);

 

    return 0;

}

 

// template instantiation generated functions were not

// lie in ‘entry()’ and ‘end_address()’.

// this is a problem, we must guess the actual codes size.

//

// it looks as if this is not a good solution for small shell codes.

//

// but in my shell code, I put all code in a PE file,

// and relocate the whole code section of the PE file.

// so, this is good idea for shell code.

// this technic is a good solution for virus,

// —- if you want write virus in C++ and use virtual function!

void end_address() {}

 

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

{

    Context context;

    context.printf = printf;

 

    typedef int (*T_entry)(const Context* context);

    unsigned char codeBuffer[16*1024];

    size_t codeSize = (unsigned char*)end_address – (unsigned char*)entry;

    size_t guessedCodeSize = sizeof(codeBuffer);

//  memcpy(codeBuffer, (void*)entry, codeSize); // run error!!

    memcpy(codeBuffer, (void*)entry, guessedCodeSize); // run ok!!

 

//  entry(&context);

    ((T_entry)(void*)codeBuffer)(&context);

 

    return 0;

}

 

 

 

使用" 参数化基类" 和" 成员函数指针" 模拟实现虚函数

阅读更多关于《使用" 参数化基类" 和" 成员函数指针" 模拟实现虚函数》

// 使用" 参数化基类"" 成员函数指针" 模拟实现虚函数。

#include "stdafx.h"

 

/*

    使用 "参数化基类 " "成员函数指针 "模拟实现虚函数。

    可能大家都以为只有疯子才会这么干,好好的虚函数干吗不用,而偏要拐弯抹角地

    搞得这么复杂,但有时候这可能是最好地选择。举个例子吧,我写 Windows PE 文件

    加壳程序的时候,遇到一个问题:

    1. 我开发了一个框架,可以只用 C++ 来写 "壳程序 ",大家很难想到吧!

    2. 但不能使用一些 C++ 功能:虚函数,异常处理,还有 switch-case 语句

    3. C++ 异常处理可以不用,但是不能使用虚函数可能太过苛刻。

 

    当我看了 "generative programming"以后,觉得 "参数化继承 "

    或许可以满足这个需求,模拟实现虚函数。

    以下是使用 "参数化继承 "实现虚函数的框架,以及要注意的事项。

 

    BaseClass 显然,实际上是 "抽象基类 ",因为如果实例化

    "InstantialClass<ConcreteClass>" 时,ConcreteClass

    必须定义响应的 "虚函数 ",否则编译就报错。如果相应的

    BaseClass InstantialClass 定义正确无误(从代码可以

    看到,这很简单,但比较麻烦,必须注意一些细节)。因此

    ConcreteClass 编译期错误不会被推迟到运行时才发现,

    而使用其它方式模拟,就很难有这个保证。

 

    其实,如果了解 C++ 的底层对象模型,这些需要注意的细节

    很容易理解!

 

    //——-

    另外有一种 C 语言模拟 C++ 虚函数的方法,可以在我以前

    (2002 )一篇文章中看到。

*/

class BaseClass

{

#define DEFINE_VIRTUAL(ret , name, param_list, call_list ) /

protected :  /

    typedef ret (BaseClass ::*T## name) param_list ;   /

    T## name p ##name;     /

public :                 /

    ret name param_list /

    { return ( this->*this ->p## name)call_list ; }

 

//////////////////////////////////////////////////////////////////////////

// expansion of :

/*  DEFINE_VIRTUAL(int, Func1,

        (int x1, int x2),

        (   x1,    x2)

        );

*/

protected :

    typedef int (BaseClass ::*TFunc1)( int x1 , int x2);

    TFunc1 pFunc1;

public :

    int Func1(int x1, int x2 )

    {

        return ( this->*this ->pFunc1)( x1, x2 );

    //  return (this->*pFunc1)(x1, x2); // can be simplified as this line.

    }

// end expansion

//////////////////////////////////////////////////////////////////////////

 

    DEFINE_VIRTUAL( int, Func2 ,

        (int x1, int x2, int x3 ),

        (   x1 ,    x2 ,    x3 )

        );

 

protected :

    template< typename AddressType >

    AddressType convert_address(AddressType address)

    {

        // if used in shell code, this must return another valid address.

        return address;

    }

public :

    template< typename BaseFuncType , typename ConcreteFuncType>

    void assign(BaseFuncType & x, ConcreteFuncType y )

    {

    // if use C Style cast like "(BaseFunType)(y)", it is danger!!

    // any member function can be assigned to x!!

    //  x = convert_address((BaseFuncType)(y)); // danger!!

        x = convert_address(static_cast <BaseFuncType>( y));

    }

    BaseClass()

    {

        pFunc1 = 0;

        pFunc2 = 0;

    }

};

 

class ConcreteClass1

{

private :

    int x1, x2 , x3;

public :

    int Func1(int x1, int x2 )

    {

        this-> x1 = x1 ;

        this-> x2 = x2 ;

        std:: cout << "ConcreteClass1::Func1" << "/n" ;

        std:: cout << "x1=" << x1 << ", x2=" << x2 << "/n/n";

        return 0;

    }

    int Func2(int x1, int x2 , int x3)

    {

        this-> x1 = x1 ;

        this-> x2 = x2 ;

        this-> x3 = x3 ;

        std:: cout << "ConcreteClass1::Func2" << "/n" ;

        std:: cout << "x1=" << x1 << ", x2=" << x2 << ", x3=" << x3 << "/n/n";

        return 0;

    }

};

 

class ConcreteClass2

{

private :

    int x1, x2 , x3;

public :

    int Func1(int x1, int x2 )

    {

        this-> x1 = x1 ;

        this-> x2 = x2 ;

        std:: cout << "ConcreteClass2::Func1" << "/n" ;

        std:: cout << "x1=" << x1 << ", x2=" << x2 << "/n/n";

        return 0;

    }

    int Func2(int x1, int x2 , int x3)

    {

        this-> x1 = x1 ;

        this-> x2 = x2 ;

        this-> x3 = x3 ;

        std:: cout << "ConcreteClass2::Func2" << "/n" ;

        std:: cout << "x1=" << x1 << ", x2=" << x2 << ", x3=" << x3 << "/n/n";

        return 0;

    }

};

 

template <class ConcreteClass>

class InstantialClass :

    // "BaseClass" must be first base class, otherwise,

    // function pointer convert in "BaseClass::assign()" may be not valid!

    public BaseClass, // interface inherit, multi inherit is not allowed!!

    protected ConcreteClass // implementation inherit, multi inherit is allowed

{

    // it is a guide line that do not hold any data member in this class!!

    //

    // if ‘BaseClass’ is not the first base class for ‘this’ class,

    // and data member is defined here,

    // and these data member will be modified,

    // it will error at runtime!

    // you can reverse the inherit order of

    // BaseClass and ConcreteClass, and try!!

    //

    int x1, x2 , x3;

public :

    // must delegate these member functions…

    int Func1(int x1, int x2 ) { return ConcreteClass::Func1 (x1, x2); }

    int Func2(int x1, int x2 , int x3)

    {

        this-> x1 = x1 ;

        this-> x2 = x2 ;

        this-> x3 = x3 ;

        return ConcreteClass::Func2 (x1, x2, x3 );

    }

 

    InstantialClass()

    {

    // must assign these member function pointers…

    //  BaseClass::pFunc1 = (TFunc1)(Func1);

        assign( pFunc1, Func1 );

        assign( pFunc2, Func2 );

 

    // if use C Style cast in assign, follow line can be compiled,

    // but will error at runtime, because pointer to ConcreteClass

    // is different from to ‘this’!!

    // pointer to ‘BaseClass’ is equal to ‘this’..

    // so, do not write such code,

    // must delegate ‘ConcreteClass::Func2’ to ‘this->Func2’.

    // assign(pFunc2, ConcreteClass::Func2);

    }

};

 

int _tmain( int argc , _TCHAR* argv[])

{

    BaseClass* p1 = new InstantialClass< ConcreteClass1>();

    BaseClass* p2 = new InstantialClass< ConcreteClass2>();

 

    p1-> Func1(1111 , 2222);

    p2-> Func1(1111 , 2222);

    p1-> Func2(1111 , 2222, 3333);

    p2-> Func2(1111 , 2222, 3333);

 

    p1-> Func1(1111 , 2222);

    p2-> Func1(1111 , 2222);

    p1-> Func2(1111 , 2222, 3333);

    p2-> Func2(1111 , 2222, 3333);

 

    delete p2;

    delete p1;

 

    return 0;

}

 

 

stl::set 的一个缺陷

阅读更多关于《stl::set 的一个缺陷》

stl::set  什么都好,就一点不好:不能仅仅通过 key去查找元素。

例如

 

搞 Java 也有一段时间了

阅读更多关于《搞 Java 也有一段时间了》

搞 Java 也有一段时间了。

Java 现在也支持 GP 了。

但是感觉 Java 好像总是那么那么的。

可能是 C++ 用惯了。

但是 C++ 的表达能力是在是比 Java 强得多。

MS 也推出了 C++/CLI,简单得看了一下,那简直就是我梦想中的 C++ 应该有的样子,虽然看上去有点复杂。

Java 的 GP 语法,虽未如 C++ 般达到了图灵完备,但是它的 F-约束,比起 C++ ,要好一些,它很直观,而实际上在 C++ 中没有相同的语法结构。

C++ 有没有必要也增加这种语法呢?