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.c | 142 +++++++++++++++++++++++++++++++++++++++++++++ libshouldbeinlibc/cacheq.h | 85 +++++++++++++++++++++++++++ 2 files changed, 227 insertions(+) create mode 100644 libshouldbeinlibc/cacheq.c create mode 100644 libshouldbeinlibc/cacheq.h diff --git a/libshouldbeinlibc/cacheq.c b/libshouldbeinlibc/cacheq.c new file mode 100644 index 00000000..8275dbe7 --- /dev/null +++ b/libshouldbeinlibc/cacheq.c @@ -0,0 +1,142 @@ +/* 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. */ + +#include +#include + +#include "cacheq.h" + +/* Move ENTRY to the most-recently-used end of CACHEQ. */ +void +cacheq_make_mru (struct cacheq *cq, void *entry) +{ + struct cacheq_hdr *h = entry; + + if (h != cq->mru) + { + /* First remove it. We known H->prev isn't 0 because H wasn't + previously == MRU. */ + ((struct cacheq_hdr *)h->prev)->next = h->next; + if (h->next) + ((struct cacheq_hdr *)h->next)->prev = h->prev; + else + cq->lru = h->prev; + + /* Now make it MRU. */ + h->next = cq->mru; + h->prev = 0; + cq->mru->prev = h; + cq->mru = h; + } +} + +/* Move ENTRY to the least-recently-used end of CACHEQ. */ +void +cacheq_make_lru (struct cacheq *cq, void *entry) +{ + struct cacheq_hdr *h = entry; + + if (h != cq->lru) + { + /* First remove it. We known H->next isn't 0 because H wasn't + previously == LRU. */ + ((struct cacheq_hdr *)h->next)->prev = h->prev; + if (h->prev) + ((struct cacheq_hdr *)h->prev)->next = h->next; + else + cq->mru = h->next; + + /* Now make it LRU. */ + h->prev = cq->lru; + h->next = 0; + cq->lru->next = h; + cq->lru = h; + } +} + +/* Change CQ's size to be LENGTH entries. */ +error_t +cacheq_set_length (struct cacheq *cq, int length) +{ + if (length != cq->length) + { + size_t esz = cq->entry_size; + void *new_entries = malloc (esz * length); + /* Source entries. */ + struct cacheq_hdr *fh = cq->mru; + /* Destination entries (and limit). */ + struct cacheq_hdr *th = new_entries, *end = new_entries + esz * length; + struct cacheq_hdr *prev_th = 0; + + if (! new_entries) + return ENOMEM; + + while (fh || th) + { + struct cacheq_hdr *next_th = + (!th || th > end) ? 0 : (void *)th + esz; + + if (fh && th) + bcopy (fh, th, esz); /* Copy the bits in a moved entry. */ + else if (th) + bzero (th, esz); /* Zero the bits in a new entry. */ + + if (th) + /* Fixup headers. */ + { + th->prev = prev_th; + th->next = next_th; + } + + /* Call user hooks as appropiate. */ + if (fh && th) + { + if (cq->move_entry) + (*cq->move_entry) (fh, th); + } + else if (th) + { + if (cq->init_entry) + (*cq->init_entry) (th); + } + else + { + if (cq->finalize_entry) + (*cq->finalize_entry) (fh); + } + + if (fh) + fh = fh->next; + if (th) + { + prev_th = th; + th = next_th; + } + } + + free (cq->entries); + cq->entries = new_entries; + cq->mru = new_entries; + cq->lru = prev_th; + cq->length = length; + } + + return 0; +} 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