Code@Pig Home

дÁ˸ö lpc °æµÄ LRU ʵÏÖ£¬×ÔÎҸоõÁ¼ºÃ£¬ºÇºÇ£¬Ìù³öÀ´ show show~

---------------------------------- lru.h -----------------------------------
#ifndef MY_LRU_H
#define MY_LRU_H

// ==== usage ====
// #define LRU_LIMIT            10              // queue ×î´óÈÝÁ¿
// #define LRU_REMOVE_CALLBACK  "func_name"     // ɾ³ýʱµÄ»Øµ÷ remove_callback(mixed mKey, mixed mData)
// #include <lru.h>
//
// ==== export func ====
// ÊÇ·ñ´æÔÚ mKey ¶ÔÓ¦µÄÊý¾Ý
// int LRU_has(mixed mKey);
//
// »ñµÃ mKey ¶ÔÓ¦µÄÊý¾Ý
// mKey ²»´æÔÚ£¬Ôò throw exception
// mixed LRU_get(mixed key);
//
// mKey ´æÔÚ, ¸üРmKey ¶ÔÓ¦µÄ mData µÄÊý¾Ý
// mKey ²»´æÔÚ, mData ¼ÓÈë¶ÓÁÐ
// void LRU_put(mixed key, mixed data);
//
// ==== WARNING ====
// mKey ²»ÄܵÈÓÚ -1

#ifndef TXE_LRU_QUEUE_H
#define TXE_LRU_QUEUE_H

// external macro
// #define LRU_LIMIT                    10
// #define LRU_REMOVE_CALLBACK          "func_name"     // func(mixed mKey, mixed mData)

// internal macro
#define LRU_TRIPLE(x, prev, next)      ({x, prev, next})
#define IDX_DATA                        0
#define IDX_PREV                        1
#define IDX_NEXT                        2

#define LRU_NULL                        (-1)

mapping g_LRU_queue = ([ ]);
mixed g_LRU_head = LRU_NULL;
mixed g_LRU_tail = LRU_NULL;


// -----------------------

int _LRU_has_data(mixed mKey)
{
        return !undefinedp(g_LRU_queue[mKey]);
}

mixed _LRU_get_data(mixed mKey)
{
        return g_LRU_queue[mKey][IDX_DATA];
}

int _LRU_size() { return sizeof(g_LRU_queue); }
mixed _LRU_head() { return g_LRU_head; }
mixed _LRU_tail() { return g_LRU_tail; }

void _LRU_push_head(mixed mKey, mixed mData)            // Í·²¿²åÈë
{
        g_LRU_queue[mKey] = LRU_TRIPLE(mData, LRU_NULL, g_LRU_head);
        if ( g_LRU_head != LRU_NULL ) g_LRU_queue[g_LRU_head][IDX_PREV] = mKey;
        g_LRU_head = mKey;

        if ( sizeof(g_LRU_queue) == 1 )
        {
                // first elem
                g_LRU_tail = mKey;
        }
}

void _LRU_pop_head()            // ɾ³ýheadÔªËØ
{
        mixed mTriple = g_LRU_queue[g_LRU_head];
        map_delete(g_LRU_queue, g_LRU_head);

        g_LRU_head = mTriple[IDX_NEXT];
        g_LRU_queue[g_LRU_head][IDX_PREV] = LRU_NULL;
}

void _LRU_pop_tail()            // ɾ³ýtailÔªËØ
{
        mixed mTriple = g_LRU_queue[g_LRU_tail];
        map_delete(g_LRU_queue, g_LRU_tail);

        g_LRU_tail = mTriple[IDX_PREV];                         // last = last.prev
        g_LRU_queue[g_LRU_tail][IDX_NEXT] = LRU_NULL;           // last.next = null
}

void _LRU_pop_lastone()         // ÌØÊâ´¦Àí»¹ÓÐÒ»¸öÔªËصÄÇé¿ö
{
        g_LRU_head  = LRU_NULL;
        g_LRU_tail  = LRU_NULL;
        g_LRU_queue = ([ ]);
}

void _LRU_pop(mixed mKey)       // ɾ³ýÔªËØ
{
        mixed mTriple;

        if ( _LRU_size() == 1 )
        {
                _LRU_pop_lastone();
                return;
        }

        if ( mKey == g_LRU_tail )
        {
                _LRU_pop_tail();
                return;
        }

        if ( mKey == g_LRU_head )
        {
                _LRU_pop_head();
                return;
        }

        // not head or tail
        mTriple = g_LRU_queue[mKey];
        map_delete(g_LRU_queue, mKey);

        g_LRU_queue[ mTriple[IDX_PREV] ][IDX_NEXT] = mTriple[IDX_NEXT]; // curr.prev.next = curr.next
        g_LRU_queue[ mTriple[IDX_NEXT] ][IDX_PREV] = mTriple[IDX_PREV]; // curr.next.prev = curr.prev
}


// -----------------------

int LRU_has(mixed mKey)
{
        return _LRU_has_data(mKey);
}

mixed LRU_get(mixed mKey)
{
        mixed mData;

        if ( !_LRU_has_data(mKey) )
                throw("Key not exist");

        // make mKey first elem
        if ( mKey != _LRU_head() )
        {
                mData = _LRU_get_data(mKey);
                _LRU_pop(mKey);
                _LRU_push_head(mKey, mData);
        }

        return _LRU_get_data(mKey);
}

void LRU_put(mixed mKey, mixed mData)
{
        if ( _LRU_has_data(mKey) )
        {
                _LRU_pop(mKey);
                _LRU_push_head(mKey, mData);
                return;
        }

        // check, if > LRU_LIMIT
        if ( _LRU_size() >= LRU_LIMIT )
        {
                mixed mRemoveKey, mRemoveData;
                mRemoveKey  = _LRU_tail();
                mRemoveData = _LRU_get_data(mRemoveKey);
                catch(call_other(this_object(), LRU_REMOVE_CALLBACK, mRemoveKey, mRemoveData));
                _LRU_pop(mRemoveKey);
        }

        _LRU_push_head(mKey, mData);
}
#endif

---------------------------------- foo.c -----------------------------------
#define LRU_LIMIT               5
#define LRU_REMOVE_CALLBACK     "remove_callback"
#include <lru.h>

void remove_callback(mixed mKey, mixed mData)
{
        debug_message(sprintf("remove, key:%O, data:%O", mKey, mData));
}

void create()
{
        for ( int i = 0; i < 5; i++ )
                LRU_put(i, i);

        debug_message("has 0 = " + LRU_has(0));

        LRU_get(0);
        LRU_get(3);
        LRU_put(7, 7);          // 1 removed
}