From 5a7a42cfce638f52f702b4d317c45c7186b8c0b4 Mon Sep 17 00:00:00 2001 From: Paul Smith Date: Fri, 10 Feb 2006 05:29:00 +0000 Subject: - New code capability: a read-only string cache. Start of solution for Savannah bug #15182, but not much uses it yet. Coming shortly. - Added short-circuiting $(and ..) and $(or ...) functions. --- strcache.c | 219 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 219 insertions(+) create mode 100644 strcache.c (limited to 'strcache.c') diff --git a/strcache.c b/strcache.c new file mode 100644 index 0000000..b20a511 --- /dev/null +++ b/strcache.c @@ -0,0 +1,219 @@ +/* Constant string caching for GNU Make. +Copyright (C) 2006 Free Software Foundation, Inc. +This file is part of GNU Make. + +GNU Make 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. + +GNU Make 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 GNU Make; see the file COPYING. If not, write to +the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, +Boston, MA 02110-1301 USA. */ + +#include "make.h" + +#include + +#include "hash.h" + +/* The size (in bytes) of each cache buffer. */ +#define CACHE_BUFFER_SIZE (4096) + + +/* A string cached here will never be freed, so we don't need to worry about + reference counting. We just store the string, and then remember it in a + hash so it can be looked up again. */ + +struct strcache { + struct strcache *next; /* The next block of strings. */ + char *end; /* Pointer to the beginning of the free space. */ + int count; /* # of strings in this buffer (for stats). */ + int bytesfree; /* The amount of the buffer that is free. */ + char buffer[1]; /* The buffer comes after this. */ +}; + +static int bufsize = CACHE_BUFFER_SIZE; +static struct strcache *strcache = NULL; + +static struct strcache * +new_cache() +{ + struct strcache *new; + new = (struct strcache *) xmalloc (sizeof (*new) + bufsize); + new->end = new->buffer; + new->count = 0; + new->bytesfree = bufsize; + + new->next = strcache; + strcache = new; + + return new; +} + +static const char * +add_string(const char *str, int len) +{ + struct strcache *best = NULL; + struct strcache *sp; + const char *res; + + /* If the string we want is too large to fit into a single buffer, then we're + screwed; nothing will ever fit! Change the maximum size of the cache to + be big enough. */ + if (len > bufsize) + bufsize = len * 2; + + /* First, find a cache with enough free space. We always look through all + the blocks and choose the one with the best fit (the one that leaves the + least amount of space free). */ + for (sp = strcache; sp != NULL; sp = sp->next) + if (sp->bytesfree > len && (!best || best->bytesfree > sp->bytesfree)) + best = sp; + + /* If nothing is big enough, make a new cache. */ + if (!best) + best = new_cache(); + + assert (best->bytesfree > len); + + /* Add the string to the best cache. */ + res = best->end; + memcpy (best->end, str, len); + best->end += len; + *(best->end++) = '\0'; + best->bytesfree -= len + 1; + ++best->count; + + return res; +} + + +/* Hash table of strings in the cache. */ + +static unsigned long +str_hash_1 (const void *key) +{ + return_ISTRING_HASH_1 ((const char *) key); +} + +static unsigned long +str_hash_2 (const void *key) +{ + return_ISTRING_HASH_2 ((const char *) key); +} + +static int +str_hash_cmp (const void *x, const void *y) +{ + return_ISTRING_COMPARE ((const char *) x, (const char *) y); +} + +static struct hash_table strings; + +static const char * +add_hash (const char *str, int len) +{ + /* Look up the string in the hash. If it's there, return it. */ + char **slot = (char **) hash_find_slot (&strings, str); + const char *key = *slot; + + if (!HASH_VACANT (key)) + return key; + + /* Not there yet so add it to a buffer, then into the hash table. */ + key = add_string (str, len); + hash_insert_at (&strings, key, slot); + return key; +} + +/* Returns true if the string is in the cache; false if not. */ +int +strcache_iscached (const char *str) +{ + struct strcache *sp; + + for (sp = strcache; sp != 0; sp = sp->next) + if (str >= sp->buffer && str < sp->end) + return 1; + + return 0; +} + +/* If the string is already in the cache, return a pointer to the cached + version. If not, add it then return a pointer to the cached version. + Note we do NOT take control of the string passed in. */ +const char * +strcache_add (const char *str) +{ + return add_hash (str, strlen (str)); +} + +const char * +strcache_add_len (const char *str, int len) +{ + char *key = alloca (len + 1); + memcpy (key, str, len); + key[len] = '\0'; + + return add_hash (key, len); +} + +int +strcache_setbufsize(int size) +{ + if (size > bufsize) + bufsize = size; + return bufsize; +} + +void +strcache_init (void) +{ + hash_init (&strings, 1000, str_hash_1, str_hash_2, str_hash_cmp); +} + + +/* Generate some stats output. */ + +void +strcache_print_stats (const char *prefix) +{ + int numbuffs = 0, numstrs = 0; + int totsize = 0, avgsize, maxsize = 0, minsize = bufsize; + int totfree = 0, avgfree, maxfree = 0, minfree = bufsize; + const struct strcache *sp; + + for (sp = strcache; sp != NULL; sp = sp->next) + { + int bf = sp->bytesfree; + int sz = (sp->end - sp->buffer) + bf; + + ++numbuffs; + numstrs += sp->count; + + totsize += sz; + maxsize = (sz > maxsize ? sz : maxsize); + minsize = (sz < minsize ? sz : minsize); + + totfree += bf; + maxfree = (bf > maxfree ? bf : maxfree); + minfree = (bf < minfree ? bf : minfree); + } + + avgsize = numbuffs ? (int)(totsize / numbuffs) : 0; + avgfree = numbuffs ? (int)(totfree / numbuffs) : 0; + + printf ("\n%s # of strings in strcache: %d\n", prefix, numstrs); + printf ("%s # of strcache buffers: %d\n", prefix, numbuffs); + printf ("%s strcache size: total = %d / max = %d / min = %d / avg = %d\n", + prefix, totsize, maxsize, minsize, avgsize); + printf ("%s strcache free: total = %d / max = %d / min = %d / avg = %d\n", + prefix, totfree, maxfree, minfree, avgfree); +} -- cgit v1.2.3