Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/LibSVM/Cache.cs @ 2527

Last change on this file since 2527 was 2415, checked in by gkronber, 15 years ago

Updated LibSVM project to latest version. #774

File size: 4.7 KB
Line 
1/*
2 * SVM.NET Library
3 * Copyright (C) 2008 Matthew Johnson
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
17 */
18
19
20using System;
21
22namespace SVM
23{
24    internal class Cache
25    {
26        private int _count;
27        private long _size;
28
29        private sealed class head_t
30        {
31            public head_t(Cache enclosingInstance)
32            {
33                _enclosingInstance = enclosingInstance;
34            }
35            private Cache _enclosingInstance;
36            public Cache EnclosingInstance
37            {
38                get
39                {
40                    return _enclosingInstance;
41                }
42            }
43            internal head_t prev, next; // a cicular list
44            internal float[] data;
45            internal int len; // data[0,len) is cached in this entry
46        }
47
48        private head_t[] head;
49        private head_t lru_head;
50
51        public Cache(int count, long size)
52        {
53            _count = count;
54            _size = size;
55            head = new head_t[_count];
56            for (int i = 0; i < _count; i++)
57                head[i] = new head_t(this);
58            _size /= 4;
59            _size -= _count * (16 / 4); // sizeof(head_t) == 16
60            lru_head = new head_t(this);
61            lru_head.next = lru_head.prev = lru_head;
62        }
63
64        private void lru_delete(head_t h)
65        {
66            // delete from current location
67            h.prev.next = h.next;
68            h.next.prev = h.prev;
69        }
70
71        private void lru_insert(head_t h)
72        {
73            // insert to last position
74            h.next = lru_head;
75            h.prev = lru_head.prev;
76            h.prev.next = h;
77            h.next.prev = h;
78        }
79
80        private static void swap<T>(ref T lhs, ref T rhs)
81        {
82            T tmp = lhs;
83            lhs = rhs;
84            rhs = tmp;
85        }
86
87        // request data [0,len)
88        // return some position p where [p,len) need to be filled
89        // (p >= len if nothing needs to be filled)
90        // java: simulate pointer using single-element array
91        public int GetData(int index, ref float[] data, int len)
92        {
93            head_t h = head[index];
94            if (h.len > 0)
95                lru_delete(h);
96            int more = len - h.len;
97
98            if (more > 0)
99            {
100                // free old space
101                while (_size < more)
102                {
103                    head_t old = lru_head.next;
104                    lru_delete(old);
105                    _size += old.len;
106                    old.data = null;
107                    old.len = 0;
108                }
109
110                // allocate new space
111                float[] new_data = new float[len];
112                if (h.data != null)
113                    Array.Copy(h.data, 0, new_data, 0, h.len);
114                h.data = new_data;
115                _size -= more;
116                swap(ref h.len, ref len);
117            }
118
119            lru_insert(h);
120            data = h.data;
121            return len;
122        }
123
124        public void SwapIndex(int i, int j)
125        {
126            if (i == j)
127                return;
128
129            if (head[i].len > 0)
130                lru_delete(head[i]);
131            if (head[j].len > 0)
132                lru_delete(head[j]);
133            swap(ref head[i].data, ref head[j].data);
134            swap(ref head[i].len, ref head[j].len);
135            if (head[i].len > 0)
136                lru_insert(head[i]);
137            if (head[j].len > 0)
138                lru_insert(head[j]);
139
140            if (i > j)
141                swap(ref i, ref j);
142
143            for (head_t h = lru_head.next; h != lru_head; h = h.next)
144            {
145                if (h.len > i)
146                {
147                    if (h.len > j)
148                        swap(ref h.data[i], ref h.data[j]);
149                    else
150                    {
151                        // give up
152                        lru_delete(h);
153                        _size += h.len;
154                        h.data = null;
155                        h.len = 0;
156                    }
157                }
158            }
159        }
160    }
161}
Note: See TracBrowser for help on using the repository browser.