[分享]利用链表设计缓存，在内存碎片化环境中更好用

104359176

在内存碎片化严重的环境中，设计未知长度的缓存，是个值得考虑的问题：
首先设计一个链表：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. void *apply_mem(int size) {
   
6.   void *ptr = malloc(size);
   
7.   if (ptr == NULL) error("apply memory fail!");
   
8.   return ptr;
   
9. }
   
10. 
    
11. struct snode {
    
12.   char* str;
    
13.   struct snode *next;
    
14. };
    
15. 
    
16. typedef struct snode Snode;
    
17. 
    
18. Snode* newSnode(void) {
    
19.   Snode* nnode = apply_mem(sizeof(struct snode));
    
20.   nnode->next = NULL;
    
21.   return nnode;
    
22. }
    
23. 
    
24. struct strs {
    
25.   struct snode* front;
    
26.   struct snode* back;
    
27.   int len;
    
28. };
    
29. 
    
30. typedef struct strs Strs;
    
31. 
    
32. Strs* newStrs(void) {
    
33.   Strs* ss = apply_mem(sizeof(struct strs));
    
34.   ss->front = NULL;
    
35.   ss->len = 0;
    
36.   return ss;
    
37. }
    
38. 
    
39. void push(Strs* ss, char* str) {
    
40.   Snode* nnode = newSnode();
    
41.   nnode->str = str;
    
42.   if (ss->len == 0) {
    
43.     ss->back = nnode;
    
44.     ss->front = nnode;
    
45.   } else {
    
46.     ss->back->next = nnode;
    
47.     ss->back = nnode;
    
48.   }
    
49.   ss->len++;  
    
50. }
    
51. 
    
52. void shift(Strs* ss) {
    
53.   Snode* fnode = ss->front;
    
54.   ss->front = fnode->next;
    
55.   ss->len--;
    
56.   free(fnode);
    
57. }
    

复制代码

这个链表是从后面添加新的元素，这样遍历就是实现了先进先出。
然后设计缓存，每个片段的长度是 64 位，正好是 64 位计算机的一个地址的长度：

1. 
   
2. struct buffer {
   
3.   int off;
   
4.   int len;
   
5.   char* str;
   
6.   Strs* strs;
   
7. };
   
8. 
   
9. typedef struct buffer Buffer;
   
10. 
    
11. Buffer* newBuffer() {
    
12.   Buffer* buf = apply_mem(sizeof(struct buffer));
    
13.   buf->str = (char*)apply_mem(64);
    
14.   buf->off = 0;
    
15.   buf->len = 0;
    
16.   buf->strs = newStrs();
    
17.   return buf;
    
18. }
    
19. 
    
20. void push_char(Buffer* buf, char ch) {
    
21.   buf->str[buf->off] = ch;
    
22.   buf->off++; buf->len++;
    
23.   if (buf->off == 64) {
    
24.     push(buf->strs, buf->str);
    
25.     buf->str = (char*)apply_mem(64);
    
26.     buf->off = 0;
    
27.   }
    
28. }
    
29. 
    
30. void push_chars(Buffer* buf, char* s) {
    
31.   int n = strlen(s); int i = 0;
    
32.   while (i < n) { push_char(buf, s[i]); i++; }
    
33. }
    
34. 
    
35. char* string(Buffer* buf) {
    
36.   char* str = apply_mem(buf->len + 1);
    
37.   int n = buf->strs->len;
    
38.   int si = 0; int i = 0; int m = 0;
    
39.   while (i < n) {
    
40.     char* s = front(buf->strs); i++;
    
41.     shift(buf->strs);
    
42.     for (m = 0; m < 64; m++) {
    
43.       str[si] = s[m]; si++;
    
44.     }
    
45.     free(s);
    
46.   }
    
47.   n = buf->off;
    
48.   char* cs = buf->str;
    
49.   for (i = 0; i < n; i++) {
    
50.     str[si] = cs[i]; si++;
    
51.   }
    
52.   str[si] = SOF;
    
53.   free(buf->str); free(buf); return str;
    
54. }
    

复制代码

这样，用碎片来做缓存，不需要用 realloc 来重新申请内存，减少了内存申请失败的可能性，也避免因为不知道数据的大小，而设置缓存初始化空间过大或过小的问题。
顺便添加几个利用缓存设计的函数：

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

复制代码

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

复制代码

ulver

做内存池就好

windoze

其实要避免内存碎片，在64位环境下最省事的办法是mmap。

shang2010

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.