2010年一月月 发布的文章

iterator的C实现

这几天一直处于编码状态,也找回了一些对代码的良好感觉。

昨天晚上闲暇时翻阅“Head First设计模式”,当翻到迭代器模式时,突然有了想法:实现一个iterator。这几天编码时恰好也写了一个简单的带有遍历功能的小数据结构,不妨用iterator改造一下这个数据结构的遍历接口,看是否能成行。

迭代器模式较为简单,网上的文章也多得很,这里就不再贽述了,直接看实现思路和代码吧。

在迭代器模式中,有几个角色不得不说,一就是iterator本身,还有一个就是所谓的“容器类”,容器类三个字显得概念很大,这里不用之。我们换一种轻松的说法,就是带有遍历功能的一类数据结构吧,这里记为类型T。类型T千变万化,iterator则以不变应万变,提供一种在无需知道T内部实现行为前提下的对T实例内各元素的有序遍历的接口。

这样一来iterator的应用场景大致就应该是这样的:

T     *t;
T_item_t *ti;

// …
iterator *itor = T_iterator(t);   
       
for ( ; has_next(itor); ) {
        ti = (T_item_t*)get_next(itor);
        // …
}

iterator_free(itor);

这里我们使用了四个函数has_next, get_next、iterator_free和T_iterator。其中has_next、get_next和iterator_free是iterator提供的函数接口,T_iterator则是需要每个支持iterator的数据结构去实现的接口。

以下是iterator.h的主要代码片段:

/* iterator.h */

#ifndef _ITERATOR_H_
#define _ITERATOR_H_

enum {
        FALSE = 0,
        TRUE  = 1
};
typedef int bool; /* TRUE or FALSE */

typedef struct iterator iterator;

typedef bool (*HAS_NEXT_HOOK_FUNC)(void *collection_instance, void *collection_inner_itor);
typedef void* (*GET_NEXT_HOOK_FUNC)(void *collection_instance, void *collection_inner_itor);

/* 提供给T类型实现T_interator时使用 */
iterator*       iterator_new(void *collection_instance,
                             void *collection_inner_itor,
                             HAS_NEXT_HOOK_FUNC h,
                             GET_NEXT_HOOK_FUNC g);

bool            has_next(iterator *itor);
void*           get_next(iterator *itor);
void            iterator_free(iterator *itor);

#endif /* _ITERATOR_H_ */

iterator_new接口主要供类型T实现T_iterator接口时使用,目的是对类型T屏蔽iterator的内部结构实现;collection_instance指向T的实例;collection_inner_itor则是类型T内部实现的一个保存iterator状态的变量,每个类型T都应该有这样一个内部数据;两个callback函数则分别由类型T内部实现,在T_iterator实现中调用iterator_new时传入。iterator对T有一定的侵入性,这在C语言中似乎是不可避免的,即使在Java中支持iterator接口的类也需要提供一个creatIterator的public接口,另外实现iterator接口的iterator类也需要提供具体的get_next和has_next实现。

以下则是iterator.c的代码,没有太多值得多说的地方,相信大家都可以看懂^_^:

/* iterator.c */
struct iterator {
        void                    *collection_instance;
        void                    *collection_inner_itor;
        HAS_NEXT_HOOK_FUNC      _has_next;
        GET_NEXT_HOOK_FUNC      _get_next;
};

iterator*       iterator_new( void *collection_instance,
                void *collection_inner_itor,
                HAS_NEXT_HOOK_FUNC h,
                GET_NEXT_HOOK_FUNC g) {
    iterator        *itor   = NULL;

    itor    = calloc(1, sizeof(*itor));
    if (!itor) return NULL;

    itor->collection_instance       = collection_instance;
    itor->collection_inner_itor     = collection_inner_itor;
    itor->_has_next = h;
    itor->_get_next = g;

    return itor;
}

void    iterator_free(iterator *itor) {
        if (itor) {
                if (itor->collection_inner_itor) free(itor->collection_inner_itor);
                free(itor);
        }
}

bool    has_next(iterator *itor) {
        return itor->_has_next(itor->collection_instance, itor->collection_inner_itor);
}

void*   get_next(iterator *itor) {
        return itor->_get_next(itor->collection_instance, itor->collection_inner_itor);
}

有了iterator,我们再举一个支持iterator遍历的list的例子,这里就不列出全部代码了,仅将关键的接口实现放出:

/* x_list.c */
struct x_list_inner_itor {
        x_list_item_t *item;
};

static bool x_list_has_next(void *collection_instance, void *collection_inner_itor) {
        x_list_t *list = (x_list_t*) collection_instance;
        struct x_list_inner_itor *p = (struct x_list_inner_itor *)collection_inner_itor;
        x_list_item_t *item = p->item;

        return (X_LIST_NEXT(item) != X_LIST_DUMMY_HEAD(list));
}

static void* list_get_next(void *collection_instance, void *collection_inner_itor) {
        struct x_list_inner_itor *p = (struct x_list_inner_itor *)collection_inner_itor;
        x_list_item_t *item = p->item;

        p->item = X_LIST_NEXT(item);

        return p->item;
}

iterator* x_list_iterator(x_list_t *list) {
        struct x_list_inner_itor *p = NULL;
        p = calloc(sizeof(*p), 1);
        if (!p) return NULL;

        p->item = X_LIST_DUMMY_HEAD(list);

        return iterator_new(list,
                (void*)p,
                x_list_has_next,
                x_list_get_next);              
}

以上只是提供了iterator的C实现的一种思路,大家见仁见智吧。

人在福州,忙!

掐指算来,这次在福州出差已有近三周多了,这期间经历了几次产品升级和测试,大家都变得疲惫不堪,最突出的表现就是精神头不再像刚来是那么足了,饭量开始减少,食欲下降,睡眠质量也下降了。

从这周开始这边的Team基本分成了两拨儿人,一拨儿人在客户现场驻守,协助解决产品运行中的问题,另一拨人则跟着我“宅”在酒店里进行新版本的开发和测试。说起来,大家在一个大屋子里办公还是很其乐融融的。由于一个新模块的开发,我也参与了紧张的编码测试工作,几天时间写了近2K行代码,由于长时间聚精会神的坐在屏幕前编码,颈椎都有些撑不住了,后颈左侧时常疼痛。记忆中我似乎也好久没有这么长时间连续编码了。

长时间的连续工作让大家都有些疲劳,原计划昨天晚上23点场集体看3D版“阿凡达”轻松一下的,票都托当地的同事排队搞到了,但是因昨天下午的一个突发事故,又泡汤了,不知道年前是否还能看得到。

在这边最让大家感觉头痛的还是吃饭问题,我们住在闽江大桥南。这个地方能吃的地方比较少。常去的地方就是酒店附近的阿瓦山寨了,我是喜欢吃湘菜的,尤为喜欢农家小炒肉^_^。不过每天都去吃,想起来都倒胃口了,特别是众口难调,人多了,意见很容易不一致。发掘能吃的地儿就成了我们工作之余的首要任务了。刚来的时候对酒店的早晨还是很期待的,现在早餐都变得难以下咽了。

当吃饭变得鸡肋,剩下的就只有工作了。

逛台江步行街

算起来这已经是我第三次到榕城了,不过这次待在这儿的时间可能会更长。

周三到这儿后就一直在客户现场做保障工作,每天工作10多个小时,大家都挺累的。周六下午大家休息差不多后就商量着出去转转。我们住在闽江大桥南侧的国谊酒店,江北不远处就是台江步行街-福州一条商业街,我们就将目的地定在了那。

走出酒店正门已是下午4点半,向北登上闽江大桥,边走边欣赏闽江的景致。北方人对南方的大江大河还是蛮有兴致的,每当有大船从桥下呼啸驶过时,我们都驻足观看,颇有一丝兴奋,这种水运在北方关外可是难得一见的。闽江大桥不长,估计不足千米,10分钟左右就到达了江对面。下桥后向西走就是台江步行街方向。

台江步行街非“名符其实”的步行街,与北京王府井、成都春熙路、沈阳的中街/太原街、昆明老街这些步行街都有不同,台江步行街中间是一条宽阔大马路,机动车自由通行,两侧是林立的商场和店铺,行人都在两侧步行^_^。从地图上来看,似乎西至五一南路,东至六一中路都是台江步行街范畴。一路逛去竟发现没什么值得我们驻足的。想找个解决晚饭的地儿也很难。麦当劳、肯德基我们是不想去的,找个有当地特色一点的饭馆才是我们的目的。终于在一个路口发现一家拌面扁肉店,正值饭点,“扁肉”二字让我们都产生了好奇,我们就走了进去。经观察后才知原来扁肉就是北方的馄饨(成都那边叫抄手,还有些地方叫云吞)。点了一碗拌面,味道还不错,似乎是麻酱拌的,但却不那么腻口,咸淡儿适中。

出了小吃店,大家也不知道去哪里是好,想起之前来的路上有看到“榕城老街”的一个牌楼,想必那里一定汇集了不少当地有关特色的产品。在前去的路上,我们穿过一片比较老旧的民宅,那些宅子有几层楼高,但又不像是我们常见的楼房,我似乎没看到单元门,也不知道那里是什么个结构样式。很多老人刚吃完晚饭在外面坐着闲聊,可以很清楚的看到他们背后屋子里的情形,桌子、椅子及其他家具摆设都看得到,都很简朴。猜测也许这就是最具福州当地特色的生活了。

出了那片生活区,不远处就看到了“榕城老街”的牌楼,以为那里会卖一些福州当地的特色产品,结果走进去一瞧才发现这个夜幕下的“榕城古街”似乎就是北方的夜市一条街。两旁烤串烤鱿鱼一应俱全,廉价服装满眼都是。除了街旁的鱼丸、肉燕的招牌让人还能想起这是在福州,失望之情绪油然而生。不过既来之,则安之。我还是吃了一碗鱼丸,味道还可,未吃过最正宗的福州鱼丸(好吃的老店似乎都集中在鼓楼区了),所以也无从比对,三个大鱼丸入肚后就觉得很饱了。

说句实在话,福州这个地方是吃的不如长沙成都;玩的不如昆明,确是缺少些吸引力。还是回酒店“宅”着吧




这里是Tony Bai的个人Blog,欢迎访问、订阅和留言!订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:


如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:


以太币:


如果您喜欢通过微信App浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:



本站Powered by Digital Ocean VPS。

选择Digital Ocean VPS主机,即可获得10美元现金充值,可免费使用两个月哟!

著名主机提供商Linode 10$优惠码:linode10,在这里注册即可免费获得。

阿里云推荐码:1WFZ0V立享9折!

View Tony Bai's profile on LinkedIn


文章

评论

  • 正在加载...

分类

标签

归档











更多