diff options
Diffstat (limited to 'libshouldbeinlibc/cacheq.h')
-rw-r--r-- | libshouldbeinlibc/cacheq.h | 85 |
1 files changed, 85 insertions, 0 deletions
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 <miles@gnu.ai.mit.edu> + + 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 <stddef.h> +#include <errno.h> + +/* 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__ */ |