数据结构接口对象化

Time: 十一月 23, 2010
Category: Programming practices

c 语言适合平台及系统等一些的大型核心构架的开发,面向过程,不支持面向对象语义,

不过我始终认为,面向对象是一种思想,而不是指某种既定的技术,所以,OO 与语言没有关系,随便一种语言,一样可以写出面向对象的代码,OO 的思想绝对不只是继承,多态等那么简单,对于某些语言如 c++ 或者 Java,支持面向对象语义因而适合表达这种思想而已,况且 Java本身设计的出现就是为了解决面向语义的问题

做项目的时候,很头疼的问题就是关于接口命名的设计,包括内部接口和外部接口,小型的项目倒也罢了,如果构架过于庞大,就容易出现接口混乱的问 题,c 风格的代码并不像 c++ 或者 java 那样简单容易白,毕竟用 c 的都是写模块的多,功能越是复杂,函数的命名就越容易出现杂乱无章的情况,很难看出你在写什么,支持面向语义的编程语言,最大的优点就是,容易写出层次分 明,结构清晰的代码,但是像 c 这样的语言可不容易,所以,好的函数命名规范对项目来说很重要

回归正题,先说说什么是对象化技术,所谓数据结构对象化,就是一组结构有各自适合的管理接口,本质上是一样的,只是写法不同而已,以红黑树为例,看看内核是怎么实现的(部分接口):

C++代码
  1. /* Macros that define a red-black tree */
  2. #define RB_HEAD(name, type)
  3. struct name {
  4.     struct type *rbh_root; /* root of the tree */
  5. }
  6. #define RB_INITIALIZER(root)
  7.     { NULL }
  8. #define RB_INIT(root) do {
  9.     (root)->rbh_root = NULL;
  10. } while (/*CONSTCOND*/ 0)
  11. #define RB_BLACK    0
  12. #define RB_RED      1
  13. #define RB_ENTRY(type)
  14. struct {
  15.     struct type *rbe_left;      /* left element */
  16.     struct type *rbe_right;     /* right element */
  17.     struct type *rbe_parent;    /* parent element */
  18.     int rbe_color;          /* node color */
  19. }
  20. /* Main rb operation.
  21.  * Moves node close to the key of elm to top
  22.  */
  23. /* Main rb operation.
  24.  * Moves node close to the key of elm to top
  25.  */
  26. #define    RB_GENERATE(name, type, field, cmp)
  27.     RB_GENERATE_INTERNAL(name, type, field, cmp,)
  28. #define    RB_GENERATE_STATIC(name, type, field, cmp)
  29.     RB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
  30. #define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)
  31. attr void
  32. name##_RB_INSERT_COLOR(struct name *head, struct type *elm) {......}
  33. attr void
  34. name##_RB_REMOVE_COLOR(struct name *head, struct type *parent,
  35. struct type *elm) {......}
  36. attr struct type *
  37. name##_RB_REMOVE(struct name *head, struct type *elm) {......}
  38. /* Inserts a node into the RB tree */
  39. attr struct type *
  40. name##_RB_INSERT(struct name *head, struct type *elm) {......}
  41. /* Finds the node with the same key as elm */
  42. attr struct type *
  43. name##_RB_FIND(struct name *head, struct type *elm) {......}
  44. /* Finds the first node greater than or equal to the search key */
  45. attr struct type *
  46. name##_RB_NFIND(struct name *head, struct type *elm) {......}
  47. /* ARGSUSED */
  48. attr struct type *
  49. name##_RB_NEXT(struct type *elm) {......}
  50. /* ARGSUSED */
  51. attr struct type *
  52. name##_RB_PREV(struct type *elm) {......}
  53. attr struct type *
  54. name##_RB_MINMAX(struct name *head, int val) {......}

主要是 RB_ENTRY 和 RB_GENERATE_STATIC ,在内核的红黑书实现里,内核并不关心具体的数据结构形式,数据与结构分离,通过 RB_ENTRY 和 Compare 函数来实现红黑书的操作的,接口全部以宏的方式来实现,关键的地方是 name,比如

C++代码
  1. #define RB_HEAD(name, type)
  2. struct name {
  3.     struct type *rbh_root; /* root of the tree */
  4. }

name 是什么呢,name 是结构的一种别名,实质上,相当于创建了一个 RB 对象,对象之间以 name 来区分,这样做的好处就是,RB 实现的代码可以高度重用,不好的地方就是,以宏替换的方式来模拟面向对象的行为,和 inline 的滥用没有什么区别,举个例子

C++代码
  1. /* Tree of chunks. */
  2. typedef struct chunk_node_s chunk_node_t;
  3. struct chunk_node_s {
  4.     /* Linkage for the chunk tree. */
  5.     RB_ENTRY(chunk_node_s) link;
  6.     /*
  7.      * Pointer to the chunk that this tree node is responsible for.
  8.      */
  9.     void    *chunk;
  10.     /* Total chunk size. */
  11.     size_t  size;
  12. };
  13. typedef struct chunk_tree_s chunk_tree_t;
  14. RB_HEAD(chunk_tree_s, chunk_node_s);
  15. static int
  16. chunk_comp(chunk_node_t *a, chunk_node_t *b)
  17. {
  18.     if(a->size > b->size)
  19.         return(1);
  20.     else if(a->size == b->size)
  21.         return(0);
  22.     else
  23.         return(-1);
  24. }
  25. /* Generate red-black tree code for chunks. */
  26. RB_GENERATE_STATIC(chunk_tree_s, chunk_node_s, link, chunk_comp);

回到刚才的,内核红黑树的接口,RB_GENERATE_STATIC 做了些什么呢?RB_GENERATE_STATIC在预处理阶段就为 name 指定的对象生成了一系列的相关操作,如果程序内包含多个红黑树对象,虽然看起来是多了一个 RB_GENERATE_STATIC宏,但是实质上相当于将原有的代码 copy 了一份,只是 name 和 compare 接口不同而已

其实有一种非常优雅的方式,就是使用函数指针,而且我们经常用到的很多内核级实现里也是经常用到的,将数据结构的行为封装在一起,Berkery DB 数据库的实现就是一个很好的例子,看:

C++代码
  1. typedef struct {
  2.     DBTYPE type;
  3.     int (*close)(const DB *db);
  4.     int (*del)(const DB *db, const DBT *key, u_int flags);
  5.     int (*fd)(const DB *db);
  6.     int (*get)(const DB *db, DBT *key, DBT *data, u_int flags);
  7.     int (*put)(const DB *db, DBT *key, const DBT *data, u_int flags);
  8.     int (*sync)(const DB *db, u_int flags);
  9.     int (*seq)(const DB *db, DBT *key, DBT *data, u_int flags);
  10. }DB;

DB 数据库对象将所有的操作封装在自身的结构体里,显然,从多个方面来看,比起那些通过命名规范来约束函数的接口以体现程序的结构层次来看,这种方式清晰明了。

Leave a Comment