C语言实现存储结构,C语言解释器的实现--存储结构(一)

落日映苍穹つ 2023-01-22 13:48 10阅读 0赞

1.内存池

在一些小的程序里，没什么必要添加内存管理模块在里面。但是对于比较复杂的代码，如果需要很多的内存操作，那么加入自己的内存管理是有必要的。至少有一些好处：能够加快内存的申请和释放；能够轻松的查找内存泄露问题；能够对整个软件的内存消耗做一个比较精确的统计；对以后的优化有很大的好处等等。所以，在我的解释器里，我加入了一个简单的内存管理模块，仿造了内存池的做法。

主要思想是这样的：

a.记录所有的申请的内存

b.当释放内存时，记录下来以供下次申请使用

c.申请内存时，可以直接使用前面释放过的内存

为了达到以上的功能。我为申请内存的大小划分粒度，例如：我得粒度这么安排\{16,32,64,128,...\}那么申请17个字节的大小时候，我会申请32个字节的大小。这样子方便管理。并且为每个粒度创建一个可用内存的双向链表。申请内存时，就可直接从这些链表头中申请(即将一个节点从链表头移除，作为被申请的空间，并插入到在使用的链表中)，内存的释放则是一个想法的过程。这些的存储结构如下所示：

![f7efb925f834439db1a195e8e66cc82b.jpg][]

(图1.1 内存池的存储结构)

typedef struct \_pool\_block\{

int size;

void \* data;

struct \_pool\_block \* next;

struct \_pool\_block \* pre;

\}pool\_block\_t;

typedef struct \_pool\{

int num\_all;

int num\_free;

pool\_block\_t \* list\_all;

pool\_block\_t \* list\_free\[POOL\_ATOM\_NUM\];

\}pool\_t;

int pool\_atom\_tab\[POOL\_ATOM\_NUM\] = \{

32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, -1

\};

说明：

a.内存的申请会按照pool\_atom\_tab数组中的大小对齐，比如申请10byte，那么，我会申请32byte.

b.为每个粒度保存一个双向链表，用于保存被释放的内存。如果要申请的内存超过8192，那么我直接调用系统的malloc，释放时，直接调用free.

c.内存申请过程：到相应的粒度链表(list\_free)中查看是否有可用内存，如果有，直接将它从该list\_free链表中移动到list\_all链表。

d.内存释放过程：要释放的内存必定保存在list\_all中，根据它的大小，把它移动到相应的list\_free链表。

e.pool\_block\_t结构被放置在申请内存的前面，则在释放时，直接根据Buffer指针就可得到pool\_block\_t的位置，从而得到next和pre，快速的在链表中移动。

2.栈

栈在解释器中用到的地方很多，不管是表达式的解析，还是代码块的解析，类型的解析，等等都用到了栈。所以不实现它是不可能的事，不过在数据结构中他是最简单的了，无非就是申请一个空间，按一个一个的节点保存进去，按一个一个的节点取出来。没什么技巧在里面，只是这个我让栈的大小空间是自动增长和减小的，这么做的目的是：栈的空间仅仅限制于内存的大小。但是，这么做得缺点是，当栈的空间大小自动变化时，栈内的数据要被复制一遍，这务必会影响效率。但没有办法，暂时之能这样了。唯一的办法是在时间和空间上做一个选择。

栈的存储结构如下：

![caa6f7a7b3496fada67db1deb1530ccd.png][]

(图1.2 栈的存储结构)

typedef struct \_stack\{

int item\_len;

int item\_num;

int stack\_size;

char \*p;

\}stack\_t;

说明：

item\_len:   保存每个节点的长度

item\_num:   栈中节点的个数

stack\_size: 栈中可保存的节点个数

p:          指向栈空间

a.当节点的个数item\_num大于stack\_size,那么必须重新申请空间，将原来的数据拷贝到新的空间。

b.当节点的个数减小到一定的数量时，可以重新申请小的数据空间，释放原来大的空间。

3.hash表

hash由于其快速的查找能力而著称，但是它太浪费内存了，所以用得的比较少，仅仅是在函数的调用时被使用。因为函数的调用是频繁的，如果从头查找函数，那将浪费很多的时间。这里引入hash也是必要的。

![c6c86554e12da53f50dd0870043a5ce7.png][]

\#define HH\_TAB\_SIZE 128

typedef struct \_hh\_node\{

unsigned int hash, klen, dlen;

void \* key;

void \* data;

struct \_hh\_node \*next;

\}hh\_node\_t;

typedef struct \_hh\_head\{

unsigned int node\_num;

hh\_node\_t \*  node\_list;

\}hh\_head\_t;

typedef struct \_hh\_hash\{

hh\_opts\_t opts;

hh\_head\_t tabs\[HH\_TAB\_SIZE\];

\}hh\_hash\_t;

typedef struct \_hh\_opts\{

int (\*cmp\_key)(void \*key1, void \*key2);

unsigned int (\*get\_hash)(void \*key);

void \* (\*new\_key)(int);

void \* (\*new\_data)(int);

void (\*del\_key)(void \*key);

void (\*del\_data)(void \*data);

\}hh\_opts\_t;

[f7efb925f834439db1a195e8e66cc82b.jpg]: /images/20221020/fa49bf257f67477c8ecf1e6c4975c606.png
[caa6f7a7b3496fada67db1deb1530ccd.png]: /images/20221020/13bcebc9c6994ef4addecd80bc6a1852.png
[c6c86554e12da53f50dd0870043a5ce7.png]: /images/20221020/b979f4b0845d4a09845959fc8f0af1ff.png