summaryrefslogtreecommitdiffstats
path: root/firmware/lru.c
diff options
context:
space:
mode:
Diffstat (limited to 'firmware/lru.c')
-rw-r--r--firmware/lru.c119
1 files changed, 119 insertions, 0 deletions
diff --git a/firmware/lru.c b/firmware/lru.c
new file mode 100644
index 0000000000..6834c3da1b
--- /dev/null
+++ b/firmware/lru.c
@@ -0,0 +1,119 @@
+/***************************************************************************
+ * __________ __ ___.
+ * Open \______ \ ____ ____ | | _\_ |__ _______ ___
+ * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
+ * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
+ * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
+ * \/ \/ \/ \/ \/
+ *
+ * Copyright (C) 2003 Tat Tang
+ *
+ * All files in this archive are subject to the GNU General Public License.
+ * See the file COPYING in the source tree root for full license agreement.
+ *
+ * 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;
+}
+