libsvm代码阅读(3):关于Cache类的分析

下面来分析Cache类的源码,该类位于svm.cpp中。这个类的主要功能是:负责运算所涉及的内存管理,包括申请、释放等。

简单来说:这个Cache类,首先通过Cache构造函数申请一块空间,这块空间的大小是:L个head_t大小的空间。然后get_data函数保证结构head_t中至少有len个float的内存,并且将可以使用的内存块的指针放在data指针中;而swap_index函数则是用于交换head[i]和head[j]。

Cache类的定义如下:

 

[cpp]       view plain   copy   技术分享   技术分享  

<EMBED id=ZeroClipboardMovie_1 height=18 name=ZeroClipboardMovie_1 type=application/x-shockwave-flash align=middle pluginspage=http://www.macromedia.com/go/getflashplayer width=18 src=http://static.blog.csdn.net/scripts/ZeroClipboard/ZeroClipboard.swf wmode="transparent" flashvars="id=1&width=18&height=18" allowfullscreen="false" allowscriptaccess="always" bgcolor="#ffffff" quality="best" menu="false" loop="false">

  1. class Cache  

  2. {  

  3. public:  

  4.     Cache(int l,long int size);  

  5.     ~Cache();  

  6.   

  7.     // request data [0,len)  

  8.     // return some position p where [p,len) need to be filled  

  9.     // (p >= len if nothing needs to be filled)  

  10.     int get_data(const int index, Qfloat **data, int len);  

  11.     void swap_index(int i, int j);    

  12. private:  

  13.     int l;  

  14.     long int size;//所指定的全部内存,据说用Mb做单位  

  15.     //结构head_t用来记录所申请内存的指针,并记录长度,而且通过双向的指针,形成链表,增加寻址的速度  

  16.     struct head_t  

  17.     {  

  18.         head_t *prev, *next;    // a circular list是一个双向链表,非循环链表  

  19.         Qfloat *data;  

  20.         int len;        // data[0,len) is cached in this entry  

  21.     };  

  22.   

  23.     head_t *head;//变量指针,该指针记录程序中所申请的内存。  

  24.     head_t lru_head;//双向链表的表头  

  25.     void lru_delete(head_t *h);//从双向链表中删去某个元素的链接,一般是删去当前所指向的元素  

  26.     void lru_insert(head_t *h);//在链表后面插入一个新的链接  

  27. };  

主要包含:

  1. 两个int变量,分别是l和size,l是样本个数,size是指定的全部内存;

  2. 一个构造函数Cache,该函数根据样本数l申请L个head_t的空间;

  3. 一个析构函数~Cache,不用多说;

  4. 一个双向链表的结构head_t;

  5. 一个get_data函数,具体下文再说;

  6. 一个swap_index函数,交换两个head_t的值;

  7. 一个双向链表的删除函数lru_delete,一个插入函数lru_insert;

  8. 一个变量指针head,该指针指向程序中所申请的内存。

关于上面的结构体head_t,它是一个双向链表方便前后内存的访问,在文献LIBSVM:A  Libray for SVM中如下说法:

技术分享

 

构造函数的代码如下:

[cpp]       view plain   copy   技术分享   技术分享  

<EMBED id=ZeroClipboardMovie_2 height=18 name=ZeroClipboardMovie_2 type=application/x-shockwave-flash align=middle pluginspage=http://www.macromedia.com/go/getflashplayer width=18 src=http://static.blog.csdn.net/scripts/ZeroClipboard/ZeroClipboard.swf wmode="transparent" flashvars="id=2&width=18&height=18" allowfullscreen="false" allowscriptaccess="always" bgcolor="#ffffff" quality="best" menu="false" loop="false">

  1. Cache::Cache(int l_,long int size_):l(l_),size(size_)  

  2. {  

  3.     //calloc函数的功能与malloc函数的功能相似,都是从堆分配内存该函数与malloc函数的一个显著不同时  

  4.     //是,calloc函数得到的内存空间是经过初始化的,其内容全为0。  

  5.     head = (head_t *)calloc(l,sizeof(head_t));  // initialized to 0  

  6.     size /= sizeof(Qfloat);//先将原来byte数目转化为float的数目。  

  7.     size -= l * sizeof(head_t) / sizeof(Qfloat);//扣除掉L个head_t的内存数目  

  8.     size = max(size, 2 * (long int) l); // cache must be large enough for two columns  

  9.     lru_head.next = lru_head.prev = &lru_head;  

  10. }  

该函数根据实参:样本数L,申请L个head_t的空间,初始化为0;size的处理是:先将输入的size值(byte单位)转化为float的数目,然后再减去L个head_t所占的空间;其中lru_head因为尚没有head_t中申请到内存,故双向链表指向自己。

析构函数的代码如下:

 

[cpp]       view plain   copy   技术分享   技术分享  

<EMBED id=ZeroClipboardMovie_3 height=18 name=ZeroClipboardMovie_3 type=application/x-shockwave-flash align=middle pluginspage=http://www.macromedia.com/go/getflashplayer width=18 src=http://static.blog.csdn.net/scripts/ZeroClipboard/ZeroClipboard.swf wmode="transparent" flashvars="id=3&width=18&height=18" allowfullscreen="false" allowscriptaccess="always" bgcolor="#ffffff" quality="best" menu="false" loop="false">

  1. Cache::~Cache()  

  2. {  

  3.     for(head_t *h = lru_head.next; h != &lru_head; h=h->next)  

  4.         free(h->data);  

  5.     free(head);  

  6. }  

这个很简单,不用多说。

 

双向链表的删去函数代码:

 

[cpp]       view plain   copy   技术分享   技术分享  

<EMBED id=ZeroClipboardMovie_4 height=18 name=ZeroClipboardMovie_4 type=application/x-shockwave-flash align=middle pluginspage=http://www.macromedia.com/go/getflashplayer width=18 src=http://static.blog.csdn.net/scripts/ZeroClipboard/ZeroClipboard.swf wmode="transparent" flashvars="id=4&width=18&height=18" allowfullscreen="false" allowscriptaccess="always" bgcolor="#ffffff" quality="best" menu="false" loop="false">

  1. void Cache::lru_delete(head_t *h)  

  2. {  

  3.     // delete from current location  

  4.     h->prev->next = h->next;  

  5.     h->next->prev = h->prev;  

  6. }  

该函数用于后面swap_index函数断开双向链表的实现。只是断开链接,没有删去数据。

 

双向链表的插入函数代码:

 

[cpp]       view plain   copy   技术分享   技术分享  

<EMBED id=ZeroClipboardMovie_5 height=18 name=ZeroClipboardMovie_5 type=application/x-shockwave-flash align=middle pluginspage=http://www.macromedia.com/go/getflashplayer width=18 src=http://static.blog.csdn.net/scripts/ZeroClipboard/ZeroClipboard.swf wmode="transparent" flashvars="id=5&width=18&height=18" allowfullscreen="false" allowscriptaccess="always" bgcolor="#ffffff" quality="best" menu="false" loop="false">

  1. void Cache::lru_insert(head_t *h)  

  2. {  

  3.     // insert to last position  

  4.     h->next = &lru_head;  

  5.     h->prev = lru_head.prev;  

  6.     h->prev->next = h;  

  7.     h->next->prev = h;  

  8. }  

该函数用于后面swap_index函数恢复前面断开连接的两个数据的实现。

 

get_data函数的代码:

 

[cpp]       view plain   copy   技术分享   技术分享  

<EMBED id=ZeroClipboardMovie_6 height=18 name=ZeroClipboardMovie_6 type=application/x-shockwave-flash align=middle pluginspage=http://www.macromedia.com/go/getflashplayer width=18 src=http://static.blog.csdn.net/scripts/ZeroClipboard/ZeroClipboard.swf wmode="transparent" flashvars="id=6&width=18&height=18" allowfullscreen="false" allowscriptaccess="always" bgcolor="#ffffff" quality="best" menu="false" loop="false">

  1. int Cache::get_data(const int index, Qfloat **data, int len)  

  2. {  

  3.     head_t *h = &head[index];  

  4.     if(h->len) lru_delete(h);  

  5.     int more = len - h->len;  

  6. <span style="white-space:pre">  </span>//因为shrink后h->len可能变小,那么more>0,现在要做的就是重新filled,即把内存变成len那么大(主要是通过realloc实现的)  

  7.     if(more > 0)  

  8.     {  

  9.         // free old space,这一步一般不会运行  

  10.         while(size < more)   //size为所指定的全部内存  

  11.         {  

  12.             head_t *old = lru_head.next;  

  13.             lru_delete(old);  

  14.             free(old->data);  

  15.             size += old->len;  

  16.             old->data = 0;  

  17.             old->len = 0;  

  18.         }  

  19.   

  20.         // allocate new space  

  21.         h->data = (Qfloat *)realloc(h->data,sizeof(Qfloat)*len);//把内存扩大到len  

  22.         size -= more;  

  23.         swap(h->len,len);  

  24.     }  

  25.   

  26.     lru_insert(h);  

  27.     *data = h->data;  

  28.     return len;  

  29. }  

该函数主要的就是每个head[i]具有len大小的内存空间。关于realloc函数是扩大内存用的。


swap_index函数的代码:

 

[cpp]       view plain   copy   技术分享   技术分享  

<EMBED id=ZeroClipboardMovie_7 height=18 name=ZeroClipboardMovie_7 type=application/x-shockwave-flash align=middle pluginspage=http://www.macromedia.com/go/getflashplayer width=18 src=http://static.blog.csdn.net/scripts/ZeroClipboard/ZeroClipboard.swf wmode="transparent" flashvars="id=7&width=18&height=18" allowfullscreen="false" allowscriptaccess="always" bgcolor="#ffffff" quality="best" menu="false" loop="false">

  1. void Cache::swap_index(int i, int j)  

  2. {  

  3.     if(i==j) return;  

  4.   

  5.     if(head[i].len) lru_delete(&head[i]);//断开双向链表  

  6.     if(head[j].len) lru_delete(&head[j]);//断开双向链表  

  7.     swap(head[i].data,head[j].data);  

  8.     swap(head[i].len,head[j].len);  

  9.     if(head[i].len) lru_insert(&head[i]);  

  10.     if(head[j].len) lru_insert(&head[j]);  

  11.   

  12.     if(i>j) swap(i,j);  

  13.     for(head_t *h = lru_head.next; h!=&lru_head; h=h->next)  

  14.     {  

  15.         if(h->len > i)  

  16.         {  

  17.             if(h->len > j)  

  18.                 swap(h->data[i],h->data[j]);  

  19.             else  

  20.             {  

  21.                 // give up  

  22.                 lru_delete(h);  

  23.                 free(h->data);  

  24.                 size += h->len;  

  25.                 h->data = 0;  

  26.                 h->len = 0;  

  27.             }  

  28.         }  

  29.     }  

  30. }  

这个函数就是交换head_t[i]和head_t[j]的内容。首先将head_t[i]和head_t[j]从双向链表中脱离出去,然后交换它们的内容,最后重新把它们恢复到链表中。

完整代码如下:

[cpp]       view plain   copy   技术分享   技术分享  

<EMBED id=ZeroClipboardMovie_8 height=18 name=ZeroClipboardMovie_8 type=application/x-shockwave-flash align=middle pluginspage=http://www.macromedia.com/go/getflashplayer width=18 src=http://static.blog.csdn.net/scripts/ZeroClipboard/ZeroClipboard.swf wmode="transparent" flashvars="id=8&width=18&height=18" allowfullscreen="false" allowscriptaccess="always" bgcolor="#ffffff" quality="best" menu="false" loop="false">

    1. //  

    2. // Kernel Cache  

    3. //  

    4. // l is the number of total data items  

    5. // size is the cache size limit in bytes  

    6. //  

    7. //类Cache负责运算所涉及的内存的管理,包括申请、释放等  

    8. class Cache  

    9. {  

    10. public:  

    11.     Cache(int l,long int size);  

    12.     ~Cache();  

    13.   

    14.     // request data [0,len)  

    15.     // return some position p where [p,len) need to be filled  

    16.     // (p >= len if nothing needs to be filled)  

    17.     int get_data(const int index, Qfloat **data, int len);  

    18.     void swap_index(int i, int j);    

    19. private:  

    20.     int l;  

    21.     long int size;//所指定的全部内存,据说用Mb做单位  

    22.     //结构head_t用来记录所申请内存的指针,并记录长度,而且通过双向的指针,形成链表,增加寻址的速度  

    23.     struct head_t  

    24.     {  

    25.         head_t *prev, *next;    // a circular list是一个双向链表,非循环链表  

    26.         Qfloat *data;  

    27.         int len;        // data[0,len) is cached in this entry  

    28.     };  

    29.   

    30.     head_t *head;//变量指针,该指针记录程序中所申请的内存。  

    31.     head_t lru_head;//双向链表的表头  

    32.     void lru_delete(head_t *h);//从双向链表中删去某个元素的链接,一般是删去当前所指向的元素  

    33.     void lru_insert(head_t *h);//在链表后面插入一个新的链接  

    34. };  

    35.   

    36. Cache::Cache(int l_,long int size_):l(l_),size(size_)  

    37. {  

    38.     //calloc函数的功能与malloc函数的功能相似,都是从堆分配内存该函数与malloc函数的一个显著不同时  

    39.     //是,calloc函数得到的内存空间是经过初始化的,其内容全为0。  

    40.     head = (head_t *)calloc(l,sizeof(head_t));  // initialized to 0  

    41.     size /= sizeof(Qfloat);//先将原来byte数目转化为float的数目。  

    42.     size -= l * sizeof(head_t) / sizeof(Qfloat);//扣除掉L个head_t的内存数目  

    43.     size = max(size, 2 * (long int) l); // cache must be large enough for two columns  

    44.     lru_head.next = lru_head.prev = &lru_head;  

    45. }  

    46.   

    47. Cache::~Cache()  

    48. {  

    49.     for(head_t *h = lru_head.next; h != &lru_head; h=h->next)  

    50.         free(h->data);  

    51.     free(head);  

    52. }  

    53.   

    54. void Cache::lru_delete(head_t *h)  

    55. {  

    56.     // delete from current location  

    57.     h->prev->next = h->next;  

    58.     h->next->prev = h->prev;  

    59. }  

    60.   

    61. void Cache::lru_insert(head_t *h)  

    62. {  

    63.     // insert to last position  

    64.     h->next = &lru_head;  

    65.     h->prev = lru_head.prev;  

    66.     h->prev->next = h;  

    67.     h->next->prev = h;  

    68. }  

    69.   

    70. //该函数保证head_t[index]中至少有len个float的内存,并且将可以使用的内存块的指针放在data指针中,返回值为申请到的内存  

    71. int Cache::get_data(const int index, Qfloat **data, int len)  

    72. {  

    73.     head_t *h = &head[index];  

    74.     if(h->len) lru_delete(h);  

    75.     int more = len - h->len;  

    76.   

    77.     if(more > 0)  

    78.     {  

    79.         // free old space  

    80.         while(size < more)   //size为所指定的全部内存  

    81.         {  

    82.             head_t *old = lru_head.next;  

    83.             lru_delete(old);  

    84.             free(old->data);  

    85.             size += old->len;  

    86.             old->data = 0;  

    87.             old->len = 0;  

    88.         }  

    89.   

    90.         // allocate new space  

    91.         h->data = (Qfloat *)realloc(h->data,sizeof(Qfloat)*len);  

    92.         size -= more;  

    93.         swap(h->len,len);  

    94.     }  

    95.   

    96.     lru_insert(h);  

    97.     *data = h->data;  

    98.     return len;  

    99. }  

    100.   

    101. void Cache::swap_index(int i, int j)  

    102. {  

    103.     if(i==j) return;  

    104.   

    105.     if(head[i].len) lru_delete(&head[i]);//断开双向链表  

    106.     if(head[j].len) lru_delete(&head[j]);//断开双向链表  

    107.     swap(head[i].data,head[j].data);  

    108.     swap(head[i].len,head[j].len);  

    109.     if(head[i].len) lru_insert(&head[i]);  

    110.     if(head[j].len) lru_insert(&head[j]);  

    111.   

    112.     if(i>j) swap(i,j);  

    113.     for(head_t *h = lru_head.next; h!=&lru_head; h=h->next)  

    114.     {  

    115.         if(h->len > i)  

    116.         {  

    117.             if(h->len > j)  

    118.                 swap(h->data[i],h->data[j]);  

    119.             else  

    120.             {  

    121.                 // give up  

    122.                 lru_delete(h);  

    123.                 free(h->data);  

    124.                 size += h->len;  

    125.                 h->data = 0;  

    126.                 h->len = 0;  

    127.             }  

    128.         }  

    129.     }  

    130. }  

    131.  

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。