C语言实现Hash Map(3)：Map代码优化

在上一节中，我们学习了C语言实现Hash Map(2)：Map代码实现详解，通过代码，我们更深入地了解了Map实现的原理，学习了如何通过key找到对应的桶并加入节点。也正如上一节提到的，虽然这是github中star比较多的代码，但是程序还可以进一步地优化：

  • 程序桶的数量是在每次添加节点的时候自动调节的，即使用realloc函数重新分配
    • 可以固定一下默认的桶的大小，而不是每次都从0开始网上分配
    • 假设使用FreeRTOS，并没有realloc函数，所以将其改为动态分配和释放
  • 程序仅支持值为char *类型的映射，且值的数据是拷贝的
    • 支持不同数据类型的键
    • 支持拷贝值和保存值的指针两种方式

文章目录

  • 1 桶的默认大小
  • 2 桶的内存分配
  • 3 支持不同的数据类型
    • 3.1 数据结构修改
    • 3.2 map_init
    • 3.3 map_set
    • 3.4 map_get
  • 4 测试
  • 5 总结

1 桶的默认大小

首先来解决桶内存的问题。由上一节我们知道，在每次增加节点的时候，若当前节点的数量大于等于桶的数量，则会使用realloc重新分配桶内存。但这样的话，最开始从0开始，随着节点的增加，分配1、 2、 4、 8个桶，未免有点太麻烦了，也可能会产生一些内存碎片。所以我们希望在初始化的时候，就初始化固定的桶。

所以解决办法很简单，我们直接在初始化函数中传入一个默认的桶数量的参数，然后调用map_resize即可。

void map_init(unsigned int nbuckets)
{
	...
	assert((nbuckets % 2) == 0);
    map_resize(&base, nbuckets);
}

由上节课可知，map_bucketidx函数中使用的是按位与来获取余数，所以这里的nbuckets的值应为2的倍数，所以这里断言判断一下。

2 桶的内存分配

另外，在map_resize函数中使用的是stdlib.h库中的realloc函数，我们就在分配之前释放上一次分配的，然后使用MAP_MALLOC分配就行了。如下图所示：

在这里插入图片描述

由于我们设置了桶的默认大小，我们可以根据实际情况调整桶的大小，只要不超过这个大小，就不会调用到map_resize函数。

3 支持不同的数据类型

从代码中可以看出：

int map_set_(map_base_t *m, const char *key, void *value, int vsize)
{
	...
	memcpy((*next)->value, value, vsize);
	...
}

value传入的是一个指针，然后函数中使用memcpy拷贝的是指针指向地址里面的值。所以这种情况就导致我们map的值只能使用字符串或定义一个变量并传入地址。假设我们希望值为int类型，然后直接写入数值就不允许了。另外，有的时候我们又希望这个函数不要拷贝函数的内容，比如我们的值传入的就是常量字符串，那我们在函数中还又拷贝一次，这样浪费了内存。所以我们就来更改一下这部分的代码，让它既支持拷贝参数内容，又支持保存参数的地址。

3.1 数据结构修改

首先我们回顾一下之前的数据结构：

typedef map_t(void*) map_void_t;
typedef map_t(char*) map_str_t;
typedef map_t(int) map_int_t;
typedef map_t(char) map_char_t;
typedef map_t(float) map_float_t;
typedef map_t(double) map_double_t;

其中map_t为：

#define map_t(T)\
  struct { map_base_t base; T ref;}

我们知道，map实际的数据结构就是map_base_t，而这个T ref就是标记不同数据类型的唯一地方了。而且ref变量仅在下面用到：

#define map_get(m, key)\
  ( (m)->ref = map_get_(&(m)->base, key) )

也就是获取键值的是保存在这个变量中，但很明显，假设类型为int，map_get_却返回的是一个指针，类型明显不符。另外将结果保存在ref中似乎也没什么意义。所以我们直接删除ref这个变量，和所有的类型的typedef，直接typedef整个结构体就行了。

为了能够区别不同数据类型的长度，我们增加两个变量，typeSize表示数据类型的大小，isCpyAddr表示设置键值的时候是拷贝地址里的值(isCpyAddr=1)，还是直接传入值给函数(拷贝参数，isCpyAddr=0)。然后将整个数据结构命名为map_c_t：

typedef struct{
    map_base_t base;
    unsigned char typeSize;
    unsigned char isCpyAddr;
}map_c_t;

接下来我们就改下面三个函数：map_init、map_set和map_get，删掉宏定义的map_set和map_get。

  • 对于其它几个宏定义和函数，如map_remove、map_deinit等，自行更改一下，主要是将函数参数map_base_t修改为map_c_t即可。

3.2 map_init

原来的map_init是一个宏定义，然后用memset将整个map数据结构置0，现在我们将其改为函数。对于不同的数据类型，我们声明一个枚举类型供用户选择传参：

typedef enum{
    MAP_TYPE_VOID_PTR,    //void *
    MAP_TYPE_CHAR_PTR,    //char *
    MAP_TYPE_INT,         //int
    MAP_TYPE_CHAR,        //char
    MAP_TYPE_FLOAT,       //float
    MAP_TYPE_DOUBLE,      //double
}MAP_TYPE;

然后map_init函数如下：

void map_init(map_c_t *instance, MAP_TYPE type, unsigned char isCpyAddr, unsigned int nbuckets)
{
    memset(instance, 0, sizeof(map_c_t));
    switch(type)
    {
    case MAP_TYPE_VOID_PTR:{instance->typeSize = sizeof(void *);break;}
    case MAP_TYPE_CHAR_PTR:{instance->typeSize = sizeof(char *);break;}
    case MAP_TYPE_INT     :{instance->typeSize = sizeof(int);break;}
    case MAP_TYPE_CHAR    :{instance->typeSize = sizeof(char);break;}
    case MAP_TYPE_FLOAT   :{instance->typeSize = sizeof(float);break;}
    case MAP_TYPE_DOUBLE  :{instance->typeSize = sizeof(double);break;}
    default:break;
    }
    instance->isCpyAddr = isCpyAddr; //拷贝地址里的内容
    assert((nbuckets % 2) == 0);
    map_resize(&instance->base, nbuckets);
}
  1. 根据枚举类型保存数据的typeSize，这样比如在用户传入数字的时候，就知道拷贝多大的数据。
  2. isCpyAddr保存是否需要拷贝地址里的内容
  3. 最后根据设置的桶的初始大小来分配内存

3.3 map_set

我们直接来看一下代码前后的对比：

在这里插入图片描述

  1. 首先将原来的map_base_t改为我们定义的map_c_t，然后更改下面所有用到base的地方
  2. 这里vsize为我们传入的参数的大小，如果参数为字符串且我们用的是拷贝方式的话，我们需要传入vsize的大小，这样用户传入字符串的时候，我们就知道拷贝多大的长度。在其它时候，vsize可以传0，vsize就设置为数据类型对应的typeSize。
  3. 最后就是根据isCpyAddr来判断是拷贝地址里的值还是拷贝地址，分别在节点已经存在时和创建节点时修改代码。

这里举一个例子，如果我们设置的是MAP_TYPE_INT，然后传入的值是123，那么这个void *类型的value的值就是123，如果直接用memcpy拷贝的话，就拷贝的是123这个地址里的值；所以传入123的时候我们就拷贝value的地址&value就行了。

3.4 map_get

map_get函数不需要做太大的改动，只要把参数改成我们定义的map_c_t，然后把map_getref中的参数改成&m->base就行了。

void *map_get(map_c_t *m, const char *key) {
  map_node_t **next = map_getref(&m->base, key);
  return next ? (*next)->value : NULL;
}

4 测试

这里我把各个类型的使用都写了一个例子，只需要更改TEST_MODE宏定义即可：

#include <stdio.h>
#include <stdlib.h>
#include "map.h"

#define TEST_MODE 1

static map_c_t langMap;
int main()
{
#if (TEST_MODE == 1)       //字符串测试:拷贝字符串地址[常用]
    map_init(&langMap, MAP_TYPE_CHAR_PTR, 0, 8);
    map_set(&langMap, "test", "1234", 0);
    char **ret = map_get(&langMap, "test");
    printf("%x %x = %s\r\n", "1234", *ret, *ret);
#elif (TEST_MODE == 2)     //字符串测试:拷贝字符串的值map_node_t后面的内存中(需要指定长度)
    map_init(&langMap, MAP_TYPE_CHAR_PTR, 1, 8);
    map_set(&langMap, "test", "1234", sizeof("1234"));
    char *ret = map_get(&langMap, "test");
    printf("%x %x = %s\r\n", "1234", ret, ret);
#elif (TEST_MODE == 3)     //int测试:保存数字的值到map_node_t后[常用]
    map_init(&langMap, MAP_TYPE_INT, 0, 8);
    map_set(&langMap, "test", 123, 0);
    int *ret = map_get(&langMap, "test");
    printf("%x = %d\r\n", *ret, *ret);
#elif (TEST_MODE == 4)     //int测试:拷贝int变量的值到map_node_t后
    const int a = 123;
    map_init(&langMap, MAP_TYPE_INT, 1, 8);
    map_set(&langMap, "test", &a, 0);
    int *ret = map_get(&langMap, "test");
    printf("%x %x = %d\r\n", &a, *ret, *ret);
#elif (TEST_MODE == 5)     //int测试:保存int变量的地址
    const int a = 123;
    map_init(&langMap, MAP_TYPE_INT, 0, 8);
    map_set(&langMap, "test", &a, 0);
    int **ret = map_get(&langMap, "test");
    printf("%x %x = %d\r\n", &a, *ret, **ret);
#elif (TEST_MODE == 6)     //char测试:拷贝字符的值到map_node_t后[常用]
    map_init(&langMap, MAP_TYPE_CHAR, 0, 8);
    map_set(&langMap, "test", 'a', 0);
    char *ret = map_get(&langMap, "test");
    printf("%x = %c\r\n", *ret, *ret);
#elif (TEST_MODE == 7)     //double测试:保存double变量地址到map_node_t后
    const double a = 3.14;
    map_init(&langMap, MAP_TYPE_DOUBLE, 0, 8);
    map_set(&langMap, "test", &a, 0);
    double **ret = map_get(&langMap, "test");
    printf("%x %x = %lf\r\n", &a, *ret, **ret);
#elif (TEST_MODE == 8)     //double测试:拷贝double变量的值到map_node_t后
    const double a = 3.14;
    map_init(&langMap, MAP_TYPE_DOUBLE, 1, 8);
    map_set(&langMap, "test", &a, 0);
    double *ret = map_get(&langMap, "test");
    printf("%x %x = %lf\r\n", &a, ret, *ret);
#else
    //1.float类型:代码同double
    //2.void *类型:这种情况一般是保存地址,所以map_init最后一个参数为0
#endif
    return 0;
}

这里来展示一下int作为值类型，传入数值时的演示结果：

在这里插入图片描述

可以看到，输出符合预期，0x7b是创建map_node_t节点时分配的内存地址里value的地址。

5 总结

本文基于Github上给的代码进行了一些小小的优化，使其可以适配不同的数据类型，并能够初始分配一个桶的内存。但正如前面所说，代码并没有完整做完适配，如map_deinit等函数还需要小小修改一下。大家可以自行修改，或者大家还有什么优化的建议都可以在我下面的git仓库中进行提交。

  • 完整代码：https://github.com/Vinolzy/map_fix

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/651923.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

You don‘t have enough free space或者no space left on device异常

You don‘t have enough free space或者no space left on device异常

1.磁盘空间不足 Linux安装软件显示 You dont have enough free space 或者docker拉镜像时&#xff0c;出现磁盘空间不足的情况 no space left on device 如果你是ubuntu系统。查看磁盘空间 df -h 多半是这个目录满了/dev/mapper/ubuntu--vg-ubuntu--lv 大多情况我们只希望扩…
阅读更多...
Android 14 - 绘制体系 - VSync（1）

Android 14 - 绘制体系 - VSync（1）

整体框架 VsyncConfiguration&#xff1a;一些基本参数的配置类&#xff0c;比如PhaseOffsets、WorkDuration等。 Scheduler&#xff1a;作为SF生成和派发VSync的整体调度器&#xff0c;主要面向SurfaceFlinger提供VSync相关接口。Scheduler包含对所有屏幕的VSync的控制。本身是…
阅读更多...
影响所有股票、债券和ETF交易！一文看懂美国“T+1”结算新规

影响所有股票、债券和ETF交易！一文看懂美国“T+1”结算新规

T1对投资者有何好处&#xff1f;有哪些风险&#xff1f;T1已经到来&#xff0c;T0还远吗&#xff1f; 美股将在本周迎来历史性时刻。 从当地时间5月28日开始&#xff0c;美股交易结算周期将由T2缩短至T1&#xff0c;即投资者当天卖出的股票&#xff0c;在交易后一个工作日就能…
阅读更多...
[Python]pyenv 环境配置

[Python]pyenv 环境配置

。pip install pyenv安装 / 去Git 下载pyenv版本安装 。安装好后控制台输入pyenv查看版本 。pyenv install --list列出所有pyenv可以支持的python版本 。pyenv install 3.9.7 安装指定的版本 。在pycharm里&#xff0c;可以选中项目&#xff0c;点击File-Settings&#xff0…
阅读更多...
如何评价 OpenAI 最新发布支持实时语音对话的模型GPT-4o？OpenAI发完GTP-4o，国内大模型行业还有哪些机会？

如何评价 OpenAI 最新发布支持实时语音对话的模型GPT-4o？OpenAI发完GTP-4o，国内大模型行业还有哪些机会？

文章目录 OpenAI发完GTP-4o&#xff0c;国内大模型行业还有哪些机会&#xff1f;详细了解一下OpenAI最新发布的支持实时语音对话的模型GPT-4o国内大模型如何寻找发展机会&#xff1f;想要发展技术必须要创新与追赶或许应用场景拓展也是一种出路产业生态构建 ChatGPT 问世才 17 …
阅读更多...
大字体学生出勤记录系统网页源码

大字体学生出勤记录系统网页源码

源码介绍 上课需要一个个点名记录出勤情况&#xff0c;就借助AI制作了一个网页版学生出勤记录系统&#xff0c; 大字体显示学生姓名和照片&#xff0c;让坐在最后排学生也能看清楚&#xff0c;显示姓名同时会语音播报姓名&#xff0c; 操作很简单&#xff0c;先导入学生姓名…
阅读更多...
制作ARM架构 docker镜像

制作ARM架构 docker镜像

docker简介 docker客户端 Docker 客户端有两种替代选项：名为 docker 的命令行应用程序或名为 Docker Desktop 的基于图形用户界面 (GUI) 的应用程序。 CLI 和 Docker Desktop 均与 Docker 服务器交互。 来自 CLI 或 Docker Desktop 的 docker 命令使用 Docker REST API 将指…
阅读更多...
C++ | Leetcode C++题解之第116题填充每个节点的下一个右侧节点指针

C++ | Leetcode C++题解之第116题填充每个节点的下一个右侧节点指针

题目&#xff1a; 题解&#xff1a; class Solution { public:Node* connect(Node* root) {if (root nullptr) {return root;}// 从根节点开始Node* leftmost root;while (leftmost->left ! nullptr) {// 遍历这一层节点组织成的链表&#xff0c;为下一层的节点更新 next…
阅读更多...
Android LAME原生音频

Android LAME原生音频

前言 我想大家都做过录音的功能吧&#xff0c;首先想到的是不是MediaRecorder&#xff1f;今天我们不用MediaRecorder&#xff0c;而是使用LAME库自己编译音频编码模块&#xff0c;很明显&#xff0c;这个需要用到NDK。凡是涉及到音视频编解码这块的&#xff0c;都需要用到And…
阅读更多...
STM32H750外设之ADC通道选择

STM32H750外设之ADC通道选择

目录 概述 1 通道选择功能介绍 2 通道选择&#xff08; SQRx、 JSQRx&#xff09; 2.1 通道复用 2.1.1 通道介绍 2.1.2 通道框图 2.2 转换分组 2.3 内部专用通道 3 通道预选寄存器 (ADCx_PCSEL) 3.1 功能介绍 3.2 预选通道寄存器 概述 本位主要介绍STM32H750外设之…
阅读更多...
2024年03月 Python（三级）真题解析#中国电子学会#全国青少年软件编程等级考试

2024年03月 Python（三级）真题解析#中国电子学会#全国青少年软件编程等级考试

Python等级考试（1~6级）全部真题・点这里 一、单选题（共25题，共50分） 第1题 在Python中，hex(2023)的功能是？（ ） A：将十进制数2023转化成十六进制数 B：将十进制数2023转化成八进制数 C：将十六进制数2023转化成十进制数 D：将八进制数2023转化成十进制数 答案：A …
阅读更多...
迭代器模式（行为型）

迭代器模式（行为型）

目录 一、前言 二、迭代器模式 三、总结 一、前言 迭代器模式(Iterator Pattern&#xff09;是一种行为型设计模式&#xff0c;提供一种方法顺序访问一个聚合对象中各个元素&#xff0c;而又不暴露该对象的内部表示。总的来说就是分离了集合对象的遍历行为&#xff0c;抽象出…
阅读更多...
深度学习环境安装教程-anaconda-python-pytorch

深度学习环境安装教程-anaconda-python-pytorch

首先是anaconda的安装&#xff0c;可以从下面地址下载安装包 Index of /anaconda/archive/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 尽量选择最新的日期的anaconda进行安装&#xff0c;我这里是windows电脑&#xff0c;因此选择了windos-x86_64.exe&#xf…
阅读更多...
TIM（Timer）简介

TIM（Timer）简介

TIM&#xff08;Timer&#xff09;定时器介绍 定时器可以对输入的时钟进行计数&#xff0c;并在计数值达到设定值时触发中断16位计数器、预分频器、自动重装寄存器的时基单元&#xff0c;在72MHz计数时钟下可以实现最大59.65s的定时不仅具备基本的定时中断功能&#xff0c;而且…
阅读更多...
软件测试金字塔,对号入座,你在哪层?

软件测试金字塔,对号入座,你在哪层?

自从学习了软件测试,脑袋也清晰了,目标也明确了,就是不知道学到哪里了.中间有很多的困难也有很多成就感,你目前在那个阶段呢? 初级测试工程师 技能要求:需求分析,使用等价类边界值等方法进行用例设计,执行功能测试,发现提交跟踪bug,使用禅道,会在测试中会操作数据库进行检查和…
阅读更多...
DSPy - prompt 优化

DSPy - prompt 优化

文章目录 一、关于 DSPy与神经网络的类比常见问题解答**DSPy 优化器可以调整什么&#xff1f;****我应该如何使用 DSPy 完成我的任务&#xff1f;****如果我对提示或合成数据生成有更好的想法怎么办&#xff1f;**DSPy 代表什么&#xff1f; 二、安装三、文档A) 教程B) 指南C) …
阅读更多...
python+pymysql对数据库进行增、删、改、查操作

python+pymysql对数据库进行增、删、改、查操作

一、概述 接口测试中&#xff0c;应用到数据库操作的场景&#xff1a; 1.校验测试数据 接口发送请求后明确会对数据库中的某个字段进行修改&#xff08;编辑&#xff0c;更新、删除操作&#xff09;&#xff0c;但&#xff0c;响应结果中无该字段数据时。 例如&#xff1a;删…
阅读更多...
读人工智能时代与人类未来笔记16_科学发现

读人工智能时代与人类未来笔记16_科学发现

1. 科学发现 1.1. 科学认识的发展往往涉及理论和实验之间的巨大差距以及大量的试错 1.2. 模型不是像传统的那样来自理论理解&#xff0c;而是来自基于实验结果得出结论的人工智能 1.2.1. 这种方法需要的专业知识不同于开发理论模型或传统计…
阅读更多...
6、python开发环境-PyCharm

6、python开发环境-PyCharm

下载完成之后双击进行安装 找到安装好的解释器程序
阅读更多...
BERT系列模型 在OCNLI 训练微调 3

BERT系列模型 在OCNLI 训练微调 3

目录 0 资料1 项目搭建1.1 环境安装1.2 项目源码1.3 模型下载1.4 目录结构 2 改进部分2.1 可以实现更多模型的切换2.2 固定随机种子&#xff0c;保证输出的数据一致2.3 增加了另一个数据集进行联合训练2.4 模型测试时选择最好的一个模型而非最后一个 3 实验结果 0 资料 这是一…
阅读更多...
最新文章

Copyright @ 2022~2023