Martini源码剖析
martini是非常优雅的Go Web框架。他基于依赖注入的思想，仿照Sinatra的路由设计，参考Express的中间件设计，而且核心微小，扩展方便，非常值得学习。但是由于本身API 设计简洁，使很多细节无法从代码理解。所以，我写一点笔记记录martini的工作方式。Martini核心
我们从最简单的官方实例入手：
package main
import"https://www.doczj.com/doc/d73372600.html,/go-martini/martini"
func main() {
m := martini.Classic()
m.Get("/", func() string {
return"Hello world!"
})
m.Run()
}
martini.Martini是自带的核心结构，负责完成依赖注入和调用的过程。martini.ClassicMartini是路由martini.Router和martini.Martini的组合，实现路由分发和逻辑调用的过程。m := martini.Classic()返回的就是
martini.ClassicMartini。具体在martini.go#L104:
func Classic() *ClassicMartini {
r := NewRouter()
m := New()
https://www.doczj.com/doc/d73372600.html,e(Logger())
https://www.doczj.com/doc/d73372600.html,e(Recovery())
https://www.doczj.com/doc/d73372600.html,e(Static("public"))
m.MapTo(r, (*Routes)(nil))
m.Action(r.Handle)
return &ClassicMartini{m, r}
}
里面的m := New()定义在martini.go#L38:
func New() *Martini {
m := &Martini{Injector: inject.New(), action: func() {}, logger: log.New(os.Stdout, "[martini] ", 0)}
m.Map(m.logger)
m.Map(defaultReturnHandler())
return m
}
依赖注入
上面很明显的看到两个奇特方法：m.Map()、m.MapTo()。这里，需要注意martini的一
个最重要原则，注入的任何类型的结构，都是唯一的。即如：
type User struct{
Id int
}
m.Map(&User{Id:1})
m.Map(&User{Id:2})
martini在寻找&User类型的时候，只能获取到&User{Id:2}结构（最后注册的）。Map的作用，就是向内部注册对应类型的具体对象或者值。类型索引是reflect.Type。从而我们可以理解到m.New()的代码中将m.Logger(*log.Logger)和defaultReturnHandler(martini.ReturnHandler)(括号中是类型索引)注入到内部。
这里出现了一个问题。接口这种类型，是无法用reflect.Type()直接获取的（因为传来的都是已经实现接口的具体结构）。解决方法就是m.MapTo()。
m.MapTo(r, (*Routes)(nil))
即将r(martini.router)按照martini.Router接口（注意大小写）类型注入到内部。(*Routes)(nil)
也是高明的构造。接口的默认值不是nil，无法直接new。但是指针的默认值是nil，可以直接赋值，比如var user *User; user = nil。因此他注册一个接口指针类型的空指针，用reflect.Type.Elem()方法就可以获取到指针的内部类型，即接口类型，并以接口类型索引注入到内部。
路由过程
HTTP处理
martini.Martini实现了http.Handler方法，实际的HTTP执行过程在代码
martini.go#L68:
func (m *Martini) ServeHTTP(res http.ResponseWriter, req *http.Request) {
m.createContext(res, req).run()
}
这里需要我们关注m.createContext，它返回*martini.context类型，代码martini.go#L87：
func (m *Martini) createContext(res http.ResponseWriter, req *http.Request) *context {
c := &context{inject.New(), m.handlers, m.action, NewResponseWriter(res), 0}
c.SetParent(m)
c.MapTo(c, (*Context)(nil))
c.MapTo(c.rw, (*http.ResponseWriter)(nil))
c.Map(req)
return c
}
创建martini.context类型；然后SetParent设置寻找注入对象的时候同时从m(martini.Martini)中寻找（martini.context和martini.Martini两个独立的inject），这样就可以获取m.Map注入的数据。
这里叉出来说：从代码看出实际上注入的数据有两层，分别在martini.context和martini.Martini。*martini.context中的是当前请求可以获取的（每个请求都会m.createContext()，都是新的对象）;martini.Martini是全局的，任何请求都可以获取到。
回到上一段，c.MapTo把martini.context按martini.Context接口，将martini.ResponseWriter按http.ResponseWriter接口，把req(http.Request)注入到当前上下文。
context.run方法定义在martini.go#L163:
func (c *context) run() {
for c.index <= len(c.handlers) {
_, err := c.Invoke(c.handler())
if err != nil {
panic(err)
}
c.index += 1
if c.Written() {
return
}
}
}
它在循环c.handlers(来自m.handlers,createContext代码中)。这里想解释三个细节。
c.Invoke是inject.Invoke方法，内部就是获取 c.hanlder()返回的
martini.Handler(func)类型的传入参数reflect.Type.In()，根据参数个数和类型去内部找对应的结构，然后拼装成[]reflect.Value给函数的reflect.Value(func).Call()。
c.handler()的返回来自两个方面,c.hanlders和c.action。c.handlers来自https://www.doczj.com/doc/d73372600.html,e()添加,c.action来自r.Handle(*martini.router.Handle)(见上文martini.ClassicMartini.New中的m.Action(r.Handle))。因此，可以发现实际上handlers是有两个列表，一个是 c.handlers([]martini.handler)和r.handlers(martini.routerContext.handlers)。而且前者先执行。也就是说无论https://www.doczj.com/doc/d73372600.html,e写在哪儿，都要比router添加的func先执行。
c.Written判断请求是否已经发送。他实际上是判断martini.ResponseWriter.status 是否大于0。因此只要发送了response status，handlers过程就会停止。
路由调用
从上面可以知道，路由调用过程有两个方面：一是https://www.doczj.com/doc/d73372600.html,e()添加的handlers，二是路由添加比如m.Get("/",handlers...)中的handlers。https://www.doczj.com/doc/d73372600.html,e的handlers调用就是上文的*martini.context.run方法，不再赘述。路由中的handlers执行是在router.go#L218: func (r *route) Handle(c Context, res http.ResponseWriter) {
context := &routeContext{c, 0, r.handlers}
c.MapTo(context, (*Context)(nil))
context.run()
}
和router.go#L315:
func (r *routeContext) run() {
for r.index < len(r.handlers) {
handler := r.handlers[r.index]
vals, err := r.Invoke(handler)
if err != nil {
panic(err)
}
r.index += 1
// if the handler returned something, write it to the http response
if len(vals) > 0 {
ev := r.Get(reflect.TypeOf(ReturnHandler(nil)))
handleReturn := ev.Interface().(ReturnHandler)
handleReturn(r, vals)
}
if r.Written() {
return
}
}
}
如果你已经理解上文中说明，这个过程和martini.context.run是一样的。唯一这里要解释的是martini.ReturnHandler。它与很上文中的m.Map(defaultReturnHandler())遥相呼应。
中间件
从上文不难理解，中间件其实就是martini.Handler被https://www.doczj.com/doc/d73372600.html,e添加到m.handlers中。这里我们来说明官方的一个中间件martini.Logger()，实现代码在logger.go:
func Logger() Handler {
return func(res http.ResponseWriter, req *http.Request, c Context, log *log.Logger) {
start := time.Now()
log.Printf("Started %s %s", req.Method, req.URL.Path)
rw := res.(ResponseWriter)
c.Next()
log.Printf("Completed %v %s in %v\n", rw.Status(), http.StatusText(rw.Status()), time.Since(start))
}
}
首先看func的传入参数，http.ResponseWriter和*http.Request来自：
c := &context{inject.New(), m.handlers, m.action, NewResponseWriter(res), 0}
// ...
c.MapTo(c.rw, (*http.ResponseWriter)(nil))
c.Map(req)
Context来自：
context := &routeContext{c, 0, r.handlers}
c.MapTo(context, (*Context)(nil))
*log.Logger来自：
m := &Martini{Injector: inject.New(), action: func() {}, logger: log.New(os.Stdout, "[martini] ", 0)}
m.Map(m.logger)
然后看rw := res.(ResponseWriter)。实际上c.rw是NewReponseWriter(res)返回的martini.ResponseWriter类型，一次可以在这里直接转换（注意在外部调用，不是martini 包中，要import并写res.(martini.ResponseWriter)）。
最后是c.Next()方法，源码在martini.go#L154:
func (c *context) Next() {
c.index += 1
c.run()
}
意思就是index自增，指向下一个handler，c.run走完所有handler，然后继续中间件里的log.Printf...。
总结
martini的对外API很简单，但是内部实现其实比较复杂的。需要仔细的阅读，并且有一定
标准库的基础，才能很好的理解他代码的用意。
我这里只是按照自己的理解说明，如果有错误请在评论中指正。
memcacheQ 配置 什么是memcacheQ ? memcacheQ是一个基于memcache协议、BDB持久数据存储、高性能轻量级队列服务程序。 特点是： 1.简单高效，基于memcache协议，这意味着只要客户端支持memcache协议即可使用。 2.队列数据存储于BDB,持久保存。 3.并发性能好。 4.支持多条队列。 并发量较的web环境，特别是数据库写入操作过多的情景，使用队列可大大缓解因并发问题造成的数据库锁死问题。生产环境中使用效果非常好。 先决条件： memcacheQ依赖于libevent，libevent-devel和BDB (BerkleyDB) 1.先检查libevent, libevent-devel是否已经安装： rpm -qa|grep libevent 输出中必须包含libevent, libevent-deve, 如果缺失，使用以下命令安装： yum install libevent yum install libevent-devel 安装完毕再复查之：rpm -qa|grep libevent, 确保安装正确。 注意事项：libevent, libevent-devel优先使用yum安装源，光盘镜像中的rpm包安装，这样稳定性和兼容性可得到保证，网上流传的使用源码安装libevent的方法会有问题，因为很可能系统已经安装libevent, 再使用源码安装，必然导致冲突，造成意外问题，所以一定要使用上述命令检查系统是否已经安装相应的库。 2.安装BerkleyDB cd /usr/local/src wget http://219.239.89.57/deploy/db-5.2.28.tar.gz tar zxvf db-5.2.28.tar.gz cd db-5.2.28 cd build_unix ../dist/configure make make install 3.准备安装memcacheQ cd /usr/local/src wget http://219.239.89.57/deploy/memcacheq-0.2.0.tar.gz tar zxvf memcacheq-0.2.0.tar.gz cd memcacheq-0.2.0 修改configure文件，找到bdbdir="/usr/local/BerkeleyDB.4.7"，修改为 bdbdir="/usr/local/BerkeleyDB.5.2", 否则执行configure时会产生找不到BDB的错误。
libevent源码深度剖析 张亮 Email: sparling.liang@https://www.doczj.com/doc/d73372600.html,
回想刚开始写时，就冠以“深度剖析”的名称，也是为了给自己一些压力，以期能写好这一系列文章，对libevent源代码的各方面作详细的分析；现在看来也算是达到了最初的目的。希望能给学习和使用libevent的朋友们有所帮助。 Email：sparkling.liang@https://www.doczj.com/doc/d73372600.html, 张亮
目录 libevent源码深度剖析 (1) 目录 (3) 一序幕 (5) 1 前言 (5) 2 Libevent简介 (5) 3 学习的好处 (5) 二Reactor模式 (6) 1 Reactor的事件处理机制 (6) 2 Reactor模式的优点 (6) 3 Reactor模式框架 (6) 4 Reactor事件处理流程 (8) 5 小结 (9) 三基本使用场景和事件流程 (10) 1 前言 (10) 2 基本应用场景 (10) 3 实例代码 (11) 4 事件处理流程 (11) 5 小结 (12) 四 libevent源代码文件组织 (13) 1 前言 (13) 2 源代码组织结构 (13) 3 小结 (14) 五 libevent的核心：事件event (15) 1 libevent的核心-event (15) 2 libevent对event的管理 (16) 3 事件设置的接口函数 (17) 4 小结 (18) 六初见事件处理框架 (19) 1 事件处理框架-event_base (19) 2 创建和初始化event_base (20) 3 接口函数 (20) 4 小节 (23) 七事件主循环 (24) 1 阶段性的胜利 (24) 2 事件处理主循环 (24) 3 I/O和Timer事件的统一 (27) 4 I/O和Signal事件的统一 (27) 5 小节 (27) 八集成信号处理 (28) 1 集成策略——使用socket pair (28)
2.空间配置器 2.1具备次配置力（sub-allocation）的SGI空间配置器 SGI含有两个空间配置器类，std::allocator内存分配类符合标准，但是仅仅是对operator new和operator delete简单封装一下而已；其次是SGI特殊的内存分配器std::alloc,其中实现采用了内存池，对于分配大量小容量的对象，可以大大减少内存碎片。 SGI标准的空间配置器std::allocator 这是对应的模板内联内存分配函数。实现起来也很简单，注意这里分配的内存仅仅是一块没有使用的空间而已，在上面并没有构造对象，后面讲解如何在上面构造对象。 模板内联内存释放函数，直接调用全局的operator delete释放对应的内存。
SGI特殊的空间配置器Std::alloc class Foo{…} Foo* pf = new Foo;//配置内存，然后构造对象delete pf;//将对象析构，然后释放内存 new的算是包含两个阶段：
1）调用：：operator new 配置内存 2）调用Foo::Foo()构造对象内容 Delete算式也包含两个阶段 1）调用Foo::~Foo()将对象析构 2）调用：：operator delete释放内存 为了精密分工，STL allocator将两个阶段的操作分开来，内存配置操作由alloc::allocate()负责，内存释放操作由alloc::deallocate()负责；对象构造由：：construct（）负责，对象析构由：：destroy（）负责。
2.stl_alloc.h 内存空间的分配和释放 内部使用malloc在堆中申请内存，其中制造了一个内存池，可以减少小型区块过多而造成的内存碎片问题。 SGI设计了双层级配置器，第一级配置器直接使用malloc()和free（），第二级配置器则视情况采用不同的策略：当配置区块超过128bytes时，采用第一级配置器，当配置区块小于128bytes时，采用第二级配置器，采用复杂的memory pool。它内存池实际上就是内部维护了16个自由链表，预先已经分配好了，当需要从内存池中取内存时候，直接从对应链表取出即可；当释放内存到内存池时候，直接将内存插入链表即可。每个链表中节点分别占用8、16、24、32、40、48、52、64、72、80、88、96、104、112、120、128字节。
Memcached 源码剖析笔记 Xguru Memcached是一个自由、源码开放、高性能、分布式 内存对象缓存系统，目的在于通过减轻数据库负载来使 动态Web应用程序提速。
目录 1.背景 (3) 2.memcached的安装 (4) 3.memcached的配置 (5) 4.memcached的使用 (6) 4.1.存储命令 (7) 4.2.读取命令 (8) 4.3.删除命令 (8) 4.4.高级命令 (9) 4.5.其他命令 (10) 5.Memcached内部工作机制 (11) 5.1.Memcached基本的数据结构 (11) 5.2.基本设计概念和处理流程 (12) 5.3.内部Hash机制 (15) 5.3.1.Hash函数及冲突解决 (15) 5.3.2.HashTable主要函数 (15) 5.4.slab内存处理机制 (17) 5.4.1.slab主要函数 (17) 5.4.2.slab机制中所采用的LRU算法 (19) 5.5.控制item各种函数 (20) 5.6.守护进程机制 (22) 5.7.Socket处理机制 (23) 1
5.7.1.Unix域协议 (23) 5.7.2.TCP/UDP协议 (24) 5.8.多线程处理机制 (25) 5.9.事件处理机制 (25) 6.未完善之处 (27) 7.参考文献 (28) 2
1.背景 Memcached 是一个高性能的分布式内存对象缓存系统，用于动态Web应用以减轻数据库负载。它通过在内存中缓存数据和对象来减少读取数据库的次数，从而提供动态、数据库驱动网站的速度。Memcached基于一个存储键/值对的hashmap。 Memcached是一个自由、源码开放、高性能、分布式内存对象缓存系统，目的在于通过减轻数据库负载来使动态Web应用程序提速。 Memcached是一个在内存中对任意的数据（比如字符串，对象等）所使用的key-value 存储。数据可以来自数据库调用，API调用，或者页面渲染的结果。 Memcached设计理念就是小而强大，它简单的设计促进了快速部署、易于开发，并解决面对大规模的数据缓存的许多难题。所开放的API能用于大部分流行的程序语言 3
8 配接器 8.1 配接器之概观与分类 1、设计模式中对配接器的定义如下:将一个class的接口转换为另一个class的接口，使原本因接口不兼容而不能合作的classes可以一起运作。 2、容器配接器（应用于容器） stack和queue是两个容器配接器，底层默认由deque构成。stack封住了所有的deque对外接口，只开放符合stack原则的几个函数；queue封住了所有的deque 对外接口，只开放符合queue原则的几个函数。 3、迭代器配接器（应用于迭代器） 3.1 insert iterators 可以把一般迭代器的复制操作转变为插入操作。 insert iterators包括back_insert_iterator（专门负责尾端插入），front_insert_iterator （专门负责头端插入）和insert_iterator（可以负责任何位置执行插入）。主要观念是，每个insert iterators内部都维护有一个容器；容器有自己的迭代器，当客户端对insert iterators做赋值操作时，就在insert iterators中转为对该容器的迭代器做插入操作，其他的迭代器功能则被关闭。 3.2 reverse iterators reverse iterators将迭代器的行进方向逆转，使原本应该前进的operator++变成了后退操作，原本后退的operator—操作变成了前进操作。当迭代器被逆转，虽然实体位置不变，但逻辑位置必须改变，主要是为了配合迭代器区间的“前闭后开“习惯。
3.3 IOStream iterators IOStream iterators可以将迭代器绑定到某个iostream对象身上。绑定一个istream object（例如：std::cin），称为istream_iterator,拥有输入功能。绑定到ostream object （例如：std::cout），称为ostream_iteratpr，拥有输出功能。内部维护一个istream member，客户端对这个迭代器做的operator++操作，会被导引调用内部所含的那个istream member的输入操作。绑定一个ostream object，就是在ostream iterator内部维护一个ostream member，客户端对这个迭代器做的operator=操作，会被导引调用内部所含的那个ostream member的输出操作。 3.4 运用实例
基于Libevent的HTTP Server 简单的Http Server 使用Libevent内置的http相关接口，可以很容易的构建一个Http Server，一个简单的Http Server如下： #include
如何成为一个程序员:想成为一个游戏程序员需要有以下资料 疯狂代码 https://www.doczj.com/doc/d73372600.html,/ ?: http:/https://www.doczj.com/doc/d73372600.html,/GameDevelopment/Article36086.html 、书籍: 算法和数据结构: 数据结构(C语言版)——严蔚敏、吴伟民 清华出版社 我觉得其配套习题集甚至比原书更有价值每个较难题都值得做下 Introduction to Algorithms第 2版 中文名算法导论 有关算法标准学习教材和工程参考手册在去年CSDN网站WebSite上其翻译版竟然评为年度 2十大技术畅销书同时员杂志上开设了“算法擂台”栏目这些溯源固本举动不由得使人对中国现今浮躁不堪所谓“IT”业又产生了线希望这本厚厚书幸亏打折我才买得起虽然厚达千页但其英文通俗晓畅内容深入浅出可见经典的作往往比般水准书还耐读还能找到MIT视频教程第节课那个老教授嘻皮笑脸后面就是长发助教上课了 C语言名题精选百则 窍门技巧篇——冼镜光 机械工业出版社 作者花费年时间搜集了各种常见C段极具窍门技巧性编程法其内容都是大有来头而且给出了详细参考资料如个普通Fibonacci数就给出了非递归解、快速算法、扩充算法等步步深入直至几无油水可榨对于视速度如生命连个普通浮点数转化为整数都另辟蹊径以减少CPU cycle游戏员怎可不看？ 计算机算法基础(第 2版)—— 佘祥宣等 华中科大出版社 我看到几个学校研究生拿它作教材(研究生才开算法太开玩笑了吧)这本书薄是薄了点用作者话来说倒也“精辟
”其实此书是Fundamentals of Computer Algorithms缩写版不过原书出版太久了反正我是没找到 The Art of Computer ProgrammingVolume 1-3 作者Donald E. Knuth是我心目中和冯.诺依曼、Dijkstra、Shannon并列 4位大师这本书作者从读大学本科时开始写直写到博士时十年磨剑足见其下足了功夫可作为计算机技术核心——算法和数据结构终极参考手册创新处也颇多譬如常见Shell排序他在书中提出可用(3i-1)/2间隔这使其稍快于O(n1. 5)当然这套书描述高度数学化为此恐怕般人(我？)最好还得先看本数学预备书Concrete Mathematics(直译为混凝土数学？^－^)再说可惜是这套书才出到第 3卷并没有覆盖全部常见算法内容不过好在对于游戏员来说越常见算法用得越多这也不算是什么要命损失 STL源码剖析—— 侯捷 华中科大出版社 侯捷不用介绍了华人技术作家中旗舰说其有世界级水准也不为过这本书我以为是C和数据结构葵花宝典(欲练此功必先自宫)也就是说不下几层地狱很难看懂它要求预备知识太多了如STL、数据结构、泛型编程、内存管理都要很扎实(为此是不是还要看看有内存管理设计模式的称Small Memory Software这本书呢？)但是旦看懂真会是所向披靡 Data Structures for Game Programmers 每个数据结构例程都是个小游戏还用SDL库实现了个算法演示系统虽然内容失的于浅但起码让人了解了数据结构在游戏中作用 其实游戏并不比其它特殊甚至要求基本功更加扎实所以花时间做些看似和实际应用不甚相干习题对今后工作是大有裨益而且有些应用很广算法如常被人津津乐道[Page]A*算法及其变种牵涉到图检索周游和分枝-限界法恐怕还得读些艰深论文才能充分明白运用如Donald E. KnuthAn analysis of alpha-beta cutoffs其实还有不少此类
深度剖析KMP,让你认识真正的Next KMP算法，想必大家都不陌生，它是求串匹配问题的一个经典算法（当然如果你要理解成放电影的KMP，请退出本页面直接登录各大电影网站，谢谢），我想很多人对它的理解仅限于此，知道KMP能经过预处理然后实现O(N*M）的效率，比brute force（暴力算法）更优秀等等，其实KMP算法中的Next函数，功能十分强大，其能力绝对不仅仅限于模式串匹配，它并不是KMP的附属品,其实它还有更多不为人知的神秘功能^_^ 先来看一个Next函数的典型应用，也就是模式串匹配，这个相信大家都很熟悉了: POJ 3461 Oulipo——很典型的模式串匹配问题，求模式串在目标串中出现的次数。 #include 深入分析STL标准模板——vector ——计算机学院--马晶义 摘要：通过阅读c++的STL标准模板库中vector的源代码，分析STL 中的内部成员、接口、内存管理、封装等方面。Vector 是一种顺序性的容器，按照严格线性存储各种对象。它其实就是一种动态的数组，正如数组，vector有他们存储在存储单元相邻元素,这就意味着他们的元素可以被存取不只有使用迭代器还定期使用指针抵消元素。但是不像普通的数组,存储在向量自动处理,允许它的扩展和简约的需要。 关键字：STL、Vcector、内部成员函数、接口函数、封装 一、vector的声明及内部常用函数 1.vector的声明 vector c.pop_back(); 删除容器最后位置处的元素 c.at(index); 返回指定index位置处的元素 c.begin(); 返回指向容器最开始位置数据的指针 c.end(); 返回指向容器最后一个数据单元的指针+1 c.front(); 返回容器最开始单元数据的引用 c.back(); 返回容器最后一个数据的引用 c.max_size(); 返回容器的最大容量 c.size(); 返回当前容器中实际存放元素的个数 c.capacity(); 同c.size() c.resize(); 重新设置vector的容量 c.reserve(); 同c.resize() c.erase(p); 删除指针p指向位置的数据，返回下指向下一个数据位置的指针（迭代器） c.erase(begin,end) 删除begin,end区间的数据，返回指向下一个数 据位置的指针（迭代器） c.clear(); 清除所有数据 c.rbegin(); 将vector反转后的开始指针返回(其实就是原来的end-1) c.rend(); 将vector反转后的结束指针返回(其实就是原来的begin-1) c.empty(); 判断容器是否为空，若为空返回true，否则返回false C++程序设计之四书五经（下篇） 荣耀/文我在上篇中“盘点”了TCPL和D&E以及入门教程、高效和健壮编程、模板和泛型编程等方面共十几本C++好书。冬去春来，让我们继续C++书籍精彩之旅。 标准库 当我还在研究院工作时，与同院另外两家研究所合作开发过一个大型水利枢纽调度集成项目。我们三家软件系统之间都要相互通信。在调试通讯模块时，细心的客户（一名好学的系统管理员）发现对于同一通信规约的解释代码，我的不超过30行，而对方的则超过了150行且很难看懂。这位系统管理员很纳闷，我说大家编程风格和习惯不一样，我使用了标准库，而他使用了传统C编程风格以及他所习惯的另外一些技术。 别误会！我绝无贬低这位合作伙伴的意思。事实上，我对那些真正有着深厚的C编程功力的程序员常常怀有钦佩之心。毕竟，C++能有今天的成功在很大程度上缘于它深深地植根于C。作为一名C++程序员，倘若不熟悉C++中的C，我往往会认为他的基本功是不扎实的，他的技术底气是不足的。 不过话又说回来，C++是一种多范型（paradigm）编程语言，具体采用哪种编程风格，专业程序员应该知道视具体情况而定。作为一名经常需要在现场做即兴开发的项目负责人，为了短平快地解决当务之急，我习惯尽量采用现有的库（和组件）。效率（以及强健性）久经验证的C++标准库已经摆在那儿了，何乐而不用呢？ Nicolai M. Josuttis,《The C++ Standard Library: A Tutorial and Reference》原文版、中文版：《C++标准程序库：自修教程与参考手册》 这是一本百科全书式的C++标准库著作，是一本需要一再查阅的参考大全。它在完备性、细致性以及精确性方面都是无与伦比的。本书详细介绍了每一标准库组件的规格和用法，内 libevent源码深度剖析一 ——序幕 张亮 1 前言 Libevent是一个轻量级的开源高性能网络库，使用者众多，研究者更甚，相关文章也不少。写这一系列文章的用意在于，一则分享心得；二则对libevent代码和设计思想做系统的、更深层次的分析，写出来，也可供后来者参考。 附带一句：Libevent是用c语言编写的（MS大牛们都偏爱c语言哪），而且几乎是无处不函数指针，学习其源代码也需要相当的c语言基础。 2 Libevent简介 上来当然要先夸奖啦，Libevent 有几个显著的亮点： 事件驱动（event-driven），高性能; 轻量级，专注于网络，不如ACE那么臃肿庞大； 源代码相当精炼、易读； 跨平台，支持Windows、Linux、*BSD和Mac Os； 支持多种I/O多路复用技术，epoll、poll、dev/poll、select和kqueue等； 支持I/O，定时器和信号等事件； 注册事件优先级； Libevent已经被广泛的应用，作为底层的网络库；比如memcached、Vomit、Ny lon、Netchat等等。 Libevent当前的最新稳定版是1.4.13；这也是本文参照的版本。 3 学习的好处 学习libevent有助于提升程序设计功力，除了网络程序设计方面外，Libevent的代码里有很多有用的设计技巧和基础数据结构，比如信息隐藏、函数指针、c语言的多态支持、链表和堆等等，都有助于提升自身的程序功力。 程序设计不止要了解框架，很多细节之处恰恰也是事关整个系统成败的关键。只对libevent 本身的框架大概了解，那或许仅仅是一知半解，不深入代码分析，就难以了解其设计的精巧之处，也就难以为自己所用。 事实上Libevent本身就是一个典型的Reactor模型，理解Reactor模式是理解libevent 的基石；因此下一节将介绍典型的事件驱动设计模式——Reactor模式。 libevent源码深度剖析二 ——Reactor模式 Disk-Based Container Objects Tom Nelson A container that's very large, or that must persist between programs, really needs to live on disk. C++ container class libraries have become a staple item in many programmers' toolkits. The introduction of templates has made these libraries notably robust and simple to use. However, their transient (memory-based) nature still imposes certain restrictions on their use. First, they cannot grow to arbitrary size if needed; second, they lack persistence, hence they disappear when the program shuts down. The second restriction is usually easier to cure than the first. To make a transient container "hold water," the container class could use a persistent streams facility to write the essential data members of each contained object to a disk file before shutting down. The next program invocation need only initialize another transient container, then sequentially extract each object from the persistent store and add it to the new container. In some cases, though, you can't guarantee that your run-time storage requirements won't overflow available memory. A priority or scheduling queue, for example, might need to process and store an unanticipated quantity of incoming data. You could write some objects to disk to free space in the container. However, to effectively process additions and deletions, a transient container normally requires the presence of all contained objects in memory at one time. When you write contained objects to a file, the logical structure of the container (pointers, state info, etc.) is lost. One solution consists of moving the entire container out to a disk file so that it becomes, in effect, a database, or "Containerized Database." This article will demonstrate techniques for building and using such disk-based container classes. They allow you to employ container objects of virtually any size regardless of memory constraints, which you can maintain indefinitely. Even when persistence is not necessary, the technique still permits arbitrary growth of the containers by storing overflow in temporary files, restricted only by available disk space. I will concentrate here on developing disk-based implementations for three fundamental structure types (lists, vectors, and binary trees). I discuss a few abstract types derived from them, and provide an example of a disk-based binary tree sort. Design and Performance Considerations Httpsqs是一个消息队列服务器，他调用的接口是tokyocabinet，tokyocabinet是一个数据库的持久化库，保存 httpsqs_handler的处理流程 图 2 上面的处理流程只列出了put,get 2种命令，其实还有其他的命令，处理很put,get差不多 上面2个图，就是httpsqs的大概的流程。 Tokyocabinet 是一个 5 关联式容器 标准的STL关联式容器分为set（集合）和map（映射表）两大类，以及这两大类的衍生体multiset（多键集合）和multimap（多键映射表），这些容器的底层机制均以RB-tree（红黑树）完成，红黑树也是一个独立的容器，但并不开放给外界使用。 SGI STL还提供了一个不在标准规格之列的关联式容器：hash table（散列表），以及hash table为底层机制的hash_set（散列集合），hash_map（散列映射表），hash_multiset（散列多键集合），hash_multimap（散列多键映射表）所谓关联式容器：每笔数据（每个元素）都一个键值（key）和一个实值（value）。当元素插入到关联式容器时，容器内部结构（可能是RB-tree ，也可能是hash table）便依照其键值大小，以某种特定规则将这个元素置于适当位置。关联式容器没有所谓的头尾。 关联式容器的内部结构是一个平衡二叉树（balanced binary tree），以便获得良好的搜寻效率，平衡二叉树包括AVL-tree,RB-tree,AA-tree。 5.1 树导览 1）二叉搜索树BST（binary search tree） 二叉搜索树的放置规则是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树的每一个节点的键值。因此从根节点一直往左走，直至无左路可走，即得最小元素；从根节点一直往右走，直至无右可走，即得最大元素。 2）平衡二叉搜索树（balanced binary search tree） 平衡：没有任何一个节点过深（深度过大） 3）AVL-tree(Adelson-Velskii-Landis tree) AVL tree是一个“加上了额外平衡条件”的二叉搜索树。其平衡条件的建立是为了确保整棵树的深度为O(logN)，AVL tree要求任何节点的左右子树的高度相差做多为1，这是一个较弱的条件，但仍能保证“对数深度”平衡状态。 3.迭代器（iterators）概念与traits编程技法 STL的中心思想在于：将数据容器（containers）和算法（algorithms）分开，彼此独立设计，最后在以一贴胶着剂将它们撮合在一起。 3.1 迭代器设计思维——STL关键所在 STL中心思想：将数据容器和算法分开，彼此独立设计，最后再以已贴粘着剂将他们撮合在一起 3.2 迭代器是一种smart pointer 迭代器是一种行为类似指针的对象，指针的最常见最重要的是内容提领（取出指标所指物体的内容dereference）和成员访问（member access）。所以，迭代器最重要的编程工作是对operator *和operator->进行重载（overloading）工作。 auto_ptr 是一个用来包装原生指针的对象，内存漏洞问题可以借此解决。用法如下，和原生指针一模一样。 3.3 迭代器相应类别（associated types） 最常用的相应类别有五种 value type：迭代器所指对象的型别。 difference type ：表示两个迭代器之间的距离，可用于表示容器的最大容量。pointer type：代表迭代器所指对象的指针类型。简言之，operator->()的返回类型。reference type：代表迭代器所指对象的引用类型。简言之，operator*()的返回类型。分为两种，不允许改变“所指对象之内容”者称为constant iterators，例如const int* pic，允许改变“所指对象之内容”者称为mutable iterators，例如int* pi。*pic/*pi的型别constant T&/T&就是reference type。 iterator category type：提出5种迭代器的类型标识。 如何学习数据结构 1、数据结构学习一定要自己独立完成代码实现，虽然有时候你理 解内容了，但是实现上面还是会愈要很多困难的，解决这些困难会帮助你提高程序设计的能力的。 2、数据结构是计算机专业最重要最基础的一门课，对于有过编程 经验的人，结合自己的编程体会，去领悟它的思想；对于初学者，捡一种自己最熟悉的语言去分析它，总之千万不要陷在语言的细节上，要高屋建瓴的去领会数据结构的思想。而且随着编程经历的丰富对它的体会越深入，最初接触是对一些思想可能只是生硬的记忆，随着学习的深入逐渐领悟了很多。对于实在弄不懂的东东，就先记住！！！ 3、将各种数据结构算法烂熟于胸，这是一个优秀程序员的必须具 备的基本素质，是后来进步的基石。书上的例子自己看看，然后不看书自己想想做成代码，在以后使用的时候看看能不能用这些数据结构来解决问题。 4、自己试着把书上的数据结构尽量写成可复用的独立模板（模 块），以后用着方便，学得也深刻，以后复习不用看书了，反复温习即便自己的代码就行了，说实话，找工作面试的时候数据结构几乎是必问的！ 5、我觉的学数据结构，应该从算法入手，不能急，我现在还在搞 数据结构呀！不过现在觉的不那么难了呀！因为主要是算法，一点一点理清，会有柳暗花明的时候的。 6、数据结构要反复看书，量变引起质变，可能一开始看不太懂， 单当看多了的时候，你会茅塞顿开！ 7、我觉得数据结构要的是思想，学的也是思想，但你至少要熟练 一门语言，要么怎能检验你的思想是否正确，强烈推荐《STL 源码剖析》！！！结合STL中的源码去分析,STL是我看到的最全 的以数据结构为宗旨的一种库,还建议你去下一个STLPORT,之 中的源码比VC提供的好些,很全,基本上能够用到的数据结构 都涉及到了,并且在学这个库的过程当中还可以学习一些设计 模式,还可以学习VC中的范型运算思想，等等，开始行动吧！！！ 8、怎样学习数据结构，最好方法是一起讨论。 9、1）如果你没有学过C语言，或者C语言学的不好的时候把数据 结构当成一本数学书来学，它所讲述的都是一些简单的图论。 在你的大脑中的主线不能丢失：线性结构，树结构和图结构。 当你不再考虑复杂的程序设计时，仅仅研究个个离散点之间的 关系，似乎数据结构也就不会那么难了。 2）学习好了抽象的 离散点关系后，再巩固一下你的C语言水平，书中描述的都是 类C。因此你只要学习简单的C定义、判断、循环语句就基本 能看的懂课本中所有程序了。3）以上都完成后，从数据结构的 线性表开始。线性表中顺序表，似乎是为你学习C语言设计的，学好线性表的链表是你起步的关键。后面的树结构，图结构， 排序，查找都少不了链式结构，往往这个也是最难的。 4）看 程序的时候一定要自己在纸上画画，最好先学会画程序的流程深入分析STL标准模板·vector
out......C语言
libevent
Disk-Based Container Objects
httpsqs源码分析
STL源码剖析总结_第五章关联式容器
STL源码剖析总结_第三章-迭代器与traits编程技法
如何学习数据结构
相关主题
文本预览