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

简介: 目录:     1. 内存池     2. 栈     3. Hash表1.内存池  在一些小的程序里,没什么必要添加内存管理模块在里面。但是对于比较复杂的代码,如果需要很多的内存操作,那么加入自己的内存管理是有必要的。

目录:

     1. 内存池

     2. 栈

     3. Hash表

1.内存池
  在一些小的程序里,没什么必要添加内存管理模块在里面。但是对于比较复杂的代码,如果需要很多的内存操作,那么加入自己的内存管理是有必要的。至少有一些好处:能够加快内存的申请和释放;能够轻松的查找内存泄露问题;能够对整个软件的内存消耗做一个比较精确的统计;对以后的优化有很大的好处等等。所以,在我的解释器里,我加入了一个简单的内存管理模块,仿造了内存池的做法。
  主要思想是这样的:
  a.记录所有的申请的内存
  b.当释放内存时,记录下来以供下次申请使用
  c.申请内存时,可以直接使用前面释放过的内存
  为了达到以上的功能。我为申请内存的大小划分粒度,例如:我得粒度这么安排{16,32,64,128,...}那么申请17个字节的大小时候,我会申请32个字节的大小。这样子方便管理。并且为每个粒度创建一个可用内存的双向链表。申请内存时,就可直接从这些链表头中申请(即将一个节点从链表头移除,作为被申请的空间,并插入到在使用的链表中),内存的释放则是一个想法的过程。这些的存储结构如下所示:
  
  (图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.栈
  栈在解释器中用到的地方很多,不管是表达式的解析,还是代码块的解析,类型的解析,等等都用到了栈。所以不实现它是不可能的事,不过在数据结构中他是最简单的了,无非就是申请一个空间,按一个一个的节点保存进去,按一个一个的节点取出来。没什么技巧在里面,只是这个我让栈的大小空间是自动增长和减小的,这么做的目的是:栈的空间仅仅限制于内存的大小。但是,这么做得缺点是,当栈的空间大小自动变化时,栈内的数据要被复制一遍,这务必会影响效率。但没有办法,暂时之能这样了。唯一的办法是在时间和空间上做一个选择。
  栈的存储结构如下:
  
  (图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也是必要的。
  
#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;

目录
相关文章
|
6天前
|
弹性计算 人工智能 安全
云上十五年——「弹性计算十五周年」系列客户故事(第二期)
阿里云弹性计算十五年深耕,以第九代ECS g9i实例引领算力革新。携手海尔三翼鸟、小鹏汽车、微帧科技等企业,实现性能跃升与成本优化,赋能AI、物联网、智能驾驶等前沿场景,共绘云端增长新图景。
|
12天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
4天前
|
云安全 人工智能 安全
Dify平台集成阿里云AI安全护栏,构建AI Runtime安全防线
阿里云 AI 安全护栏加入Dify平台,打造可信赖的 AI
|
11天前
|
人工智能 自然语言处理 自动驾驶
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
|
7天前
|
人工智能 运维 Java
Spring AI Alibaba Admin 开源!以数据为中心的 Agent 开发平台
Spring AI Alibaba Admin 正式发布!一站式实现 Prompt 管理、动态热更新、评测集构建、自动化评估与全链路可观测,助力企业高效构建可信赖的 AI Agent 应用。开源共建,现已上线!
637 17
|
6天前
|
人工智能 Java Nacos
基于 Spring AI Alibaba + Nacos 的分布式 Multi-Agent 构建指南
本文将针对 Spring AI Alibaba + Nacos 的分布式多智能体构建方案展开介绍,同时结合 Demo 说明快速开发方法与实际效果。
427 34
|
12天前
|
编解码 自然语言处理 文字识别
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
凌晨,Qwen3-VL系列再添新成员——Dense架构的Qwen3-VL-8B、Qwen3-VL-4B 模型,本地部署友好,并完整保留了Qwen3-VL的全部表现,评测指标表现优秀。
729 7
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大