firmware/lru.c

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