软件设计本质论(Essential Design) —从链表设计说起

软件设计本质论(Essential Design) —从链表设计说起

转载时请注明出处：http://blog.csdn.net/absurd/

大师说，软件设计不过是在适当的时候做出适当的决策罢了。对此我深以为然，好的设计就是做出了正确决策。然而，在多种互相竞争的因素下，要好做出正确的决策可不是件容易的事！本文以一个双向链表的设计为例，阐述一下软件设计为什么这样困难。

双向链表无疑是最简单的数据结构之一。即使没有系统的学习过《数据结构》的程序员，可能不知道AVL或者红黑(RB)树，但决不会不知道双向链表。他们会说双向链表是下面这样的数据结构:

Struct _DLIST

{

struct _DLIST* prev;

struct _DLIST* next;

TYPE value;

};

如果用形象一点的图形来表示，可以表示为：

<shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"></path><lock v:ext="edit" aspectratio="t"></lock></shapetype><shape id="_x0000_i1025" style="WIDTH: 414.75pt; HEIGHT: 153.75pt" type="#_x0000_t75" o:ole=""><imagedata src="file:///C:/DOCUME~1/q/LOCALS~1/Temp/msoclip1/01/clip_image001.png" o:title=""></imagedata></shape>

再辅以文字说明：像链子一样一环套一环，除第一个结点外的所有链表结点都有一个指向前一个结点的指针，除最后一个结点外的所有链表结点有一个指向后一个结点的指针，所有链表结点还有一个用于保存数据的域。

看来双向链表很简单，似乎没有什么好说的，那么本文是不是应该到此结束呢？当然不是，尽管在真正做软件设计时，双向链表是一个基本组件，所以很少有人去考虑它。但是如果要实现一套容器/算法的基本程序库，对双向链表的考虑就要纳入设计范畴了，这正是本文要说的。

思想与语言无关，而设计是与语言相关的。在《说说动态语言》中曾说“不少设计模式，在动态语言里根本就是多此一举，一切来得直截了当，根本不用如此拐弯抹角。”。我想并非是这些设计的思想在动态语言中就没有了，相反可能这些思想太重要了，以至于在语言层面已经有了支持，程序员不需要付出任何努力就可以享受这些思想的好处，所以说思想是与语言无关的。同样，如果语言对这种思想有了支持，程序员在设计时就不必考虑了，在使用不同的语言，在设计时考虑的内容有所不同，所以说设计是与语言相关的。

在本系列的序言中，我曾经说过，我们提到的方法同样适用于所有语言，但我们是基于C语言来讲解的。双向链表库设计中，有的决策正是与语言有关的，下面我们来看看用C实现双向链表遇到的问题：

1. 专用还是通用。我们面临的第一个决策可能是：设计一个专用链表还是通用链表？从现有的代码来，两者都有大量的应用。按存在即合理的原则来看，它们都是合理的。专用还是通用，这是一个两难的选择，在做出选择之前弄清它们各自的特点是有必要的。特点也就决定了它们的适用条件，这可以帮助我们做出决策。

专用链表至少具有以下优点：

类型安全：既然是专用的，前面所说节点数据的TYPE是特定的，即类型是确定的。编译器可以进行类型检查，所以专用链表是类型安全的。

性能更高。专用链表往往是给实现者自己用的，无需要对外提供干净的接口，常常把对链表的操作和对链表中数据的操作揉合在一起，省去一些函数的调用，在性能上可能会有更好的表现。

实现简单。由于是给自己用的，可以只是实现暂时用得着的函数，其它函数完全不用理会。给自己用，很多情况都在控制范围内，一些边界条件没有必要考虑，实现进一步简化。

通用链表至少具有以下优点：

代码重用。既然是通用的，也就是说一次编写到处使用，这有效的避免了代码重复。同时由于使用的地方多，测试更加严谨，代码会越来越稳定。这正是设计通用链表最重要的原因。

便于测试。通用链表要求接口函数设计得比较合理，也比较全面。可以基于契约式设计，对它进行全面测试。另外，把对链表的操作和对链表中数据的操作分开了，对链表测试更加容易。

事实上，专用链表和通用链表各自的优点正是对方的缺点，这里对它们的缺点不再多说。至于如何选择，您老自己做主，只有你自己才知道你想要什么。

2. 存值还是存指针。双向链表归根结底只是一个容器，我们的目的是用它存放我们数据。那么，我们应该在里面存放指向数据的指针，还是存放数据本身呢？为了做出这个决定，我们先研究一下两种方式各自的特点：

存放指向数据的指针的特点：

性能更高。在链表中获取、插入或删除数据，不需要拷贝数据本身，速度会更快。

更容易造成内存碎片。因为存放的是指针，数据和链表结点在两块不同的内存上，要分两次分配。链表本身就容易造成内存碎片了，若存放数据指针让内存分配次数加倍，这会加剧内存碎片倾向。

数据的生命周期难以管理。要保证数据的生命周期大于等于链表的生命期，否则会造成野指针问题。数据由链表释放还是由调用者释放呢？通常用链表释放比较简单一些，这需要调用者提供一个释放函数。也可以由链表提供一个遍历函数，由调用者遍历所有结点，在遍历时释放它们。

存放数据本身的特点：

效率较低。因为涉及到数据的拷贝，所以效率较低。

数据拷贝复杂。如果数据是基本数据类型或者普通结构，问题不大，但如果结构中包含了指其数据的指针，怎么办？这时数据要提供深拷贝函数。

同样，至于如何选择，要看情况和你当时的心情。

3. 要封装还是要性能。

封装的目的是想把变化隔离开来，也就是说如果链表的实现变化了，不会影响链表的使用者。链表的实现比较简单，你可能会认为它不会有什么变化。这可很难说，比如，现在多核CPU风行，大家都在打多线程的主意，假设你想把链表改为线程安全的，那麻烦就来了。

要达到线程安全的目的，要对所有对链表的操作进行同步处理，也就是要加锁。如果你的运气比较好，调用者都通过链表函数来访问链表，加锁操作在链表函数内部实现，这对调用者没有什么影响。但是如果调用者直接访问了链表的数据成员，这种改造一定会影响调用者。

封装隔离了变化，特别是对于那些易变的实现来说，封装会带来极大价值。当然，凡事有利必有弊，封装也会带来一点点性能上的损失。在大多数情况下，这种损失微不足道，而在一些关键的地方，也可能成性能的瓶颈。

至于选择封装还是性能，要看具体情况而定。也可以采用一种折中的方法：通过宏或者inline函数去访问数据成员。

4. 是否支持遍历，支持何种遍历。

很多人认为遍历链表很简单，不就是用一个foreach函数把链表中的元素都访问一遍吗？没错，如果是只读遍历(即不增加/删除链表的结点)，那确实如此。但实际情况并非那样简单，考虑下面几种情况(为了便于说明，我们把遍历函数称为foreach，访问元素的函数称为visit)：

visit函数的上下文(context)。遍历链表的主要目的是要对链表中的元素进行操作，而对元素操作并非是孤立的，可能要依赖于某个上下文(context)。比如，要把链表中的元素写入文件，此时文件句柄就是一个上下文(context)。visit函数中如何得到这个上下文呢，这是foreach函数要考虑的。

遍历时增加/删除链表的结点。要做到这一点并不是件容易的事，通常visit拿到的只是数据本身，它对数据在链表中的位置一无所知，所以它还需要额外的信息。即使它有了需要的信息，仍然不是那么简单，foreach里面还要做特殊处理，以防止引用被删除的结点。

遍历的终止条件。多数情况下，我们可能希望遍历链表中的所有结点。而有时当我们找到了需要的结点时，我们可能希望中止遍历，避免不必要的时间浪费。这是foreach要考虑的，当然实现很简单，可以根据visit的返回值来决定继续还是中止。

由此可见，遍历并非那么简单，至于是否要实现遍历，实现到何种程度，完全看你需要而定。如果你不嫌麻烦，可以使用后面的介绍的迭代器，它使遍历的实现大大简化。

5. 谁来管理内存。

链表是最容易产生内存碎片的容器，它往往有大量的结点，每个结点都占一块内存，每个内存块的大小很小。链表的优点是插入和删除操作非常迅捷，调用者既然选择了链表，也味着调用者可能频繁的做插入和删除操作，这种操作伴随着频繁分配/释放小块内存，所以会带内存碎片问题。

要对付内存碎片，通常采用专用的内存分配算法，比如固定大小分配。这种分配算法简单，问题是应该由谁来实现呢？由链表来实现吗？如果是，那么如果在平衡二叉树或者哈希表中要用到，是不是也要自己实现一套呢？所以，显然不应该由链表使用，链表只是使用者。

当然，如果底层的内存管理算法做得非常好，你可以不必考虑这一点。

6. 算法与容器是否分开。

链表只是一个容器，它的目的是方便我们对容器里的数据元素操作。对数据元素的操作即算法，是与容器合二为一，还是独立存在呢？我们当然会选择后者，原因是容器中的元素是不确定的，操作它们的算法也是不确定的。如果这里算法与链表放在一起，每次增加或者修改算法，都要修改链表，变化没有隔离开来。

算法与链表分开了，但算法可能要调用链表的函数，才能存取或者遍历链表中的元素，也就是说算法与链表的耦合仍然很紧密。这些算法本来可能也适用于哈希表或者二叉树的，现在与链表的耦合起来了，我们不得不为其它容器各写一套。

要彻底分离算法与容器，我们希望一种不暴露容器的实现，又能对容器用元素进行操作的方法。这就是迭代器模式，迭代器并非是C++的专利，在C语言里也可以使用。这里我们介绍一下C语言实现迭代器的方法(下面代码仅作演示所用，未经验证)：

定义抽象的迭代器：

struct _iterator;

typedef struct _iterator iterator;

typedef BOOL (iterator_prev)(iterator* iter);

typedef BOOL (iterator_next)(iterator* iter);

typedef BOOL (iterator_advance)(iterator* iter, int offset);

typedef BOOL (iterator_is_valid)(iterator* iter);

typedef void* (iterator_get_data)(iterator* iter);

typedef void (iterator_destroy)(iterator* iter);

struct _iterator

{

iterator_prev prev;

iterator_next next;

iterator_advance advance;

iterator_get_data get_data;

iterator_is_valid is_valid;

iterator_destroy destroy;

char priv[1];

};

实现具体的迭代器：

typedef struct _ListIterData

{

List* list;

ListNode* current;

}ListIterData;

iterator* list_begin(List* list)

{

ListIterData* data = NULL;

iterator* iter = (iterator*)malloc(sizeof(iterator) + sizeof(ListIterData));

iter->prev = list_iter_prev;

iter->next = list_iter_next;

iter->advance = list_iter_advance;

iter->get_data = list_iter_get_data;

iter->is_valid = list_iter_is_valid;

iter->destroy = list_iter_destroy;

data = (ListIterData*)iter->priv;

data->list = list;

data->current = list->first;

return iter;

}

使用迭代器：

iterator* iter = list_begin(list);

for(; iter->is_valid(iter); iter->next(iter))

{

data = iter->get_data(iter);

...

}

iter->destroy(iter);

7. 抽象还是硬编码。

每种容器都有自己的优缺点。链表的优点是插入/删除比较快捷，因它只需要修改结点的指针，而不需要移动数据。缺点是排序不方便，它不能采用像快速排序或堆排序这样的高级排序方法，查找也不能采用像二分(折半)查找那样的高级查找方法。而数组恰恰相反，插入/删除非常慢，而排序和查找非常方便。

同一个软件，在有的条件下，可能主要是对数据进行插入/删除，很少去查找，这时用链表比较合适。在另外一种条件下，很少对数据进行插入/删除，多数情况下是查找，这时用数组比较合适。我们能不能动态的切换容器，自适应的各种情况呢？

当然可以，那就是抽象一个容器接口。所有容器都实现这个接口，调用者使用抽象的容器接口，而不是具体的容器。

这样抽象的后果是，实现复杂了，同时限制了容器的功能。因为容器接口只能提供所有容器都能实现的函数，不能支持各种容器的专用函数了。

下面我们看一下用C语言如何实现(下面代码仅作演示所用，未经验证)：：

定义抽象的容器：

struct _container;

typedef struct _container container;

typedef iterator* (container_begin)(container* thiz);

typedef BOOL (container_insert)(container* thiz, void* data);

typedef BOOL (container_erase)(container* thiz, void* data);

typedef BOOL (container_remove)(container* thiz, void* data);

typedef void (container_destroy)(container* thiz);

struct _container

{

container_begin begin;

container_insert insert;

container_erase erase;

container_remove remove;

container_destroy destroy;

char priv[1];

};

实现具体的容器：

typedef struct _ListData

{

ListNode* first;

}ListData;

container* list_container_create(void)

{

ListData* data = NULL;

container* thiz = (container*)malloc(sizeof(container) + sizeof(ListData));

thiz->begin = list_begin;

thiz->insert = list_insert;

thiz->erase = list_erase;

thiz->remove = list_remove;

thiz->destroy = list_destroy;

data = (ListData*)thiz->priv;

data->first = NULL;

return thiz;

}

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

typedef struct _VectorData

{

VectorNode* first;

}VectorData;

container* vector_container_create(void)

{

VectorData* data = NULL;

container* thiz = (container*)malloc(sizeof(container) + sizeof(VectorData));

thiz->begin = vector_begin;

thiz->insert = vector_insert;

thiz->erase = vector_erase;

thiz->remove = vector_remove;

thiz->destroy = vector_destroy;

data = (VectorData*)thiz->priv;

data->first = NULL;

return thiz;

}

8. 支持多线程。

要不要支持多线程？尽管我认为考虑多线程，应该从架构着手，减少同步点，最大化并发。否则各个线程之间的关系耦合太紧，同步点太多，不但于提升性能无益，反而对程序的稳定性造成伤害。但这种同步点毕竟无法避免，假设多线程都要对链表进行访问，对链表加锁就是必需的了。

由调用者加锁，还是由容器加锁呢。由调用者加锁，则使用麻烦一点，也容易出错一些，好处是链表的实现简单。由链表加锁，会简化调用者的任务，但链表实现比较复杂，有时可能要考虑实现递归锁。比如在foreach里加锁了，而在visit里又要调用删除函数，删除函数里又加锁了，直接使用pthread的函数可能会造成死锁，这时你不得不自己实现递归锁。

一个小小链表的设计，竟然要面临如此之多设计决策，其它设计是不是更复杂呢? 当然不用太悲观，孙子说，多算胜少算，而况于不算乎。考虑总比不考虑好，多考虑比少考虑好，考虑得多对问题把握得更全面。关于设计，一位同事总结得非常精辟，多想少做。考虑了不去做，和不考虑不去做，两者是不可同日而语的。

~~end~~