cache-node.c 5.29 KB
Newer Older
Linus Tolke Y's avatar
Linus Tolke Y committed
1
/*
2
 * $Id: cache-node.c,v 0.16 1998/07/08 13:41:43 ceder Exp $
Per Cederqvist's avatar
Per Cederqvist committed
3
 * Copyright (C) 1991, 1993, 1994, 1996  Lysator Academic Computer Association.
Linus Tolke Y's avatar
Linus Tolke Y committed
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
 *
 * This file is part of the LysKOM server.
 * 
 * LysKOM 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 1, or (at your option) 
 * any later version.
 * 
 * LysKOM is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with LysKOM; see the file COPYING.  If not, write to
 * Lysator, c/o ISY, Linkoping University, S-581 83 Linkoping, SWEDEN,
 * or the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, 
 * MA 02139, USA.
 *
 * Please mail bug reports to bug-lyskom@lysator.liu.se. 
 */
Per Cederqvist's avatar
Per Cederqvist committed
25 26 27 28 29 30
/*
 * cache-node.c
 *
 * Used in diskomd.
 */

31 32
static const char *
rcsid = "$Id: cache-node.c,v 0.16 1998/07/08 13:41:43 ceder Exp $";
33 34
#include "rcs.h"
USE(rcsid);
Per Cederqvist's avatar
Per Cederqvist committed
35

Per Cederqvist's avatar
Per Cederqvist committed
36
#include <sys/types.h>
Per Cederqvist's avatar
Per Cederqvist committed
37
#include <stdio.h>
Per Cederqvist's avatar
Per Cederqvist committed
38 39 40
#ifdef HAVE_STDDEF_H
#  include <stddef.h>
#endif
Per Cederqvist's avatar
Per Cederqvist committed
41

Per Cederqvist's avatar
Per Cederqvist committed
42
#include "cache-node.h"
Per Cederqvist's avatar
Per Cederqvist committed
43 44
#include "exp.h"
#include "server/smalloc.h"
Per Cederqvist's avatar
Per Cederqvist committed
45 46
#include "lyskomd.h"

Per Cederqvist's avatar
Per Cederqvist committed
47
EXPORT const Cache_node EMPTY_CACHE_NODE =
48
    {{ 0, 0}, NULL, NULL, 0, 0, 0, 0, NULL, NULL, 0};
Per Cederqvist's avatar
Per Cederqvist committed
49 50

EXPORT const Cache_node_block EMPTY_CACHE_NODE_BLOCK =
Per Cederqvist's avatar
Per Cederqvist committed
51
    { 0, NULL, NULL};
Per Cederqvist's avatar
Per Cederqvist committed
52 53

EXPORT const Cache_node_mcb EMPTY_CACHE_NODE_MCB =
Per Cederqvist's avatar
Per Cederqvist committed
54
    { 0, NULL, 0, 0, NULL, NULL, 0, NULL };
Per Cederqvist's avatar
Per Cederqvist committed
55 56 57 58 59 60 61 62 63


EXPORT  void
unlink_lru(Cache_node *node,
	   Cache_node **lru,
	   Cache_node **mru)
{
    Cache_node *link;
    
Per Cederqvist's avatar
Per Cederqvist committed
64
    link = node->next;
Per Cederqvist's avatar
Per Cederqvist committed
65

Per Cederqvist's avatar
Per Cederqvist committed
66 67
    if ( node->next != NULL )
	node->next->prev = node->prev;
Per Cederqvist's avatar
Per Cederqvist committed
68
    else if (*lru == node)
Per Cederqvist's avatar
Per Cederqvist committed
69
	*lru = node->prev;
Per Cederqvist's avatar
Per Cederqvist committed
70

Per Cederqvist's avatar
Per Cederqvist committed
71 72
    if ( node->prev != NULL )
	node->prev->next = link;
Per Cederqvist's avatar
Per Cederqvist committed
73 74
    else if (*mru == node)
	*mru = link;
Per Cederqvist's avatar
Per Cederqvist committed
75 76 77

    node->next = NULL;
    node->prev = NULL;
Per Cederqvist's avatar
Per Cederqvist committed
78 79
}

80
static void
Per Cederqvist's avatar
Per Cederqvist committed
81 82 83 84
insert_mru(Cache_node *node,
	   Cache_node **lru,
	   Cache_node **mru)
{
Per Cederqvist's avatar
Per Cederqvist committed
85 86
    node->prev = NULL;
    node->next = *mru;
Per Cederqvist's avatar
Per Cederqvist committed
87 88 89 90
    *mru = node;
    if ( *lru == NULL )
	*lru = node;

Per Cederqvist's avatar
Per Cederqvist committed
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
    if ( node->next != NULL )
	node->next->prev = node;
}

static Cache_node_mcb *
alloc_cache_node_mcb(void)
{
    Cache_node_mcb *t;

    t = smalloc(sizeof(Cache_node_mcb));
    *t = EMPTY_CACHE_NODE_MCB;
    return t;
}

static Cache_node_block *
alloc_cache_node_block(int table_size)
{
    Cache_node_block *t;

    t = smalloc(sizeof(Cache_node_block));
    *t = EMPTY_CACHE_NODE_BLOCK;
    t->nodes = smalloc (table_size * sizeof (Cache_node));
    t->next_free = 0;
    t->link = NULL;

    return t;
Per Cederqvist's avatar
Per Cederqvist committed
117 118 119 120 121 122 123 124 125 126 127 128 129 130
}


EXPORT Cache_node_mcb *
create_cache_node_mcb(int mcb_size, 
		      int table_size)
{
    Cache_node_mcb *tmp;

    tmp = alloc_cache_node_mcb();
    *tmp = EMPTY_CACHE_NODE_MCB;
    tmp->lookup_table = smalloc(sizeof(Cache_node *) * table_size);
    tmp->lookup_table_size = table_size;
    tmp->mcb_size = mcb_size;
Per Cederqvist's avatar
Per Cederqvist committed
131
    tmp->last_block = NULL;
Per Cederqvist's avatar
Per Cederqvist committed
132 133 134 135 136 137 138

    return tmp;
}

/* +++ No check is done that it is initialized. */
EXPORT Cache_node *
get_cache_node (Cache_node_mcb *control,
Per Cederqvist's avatar
Per Cederqvist committed
139
		unsigned long   key)
Per Cederqvist's avatar
Per Cederqvist committed
140 141 142 143 144 145 146 147
{
    if ( key >= control->lookup_table_size )
	return NULL;

    return control->lookup_table[ key ];
}

static Cache_node *
Per Cederqvist's avatar
Per Cederqvist committed
148
alloc_cache_node (Cache_node_mcb *control)
Per Cederqvist's avatar
Per Cederqvist committed
149 150
{
    Cache_node *c;
Per Cederqvist's avatar
Per Cederqvist committed
151
    Cache_node_block *new_block;
Per Cederqvist's avatar
Per Cederqvist committed
152

Per Cederqvist's avatar
Per Cederqvist committed
153 154 155 156 157 158 159 160 161 162
    if ( control->last_block == NULL
	|| control->last_block->next_free >= control->mcb_size )
    {
	new_block = alloc_cache_node_block (control->mcb_size);
	new_block->link = control->last_block;
	control->last_block = new_block;
    }

    c = &control->last_block->nodes[ control->last_block->next_free++ ];

Per Cederqvist's avatar
Per Cederqvist committed
163 164 165 166
    *c = EMPTY_CACHE_NODE;
    return c;
}

Per Cederqvist's avatar
Per Cederqvist committed
167 168
EXPORT void
destruct_cache_node(Cache_node_mcb  *control,
Per Cederqvist's avatar
Per Cederqvist committed
169
		    unsigned long    key)
Per Cederqvist's avatar
Per Cederqvist committed
170 171 172 173 174 175 176
{
    if ( key >= control->lookup_table_size )
	return;

    control->lookup_table[ key ] = NULL;
}

Per Cederqvist's avatar
Per Cederqvist committed
177 178
EXPORT  void
create_cache_node (Cache_node_mcb *control,
Per Cederqvist's avatar
Per Cederqvist committed
179
		   unsigned long   key)
Per Cederqvist's avatar
Per Cederqvist committed
180 181
{
    if ( key >= control->lookup_table_size )
Per Cederqvist's avatar
Per Cederqvist committed
182 183
	restart_kom("%s(%lu, %lu): lookup_table_size = %lu\n",
		    "ERROR: create_cache_node",
Per Cederqvist's avatar
Per Cederqvist committed
184
		    (unsigned long) control, key,
Per Cederqvist's avatar
Per Cederqvist committed
185 186
		    control->lookup_table_size);

Per Cederqvist's avatar
Per Cederqvist committed
187
    control->lookup_table[ key ] = alloc_cache_node(control);
Per Cederqvist's avatar
Per Cederqvist committed
188 189
}

Per Cederqvist's avatar
Per Cederqvist committed
190 191
EXPORT  void
zero_init_cache_node (Cache_node_mcb *control,
Per Cederqvist's avatar
Per Cederqvist committed
192
		      unsigned long   key)
Per Cederqvist's avatar
Per Cederqvist committed
193 194
{
    if ( key >= control->lookup_table_size )
Per Cederqvist's avatar
Per Cederqvist committed
195 196
	restart_kom("%s(%lu, %lu): lookup_table_size = %lu\n",
		    "ERROR: zero_init_cache_node",
Per Cederqvist's avatar
Per Cederqvist committed
197
		    (unsigned long)control, key,
Per Cederqvist's avatar
Per Cederqvist committed
198 199 200 201 202 203
		    control->lookup_table_size);

    control->lookup_table[ key ] = NULL;
}


Per Cederqvist's avatar
Per Cederqvist committed
204 205 206

EXPORT void
set_mru(Cache_node_mcb *mcb,
Per Cederqvist's avatar
Per Cederqvist committed
207
	unsigned long   key)
Per Cederqvist's avatar
Per Cederqvist committed
208 209 210 211 212 213
{
    Cache_node *node;

    node = get_cache_node(mcb, key);

    if (node == NULL)
214
	restart_kom("set_mru(%lu): nonexistent.\n", key);
Per Cederqvist's avatar
Per Cederqvist committed
215 216 217 218

    unlink_lru(node, &mcb->lru, &mcb->mru);
    insert_mru(node, &mcb->lru, &mcb->mru);
}
Per Cederqvist's avatar
Per Cederqvist committed
219

220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241
static void
free_cache_node_block (Cache_node_block *block)
{
    sfree(block->nodes);
    sfree(block);
}

extern void
free_cache_node_mcb(Cache_node_mcb *control)
{
    Cache_node_block *block;

    while ( control->last_block != NULL )
    {
	block = control->last_block;
	control->last_block = block->link;
	free_cache_node_block (block);
    }

    sfree(control->lookup_table);
    sfree(control);
}