暂时没任务，了解一下MudOS的源码。推荐使用vim来看，搭配上ctags插件跳转函数定义。
下面先来讲一讲数据类型：array、mapping、string。
array
array类似于其他语言中线性表的概念，比如说：c++语言的vector、python的list。array.h中定义了结构体array_t，array_t就是主要的存储数据的类型：
typedef struct array_s {
unsigned short ref;
int extra_ref;
unsigned short size;
svalue_t item[1];
}
上面的svalue_t item[1];就是存储具体数据的地方。明显是一个数组。svaluet_t是一个结构体类型，定义在lpc.h中：
37 typedef struct svalue_s {
38 short type;
39 short subtype;
40 union u u;
41 } svalue_t;
11 union u {
12 char *string;
13 int number;
14 float real;
15
16 refed_t *refed; /* any of the block below */
21 struct object_s *ob;
22 struct array_s *arr;
23 struct mapping_s *map;
24 struct funptr_s *fp;
25
26 struct svalue_s *lvalue;
27 struct ref_s *ref;
28 unsigned char *lvalue_byte;
29 void (*error_handler) PROT((void));
30 };
通过上面基本上了解到array是如何定义的了。
比较有意思的是array提供的一个排序函数：f_sort_array。
内部使用的是快速排序，快速排序定义在qsort.c中。
可以看到关于快排的注释:
/* qsort adapted from page 87 of K&R 2nd edition */
Mudos作者引用了K&R写的c程序设计第2版的87页。
附上array支持的函数：
allocate() - 配置内存给一个有 size 个元素的数组
arrayp() - 看一个给定的变量是否为数组 (array).
filter_array() - 返回一个过滤旧数组内容的新数组.
map_array() - 经由一个函数修改一个数组的元素 (element)
member_array() - 在一个数组 (array) 或字符串 (string) 中找寻指定的项目 (item)
pointerp() - 判断指定的变量是否为一个数组 (array).
sort_array() - 将一个数组的内容排序.
unique_array() - 将一个物件数组分组.
mapping
在mapping.h中定义了mapping在内存中实际的类型：
32 typedef struct mapping_s {
33 unsigned short ref; /* how many times this map has been* referenced */
38 mapping_node_t **table; /* the hash table */
39 unsigned short table_size; /* # of buckets in hash table == power of 2 */
40 unsigned short unfilled; /* # of buckets among 80% of total buckets that do not have entries */
41 unsigned int count; /* total # of nodes actually in mapping */
45 } mapping_t;
11 typedef struct mapping_node_s {
12 struct mapping_node_s *next;
13 svalue_t values[2];
14 } mapping_node_t;
从注释很容易可以看出来，mapping底层是用hash_table来存储数据的。
很想吐槽这注释....
从mapping_node_t **table;可以知道，使用的是链地址法的方式实现的hashtable。
下面看一个返回所有value值的函数实现(mapping.c):
1256 /* mapping_values */
1257
1258 array_t *
1259 mapping_values P1(mapping_t *,m)
1260 {
1261 array_t *v;
1262 int j = m->table_size;
1263 mapping_node_t *elt, **a = m->table;
1264 svalue_t *sv;
1265
1266 debug(mapping,("mapping_values: size = %d\n",MAP_COUNT(m)));
1267
1268 v = allocate_empty_array(MAP_COUNT(m));
1269 sv = v->item;
1270 do {
1271 for (elt = a[j]; elt; elt = elt->next)
1272 assign_svalue_no_free(sv++, elt->values + 1);
1273 } while (j--);
1274 return v;
1275 }
很容易就能看懂。其实就是对于mapping的一次遍历。
附上mappings支持的函数：
allocate_mapping() - 预先配置 (pre-allocate) 一块内存给一个映射 (mapping).
each() - 分次返回一个映射变量 (mapping) 的各个 (key, value) 的内容.
filter_mapping() - 以一个函数为准, 移除一个映射变量中的某些元素.
keys() - 返回在一个映射变量 (mapping) 中所有 (关键字, 内容值) (即 (key, value) ) 数据关键字的数组 (array).
values() - 从一个映射变量的 (关键字, 内容值) ( (keys, values) ) 中, 以数组返回内容值.
map_delete() - 以关键字从一个映射变量中删除一对 (关键字, 内容值) ((key, value)).
map_mapping() - 经由一个函数修改一个映射变量中的元素
mapp() - 判断一个指定的变量是否为映射变量 (mapping).
match_path() - 在一个映射变量 (mapping) 中找寻路径名称 (path)
unique_mapping() - 以一个函数为准, 从一个数组另创一个映射 (mapping).
string
string其实就是一个对于字符数组的封装。
string在mudos内的定义位于stralloc.h和stralloc.c中。来看看stralloc.h声明的函数有：
125 void init_strings PROT((void)); //初始化字符串
126 char *findstring PROT((char *)); //查找字符串
127 char *make_shared_string PROT((char *)); //共享字符串
128 char *ref_string PROT((char *)); //引用字符串
129 void free_string PROT((char *)); //释放字符串
130 void deallocate_string PROT((char *)); //解除string的内存分配
131 int add_string_status PROT((outbuffer_t *, int)); //增加字符串的状态
来看一下init_strings函数：
85 void init_strings()
86 { 87 int x, y;
88
89 /* ensure that htable size is a power of 2 */
90 y = HTABLE_SIZE;
91 for (htable_size = 1; htable_size < y; htable_size *= 2)
92 ;
93 htable_size_minus_one = htable_size - 1;
94 base_table = CALLOCATE(htable_size, block_t *,
95 TAG_STR_TBL, "init_strings");
99
100 for (x = 0; x < htable_size; x++) {
101 base_table[x] = 0;
102 }
103 }
mudos的底层是通过hashtable来管理string的。init_strings函数就是初始化这个hashtable。
再来看看findstring ：
141 char *
142 findstring P1(char *, s)
143 {
144 block_t *b;
145
146 if ((b = findblock(s))) {
147 return STRING(b);
148 } else {
149 return (NULL);
150 }
151 }
67 #define findblock(s) sfindblock(s, StrHash(s))
112 INLINE_STATIC block_t *
113 sfindblok P2(char *, s, int, h)
114 {
115 block_t *curr, *prev;
116
117 curr = base_table[h];
118 prev = NULL;
119 #ifdef STRING_STATS
120 num_str_searches++;
121 #endif
122
123 while (curr) {
124 #ifdef STRING_STATS
125 search_len++;
126 #endif
127 if (*(STRING(curr)) == *s && !strcmp(STRING(curr), s)) { /* found it */
128 if (prev) { /* not at head of list */
129 NEXT(prev) = NEXT(curr);
130 NEXT(curr) = base_table[h];
131 base_table[h] = curr;
132 }
133 return (curr); /* pointer to string */
134 }
135 prev = curr;
136 curr = NEXT(curr);
137 }
138 return ((block_t *) 0); /* not found */
139 }
find_string就是在hashtable中去查找给定字符串。查找步骤如下：
1、通过hash(s)确定s所在的桶。
2、顺序查找单链表。
3、如果找到了，并且不是单链表头结点，就提前到头结点。
4、返回结果。
mudos的string也是用了慢拷贝来做的。慢拷贝是指如果新定义的字符串已经存在的话，就增加对这个字符串的引用，而不是新开一块内存去存储。这样的做法就导致了，string不能改，改起来会特别麻烦。
每个string都带了一个引用计数器。一般这种引用计数的话，在多线程情况下会出现竞争，因为i++不是原子的，转换成汇编语句会变成:
mov eax，【xxxxxxxx】
inc eax
```
因为两条语句中间可能会出现中断，move指令执行之后，此时如果转入到另外一条线程下面，刚好也执行了move指令，那么两个线程各自的eax都加了一，但是实际上应该加二才对。
一种比较简单处理是在原子语句之间先关闭中断，然后进行原子操作后再
打开中断就OK了。
efuns提供的关于string的函数有：
```
stringp() - 判断一个变量是否为字符串类型 (string).
break_string() - 以固定的间隔打断一个字符串 (string).返回一个字符串
capitalize() - 把一个字符串的第一个英文字符 (character) 转成大写.
clear_bit() - 清除一个字符串中的某一个 bit .
crypt() - 对一个字符串进行编码.
explode() - 打断一个字符串.返回字符串数组
implode() - 连结多个字符串.
lower_case() - 转换一个指定字符串的内容为小写
reg_assoc() - 一个正规样式 (regular pattern) 子字符串撷取器(extractor)
regexp() - 正规描述式(regular expression)处理程序
replace_string() - 替换一个字符串中符合条件的字.
set_bit() - 设定一个位元字符串 (bitstring) 中的一个位元 (bit).
printf, sprintf - 转换成指定格式的输出结果.
sscanf() - 从一个字符串中读进与指定格式相符的数据.
strcmp() - 判断两个字符串间的语句关系 (lexical relationship).
strlen() - 返回一个字符串的长度
strsrch() - 在一个字符串中寻找特定的字符串.
test_bit() - 检查一个位元字符串 (bitstring) 中某一个位元 (bit) 的值.
```
网友评论