Enterprise Just Builder

Solution for Enterprise Software Architecture

c++

将 Win32 枚举型 APIs 转换为 STL 迭代器

原文1

操作系统都有许多 API 用于存取实体集合的,比方说 Unix 的 opendir()/readdir() 函数。Win32 API 也提供了许多函数用来枚举集合内的元素,通常采用的模型无外乎下面几种:回调函数 (如 EnumChildWindows), get-first/get-next (取第一个/取下一个 比如FindFirst/NextFile), 或 get-nth (取第n个 如 RegEnumValue) — 其语义和前二者完全不同。

现在 C++ 社区正在逐步朝着符合 STL 的通用编码格式迈进,如使用容器 (序列和关联)、迭代器、泛函 (或函子或函数对象)、算法和适配器等等。这一做法的最大好处是可以采用一种通用的方法操纵不同的实体, 大大减少开发者的工作量, 同时提高健壮性、可维护性和重用。

STL 技术未被广泛运用的原因之一是除了标准库所提供的类和函数 (list, vector, for_each 等) 之外, 缺少可用的 STL 兼容库, 特别对于操作系统 API。原因之一是这涉及编程模型之间迁移转换的复杂性, 特别是对于集合和序列。本文通过将两种 Win32 枚举模型实际转换 STL 序列, 创建封装了 Win32 API 的轻量级序列类, 并提供了可按 STL 标准算法来操纵枚举实体的迭代器。

本文所演示的类是 WinSTL 库的一部分,WinSTL 则是 STLSoft 的子项目。STLSoft 是个开源组织,一直致力于将 STL 概念运用到多种技术和操作系统中去。

>>> 阅读全文

 

, , , ,

C++ 设计模式之一 建造型模式

设计模式既不是某种静态解决方案,也不是某种算法。设计模式通过其名称(大多数是对目标的简单描述)来介绍或引入一些常见设计问题的重复解决方案或方法,或者说是解决一般性问题的常用方法。因此作为对具体实现的一种抽象,设计模式在设计阶段就十分有用。有了这个概念,在做设计选择时作为标准技术进行沟通,可以让团队成员更容易分享其设计理念。

根据所解决的设计问题,设计模式主要分为以下几大类:

  • 创建型模式 (Creational Patterns)
  • 结构型模式 (Structural Patterns)
  • 行为型模式 (Behavioral Patterns)

模式在 C++ 或 Java 这类面向对象的编程语言中十分常见。它可被视为模板,用来说明如何解决某个在不同场景或应用中反复出现的问题。设计模式不是代码重用,因为它通常没有具体代码,但通过设计模式轻松创建代码。面向对象的设计模式通常显示的是类或对象之间的关系和互动,而无需涉及应用最终呈现的类或对象。

每个设计模式由以下几个部分组成:

  • 问题或需求(Problem/Requirement):它阐述了所要解决的问题的需求。通常是在多个应用中都会遇到的常见问题。
  • 制约条件(Forces): 它描述了技术限制,用来帮助指导创建解决方案.
  • 解决方案(Solution): 它描述了介绍如何编码来解决上述问题。这是设计模式的设计部分。它可能包含类图
    时序图等等。

设计模式可以视为一个标准,是广泛认可的用来解决某个特定设计问题的最佳实践。在应用程序内采用良好的设计模式,可以大大加速你的设计工作,并有助于和其他程序员进行沟通,从而避免解决方案陷入繁琐晦涩的境地。

>>> 阅读全文

 

,

Microsoft Bond C++ 使用手册

文章评价:

Bond 是微软开发的数据结构化(schema)处理框架,它支持跨语言的序列化与反序列化,支持强大的泛型机制,因此能够对数据进行有效地处理。该框架在微软公司内部的高扩展服务中得到了广泛的应用。Bond 可适用于服务间通信、大数据存储和处理等诸多应用场景。

Bond 定义了一个富类型系统和一套 schema 版本控制规则以提供前后向的兼容性。Bond 的核心功能包括高性能的数据序列化/反序列化和一个强大的通用数据转化机制。通过可插拔的序列化协议、数据流和用户自定义类型别名(user defined type aliases)等机制,由此 Bond 实现了高可扩展性。

目前该项目已经基于宽松的 MIT 许可开源在了 GitHub 上,当前版本支持 C++、C# 和 Python,可运行 在Linux、OS-X 和 Windows 平台上。Bond 的编译器完全是使用 Haskell 编写的。

Bond 与其他序列化系统具有很多相似性,例如 Google Protocol Buffers (ProtoBuf)、Thrift 以及 Avro等等。和它们相比,Bond 有以下特点:

>>> 阅读全文

 

, , ,

无锁双向链表

基于锁的同步机制总是受到象优先级反转(priority inversion )和死锁的困扰,即使这样,无锁同步还未引起重视。原因是要编写正确且高效的无锁代码实在困难1。本文演示了一个无锁双向链表的实现,实用且易于理解。第一个无锁双向链表是由 H°akan Sundell 实现的,本文中的方案利用了单字 (single-word) 的比较并转换(CAS — compare-and-swap)原子原语。在附录中提供了本方案与 H°akan Sundell 实现的链表的比较结果。 2

背景: 原子操作与 CAS
原子操作是指一系列必须整体完成的操作步骤,如果任何一步操作没有完成,那么所有完成的步骤都必须回滚,这样就可以保证要么所有操作步骤都未完成,要么所有操作步骤都被完成。在单核系统里,单个的机器指令可以看成是原子操作(如果有编译器优化、乱序执行等情况除外);在多核系统中,单个的机器指令就不是原子操作,因为多核系统里是多指令流并行运行的,一个核在执行一个指令时,其他核同时执行的指令有可能操作同一块内存区域,从而出现数据竞争现象。多核系统中的原子操作通常使用内存栅障(memory barrier)来实现,即一个 CPU 核在执行原子操作时,其他 CPU 核必须停止对内存操作或者不对指定的内存进行操作,这样才能避免数据竞争问题。3

因此在 X86 平台上,Intel 提供了在指令执行期间对总线加锁的手段。CPU 芯片上有一条引线 #HLOCKpin,如果汇编程序中的某条指令带了前缀 “LOCK”,CPU 执行到这条指令时就会 #HLOCKpin 的电位拉低直到该指令结束,从而将总线锁住,这样同一总线上其它 CPU 就暂时不能通过总线访问内存了,这样保证了指令在多处理器环境中的原子性。

所谓比较并交换 (CAS) 是在多线程中可用来获得同步的原子指令。CAS 操作包含三个操作数 —— 目标值(V)、原值(A)和新值(B)。CAS 指令会先将目标值 V 与原值 A 进行比较,如果二者相同,那么就可以新值 B 赋予目标值。

在 Windows 和 .NET 平台,由于历史原因,CAS 被写做 Interlocked API。原子操作在 Intel 架构 CPU 对应的汇编指令有 XCHG、CMPXCHG、INC 等,当然还得加上 LOCK 作为前缀。

>>> 阅读全文

 

, , ,

C++ 模板编程入门 (一)

于天生的畏惧,大多数 c++ 程序员都尽量远离模板技术,反对的声音有:

  • 模板难以学习和运用
  • 编译时的错误信息模糊又冗长
  • 不值得花费精力

我承认模板都有点难以学习、理解和运用。但是从模板中获得的益处会多于其负面影响。许多泛型函数或类都可以被模板所包装。我后面会加以解释。

虽然从技术上来看 c++ 模板与 STL (标准模板库) 是同门兄弟。不过在本文中,我将只涵盖模板的核心部分。在下一篇文章中,我会阐述更高级且有趣的模板技术以及使用 STL 的一些诀窍。

语法
你可能已经知道,大部分模板都使用尖括号:小于号(<)和大于号(>),其使用形式总是如下所示:

< Content >

这里的 Content 可以是:

>>> 阅读全文

 

, ,

基于 MYSQL 存储引擎实现虚拟数据表查询 (一)

文章评价:
MySQL 支持多种可用于存储管理与检索的存储引擎,最常见的是 MyISAM 和 InnoDB 。创建数据表时可以指定存储引擎。最简单的存储引擎只能读取数据表。大多数引擎支持从文件读取数据并回馈给 MySQL。所以,我设想调用 API 来检索数据并将数据直接回馈给 MySQL。在此之上,我们可以利用 SQL 语句对检索到的数据进行复杂分析。为此我需要在相关 API 之上编写一个引擎,不过我并不打算从头开始编写新引擎,而是打算构建一个通用的组件让所有存储引擎调用,这将大大简化编写引擎的工作。1

背景
我希望透过 MySQL 对系统中的进程进行分析,通过 MySQL 控制台上获得运行中的进程的列表,进而执行复杂分析,比如说查询某个进程所包含的模块。为了提供简单的视图,我希望将这些以数据表的形式呈现,由存储引擎来调用相关 API 检索数据。API 是操作系统中现成的。对于其他部分,传统办法是创建数据表,每当有新进程启动就插入新的数据行,有进程终止时就删除数据行。

显然这种方法有很多缺点:

  • 插入删除数据行都是系统开销。
  • 在查询数据表前,你需要触发负责插入或删除数据行的日志程序。
  • 即便只需查看单一进程,数据表中还是需要维护所有进程的信息。
  • 一旦进程终止它的进程 ID 又为新进程所用,这时如旧数据行未删除就插入新数据行会产生 ID 冲突。
  • 插入或删除需要表锁定,可能会是整个检索单元的性能瓶颈。

因此新的构思应当解决这些问题:

  • 无需插入或删除数据行
  • 查询数据表之前无需触发日志应用
  • 如只查询单一进程则不用读取所有进程的消息
  • 无进程 ID 的不一致性,因为该数据表只是系统的状态快照
  • 无性能瓶颈,因为没有插入或删除操作

好处
新构想比传统方法更好地解决了一个具体问题:即表中的数据可以有时间轴。当表的大小达到一定限度时,可以创建新表。这也是使用 Tableau 商业智能工具进行分析时的要求。Tableau 可以生成 SQL 查询。为方便起见,要求使用单个表而在背后维护多表间的关系。我们可以生成编程式查询来检索某时间段内的数据并显示在 web 页面上,但 Tableau 无法使用这些程序。一种传统技术是将数据复制到单个表中,但同时我们所维护多表的关联就会失效。另一种传统技术是使用视图,但是在视图背后使用编程式查询会导致视图失效。我所构想的是只公开单个数据表,利用 API 从多个表中检索数据。编写存储引擎可以提供解决方法。最简单的引擎会回馈所有的数据让 MySQL 筛选,但这非常低效。而我所构想的存储引擎将利用 MySQL 查询分析器的强大能力。在 MySQL 查询期间 where 子句会被转换为对函数和 API 的调用,这样某种程度上我们只要检索所需的数据。这个构想广义上可以推广到任何 API,无需重写生成 API 调用等核心逻辑。

>>> 阅读全文

 

, , ,

用 libclang 实现代码生成器

文章评价:
代码生成器对大型 C++ 项目而言是非常有用的工具。由于语言层面上缺乏自省(introspection)机制,要实现反射、脚本绑定(script binding)及序列化都需要编写代码样板(boilerplate) 以保留相关信息,否则在编译时这些数据会全部被丢弃。大部分解决方案要嘛是侵入式的(严重依赖于宏 — Macro,结果难以调试且要求怪异的语法声明)要嘛非常脆弱(fragile)(要根据实际代码不断更新样板,常常没有任何警告就中止运行)。提高鲁棒性的方法之一是自动生成这类样板。要实现这一目标,需要用某种方式解析代码,换句话说,需要了解什么信息该被保留。然而,解析 C++ 本身就是极其复杂的工作,要考虑各种怪异情况,如果真想这样做,消费的时间可能相当漫长。 1

即使只针对 C++ 某个“差堪可用”的子集进行解析,这类尝试要嘛失败了要嘛对编码规则有严格要求。也就是说,要求避免使用解析器无法理解的语法 — 一旦有人不按规矩提交代码解析器就会中止工作。要解决这个问题,我发现 LLVM 项目中有一个很好的工具:libclang2。由于 CLANG C++ 前端 和 libclang 调用的代码是相同的,所以它了解 C++ 的一切。该类库的最新发布可以支持 C++1x(如不出意外将是 C++14)的功能。唯一略有欠缺的是文档方面:其官方文档不过是 Doxygen 生成的参考,虽然有用,但不足以介绍如何使用该类库;加上问题本身的复杂性,学习曲线将十分陡峭。

本文要讲述的是如何用 libclang 及其 Python 绑定来实现一个实用的 C++ 代码生成器。在某种意义上,“实用” 意味着这不是一个通用的解决方案。这里所演示的不是某种具体的实现,而是一种解决问题的思路、一个详细的范例。借助这些想法,你可以自己创建通用的反射方案。本文的另一设计原则是尽力减少代码侵入以便能按自然 C++ 语法编写代码。同时我也鼓励读者自己动手,从头开始尝试实现自己的代码生成器。

我必须感谢 Eli Bendersky 的有关帖子3,它是我收集的资料中最好的参考之一。

准备工作
要读懂本文,读者可能需要具备以下知识点:

>>> 阅读全文

 

, , , , ,

C++ 11 中的多线程

文章评价:

第一个 C++ 标准发布至今已经过去十三年了,随着新的 C++11(或称 C++0X)标准的推出,C++ 标准委员会所做出的显著改变之一就是支持多线程编程。这是首次在 C++ 语言中为并行编程提供支持,而且与平台无关。

在 C++11 标准之前,编写多线程应用需要依赖于特定的平台扩展,如 Intel TBB、OpenMP、Pthreads 等等。现在有了 C++11 的标准线程库就方便了应用移植(例如 Windows 上的 C++11 多线程应用将很容易移植到 Linux 平台),另外对于熟知 Boost 线程库的用户来说,由于 C++11 标准库中许多命名与结构都和 Boost 相同,上手非常容易。1

C++11 标准库中的类可用于线程操作与同步、公用保护数据及低层次的原子操作。

C++11 标准中涉及多线程编程的主要有四个头文件,分别是:<atomic> ,<thread>,<mutex>,<condition_variable>和<future>:

>>> 阅读全文

 

, , ,

操作系统开发初体验(2)C++ 支持代码和控制台

在开始阅读第二篇文章前,我建议你翻阅上一篇文章,不然,接下来的内容可能就用处不大了。

现在我们需要一些支持代码,G++ 会用到其中的一些,不过我们增加了更多的代码以避免奇怪的错误。这里我们要添加的代码有:

  • 对构造器的调用
  • 提供 new 和 delete 的实现
  • 在 GCC 无法调用虚拟方法的时候提供一个方法以供调用。

除了上述三个,还有就是:据说有些操作系统会在内核代码结束的地方调用析构函数,但我没看过这样的案例,大多数多任务操作系统都会在 main 函数的末尾进入无限循环,这样定时器 IRQ 就可以来接管任务。(要晚很多)

首先,我们需要调用构造函数。链接脚本可以指出这些构造函数的指针起始和结束的地址。要调用它们,我们要做只是遍历它们。虽然链接器有可能会弄错顺序,不过概率很低。至少在本系列文章中,我们还是可以信任 GCC 的。

要调用构造器,我们可以使用下面的代码:

>>> 阅读全文

 

, ,

操作系统开发初体验 (1)

文章评价:
如果你正在读这篇文章,没准你想知道更多有关如何创建自己的 OS 方面的内容。不过你首先要知道,我这短短几篇文章是没办法涵盖 OS 开发的各个方面的。我会介绍一些 OS 的基础知识,但还需要靠你自己去研读相关的技术文档,这样你才能明白操作系统为何如此工作。确定还想读下去吗?好,让我们开始吧。

理解 OS 开发很关键的一点是:一切将从零开始,你直接和硬件打交道。你会遇到硬件故障,也不能指望系统每次都如期工作。你没有标准库可供使用,更没有 .NET 框架或者Java 虚拟机。一切只能靠你自己。

开始之前,你要了解系统控制权是如何转交到你手上的。很奇怪的是,没有什么标准规定电脑开机之后应置于什么状态,唯一能确定的是,开机之后一定会去执行引导扇区,它位于可启动的存储介质的起始部分,会被加载到内存地址 0x7C00 处,其长度为 512字节,并以 0xAA55 作为文件末尾签名。引导扇区通常用汇编语言编写。为了节约时间,我们将使用现成的 GRUB (Grand Unified Bootloader)。这可为后续工作提供可靠的基础,并将电脑置于同一个标准状态。

Grub 会将电脑置于以下状态:

  • 保护模式
  • A20 地址线启用
  • 寄存器 EBX 存有指向多重启动信息结构(Multiboot information structure)的指针
  • 寄存器 EAX 存有固定值 0x2BADB002
  • 分页机制关闭
  • 栈位于内存的某处
  • 中断机制关闭

下面我会逐一介绍这些状态。保护模式允许内核开发人员按虚拟地址空间访问最大为 4GB 的内存,并引入了保护环“Ring”的概念。以下几小节会介绍更多的内容。 A20 门电路是键盘控制器附近的一条“古老”的地址线。它最初设计是为了与 8086 保持兼容,在“关闭”的时候,屏蔽了对内存开始部分 1M 以上地址的访问。

>>> 阅读全文

 

, , , , , , , ,

Flex 和 Bison 简介 (三) 支持 C++

和一些收费软件相比,Flex 和 Bison 在某一些方面还是相对比较的弱的,比如说 Flex 对 C++ 的支持还处在实验状态,这意味着在将来的版本中有可能发生较大的改动,而且目前的解决方案在一些细节上处理得还并不好,但作为一个免费软件,Flex 和 Bison 总体上还是非常不错的软件,而且生成的词法生成器不依赖于其他库文件,可移植性比较好。

如果你更倾向于 Flex 和 Bison ,而不是用我们在第二节末尾提到的商业收费软件 Parser Generator 来生成资源模板解析器,那么请跟随本文来了解一下 Flex 和 Bison 是如何支持 C++ 的。

Flex 对 C++ 支持的基本是通过继承来完成的。在头文件 FlexLexer.h中定义了两个类 FlexLexer 和 yyFlexLexer。前者是一个抽象类,定义了 Flex 所生成的词法分析器的接口(interface),比如yylex();后者则继承自FlexLexer,是词法分析器的实现类,封装了词法分析器用到的状态变量等。因此,在默认的 C++ 模式下,Flex 的任务就是根据 “.l” 源文件自动生成 yyFlexLexer 中各成员函数的定义。规则的动作代码自然是被合成为 yyFlexLexer::yylex() 的实现啦,因此在规则动作中我们访问的变量和函数实际都是 yyFlexLexer 类的成员(或者是yylex()的参数 ),而不再是全局变量或全局函数。这便是 Flex 对 C++ 解决方案的基本原理。

这里还有一个问题。即在默认情况下,Flex 把生成的代码都放在了 yyFlexLexer 这一个类里,而事实上,实现类是应该有多个的,尤其是当我们的程序需要多个词法分析器的时候,每个词法分析器都应该对应一个实现类。Flex 是怎么解决这个问题的呢?事实上,在包含进这个头文件之前,”yyFlexLexer” 已经被定义为一个宏,其默认值为”yyFlexLexer”,而 Flex 提供了一些机制来重新定义这个宏,这样就能避免命名冲突的问题啦。关于这个问题我们先讲这么多,下面我们先详细讨论在默认情况下的具体做法,再回来讨论定制的问题。

为了让它跑起来,有两件最基本的事情是必须做的。首先,要在文件的定义段打开 c++ 选项,即添加 “%option c++” 一行。 或者在命令行使用 “-+” 选项也是一样的。打开这个选项之后,Flex 就会生成 C++ 代码,生成的代码会默认输出到 lex.yy.cc文件中(后缀不是”.c”啦)。可是如果这个时候直接编译(使用命令$ flex abc.l && g++ lex.yy.cc),则会收到链接出错的提示:”undefined reference to yyFlexLexer::yywrap()”。怎么回事呢?是不是忘记添库文件啦?仔细想一想,这个错误其实是在抱怨yyFlexLexer::yywrap()函数没有定义。原来,Flex 忘记帮我们生成一个默认的 yywrap() 的定义啦。其实这也不能怪 Flex 粗心,因为即便在 c 的情况下,它也不会自动合成这个函数的定义,我们之所以使用 C 语言时没有收到这个链接错误,只是因为在 fl 库中提供了一个默认的实现而已,因此如果我们自己不写,链接器就会把 fl 库中的那一个链接进来啦。可是,这种方法在 C++ 的环境下就不工作,因为这个是一个类的成员函数,而不是全局的啦。

>>> 阅读全文

 

, ,

Flex 和 Bison 简介 (二)

在上一篇文章中,我们讨论了如何用 flex 和 Bison 来 创建词法分析器(标记识别器)和解析器。本文是本系列文章的第二篇,我们将会看到如何用这些工具来创建可以读取 Visual Studio 6 资源文件的解析器。本文将重点关注于词法分析器。

不过考虑到这两个工具的密切联系,我们会在解析器和词法分析器之间来回跳转。在本文的最后,你可以下载到词法分析器和解析器的源代码。

如我们在第一篇文章中讨论的,词法分析器负责从某处读取输入流,并将其分解成一连串的标记。每个标记代表着最底层的构造块,用于表示诸如字符串、 数字或关键字等等东西。词法分析器通过将输入数据和一系列正则表达式 (规则) 相匹配来实现实现这一点。当它找到和特定规则的一个匹配时,它会执行将程序员所编写的一些执行代码,并向解析器返回一个标记,用于表明哪个规则被匹配了。它还可能会返回一些与规则关联的数据。

例如下面的正则表达式。

/* Decimal numbers */
-?[09]+    {
        yylval.ival = atoi(yytext);
        return NUMBER;
    }

该表达式会匹配以负号开头的包含至少一个数的十进制数序列。(有关正则表达式的含义和格式,你可以参考:http://www.monmouth.com/~wstreett/lex-yacc/flex_1.html 并搜索的”模式”)。当找到匹配时,它会调用 atoi 函数并将字符串 yytext 传递给它作为参数,yytext 正好是符合规则的字符串。另一方面,atoi 的返回值被赋给在解析器中定义的联合 yylval 的成员 ival。最后该操作会返回一个 NUMBER 标记给解析器并终止。

>>> 阅读全文

 

, , , , ,

Flex 和 Bison 简介(一)

文章评价:
我手边有个项目需要编写个对话框编辑器,该编辑器能够加载对话框模板,然后显示出相应的对话框。

实现该设计有简单的办法,也有比较困难的办法。简单的做法只需将资源脚本编译成 .res 文件,就能得到编译过的模板。然后让程序访问这些 .res 文件,由此得到对话框模板的句柄,并传递给 CreateDialogIndirect 函数。这样就可以用代码来检查每个控件的属性。但这种方式要求一旦修改某个模板之后就必须重新编译资源脚本,否则将导致严重的逻辑错误。

为此,我舍易求难,选择了较为困难的方法:实现一个能读取 Visual Studio6 资源文件 (.rc 文件)的解析器,然后返回一系列编译过的对话框模板。

具体要如何实现呢?如果你曾看资源模板文件的源文件,你会发现自己一个人从零开始实现这样一个解析器基本是不可能的。资源文件包含许多文本块,其中有注释、工具栏资源、菜单、对话框等等。每种文本块都有固定的格式。要用面向过程的方法来编写能够解析这些文本块的程序,要解决的问题实在太多了。还好我们有 Flex 和 Bison 可以提供帮助。

什么是 Flex 和 Bison?
既然提到 Flex 和 Bison 就不能不说到其前身 Yacc 和 Lex 。Yacc 和 Lex 起源于 UNIX 世界。Yacc 是 “yet another compiler compiler” 的缩写,而 Lex 则是 ‘lexical analyser’ 的简称。光了解这些名称就已经说明了很多问题 !你可以参阅 compilertools 站点 ,该站点提供了适合不同水平用户的范例,而且还有很详细的说明和解释。

>>> 阅读全文

 

, , , , ,

C++11 智能指针

文章评价:

许多程序员总避免使用指针,因为一旦处理不当,就会带来很多问题。所以新手程序员都不太喜欢指针。使用指针可能会引发许多问题,例如需确保指针所引用的对象的生命周期、虚引用(dangling references)和内存泄漏。

如果某内存块为多个指针变量所引用,而其中有个变量释放了这片内存,就会造成虚引用(dangling references)。另一种情况是,程序员从堆里申请了内存块,但未进行释放,这时则会造成内存泄漏。

某些资深程序员可能会说,你看我正确地从堆里获得了内存,进行相关操作,最后也正确地释放了内存, 这段代码干净漂亮,为什么还需要智能指针呢?

void Foo( )
{
    int* iPtr = new int[5];
    //manipulate the memory block
    .
    .
    .
    delete[ ] iPtr;    
}

的确,上面的代码目前工作正常,在理想情况下也能正确地释放内存。但如果考虑运行代码时的实际环境,在内存分配与释放之间存在着许多指令,这些指令可以做一些乱七八糟的事,比如访问无效的内存位置、除零错,甚至可能你的同事修改了你的代码,添加某种条件下的 return 语句。

>>> 阅读全文

 

,

GPerf 和完美哈希函数

GNU Gperf 工具用来生成一种 “完美的” 散列函数(perfect hash function),可以将用户提供的一组特定字符串生成散列表、散列函数和查找函数的 C/C++ 代码。 所谓完美散列函数或完美 Hash 函数,指存在这样一个 hash 函数 F,可以将一个含有 n 元素的用户特定关键字集合 N 到集合 W, N 的关键字被唯一映射到 W 的 0..k-1 范围,其中 k>=n。如果 k=n 那么 F 就是“最小化完美 hash 函数”。

最小化完美 hash 函数具有两个特性:

  • 只需要执行一次查找就能完成静态搜索结构中的关键字识别,即所谓的“完美”。
  • 为保存关键字所分配的内存刚刚可以容纳关键字集合,不会多余。即“最小化”。

Gperf 被普遍地用在多种商业编译器、研究型编译器、语言处理工具的词法分析器上,用来生成关键字识别器,包括:GNU C, GNU C++, GNU Pascal, GNU Modula 3 和 GNU indent 等等。Gperf 将从用户提供的文件中(即关键字文件,通常使用 .gperf 作为扩展名,但不做强制要求)生成 C/C++ 源代码。所有代码被定向到标准输出,然后必须重定向到类似下面的文件:

gperf  -L C++ keyfile.gperf > perfecthash.hpp

注意: -L 选项将指示 gperf 生成 C++ 代码。

Gperf 会生成一个 0..K 元素的静态查找结构和一对 C 函数的源代码。利用这些函数只需要一次查找,就可以判断给定的字符串 S 是否在集合 W 中。这两个函数是:

>>> 阅读全文

 

, , ,

Previous Posts