firmware/lru.c

   1 /***************************************************************************
   2  *             __________               __   ___.
   3  *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4  *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5  *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6  *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7  *                     \/            \/     \/    \/            \/
   8  *
   9  * Copyright (C) 2003 Tat Tang
  10  *
  11  * All files in this archive are subject to the GNU General Public License.
  12  * See the file COPYING in the source tree root for full license agreement.
  13  *
  14  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  15  * KIND, either express or implied.
  16  *
  17  ****************************************************************************/
  18
  19 #include "lru.h"
  20
  21 struct lru_node
  22 {
  23     short _next;
  24     short _prev;
  25     unsigned char data[1]; /* place holder */
  26 };
  27
  28 #define lru_node_p(pl, x) \
  29     ((struct lru_node*)(pl->_base + pl->_slot_size * x))
  30
  31 /*******************************************************************************
  32  * lru_create
  33  ******************************************************************************/
  34 void lru_create(struct lru* pl, void *buf, short size, short data_size)
  35 {
  36     pl->_base = (unsigned char*) buf;
  37     pl->_slot_size = data_size + LRU_SLOT_OVERHEAD;
  38
  39     pl->_size = size;
  40
  41     pl->_head = 0;
  42     pl->_tail = pl->_size - 1;
  43
  44     /* Initialise slots */
  45     int i;
  46     for (i=0; i<pl->_size; i++)
  47     {
  48         lru_node_p(pl, i)->_next = i + 1;
  49         lru_node_p(pl, i)->_prev = i - 1;
  50     }
  51
  52     /* Fix up head and tail to form circular buffer */
  53     lru_node_p(pl, 0)->_prev = pl->_tail;
  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     struct lru_node* prev_node = lru_node_p(pl, curr_node->_prev);
  94     struct lru_node* next_node = lru_node_p(pl, curr_node->_next);
  95
  96     prev_node->_next = curr_node->_next;
  97     next_node->_prev = curr_node->_prev;
  98
  99     /* insert current node at tail */
 100     struct lru_node* tail_node = lru_node_p(pl, pl->_tail);
 101     short tail_node_next_handle = tail_node->_next; /* Bug fix */
 102     struct lru_node* tail_node_next = lru_node_p(pl, tail_node_next_handle); /* Bug fix */
 103
 104     curr_node->_next = tail_node->_next;
 105     curr_node->_prev = pl->_tail;
 106     tail_node_next->_prev = handle; /* Bug fix */
 107     tail_node->_next = handle;
 108
 109     pl->_tail = handle;
 110 }
 111
 112 /*******************************************************************************
 113  * lru_data
 114  ******************************************************************************/
 115 void *lru_data(struct lru* pl, short handle)
 116 {
 117     return lru_node_p(pl, handle)->data;
 118 }
 119