From 3ac9f64c72f363be180ca81232363ebc11d9dd7f Mon Sep 17 00:00:00 2001 From: Miles Bader Date: Mon, 29 Apr 1996 19:51:40 +0000 Subject: Initial revision --- libshouldbeinlibc/cacheq.h | 85 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 85 insertions(+) create mode 100644 libshouldbeinlibc/cacheq.h (limited to 'libshouldbeinlibc/cacheq.h') diff --git a/libshouldbeinlibc/cacheq.h b/libshouldbeinlibc/cacheq.h new file mode 100644 index 00000000..d3c688e8 --- /dev/null +++ b/libshouldbeinlibc/cacheq.h @@ -0,0 +1,85 @@ +/* Helper functions for maintaining a fixed-size lru-ordered queue + + Copyright (C) 1996 Free Software Foundation, Inc. + + Written by Miles Bader + + 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, or (at + your option) any later version. + + This program 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 this program; if not, write to the Free Software + Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#ifndef __CACHEQ_H__ +#define __CACHEQ_H__ + +#include +#include + +/* This header occurs at the start of every cacheq entry. */ +struct cacheq_hdr +{ + /* Next and prev entries in the cache, linked in LRU order. These are of + type `void *' so that it's conveient to iterate through the list using a + variable pointing to a structure that contains the header, by using + something like `VAR = VAR->hdr.next'. */ + void *next, *prev; +}; + +/* A cacheq. Note that this structure is laid out to allow convenient use as + static initialized data. */ +struct cacheq +{ + /* The size of each entry, including its cacheq_hdr. */ + size_t entry_size; + + /* If non-0, then when making new entries (for instance, when the cacheq is + initialized, or when its size is increased), this function is called on + each new entry (with it's header already initialized). If this function + isn't defined, then each entry is simply zeroed. */ + void (*init_entry) (void *entry); + + /* When an entry is moved from one place in memory to another (for + instance, changing the size of the cache, new storage is used), this is + called for each entry, with FROM and TO the old and new locations of the + entry (and TO contains a bitwise copy of FROM). This is often useful + when the entry points to something that contains a backpointer to it. */ + void (*move_entry) (void *from, void *to); + + /* When entries are removed for some reason (for instance, when reducing + the size of the cacheq), this function is called on each. */ + void (*finalize_entry) (void *entry); + + /* The number of entries in the cache. This number is fixed. */ + int length; + + /* A buffer holding malloc'd memory for all the entries -- NUM_ENTRIES + entries of size ENTRY_SIZE. */ + void *entries; + + /* The least, and most, recently used entries in the cache. These point to + either end of a linked list composed of all the elements of the cache. + This list will always be the same length -- if an element is `removed', + its entry is simply marked inactive, and moved to the LRU end of the list + so it will be reused first. */ + struct cacheq_hdr *lru, *mru; +}; + +/* Move ENTRY to the most-recently-used end of CACHEQ. */ +void cacheq_make_mru (struct cacheq *cq, void *entry); + +/* Move ENTRY to the least-recently-used end of CACHEQ. */ +void cacheq_make_lru (struct cacheq *cq, void *entry); + +/* Change CQ's size to be LENGTH entries. */ +error_t cacheq_set_length (struct cacheq *cq, int length); + +#endif /* __CACHEQ_H__ */ -- cgit v1.2.3