C.Interface.And.Implementations—table(key-value系统)的实现

2024-08-24 18:18

本文主要是介绍C.Interface.And.Implementations—table(key-value系统)的实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1、An  associative table is a set of key-value pairs. It’s like an array except that the indices can be values of any type.


C语言中宏的作用域是文件或者遇到undef为止。


table的实现是以哈希表和链表实现。内存形式如下:



===========================table.h===============================

#ifndef TABLE_INCLUDED
#define TABLE_INCLUDED#define T Table_T
typedef struct T *T;//exported functions
extern T    Table_new(int hint, int cmp(const void *x, const void *y),unsigned hash(const void *key));extern void   Table_free(T *table);extern int    Table_length(T table);
extern void  *Table_put   (T table, const void *key,void *value);
extern void  *Table_get   (T table, const void *key);
extern void  *Table_remove(T table, const void *key);
extern void   Table_map   (T table, void apply(const void *key, void **value, void *cl),void *cl);
extern void **Table_toArray(T table, void *end);#undef T
#endif

=========================table.c===============================

#include <limits.h>
#include <stddef.h>
#include "mem.h"
#include "assert.h"
#include "table.h"#define T Table_T//types
struct T{//fieldsint size;int (*cmp)(const void *x, const void *y);unsigned (*hash)(const void *key);int length;unsigned timestamp;struct binding{struct binding *link;const void *key;void *value;} **buckets;
};//static functions
static int cmpatom(const void *x, const void *y){return x != y;
}static unsigned hashatom(const void *key){return (unsigned long)key>>2;
}//functions
T Table_new(int hint,int cmp(const void *x, const void *y),unsigned hash(const void *key)){T table;int i;static int primes[] = {509, 509, 1021, 2053, 4093,8191, 16383, 32771, 65521, INT_MAX };assert(hint >= 0);for(i = 1; primes[i] < hint; ++i);table = ALLOC(sizeof(*table) + primes[i-1]*sizeof(table->buckets[0]));table->size = primes[i-1];table->cmp = cmp ? cmp : cmpatom;table->hash = hash ? hash : hashatom;table->buckets = (struct binding **)(table + 1);for(i = 0; i < table->size; ++i)table->buckets[i] = NULL;table->length = 0;table->timestamp = 0;return table;
}void *Table_get(T table, const void *key){int i;struct binding *p;assert(table);assert(key);i = (*table->hash)(key)%table->size;for(p = table->buckets[i]; p; p = p->link){if((*table->cmp)(key,p->key) == 0 )break;}return p ? p->value : NULL;
}void *Table_put(T table, const void *key, void *value){int i;struct binding *p;void *prev;assert(table);assert(key);//search table for keyi = (*table->hash)(key)%table->size;for(p = table->buckets[i]; p; p = p->link){if((*table->cmp)(key,p->key) == 0)break;}if(p == NULL){NEW(p);p->key = key;p->link = table->buckets[i];table->buckets[i] = p;table->length++;prev = NULL;}else{prev = p->value;}p->value = value;table->timestamp++;return prev;
}int Table_length(T table){assert(table);return table->length;
}void Table_map(T table,void apply(const void *key, void **value, void *cl),void *cl){int i;unsigned stamp;struct binding *p;assert(table);assert(apply);stamp = table->timestamp;for(i = 0; i < table->size; ++i){for(p = table->buckets[i]; p; p = p->link){apply(p->key, &p->value, cl);assert(table->timestamp == stamp);}}
}void *Table_remove(T table, const void *key){int i;struct binding **pp;assert(table);assert(key);table->timestamp++;i = (*table->hash)(key)%table->size;for(pp = &table->buckets[i]; *pp; pp = &(*pp)->link){if((*table->cmp)(key, (*pp)->key) == 0){struct binding *p = *pp;void *value = p->value;*pp = p->link;FREE(p);table->length--;return value;}}return NULL;
}void **Table_toArray(T table, void *end){int i, j = 0;void **array;struct binding *p;assert(table);array = ALLOC((2*table->length + 1)*sizeof(*array));for(i = 0; i < table->size; ++i){for(p = table->buckets[i]; p; p = p->link){array[j++] = (void *)p->key;array[j++] = p->value;}}array[j] = end;return array;
}void Table_free(T *table){assert(table && *table);if((*table)->length > 0){int i;struct binding *p, *q;for(i = 0; i < (*table)->size; ++i){for(p = (*table)->buckets[i]; p; p = q){q = p->link;FREE(p);}}}FREE(*table);
}


这篇关于C.Interface.And.Implementations—table(key-value系统)的实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1103234

相关文章

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发,所以面试百分百会问到

Go语言并发之通知退出机制的实现

《Go语言并发之通知退出机制的实现》本文主要介绍了Go语言并发之通知退出机制的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、通知退出机制1.1 进程/main函数退出1.2 通过channel退出1.3 通过cont

Python实现PDF按页分割的技术指南

《Python实现PDF按页分割的技术指南》PDF文件处理是日常工作中的常见需求,特别是当我们需要将大型PDF文档拆分为多个部分时,下面我们就来看看如何使用Python创建一个灵活的PDF分割工具吧... 目录需求分析技术方案工具选择安装依赖完整代码实现使用说明基本用法示例命令输出示例技术亮点实际应用场景扩

java如何实现高并发场景下三级缓存的数据一致性

《java如何实现高并发场景下三级缓存的数据一致性》这篇文章主要为大家详细介绍了java如何实现高并发场景下三级缓存的数据一致性,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 下面代码是一个使用Java和Redisson实现的三级缓存服务,主要功能包括:1.缓存结构:本地缓存:使

如何在Java Spring实现异步执行(详细篇)

《如何在JavaSpring实现异步执行(详细篇)》Spring框架通过@Async、Executor等实现异步执行,提升系统性能与响应速度,支持自定义线程池管理并发,本文给大家介绍如何在Sprin... 目录前言1. 使用 @Async 实现异步执行1.1 启用异步执行支持1.2 创建异步方法1.3 调用

Spring Boot配置和使用两个数据源的实现步骤

《SpringBoot配置和使用两个数据源的实现步骤》本文详解SpringBoot配置双数据源方法,包含配置文件设置、Bean创建、事务管理器配置及@Qualifier注解使用,强调主数据源标记、代... 目录Spring Boot配置和使用两个数据源技术背景实现步骤1. 配置数据源信息2. 创建数据源Be

在MySQL中实现冷热数据分离的方法及使用场景底层原理解析

《在MySQL中实现冷热数据分离的方法及使用场景底层原理解析》MySQL冷热数据分离通过分表/分区策略、数据归档和索引优化,将频繁访问的热数据与冷数据分开存储,提升查询效率并降低存储成本,适用于高并发... 目录实现冷热数据分离1. 分表策略2. 使用分区表3. 数据归档与迁移在mysql中实现冷热数据分

linux批量替换文件内容的实现方式

《linux批量替换文件内容的实现方式》本文总结了Linux中批量替换文件内容的几种方法,包括使用sed替换文件夹内所有文件、单个文件内容及逐行字符串,强调使用反引号和绝对路径,并分享个人经验供参考... 目录一、linux批量替换文件内容 二、替换文件内所有匹配的字符串 三、替换每一行中全部str1为st

SpringBoot集成MyBatis实现SQL拦截器的实战指南

《SpringBoot集成MyBatis实现SQL拦截器的实战指南》这篇文章主要为大家详细介绍了SpringBoot集成MyBatis实现SQL拦截器的相关知识,文中的示例代码讲解详细,有需要的小伙伴... 目录一、为什么需要SQL拦截器?二、MyBATis拦截器基础2.1 核心接口:Interceptor

SpringBoot集成EasyPoi实现Excel模板导出成PDF文件

《SpringBoot集成EasyPoi实现Excel模板导出成PDF文件》在日常工作中,我们经常需要将数据导出成Excel表格或PDF文件,本文将介绍如何在SpringBoot项目中集成EasyPo... 目录前言摘要简介源代码解析应用场景案例优缺点分析类代码方法介绍测试用例小结前言在日常工作中,我们经