1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
/***************************************************************************
* __________ __ ___.
* Open \______ \ ____ ____ | | _\_ |__ _______ ___
* Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
* Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
* Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
* \/ \/ \/ \/ \/
*
* Copyright (C) 2003 Tat Tang
*
* 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 software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
* KIND, either express or implied.
*
****************************************************************************/
#include "lru.h"
struct lru_node
{
short _next;
short _prev;
unsigned char data[1]; /* place holder */
};
#define lru_node_p(pl, x) \
((struct lru_node*)(pl->_base + pl->_slot_size * x))
/*******************************************************************************
* lru_create
******************************************************************************/
void lru_create(struct lru* pl, void *buf, short size, short data_size)
{
pl->_base = (unsigned char*) buf;
pl->_slot_size = data_size + LRU_SLOT_OVERHEAD;
pl->_size = size;
pl->_head = 0;
pl->_tail = pl->_size - 1;
/* Initialise slots */
int i;
for (i=0; i<pl->_size; i++)
{
lru_node_p(pl, i)->_next = i + 1;
lru_node_p(pl, i)->_prev = i - 1;
}
/* Fix up head and tail to form circular buffer */
lru_node_p(pl, 0)->_prev = pl->_tail;
lru_node_p(pl, pl->_tail)->_next = pl->_head;
}
/*******************************************************************************
* lru_traverse
******************************************************************************/
void lru_traverse(struct lru* pl, void (*callback)(void* data))
{
short i;
struct lru_node* slot;
short loc = pl->_head;
for (i = 0; i < pl->_size; i++)
{
slot = lru_node_p(pl, loc);
callback(slot->data);
loc = slot->_next;
}
}
/*******************************************************************************
* lru_touch
******************************************************************************/
void lru_touch(struct lru* pl, short handle)
{
if (handle == pl->_head)
{
pl->_head = lru_node_p(pl, pl->_head)->_next;
pl->_tail = lru_node_p(pl, pl->_tail)->_next;
return;
}
if (handle == pl->_tail)
{
return;
}
/* Remove current node from linked list */
struct lru_node* curr_node = lru_node_p(pl, handle);
struct lru_node* prev_node = lru_node_p(pl, curr_node->_prev);
struct lru_node* next_node = lru_node_p(pl, curr_node->_next);
prev_node->_next = curr_node->_next;
next_node->_prev = curr_node->_prev;
/* insert current node at tail */
struct lru_node* tail_node = lru_node_p(pl, pl->_tail);
short tail_node_next_handle = tail_node->_next; /* Bug fix */
struct lru_node* tail_node_next = lru_node_p(pl, tail_node_next_handle); /* Bug fix */
curr_node->_next = tail_node->_next;
curr_node->_prev = pl->_tail;
tail_node_next->_prev = handle; /* Bug fix */
tail_node->_next = handle;
pl->_tail = handle;
}
/*******************************************************************************
* lru_data
******************************************************************************/
void *lru_data(struct lru* pl, short handle)
{
return lru_node_p(pl, handle)->data;
}
|
