免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 文库 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 2808 | 回复: 3

[算法] [分享]利用链表设计缓存,在内存碎片化环境中更好用 [复制链接]

求职 : 软件工程师
论坛徽章:
3
程序设计版块每日发帖之星
日期:2015-10-07 06:20:00程序设计版块每日发帖之星
日期:2015-12-13 06:20:00程序设计版块每日发帖之星
日期:2016-05-05 06:20:00
发表于 2018-09-17 08:50 |显示全部楼层
在内存碎片化严重的环境中,设计未知长度的缓存,是个值得考虑的问题:
首先设计一个链表:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. void *apply_mem(int size) {
  5.   void *ptr = malloc(size);
  6.   if (ptr == NULL) error("apply memory fail!");
  7.   return ptr;
  8. }

  9. struct snode {
  10.   char* str;
  11.   struct snode *next;
  12. };

  13. typedef struct snode Snode;

  14. Snode* newSnode(void) {
  15.   Snode* nnode = apply_mem(sizeof(struct snode));
  16.   nnode->next = NULL;
  17.   return nnode;
  18. }

  19. struct strs {
  20.   struct snode* front;
  21.   struct snode* back;
  22.   int len;
  23. };

  24. typedef struct strs Strs;

  25. Strs* newStrs(void) {
  26.   Strs* ss = apply_mem(sizeof(struct strs));
  27.   ss->front = NULL;
  28.   ss->len = 0;
  29.   return ss;
  30. }

  31. void push(Strs* ss, char* str) {
  32.   Snode* nnode = newSnode();
  33.   nnode->str = str;
  34.   if (ss->len == 0) {
  35.     ss->back = nnode;
  36.     ss->front = nnode;
  37.   } else {
  38.     ss->back->next = nnode;
  39.     ss->back = nnode;
  40.   }
  41.   ss->len++;  
  42. }

  43. void shift(Strs* ss) {
  44.   Snode* fnode = ss->front;
  45.   ss->front = fnode->next;
  46.   ss->len--;
  47.   free(fnode);
  48. }
复制代码
这个链表是从后面添加新的元素,这样遍历就是实现了先进先出。
然后设计缓存,每个片段的长度是 64 位,正好是 64 位计算机的一个地址的长度:

  1. struct buffer {
  2.   int off;
  3.   int len;
  4.   char* str;
  5.   Strs* strs;
  6. };

  7. typedef struct buffer Buffer;

  8. Buffer* newBuffer() {
  9.   Buffer* buf = apply_mem(sizeof(struct buffer));
  10.   buf->str = (char*)apply_mem(64);
  11.   buf->off = 0;
  12.   buf->len = 0;
  13.   buf->strs = newStrs();
  14.   return buf;
  15. }

  16. void push_char(Buffer* buf, char ch) {
  17.   buf->str[buf->off] = ch;
  18.   buf->off++; buf->len++;
  19.   if (buf->off == 64) {
  20.     push(buf->strs, buf->str);
  21.     buf->str = (char*)apply_mem(64);
  22.     buf->off = 0;
  23.   }
  24. }

  25. void push_chars(Buffer* buf, char* s) {
  26.   int n = strlen(s); int i = 0;
  27.   while (i < n) { push_char(buf, s[i]); i++; }
  28. }

  29. char* string(Buffer* buf) {
  30.   char* str = apply_mem(buf->len + 1);
  31.   int n = buf->strs->len;
  32.   int si = 0; int i = 0; int m = 0;
  33.   while (i < n) {
  34.     char* s = front(buf->strs); i++;
  35.     shift(buf->strs);
  36.     for (m = 0; m < 64; m++) {
  37.       str[si] = s[m]; si++;
  38.     }
  39.     free(s);
  40.   }
  41.   n = buf->off;
  42.   char* cs = buf->str;
  43.   for (i = 0; i < n; i++) {
  44.     str[si] = cs[i]; si++;
  45.   }
  46.   str[si] = SOF;
  47.   free(buf->str); free(buf); return str;
  48. }
复制代码
这样,用碎片来做缓存,不需要用 realloc 来重新申请内存,减少了内存申请失败的可能性,也避免因为不知道数据的大小,而设置缓存初始化空间过大或过小的问题。
顺便添加几个利用缓存设计的函数:

  1. char* readfile(char* fname) {
  2.   Buffer* buf = newBuffer();
  3.   FILE* fh = fopen(fname, "r");
  4.   if (fh == NULL) {
  5.     printf("file %s not exists!\n", fname);
  6.     exit(1);
  7.   }
  8.   while (!feof(fh)) {
  9.     char ch = fgetc(fh);
  10.     if (ch == '\r') continue;
  11.     if (ch < 0) continue;
  12.     push_char(buf, ch);
  13.   }
  14.   fclose(fh);
  15.   return string(buf);
  16. }
复制代码

  1. char* readline(void) {
  2.   Buffer* buf = newBuffer();
  3.   int i = 0;
  4.   while (i < 99) {
  5.     char c = getchar(); i++;
  6.     if (c < 10 || c > 127) continue;
  7.     if (c == '\r' || c == '\n') break;
  8.     push_char(buf,c);
  9.   }
  10.   return string(buf);
  11. }
复制代码


论坛徽章:
0
发表于 2018-10-12 18:27 |显示全部楼层
做内存池就好

论坛徽章:
43
15-16赛季CBA联赛之四川
日期:2018-10-13 23:26:5015-16赛季CBA联赛之新疆
日期:2016-04-25 10:55:452016科比退役纪念章
日期:2016-04-23 00:51:2315-16赛季CBA联赛之山东
日期:2016-04-17 12:00:2815-16赛季CBA联赛之福建
日期:2016-04-12 15:21:2915-16赛季CBA联赛之辽宁
日期:2016-03-24 21:38:2715-16赛季CBA联赛之福建
日期:2016-03-18 12:13:4015-16赛季CBA联赛之佛山
日期:2016-02-05 00:55:2015-16赛季CBA联赛之佛山
日期:2016-02-04 21:11:36程序设计版块每日发帖之星
日期:2016-07-02 06:20:0015-16赛季CBA联赛之天津
日期:2016-11-02 00:33:1215-16赛季CBA联赛之浙江
日期:2017-01-13 01:31:49
发表于 2018-10-14 22:24 |显示全部楼层
其实要避免内存碎片,在64位环境下最省事的办法是mmap。

论坛徽章:
131
操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57数据库技术版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:052022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:57IT运维版块每日发帖之星
日期:2016-05-11 17:06:49操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57程序设计版块每日发帖之星
日期:2016-05-11 17:06:57
发表于 2018-10-21 23:45 |显示全部楼层
Unix is like a wigwam -- no Gates, no Windows, and an Apache inside.
Unix is very user-friendly. It`s just picky who its friends are.
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

数据风云,十年变迁
DTCC 第十届中国数据库技术大会已启航!

2019年5月8日~5月10日,由IT168旗下ITPUB企业社区平台主办的第十届中国数据库技术大会(DTCC2019),将在北京隆重召开。大会将邀请百余位行业专家,就热点技术话题进行分享,是广大数据领域从业人士的又一次年度盛会和交流平台。与SACC2018类似,本届大会将采用“3+2”模式:3天传统技术演讲+2天深度主题培训。大会不仅提供超100场的主题演讲,还会提供连续2天的深度课程培训,深化数据领域的项目落地实践方案。
DTCC2019,一场值得期待的数据技术盛会,殷切地希望您报名参与!

活动入口>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP