cache.cs

SVM的一个源程序

//Copyright (C) 2007 Matthew Johnson

//This program is free software; you can redistribute it and/or modify
//it under the terms of the GNU General Public License as published by
//the Free Software Foundation; either version 2 of the License, or
//(at your option) any later version.

//This program is distributed in the hope that it will be useful,
//but WITHOUT ANY WARRANTY; without even the implied warranty of
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//GNU General Public License for more details.

//You should have received a copy of the GNU General Public License along
//with this program; if not, write to the Free Software Foundation, Inc.,
//51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

using System;
using System.Collections.Generic;
using System.Text;

namespace SVM
{
    internal class Cache
    {
        private int _count;
        private long _size;

        private sealed class head_t
        {
            public head_t(Cache enclosingInstance)
            {
                _enclosingInstance = enclosingInstance;
            }
            private Cache _enclosingInstance;
            public Cache EnclosingInstance
            {
                get
                {
                    return _enclosingInstance;
                }
            }
            internal head_t prev, next; // a cicular list
            internal float[] data;
            internal int len; // data[0,len) is cached in this entry
        }

        private head_t[] head;
        private head_t lru_head;

        internal Cache(int count, long size)
        {
            _count = count;
            _size = size;
            head = new head_t[_count];
            for (int i = 0; i < _count; i++)
                head[i] = new head_t(this);
            _size /= 4;
            _size -= _count * (16 / 4); // sizeof(head_t) == 16
            lru_head = new head_t(this);
            lru_head.next = lru_head.prev = lru_head;
        }

        private void lru_delete(head_t h)
        {
            // delete from current location
            h.prev.next = h.next;
            h.next.prev = h.prev;
        }

        private void lru_insert(head_t h)
        {
            // insert to last position
            h.next = lru_head;
            h.prev = lru_head.prev;
            h.prev.next = h;
            h.next.prev = h;
        }

        // request data [0,len)
        // return some position p where [p,len) need to be filled
        // (p >= len if nothing needs to be filled)
        // java: simulate pointer using single-element array
        internal virtual int get_data(int index, float[][] data, int len)
        {
            head_t h = head[index];
            if (h.len > 0)
                lru_delete(h);
            int more = len - h.len;

            if (more > 0)
            {
                // free old space
                while (_size < more)
                {
                    head_t old = lru_head.next;
                    lru_delete(old);
                    _size += old.len;
                    old.data = null;
                    old.len = 0;
                }

                // allocate new space
                float[] new_data = new float[len];
                if (h.data != null)
                    Array.Copy(h.data, 0, new_data, 0, h.len);
                h.data = new_data;
                _size -= more;
                do
                {
                    int _ = h.len; h.len = len; len = _;
                }
                while (false);
            }

            lru_insert(h);
            data[0] = h.data;
            return len;
        }

        internal virtual void swap_index(int i, int j)
        {
            if (i == j)
                return;

            if (head[i].len > 0)
                lru_delete(head[i]);
            if (head[j].len > 0)
                lru_delete(head[j]);
            do
            {
                float[] _ = head[i].data; head[i].data = head[j].data; head[j].data = _;
            }
            while (false);
            do
            {
                int _ = head[i].len; head[i].len = head[j].len; head[j].len = _;
            }
            while (false);
            if (head[i].len > 0)
                lru_insert(head[i]);
            if (head[j].len > 0)
                lru_insert(head[j]);

            if (i > j)
                do
                {
                    int _ = i; i = j; j = _;
                }
                while (false);
            for (head_t h = lru_head.next; h != lru_head; h = h.next)
            {
                if (h.len > i)
                {
                    if (h.len > j)
                        do
                        {
                            float _ = h.data[i]; h.data[i] = h.data[j]; h.data[j] = _;
                        }
                        while (false);
                    else
                    {
                        // give up
                        lru_delete(h);
                        _size += h.len;
                        h.data = null;
                        h.len = 0;
                    }
                }
            }
        }
    }
}