“ 一说到容器,可能就是鼎鼎大名的 C++ STL。在别的编程语言里面也现成的容器可用,单单唯独 C 语言没有像样的容器可用。在闲的蛋疼之际,我为 C 语言实现了一套容器接口,当然不能做到 STL 那么精美绝伦,功能强大,这只为一探容器的究竟”
参考 C++ 的 STL。容器本身有三个主要部分组成:
泛型,C++ 中因为有模版的机制,所以 C++ 中实现泛型就十分简单,实现原理是编译期间的源文件产生和字符串的拷贝。可 C 就没有泛型的机制,它要实现泛型功能,需要把数据在容器内的行为包装成函数,使不同数据在容器中提供统一的接口。
迭代器,可在容器对象(container,例如 链表 或 数组 )上遍访的接口,设计人员无需关心容器对象的内存分配的实现细节。
容器,对外提供增删查改的接口。
大概就这些了,根据以上内容。我们可以大致做如下的编码设计:
01 泛型
根据初步设计,数据在容器当中的行为有这几种:相等比较、大小比较、赋值、交换、不定参数转化、数据尺寸,于是代码设计如下:
// adapter 是所有行为接口的统一形式。
typedef void (*T_adapter)(void);
// 比较是否相等的行为接口
typedef int (*adpter_eq) (T*, T*);
// 比较大小的行为接口
typedef int (*adpter_less) (T*, T*);
// 不定参数转化行为接口
typedef int (*adpter_vargs) (va_list);
复制代码
typedef struct {
// 给这个泛型定义起个ID
int ty_id;
// 指明此泛型的大小
int ty_size;
} T_def;
复制代码
typedef struct {
// id 及 大小
T_def _def;
// 行为接口
T_adapter _adapter[3];
} T_clazz;
复制代码
为了开箱即用,需要内定一些常用的数据对象。例如整型(int)和浮点(float)。
// 定义两种内在的数据对象的ID
// ID 的用处会在稍后展示。
typedef enum {
int_t = 1,
float
} built_in_type_t;
// 再给行为函数也取个ID
typedef enum {
adp_eq=0,
adp_less,
adp_vargs,
} adapter_t;
复制代码
// 整型的相等比较
int eq_int(T* t1, T* t2)
{
int v1 = *((int*)(t1));
int v2 = *((int*)(t2));
return v1 == v2;
}
// 整型的大小比较
int less_int(T* t1, T* t2)
{
int v1 = *((int*)(t1));
int v2 = *((int*)(t2));
return v1 < v2;
}
// 整型的不定参数转化
int vargs_int(va_list valist, T* t)
{
int type_v = va_arg(valist, int);
*((int*)t) = type_v;
return 0;
}
复制代码
int eq_float(T* t1, T* t2)
{
float v1 = *((int*)(t1));
float v2 = *((int*)(t2));
if (fabs(v1 - v2) <= 0.00001) return 1;
return 0;
}
int less_float(T* t1, T* t2)
{
float v1 = *((int*)(t1));
float v2 = *((int*)(t2));
return v1 < v2;
}
int vargs_float(va_list valist, T* t)
{
double v = va_arg(valist, double);
*((float*)t) = (float)v;
return 0;
}
复制代码
为了开箱即用,在全局作一数组用于存放整型和浮点型的数据对象。
// 全局的 T_def 的数组。使用 static 定义为私域数组,通过公域接口来获取。
static T_def __T_DEFS_BASE[4] =
{
// 0
{0, 0},
{int_t, sizeof(int)},
{fl_t, sizeof(float)},
// 2 ~ 5 保留备用
{0, 0}
};
// 存放行为函数的数组。使用 static 定义为私域数组,通过公域接口来获取。
static T_adapter __T_ADAPTERS_TAB[4][3] =
{
{0,0,0},
// eq_int, less_int,vargs_int另外定义在built_in_type.c中
{&eq_int, &less_int, &vargs_int},
{&eq_float, &less_int, &vargs_float},
//备用,当有
{0,0,0}
};
复制代码
使用两个全局函数获取 T_def 与 T_adapter
// 根据泛型 ID 返回泛型
T_def T_def_get(int T_id)
{
return __T_DEFS_BASE[T_id];
}
// 根据泛型的 ID 返回泛型的适配器。
T_adapter T_adapter_get(int T_id, int adapter)
{
return __T_ADAPTERS_TAB[T_id][adapter];
}
复制代码
定义几个关于 T_adapter 的宏,方便调用数据对象的行为函数
#define T_size(clazz_ptr) ((clazz_ptr)->_def.ty_size)
#define T_eq(clazz_ptr) ((adapter_eq)((clazz_ptr)->_adapter[adp_less]))
#define T_less(clazz_ptr) ((adapter_less)((clazz_ptr)->_adapter[adp_less]))
#define T_vargs_to(clazz_ptr) ((adapter_vargs) ((clazz_ptr)->_adapter[adp_vargs]))
复制代码
02 迭代器
迭代器就比较容易了。只需要两个字段:指向数据的指针、指向当前迭代器的指针。数据指针是为了获取数据,而指向容器的指针是为了调用迭代器移动的函数。
迭代器的定义如下:
typedef struct _iterator iter_t;
struct _iterator {
container_t* container;
T* reference;
};
复制代码
在定义一个方便构造迭代器的宏:
#define __iterator(__refer, __container) \
({ \
iter_t it = { .reference = (__refer), \
.container = (__container)}; \
it; \
})
复制代码
03 容器
终于到主角了。
这里为了点到为止,就只展示容器的几个关键的接口,返回第一个迭代器、返回最后一个迭代器、移动、添加、删除等这几个接口:
struct _container {
// 返回第一个数据的函数指针
iterator_t (*first) (container_t* container_ptr);
// 返回最后一个数据的函数指针
iterator_t (*last) (container_t * container_ptr);
// 移动的迭代器的函数指针
int (*move) (iterator_t* iter, int step);
// 插入函数
int (*insert) (container_t* container_ptr, iterator_t iter, ...);
// 删除函数
int (*remove) (container_t* container_ptr, iterator_t iter);
// 当前容器中的数据类型
T_clazz *type_clazz;
};
复制代码
以上便是容器接口的定义。可以说是套在容器外的一层壳。那如何将其变成真实能用的容器。
且看下一集:链表。
以上代码均来自:https://github.com/zuweie/boring-code
评论