数据结构：缓冲区/缓存简单实现
本文共 11089 字，大约阅读时间需要 36 分钟。
-
简单图解
缓冲区内部：容量为 capacity 的 内存块 可以看作 长度为 capacity 的 字节数组
读/写指针的变化：版本二中的读写操作函数使用 memcpy 函数复制内存，当写指针在读指针右边时，读取操作最多调用 1 次 memcpy 函数，而写入操作最多调用 2 次 memcpy 函数。当写指针在读指针左边时，读取操作最多调用两次 memcpy 函数，而写入操作最多调用 1 次 memcpy 函数。 
-
（读写操作，版本一：函数内部 每次读/写一个字节，操作大量数据时效率很低）
利用 取余运算 使得读/写指针在长度为 capacity 的连续内存空间上循环进行读/写操作 -
（读写操作，版本二：使用 memcpy 函数复制内存 ，效率高）
-
（读写操作，版本三：线程安全版本，可以使用互斥量并委托使用版本二的读写函数作简单实现）
目录
- 头文件 buffer.h
- 源文件 buffer.c
- 简单测试 test.c
1. 头文件 buffer.h
/* buffer.h */#include#include #include #include struct buffer { /* 缓冲区容量，用于 malloc 申请内存空间 */ size_t capacity; /* 累计所有写入操作实际写入的字节总数，其对 capacity 取余即为‘下一个写入位置’ */ size_t byte_writed_count; /* 累计所有读取操作实际读取的字节总数，其对 capacity 取余即为‘下一个读取位置’ */ size_t byte_readed_count; /* 指向实际缓冲区 */ char *data;};/* 初始化缓冲区 buf，使用指定容量 capacity 申请内存空间 */void buffer_init(struct buffer *buf, size_t capacity);/* 版本一：读写函数，内部每次读写一个字节， 将指针 chars 指向的长度为 len 的数据写入缓冲区 buf， 返回值：实际写入的字节数，可能小于 len，当缓冲区可写空间不足时。 */size_t buffer_write(struct buffer *buf, char *chars, size_t len);/* 从缓冲区 buf 中读取长度为 len 的数据到指针 chars 指向的空间， 返回值：实际读取的字节数，可能小于 len，当缓冲区没有足够的数据时。 */size_t buffer_read(struct buffer *buf, char *chars, size_t len);/* 版本二：读/写函数，内部使用 memcpy 函数进行内存复制，效率高 */size_t buffer_write_by_memcpy(struct buffer *buf, char *chars, size_t len);size_t buffer_read_by_memcpy(struct buffer *buf, char *chars, size_t len);/* （待实现）版本三：线程安全版本 （待实现）线程安全写，应与线程安全读 buffer_pread 配合使用 */// size_t buffer_pwrite(struct buffer *buf, char *chars, size_t len);/* （待实现）线程安全读，应与线程安全写 buffer_pwrite 配合使用 */// size_t buffer_pread(struct buffer *buf, char *chars, size_t len);/* 返回值：缓冲区中已缓存的（可读取）字节数 */size_t buffer_available_read(struct buffer *buf);/* 返回值：缓冲区可写入的字节数 */size_t buffer_available_write(struct buffer *buf);/* 返回值：缓冲区容量 capacity */size_t buffer_capacity(struct buffer *buf);/* 清空缓冲区，实际上仅仅重置读/写指针，缓冲区容量不变 */void buffer_clear(struct buffer *buf);/* 销毁/释放缓冲区，free 内存资源 */void buffer_destroy(struct buffer *buf);/* 简单错误日志输出至 stderr */void errlog(const char *msg);/* 简单日志输出至 stdout */void infolog(const char *msg);
2. 源文件 buffer.c
/* buffer.c */#include "buffer.h"// 初始化缓冲区 buf，使用指定容量 capacity 申请内存空间void buffer_init(struct buffer *buf, size_t capacity){ if(buf == NULL || capacity <= 0){ errlog("Invalid argument."); // error errno = EINVAL; // // Invalid argument exit(EXIT_FAILURE); } // 实际分配内存 buf -> data = malloc(capacity); if(buf -> data == NULL){ errlog("Cannot allocate memory: unknown error."); // error errno = ENOMEM; exit(EXIT_FAILURE); } buf -> capacity = capacity; buf -> byte_readed_count = 0; buf -> byte_writed_count = 0; }// 版本一，内部每次读/写一个字节，效率低// 将指针 chars 指向的长度为 len 的数据写入缓冲区 buf，// 返回值：实际写入的字节数，可能小于 len，当缓冲区可写空间不足时。size_t buffer_write(struct buffer *buf, char *chars, size_t len){ if(buffer_available_write(buf) == 0){ return 0; } if(buf != NULL && chars != NULL && len > 0){ int i = 0; for(;i < len && buffer_available_write(buf) > 0;i++, buf -> byte_writed_count ++){ // 每次写入一个字节 (buf -> data)[buf -> byte_writed_count % buf -> capacity] = *(chars + i); } return i; }else{ errlog("Invalid argument"); // error errno = EINVAL; exit(EXIT_FAILURE); }}// 版本一，内部每次读/写一个字节，效率低// 从缓冲区 buf 中读取长度为 len 的数据到指针 chars 指向的空间，// 返回值：实际读取的字节数，可能小于 len，当缓冲区没有足够的数据时。size_t buffer_read(struct buffer *buf, char *chars, size_t len){ if(buffer_available_read(buf) == 0){ return 0; } if(buf != NULL && chars != NULL && len > 0){ int i = 0; for(;i < len && buffer_available_read(buf) > 0;i++, buf -> byte_readed_count ++){ // 每次读取一个字节 *(chars + i) = (buf -> data)[buf -> byte_readed_count % buf -> capacity]; } return i; }else{ errlog("Invalid argument"); // error errno = EINVAL; exit(EXIT_FAILURE); }}// 版本二，使用 memcpy 函数复制内存，效率高size_t buffer_write_by_memcpy(struct buffer *buf, char *chars, size_t len){ if(buffer_available_write(buf) == 0){ return 0; } if(buf != NULL && chars != NULL && len > 0){ // int avail_write_count = buffer_available_write(buf); int next_write_index = (buf -> byte_writed_count) % (buf -> capacity); int first_count = (buf -> capacity) - next_write_index; if(avail_write_count <= first_count){ // ‘可写区域’分布在写指针右侧，即：memcpy 函数最多可执行 1 次 int write_count; if(avail_write_count <= len){ write_count = avail_write_count; }else{ write_count = len; } memcpy(&(buf -> data)[next_write_index], chars, write_count); buf -> byte_writed_count += write_count; return write_count; }else{ // avail_write_count > first_count // ‘可写区域’分布在写指针两侧，即：memcpy 函数最多可执行 2 次 if(len <= first_count){ memcpy(&(buf -> data)[next_write_index], chars, len); buf -> byte_writed_count += len; return len; }else{ // first write memcpy(&(buf->data)[next_write_index], chars, first_count); buf->byte_writed_count += first_count; int write_count; if (avail_write_count >= len){ write_count = len - first_count; }else{ // avail_write_count < len write_count = avail_write_count - first_count; } // second write memcpy(&(buf->data)[0], &chars[first_count], write_count); buf->byte_writed_count += write_count; return first_count + write_count; } } }else{ errlog("Invalid argument"); // error errno = EINVAL; exit(EXIT_FAILURE); }}// 版本二，使用 memcpy 函数复制内存，效率高size_t buffer_read_by_memcpy(struct buffer *buf, char *chars, size_t len){ if(buffer_available_read(buf) == 0){ return 0; } if(buf != NULL && chars != NULL && len > 0){ // int avail_read_count = buffer_available_read(buf); int next_read_index = (buf -> byte_readed_count) % (buf -> capacity); int first_count = (buf -> capacity) - next_read_index; if(avail_read_count <= first_count){ // ‘可读区域’分布在读指针右侧，即：memcpy 函数最多可执行 1 次 int read_count; if(avail_read_count <= len){ read_count = avail_read_count; }else{ read_count = len; } memcpy(chars, &(buf -> data)[next_read_index], read_count); buf -> byte_readed_count += read_count; return read_count; }else{ // avail_read_count > first_count // ‘可读区域’分布在读指针两侧，即：memcpy 函数最多可执行 2 次 if(len <= first_count){ memcpy(chars, &(buf -> data)[next_read_index], len); buf -> byte_readed_count += len; return len; }else{ // first write memcpy(chars, &(buf -> data)[next_read_index], first_count); buf->byte_readed_count += first_count; int read_count; if (avail_read_count >= len){ read_count = len - first_count; }else{ // avail_read_count < len read_count = avail_read_count - first_count; } // second write memcpy(&chars[first_count], &(buf->data)[0], read_count); buf->byte_readed_count += read_count; return first_count + read_count; } } }else{ errlog("Invalid argument"); // error errno = EINVAL; exit(EXIT_FAILURE); }}// 返回值：缓冲区中已缓存的（可读取）字节数size_t buffer_available_read(struct buffer *buf){ if(buf != NULL){ return (buf -> byte_writed_count) - (buf -> byte_readed_count); }else{ return 0; }}// 返回值：缓冲区可写入的字节数size_t buffer_available_write(struct buffer *buf){ if(buf != NULL){ return (buf -> capacity) - ((buf -> byte_writed_count) - (buf -> byte_readed_count)); }else{ return 0; }}// 返回值：缓冲区容量 capacitysize_t buffer_capacity(struct buffer *buf){ if(buf != NULL){ return buf -> capacity; }else{ return 0; }}// 清空缓冲区，实际上仅仅重置读/写指针，缓冲区容量不变void buffer_clear(struct buffer *buf){ if(buf != NULL){ buf -> byte_readed_count = 0; buf -> byte_writed_count = 0; }}// 销毁/释放缓冲区，free 内存资源void buffer_destroy(struct buffer *buf){ if(buf != NULL){ buf -> capacity = 0; free(buf -> data); }}// 简单错误日志输出void errlog(const char *msg){ fprintf(stderr, "error: %s\n", msg);}// 简单日志输出void infolog(const char *msg){ fprintf(stdout, "info: %s\n", msg);} 3. 简单测试
/* test.c */#include "buffer.h"/* 简单测试 */void main(){ // 1 // test func: errlog // errlog("invalid arguments"); // infolog("this is hello"); // 2 // test func buffer_init struct buffer buf; char str[1024]; long int res; buffer_init(&buf, 10); printf("buffer capacity is %ld bytes\n", buf.capacity); printf("writed %ld\n", buffer_write(&buf, "abc", 3)); printf("1 - buffer_available_read is %ld bytes\n", buffer_available_read(&buf)); printf("1 - buffer_available_write is %ld bytes\n", buffer_available_write(&buf)); res = buffer_read(&buf, str, res = buffer_available_read(&buf)); str[res] = '\0'; printf("readed str: %s\n", str); printf("2 - buffer_available_read is %ld bytes\n", buffer_available_read(&buf)); printf("2 - buffer_available_write is %ld bytes\n", buffer_available_write(&buf)); // printf("writed %ld\n", buffer_write(&buf, "abc123456789xyz", 10)); printf("writed %ld\n", buffer_write(&buf, "abc123456789xyz", 10)); printf("3 - buffer_available_read is %ld bytes\n", buffer_available_read(&buf)); printf("3 - buffer_available_write is %ld bytes\n", buffer_available_write(&buf)); res = buffer_read(&buf, str, res = buffer_available_read(&buf)); str[res] = '\0'; printf("readed str: %s\n", str); printf("4 - buffer_available_read is %ld bytes\n", buffer_available_read(&buf)); printf("4 - buffer_available_write is %ld bytes\n", buffer_available_write(&buf)); buffer_clear(&buf); buffer_destroy(&buf);} 运行测试，执行结果如下：
ubuntu@cuname:~/dev/beginning-linux-programming/test$ gcc -o test test.c buffer.cubuntu@cuname:~/dev/beginning-linux-programming/test$ ./testbuffer capacity is 10 byteswrited 31 - buffer_available_read is 3 bytes1 - buffer_available_write is 7 bytesreaded str: abc2 - buffer_available_read is 0 bytes2 - buffer_available_write is 10 byteswrited 10writed 03 - buffer_available_read is 10 bytes3 - buffer_available_write is 0 bytesreaded str: abc12345674 - buffer_available_read is 0 bytes4 - buffer_available_write is 10 bytes
转载地址：http://aclsi.baihongyu.com/
你可能感兴趣的文章
vue2.* 中 使用socket.io
查看>>
openlayers安装引用
查看>>
js报错显示subString/subStr is not a function
查看>>
高德地图js API实现鼠标悬浮于点标记时弹出信息窗体显示详情，点击点标记放大地图操作
查看>>
初始化VUE项目报错
查看>>
vue项目使用安装sass
查看>>
HTTP和HttpServletRequest 要点
查看>>
HttpServletResponse 要点
查看>>
Qt中的QString和QStringList常用方法
查看>>
Quick QML 一个QML调用另一个文件夹下的QML方法
查看>>
leetcode----63. Unique Paths II
查看>>
leetcode----89. Gray Code
查看>>
leetcode----90. Subsets II
查看>>
leetcode----91. Decode Ways
查看>>
leetcode----92. Reverse Linked List II
查看>>
leetcode----93. Restore IP Addresses
查看>>
leetcode----94. Binary Tree Inorder Traversal
查看>>
leetcode----96. Unique Binary Search Trees
查看>>
leetcode----95. Unique Binary Search Trees II
查看>>
leetcode----98. Validate Binary Search Tree
查看>>