diff options
author | Ulrich Drepper <drepper@redhat.com> | 2005-07-26 05:00:05 +0000 |
---|---|---|
committer | Ulrich Drepper <drepper@redhat.com> | 2005-07-26 05:00:05 +0000 |
commit | b08d5a8fb42f4586d756068065186b5af7e48dad (patch) | |
tree | 9f05f86be7877ed461b4dc05f53b29ea4fc0d2a1 /lib | |
download | elfutils-b08d5a8fb42f4586d756068065186b5af7e48dad.tar.gz |
Adjust for monotone.
Diffstat (limited to 'lib')
-rw-r--r-- | lib/.cvsignore | 1 | ||||
-rw-r--r-- | lib/ChangeLog | 39 | ||||
-rw-r--r-- | lib/Makefile.am | 35 | ||||
-rw-r--r-- | lib/crc32.c | 86 | ||||
-rw-r--r-- | lib/crc32_file.c | 59 | ||||
-rw-r--r-- | lib/dynamicsizehash.c | 316 | ||||
-rw-r--r-- | lib/dynamicsizehash.h | 107 | ||||
-rw-r--r-- | lib/fixedsizehash.h | 255 | ||||
-rw-r--r-- | lib/list.h | 85 | ||||
-rw-r--r-- | lib/next_prime.c | 54 | ||||
-rw-r--r-- | lib/system.h | 40 | ||||
-rw-r--r-- | lib/xmalloc.c | 68 | ||||
-rw-r--r-- | lib/xstrdup.c | 27 | ||||
-rw-r--r-- | lib/xstrndup.c | 31 |
14 files changed, 1203 insertions, 0 deletions
diff --git a/lib/.cvsignore b/lib/.cvsignore new file mode 100644 index 00000000..70845e08 --- /dev/null +++ b/lib/.cvsignore @@ -0,0 +1 @@ +Makefile.in diff --git a/lib/ChangeLog b/lib/ChangeLog new file mode 100644 index 00000000..9ddc2163 --- /dev/null +++ b/lib/ChangeLog @@ -0,0 +1,39 @@ +2005-05-03 Roland McGrath <roland@redhat.com> + + * crc32_file.c: New file. + * Makefile.am (libeu_a_SOURCES): Add it. + * system.h: Declare crc32_file. + +2005-04-30 Ulrich Drepper <drepper@redhat.com> + + * Makefile.am: Use -ffunction-sections for xmalloc.c. + +2005-02-15 Ulrich Drepper <drepper@redhat.com> + + * dynamicsizehash.c (lookup): Mark val parameter as possibly unused. + +2005-02-06 Ulrich Drepper <drepper@redhat.com> + + * fixedsizehash.h: Mark unused parameters. Correct CLASS and + const order for fshash_find. + + * Makefile.am: Cleanup AM_CFLAGS handling. Add -Wunused -Wextra. + +2005-02-05 Ulrich Drepper <drepper@redhat.com> + + * Makefile.am [MUDFLAP] (AM_CFLAGS): Add -fpic and -fmudflap. + +2004-01-17 Ulrich Drepper <drepper@redhat.com> + + * Makefile.am: Support building with mudflap. + +2003-09-22 Ulrich Drepper <drepper@redhat.com> + + * Makefile.am (AM_CFLAGS): Add -fpic. + + * Makefile.am (noinst_HEADERS): Add list.h. + * list.h: New file. + +2003-08-11 Ulrich Drepper <drepper@redhat.com> + + * Moved to CVS archive. diff --git a/lib/Makefile.am b/lib/Makefile.am new file mode 100644 index 00000000..facb5634 --- /dev/null +++ b/lib/Makefile.am @@ -0,0 +1,35 @@ +## Process this file with automake to create Makefile.in +## +## Copyright (C) 1996-2001, 2002, 2004, 2005 Red Hat, Inc. +## +## 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, version 2. +## +## 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. +## +DEFS = -D_GNU_SOURCE -DHAVE_CONFIG_H +if MUDFLAP +AM_CFLAGS = -fmudflap +else +AM_CFLAGS = +endif +AM_CFLAGS += -fpic -Wall -Wshadow -Werror -Wunused -Wextra $($(*F)_CFLAGS) +INCLUDES = -I$(srcdir)/../libelf -I.. + +noinst_LIBRARIES = libeu.a + +libeu_a_SOURCES = xstrdup.c xstrndup.c xmalloc.c next_prime.c \ + crc32.c crc32_file.c + +noinst_HEADERS = fixedsizehash.h system.h dynamicsizehash.h list.h +EXTRA_DIST = dynamicsizehash.c + +xmalloc_CFLAGS = -ffunction-sections diff --git a/lib/crc32.c b/lib/crc32.c new file mode 100644 index 00000000..a198e8e4 --- /dev/null +++ b/lib/crc32.c @@ -0,0 +1,86 @@ +/* Copyright (C) 2002 Red Hat, Inc. + + 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, version 2. + + 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +#include <stdint.h> +#include "system.h" + + +/* Table computed with Mark Adler's makecrc.c utility. */ +static const uint32_t crc32_table[256] = +{ + 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, + 0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, + 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, + 0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, + 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856, + 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, + 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, + 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, + 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, + 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a, + 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599, + 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, + 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, + 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, + 0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e, + 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01, + 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed, + 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, + 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, + 0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, + 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, + 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5, + 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010, + 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, + 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, + 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, + 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615, + 0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, + 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344, + 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, + 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, + 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, + 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, + 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c, + 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef, + 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, + 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, + 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, + 0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c, + 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, + 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b, + 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, + 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, + 0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, + 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278, + 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7, + 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66, + 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, + 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, + 0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, + 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, + 0x2d02ef8d +}; + +uint32_t +crc32 (uint32_t crc, unsigned char *buf, size_t len) +{ + unsigned char *end; + + crc = ~crc; + for (end = buf + len; buf < end; ++buf) + crc = crc32_table[(crc ^ *buf) & 0xff] ^ (crc >> 8); + return ~crc; +} diff --git a/lib/crc32_file.c b/lib/crc32_file.c new file mode 100644 index 00000000..e6d468b4 --- /dev/null +++ b/lib/crc32_file.c @@ -0,0 +1,59 @@ +#include "system.h" +#include <errno.h> +#include <unistd.h> +#include <sys/stat.h> +#include <sys/mman.h> + +int +crc32_file (int fd, uint32_t *resp) +{ + unsigned char buffer[1024 * 8]; + uint32_t crc = 0; + off_t off = 0; + ssize_t count; + + struct stat st; + if (fstat (fd, &st) == 0) + { + /* Try mapping in the file data. */ + size_t mapsize = st.st_size; + void *mapped = mmap (NULL, mapsize, PROT_READ, MAP_PRIVATE, fd, 0); + if (mapped == MAP_FAILED && errno == ENOMEM) + { + const size_t pagesize = sysconf (_SC_PAGE_SIZE); + mapsize = ((mapsize / 2) + pagesize - 1) & -pagesize; + while (mapsize >= pagesize + && (mapped = mmap (NULL, mapsize, PROT_READ, MAP_PRIVATE, + fd, 0)) == MAP_FAILED && errno == ENOMEM) + mapsize /= 2; + } + if (mapped != MAP_FAILED) + { + do + { + if (st.st_size <= (off_t) mapsize) + { + *resp = crc32 (crc, mapped, st.st_size); + munmap (mapped, mapsize); + return 0; + } + crc = crc32 (crc, mapped, mapsize); + off += mapsize; + st.st_size -= mapsize; + } while (mmap (mapped, mapsize, PROT_READ, MAP_FIXED|MAP_PRIVATE, + fd, off) == mapped); + munmap (mapped, mapsize); + } + } + + while ((count = TEMP_FAILURE_RETRY (pread (fd, buffer, sizeof buffer, + off))) > 0) + { + off += count; + crc = crc32 (crc, buffer, count); + } + + *resp = crc; + + return count == 0 ? 0 : -1; +} diff --git a/lib/dynamicsizehash.c b/lib/dynamicsizehash.c new file mode 100644 index 00000000..61759636 --- /dev/null +++ b/lib/dynamicsizehash.c @@ -0,0 +1,316 @@ +/* Copyright (C) 2000, 2001, 2002, 2005 Red Hat, Inc. + Written by Ulrich Drepper <drepper@redhat.com>, 2000. + + This program is Open Source software; you can redistribute it and/or + modify it under the terms of the Open Software License version 1.0 as + published by the Open Source Initiative. + + You should have received a copy of the Open Software License along + with this program; if not, you may obtain a copy of the Open Software + License version 1.0 from http://www.opensource.org/licenses/osl.php or + by writing the Open Source Initiative c/o Lawrence Rosen, Esq., + 3001 King Ranch Road, Ukiah, CA 95482. */ + +#include <assert.h> +#include <stdlib.h> +#include <system.h> + +/* Before including this file the following macros must be defined: + + NAME name of the hash table structure. + TYPE data type of the hash table entries + COMPARE comparison function taking two pointers to TYPE objects + + The following macros if present select features: + + ITERATE iterating over the table entries is possible + REVERSE iterate in reverse order of insert + */ + + +static size_t +lookup (htab, hval, val) + NAME *htab; + unsigned long int hval; + TYPE val __attribute__ ((unused)); +{ + /* First hash function: simply take the modul but prevent zero. */ + size_t idx = 1 + hval % htab->size; + + if (htab->table[idx].hashval != 0) + { + unsigned long int hash; + + if (htab->table[idx].hashval == hval + && COMPARE (htab->table[idx].data, val) == 0) + return idx; + + /* Second hash function as suggested in [Knuth]. */ + hash = 1 + hval % (htab->size - 2); + + do + { + if (idx <= hash) + idx = htab->size + idx - hash; + else + idx -= hash; + + /* If entry is found use it. */ + if (htab->table[idx].hashval == hval + && COMPARE (htab->table[idx].data, val) == 0) + return idx; + } + while (htab->table[idx].hashval); + } + return idx; +} + + +static void +insert_entry_2 (NAME *htab, unsigned long int hval, size_t idx, TYPE data) +{ +#ifdef ITERATE + if (htab->table[idx].hashval == 0) + { +# ifdef REVERSE + htab->table[idx].next = htab->first; + htab->first = &htab->table[idx]; +# else + /* Add the new value to the list. */ + if (htab->first == NULL) + htab->first = htab->table[idx].next = &htab->table[idx]; + else + { + htab->table[idx].next = htab->first->next; + htab->first = htab->first->next = &htab->table[idx]; + } +# endif + } +#endif + + htab->table[idx].hashval = hval; + htab->table[idx].data = data; + + ++htab->filled; + if (100 * htab->filled > 90 * htab->size) + { + /* Table is filled more than 90%. Resize the table. */ +#ifdef ITERATE + __typeof__ (htab->first) first; +# ifndef REVERSE + __typeof__ (htab->first) runp; +# endif +#else + unsigned long int old_size = htab->size; +#endif +#define _TABLE(name) \ + name##_ent *table = htab->table +#define TABLE(name) _TABLE (name) + TABLE(NAME); + + htab->size = next_prime (htab->size * 2); + htab->filled = 0; +#ifdef ITERATE + first = htab->first; + htab->first = NULL; +#endif + htab->table = calloc ((1 + htab->size), sizeof (htab->table[0])); + if (htab->table == NULL) + { + /* We cannot enlarge the table. Live with what we got. This + might lead to an infinite loop at some point, though. */ + htab->table = table; + return; + } + + /* Add the old entries to the new table. When iteration is + supported we maintain the order. */ +#ifdef ITERATE +# ifdef REVERSE + while (first != NULL) + { + insert_entry_2 (htab, first->hashval, + lookup (htab, first->hashval, first->data), + first->data); + + first = first->next; + } +# else + assert (first != NULL); + runp = first = first->next; + do + insert_entry_2 (htab, runp->hashval, + lookup (htab, runp->hashval, runp->data), runp->data); + while ((runp = runp->next) != first); +# endif +#else + for (idx = 1; idx <= old_size; ++idx) + if (table[idx].hashval != 0) + insert_entry_2 (htab, table[idx].hashval, + lookup (htab, table[idx].hashval, table[idx].data), + table[idx].data); +#endif + + free (table); + } +} + + +int +#define INIT(name) _INIT (name) +#define _INIT(name) \ + name##_init +INIT(NAME) (htab, init_size) + NAME *htab; + unsigned long int init_size; +{ + /* We need the size to be a prime. */ + init_size = next_prime (init_size); + + /* Initialize the data structure. */ + htab->size = init_size; + htab->filled = 0; +#ifdef ITERATE + htab->first = NULL; +#endif + htab->table = (void *) calloc ((init_size + 1), sizeof (htab->table[0])); + if (htab->table == NULL) + return -1; + + return 0; +} + + +int +#define FREE(name) _FREE (name) +#define _FREE(name) \ + name##_free +FREE(NAME) (htab) + NAME *htab; +{ + free (htab->table); + return 0; +} + + +int +#define INSERT(name) _INSERT (name) +#define _INSERT(name) \ + name##_insert +INSERT(NAME) (htab, hval, data) + NAME *htab; + unsigned long int hval; + TYPE data; +{ + size_t idx; + + /* Make the hash value nonzero. */ + hval = hval ?: 1; + + idx = lookup (htab, hval, data); + + if (htab->table[idx].hashval != 0) + /* We don't want to overwrite the old value. */ + return -1; + + /* An empty bucket has been found. */ + insert_entry_2 (htab, hval, idx, data); + return 0; +} + + +#ifdef OVERWRITE +int +#define INSERT(name) _INSERT (name) +#define _INSERT(name) \ + name##_overwrite +INSERT(NAME) (htab, hval, data) + NAME *htab; + unsigned long int hval; + TYPE data; +{ + size_t idx; + + /* Make the hash value nonzero. */ + hval = hval ?: 1; + + idx = lookup (htab, hval, data); + + /* The correct bucket has been found. */ + insert_entry_2 (htab, hval, idx, data); + return 0; +} +#endif + + +TYPE +#define FIND(name) _FIND (name) +#define _FIND(name) \ + name##_find +FIND(NAME) (htab, hval, val) + NAME *htab; + unsigned long int hval; + TYPE val; +{ + size_t idx; + + /* Make the hash value nonzero. */ + hval = hval ?: 1; + + idx = lookup (htab, hval, val); + + if (htab->table[idx].hashval == 0) + return NULL; + + return htab->table[idx].data; +} + + +#ifdef ITERATE +# define ITERATEFCT(name) _ITERATEFCT (name) +# define _ITERATEFCT(name) \ + name##_iterate +TYPE +ITERATEFCT(NAME) (htab, ptr) + NAME *htab; + void **ptr; +{ + void *p = *ptr; + +# define TYPENAME(name) _TYPENAME (name) +# define _TYPENAME(name) name##_ent + +# ifdef REVERSE + if (p == NULL) + p = htab->first; + else + p = ((TYPENAME(NAME) *) p)->next; + + if (p == NULL) + { + *ptr = NULL; + return NULL; + } +# else + if (p == NULL) + { + if (htab->first == NULL) + return NULL; + p = htab->first->next; + } + else + { + if (p == htab->first) + return NULL; + + p = ((TYPENAME(NAME) *) p)->next; + } +# endif + + /* Prepare the next element. If possible this will pull the data + into the cache, for reading. */ + __builtin_prefetch (((TYPENAME(NAME) *) p)->next, 0, 2); + + return ((TYPENAME(NAME) *) (*ptr = p))->data; +} +#endif diff --git a/lib/dynamicsizehash.h b/lib/dynamicsizehash.h new file mode 100644 index 00000000..39a706fd --- /dev/null +++ b/lib/dynamicsizehash.h @@ -0,0 +1,107 @@ +/* Copyright (C) 2000, 2001, 2002 Red Hat, Inc. + Written by Ulrich Drepper <drepper@redhat.com>, 2000. + + This program is Open Source software; you can redistribute it and/or + modify it under the terms of the Open Software License version 1.0 as + published by the Open Source Initiative. + + You should have received a copy of the Open Software License along + with this program; if not, you may obtain a copy of the Open Software + License version 1.0 from http://www.opensource.org/licenses/osl.php or + by writing the Open Source Initiative c/o Lawrence Rosen, Esq., + 3001 King Ranch Road, Ukiah, CA 95482. */ + +#include <stddef.h> + +/* Before including this file the following macros must be defined: + + NAME name of the hash table structure. + TYPE data type of the hash table entries + + The following macros if present select features: + + ITERATE iterating over the table entries is possible + */ + + +/* Optionally include an entry pointing to the first used entry. */ +#ifdef ITERATE +# define FIRST(name) name##_ent *first; +# define NEXT(name) struct name##_ent *next; +#else +# define FIRST(name) +# define NEXT(name) +#endif + + +/* Defined separately. */ +extern size_t next_prime (size_t seed); + + +/* Table entry type. */ +#define _DYNHASHENTTYPE(name) \ + typedef struct name##_ent \ + { \ + unsigned long int hashval; \ + TYPE data; \ + NEXT (name) \ + } name##_ent +#define DYNHASHENTTYPE(name) _DYNHASHENTTYPE (name) +DYNHASHENTTYPE (NAME); + + +/* Type of the dynamic hash table data structure. */ +#define _DYNHASHTYPE(name) \ +typedef struct \ +{ \ + unsigned long int size; \ + unsigned long int filled; \ + name##_ent *table; \ + FIRST (name) \ +} name +#define DYNHASHTYPE(name) _DYNHASHTYPE (name) +DYNHASHTYPE (NAME); + + + +#define _FUNCTIONS(name) \ +/* Initialize the hash table. */ \ +extern int name##_init (name *htab, unsigned long int init_size); \ + \ +/* Free resources allocated for hash table. */ \ +extern int name##_free (name *htab); \ + \ +/* Insert new entry. */ \ +extern int name##_insert (name *htab, unsigned long int hval, TYPE data); \ + \ +/* Insert new entry, possibly overwrite old entry. */ \ +extern int name##_overwrite (name *htab, unsigned long int hval, TYPE data); \ + \ +/* Find entry in hash table. */ \ +extern TYPE name##_find (name *htab, unsigned long int hval, TYPE val); +#define FUNCTIONS(name) _FUNCTIONS (name) +FUNCTIONS (NAME) + + +#ifdef ITERATE +# define _XFUNCTIONS(name) \ +/* Get next element in table. */ \ +extern TYPE name##_iterate (name *htab, void **ptr); +# define XFUNCTIONS(name) _XFUNCTIONS (name) +XFUNCTIONS (NAME) +#endif + +#ifndef NO_UNDEF +# undef DYNHASHENTTYPE +# undef DYNHASHTYPE +# undef FUNCTIONS +# undef _FUNCTIONS +# undef XFUNCTIONS +# undef _XFUNCTIONS +# undef NAME +# undef TYPE +# undef ITERATE +# undef COMPARE +# undef FIRST +# undef NEXT +#endif diff --git a/lib/fixedsizehash.h b/lib/fixedsizehash.h new file mode 100644 index 00000000..c1c607dd --- /dev/null +++ b/lib/fixedsizehash.h @@ -0,0 +1,255 @@ +/* Fixed size hash table with internal linking. + Copyright (C) 2000, 2001, 2002, 2004, 2005 Red Hat, Inc. + Written by Ulrich Drepper <drepper@redhat.com>, 2000. + + 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, version 2. + + 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +#include <errno.h> +#include <stdlib.h> +#include <string.h> +#include <sys/cdefs.h> +#include <sys/param.h> + +#include <system.h> + +#define CONCAT(t1,t2) __CONCAT (t1,t2) + +/* Before including this file the following macros must be defined: + + TYPE data type of the hash table entries + HASHFCT name of the hashing function to use + HASHTYPE type used for the hashing value + COMPARE comparison function taking two pointers to TYPE objects + CLASS can be defined to `static' to avoid exporting the functions + PREFIX prefix to be used for function and data type names + STORE_POINTER if defined the table stores a pointer and not an element + of type TYPE + INSERT_HASH if defined alternate insert function which takes a hash + value is defined + NO_FINI_FCT if defined the fini function is not defined +*/ + + +/* Defined separately. */ +extern size_t next_prime (size_t seed); + + +/* Set default values. */ +#ifndef HASHTYPE +# define HASHTYPE size_t +#endif + +#ifndef CLASS +# define CLASS +#endif + +#ifndef PREFIX +# define PREFIX +#endif + + +/* The data structure. */ +struct CONCAT(PREFIX,fshash) +{ + size_t nslots; + struct CONCAT(PREFIX,fshashent) + { + HASHTYPE hval; +#ifdef STORE_POINTER +# define ENTRYP(el) (el).entry + TYPE *entry; +#else +# define ENTRYP(el) &(el).entry + TYPE entry; +#endif + } table[0]; +}; + + +/* Constructor for the hashing table. */ +CLASS struct CONCAT(PREFIX,fshash) * +CONCAT(PREFIX,fshash_init) (size_t nelems) +{ + struct CONCAT(PREFIX,fshash) *result; + /* We choose a size for the hashing table 150% over the number of + entries. This will guarantee short medium search lengths. */ + const size_t max_size_t = ~((size_t) 0); + + if (nelems >= (max_size_t / 3) * 2) + { + errno = EINVAL; + return NULL; + } + + /* Adjust the size to be used for the hashing table. */ + nelems = next_prime (MAX ((nelems * 3) / 2, 10)); + + /* Allocate the data structure for the result. */ + result = (struct CONCAT(PREFIX,fshash) *) + xcalloc (sizeof (struct CONCAT(PREFIX,fshash)) + + (nelems + 1) * sizeof (struct CONCAT(PREFIX,fshashent)), 1); + if (result == NULL) + return NULL; + + result->nslots = nelems; + + return result; +} + + +#ifndef NO_FINI_FCT +CLASS void +CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab) +{ + free (htab); +} +#endif + + +static struct CONCAT(PREFIX,fshashent) * +CONCAT(PREFIX,fshash_lookup) (struct CONCAT(PREFIX,fshash) *htab, + HASHTYPE hval, TYPE *data) +{ + size_t idx = 1 + hval % htab->nslots; + + if (htab->table[idx].hval != 0) + { + HASHTYPE hash; + + /* See whether this is the same entry. */ + if (htab->table[idx].hval == hval + && COMPARE (data, ENTRYP (htab->table[idx])) == 0) + return &htab->table[idx]; + + /* Second hash function as suggested in [Knuth]. */ + hash = 1 + hval % (htab->nslots - 2); + + do + { + if (idx <= hash) + idx = htab->nslots + idx - hash; + else + idx -= hash; + + if (htab->table[idx].hval == hval + && COMPARE (data, ENTRYP(htab->table[idx])) == 0) + return &htab->table[idx]; + } + while (htab->table[idx].hval != 0); + } + + return &htab->table[idx]; +} + + +CLASS int +__attribute__ ((unused)) +CONCAT(PREFIX,fshash_insert) (struct CONCAT(PREFIX,fshash) *htab, + const char *str, + size_t len __attribute__ ((unused)), TYPE *data) +{ + HASHTYPE hval = HASHFCT (str, len ?: strlen (str)); + struct CONCAT(PREFIX,fshashent) *slot; + + slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data); + if (slot->hval != 0) + /* We don't want to overwrite the old value. */ + return -1; + + slot->hval = hval; +#ifdef STORE_POINTER + slot->entry = data; +#else + slot->entry = *data; +#endif + + return 0; +} + + +#ifdef INSERT_HASH +CLASS int +__attribute__ ((unused)) +CONCAT(PREFIX,fshash_insert_hash) (struct CONCAT(PREFIX,fshash) *htab, + HASHTYPE hval, TYPE *data) +{ + struct CONCAT(PREFIX,fshashent) *slot; + + slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data); + if (slot->hval != 0) + /* We don't want to overwrite the old value. */ + return -1; + + slot->hval = hval; +#ifdef STORE_POINTER + slot->entry = data; +#else + slot->entry = *data; +#endif + + return 0; +} +#endif + + +CLASS int +__attribute__ ((unused)) +CONCAT(PREFIX,fshash_overwrite) (struct CONCAT(PREFIX,fshash) *htab, + const char *str, + size_t len __attribute__ ((unused)), + TYPE *data) +{ + HASHTYPE hval = HASHFCT (str, len ?: strlen (str)); + struct CONCAT(PREFIX,fshashent) *slot; + + slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data); + slot->hval = hval; +#ifdef STORE_POINTER + slot->entry = data; +#else + slot->entry = *data; +#endif + + return 0; +} + + +CLASS const TYPE * +CONCAT(PREFIX,fshash_find) (const struct CONCAT(PREFIX,fshash) *htab, + const char *str, + size_t len __attribute__ ((unused)), TYPE *data) +{ + HASHTYPE hval = HASHFCT (str, len ?: strlen (str)); + struct CONCAT(PREFIX,fshashent) *slot; + + slot = CONCAT(PREFIX,fshash_lookup) ((struct CONCAT(PREFIX,fshash) *) htab, + hval, data); + if (slot->hval == 0) + /* Not found. */ + return NULL; + + return ENTRYP(*slot); +} + + +/* Unset the macros we expect. */ +#undef TYPE +#undef HASHFCT +#undef HASHTYPE +#undef COMPARE +#undef CLASS +#undef PREFIX +#undef INSERT_HASH +#undef STORE_POINTER +#undef NO_FINI_FCT diff --git a/lib/list.h b/lib/list.h new file mode 100644 index 00000000..c039a0ba --- /dev/null +++ b/lib/list.h @@ -0,0 +1,85 @@ +/* Copyright (C) 2001, 2002, 2003 Red Hat, Inc. + Written by Ulrich Drepper <drepper@redhat.com>, 2001. + + This program is Open Source software; you can redistribute it and/or + modify it under the terms of the Open Software License version 1.0 as + published by the Open Source Initiative. + + You should have received a copy of the Open Software License along + with this program; if not, you may obtain a copy of the Open Software + License version 1.0 from http://www.opensource.org/licenses/osl.php or + by writing the Open Source Initiative c/o Lawrence Rosen, Esq., + 3001 King Ranch Road, Ukiah, CA 95482. */ + +#ifndef LIST_H +#define LIST_H 1 + +/* Add element to the end of a circular, double-linked list. */ +#define CDBL_LIST_ADD_REAR(first, newp) \ + do { \ + __typeof (newp) _newp = (newp); \ + assert (_newp->next == NULL); \ + assert (_newp->previous == NULL); \ + if (unlikely ((first) == NULL)) \ + (first) = _newp->next = _newp->previous = _newp; \ + else \ + { \ + _newp->next = (first); \ + _newp->previous = (first)->previous; \ + _newp->previous->next = _newp->next->previous = _newp; \ + } \ + } while (0) + +/* Remove element from circular, double-linked list. */ +#define CDBL_LIST_DEL(first, elem) \ + do { \ + __typeof (elem) _elem = (elem); \ + /* Check whether the element is indeed on the list. */ \ + assert (first != NULL && _elem != NULL \ + && (first != elem \ + || ({ __typeof (elem) _runp = first->next; \ + while (_runp != first) \ + if (_runp == _elem) \ + break; \ + else \ + _runp = _runp->next; \ + _runp == _elem; }))); \ + if (unlikely (_elem->next == _elem)) \ + first = NULL; \ + else \ + { \ + _elem->next->previous = _elem->previous; \ + _elem->previous->next = _elem->next; \ + if (unlikely (first == _elem)) \ + first = _elem->next; \ + } \ + assert ((_elem->next = _elem->previous = NULL, 1)); \ + } while (0) + + +/* Add element to the front of a single-linked list. */ +#define SNGL_LIST_PUSH(first, newp) \ + do { \ + __typeof (newp) _newp = (newp); \ + assert (_newp->next == NULL); \ + _newp->next = first; \ + first = _newp; \ + } while (0) + + +/* Add element to the rear of a circular single-linked list. */ +#define CSNGL_LIST_ADD_REAR(first, newp) \ + do { \ + __typeof (newp) _newp = (newp); \ + assert (_newp->next == NULL); \ + if (unlikely ((first) == NULL)) \ + (first) = _newp->next = _newp; \ + else \ + { \ + _newp->next = (first)->next; \ + (first) = (first)->next = _newp; \ + } \ + } while (0) + + +#endif /* list.h */ diff --git a/lib/next_prime.c b/lib/next_prime.c new file mode 100644 index 00000000..5d608046 --- /dev/null +++ b/lib/next_prime.c @@ -0,0 +1,54 @@ +/* Determine prime number. + Copyright (C) 2000, 2002 Free Software Foundation, Inc. + Written by Ulrich Drepper <drepper@redhat.com>, 2000. + + 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, version 2. + + 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +#include <stddef.h> + + +/* Test whether CANDIDATE is a prime. */ +static int +is_prime (size_t candidate) +{ + /* No even number and none less than 10 will be passed here. */ + size_t divn = 3; + size_t sq = divn * divn; + + while (sq < candidate && candidate % divn != 0) + { + size_t old_sq = sq; + ++divn; + sq += 4 * divn; + if (sq < old_sq) + return 1; + ++divn; + } + + return candidate % divn != 0; +} + + +/* We need primes for the table size. */ +size_t +next_prime (size_t seed) +{ + /* Make it definitely odd. */ + seed |= 1; + + while (!is_prime (seed)) + seed += 2; + + return seed; +} diff --git a/lib/system.h b/lib/system.h new file mode 100644 index 00000000..e29c2dbb --- /dev/null +++ b/lib/system.h @@ -0,0 +1,40 @@ +/* Copyright (C) 2000, 2002, 2004, 2005 Free Software Foundation, Inc. + + 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, version 2. + + 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + +#ifndef LIB_SYSTEM_H +#define LIB_SYSTEM_H 1 + +#include <stddef.h> +#include <stdint.h> + +extern void *xmalloc (size_t) __attribute__ ((__malloc__)); +extern void *xcalloc (size_t, size_t) __attribute__ ((__malloc__)); +extern void *xrealloc (void *, size_t) __attribute__ ((__malloc__)); + +extern char *xstrdup (const char *) __attribute__ ((__malloc__)); +extern char *xstrndup (const char *, size_t) __attribute__ ((__malloc__)); + + +extern uint32_t crc32 (uint32_t crc, unsigned char *buf, size_t len); +extern int crc32_file (int fd, uint32_t *resp); + +/* A special gettext function we use if the strings are too short. */ +#define sgettext(Str) \ + ({ const char *__res = strrchr (gettext (Str), '|'); \ + __res ? __res + 1 : Str; }) + +#define gettext_noop(Str) Str + +#endif /* system.h */ diff --git a/lib/xmalloc.c b/lib/xmalloc.c new file mode 100644 index 00000000..0934e641 --- /dev/null +++ b/lib/xmalloc.c @@ -0,0 +1,68 @@ +/* Copyright (C) 2000, 2002 Free Software Foundation, Inc. + + This program is Open Source software; you can redistribute it and/or + modify it under the terms of the Open Software License version 1.0 as + published by the Open Source Initiative. + + You should have received a copy of the Open Software License along + with this program; if not, you may obtain a copy of the Open Software + License version 1.0 from http://www.opensource.org/licenses/osl.php or + by writing the Open Source Initiative c/o Lawrence Rosen, Esq., + 3001 King Ranch Road, Ukiah, CA 95482. */ + +#ifdef HAVE_CONFIG_H +# include <config.h> +#endif + +#include <error.h> +#include <libintl.h> +#include <stddef.h> +#include <stdlib.h> +#include <sys/types.h> +#include "system.h" + +#ifndef _ +# define _(str) gettext (str) +#endif + + +/* Allocate N bytes of memory dynamically, with error checking. */ +void * +xmalloc (n) + size_t n; +{ + void *p; + + p = malloc (n); + if (p == NULL) + error (EXIT_FAILURE, 0, _("memory exhausted")); + return p; +} + + +/* Allocate memory for N elements of S bytes, with error checking. */ +void * +xcalloc (n, s) + size_t n, s; +{ + void *p; + + p = calloc (n, s); + if (p == NULL) + error (EXIT_FAILURE, 0, _("memory exhausted")); + return p; +} + + +/* Change the size of an allocated block of memory P to N bytes, + with error checking. */ +void * +xrealloc (p, n) + void *p; + size_t n; +{ + p = realloc (p, n); + if (p == NULL) + error (EXIT_FAILURE, 0, _("memory exhausted")); + return p; +} diff --git a/lib/xstrdup.c b/lib/xstrdup.c new file mode 100644 index 00000000..ad70a630 --- /dev/null +++ b/lib/xstrdup.c @@ -0,0 +1,27 @@ +/* Copyright (C) 2000, 2002 Free Software Foundation, Inc. + + This program is Open Source software; you can redistribute it and/or + modify it under the terms of the Open Software License version 1.0 as + published by the Open Source Initiative. + + You should have received a copy of the Open Software License along + with this program; if not, you may obtain a copy of the Open Software + License version 1.0 from http://www.opensource.org/licenses/osl.php or + by writing the Open Source Initiative c/o Lawrence Rosen, Esq., + 3001 King Ranch Road, Ukiah, CA 95482. */ + +#ifdef HAVE_CONFIG_H +# include <config.h> +#endif + +#include <string.h> +#include "system.h" + + +/* Return a newly allocated copy of STRING. */ +char * +xstrdup (string) + const char *string; +{ + return strcpy (xmalloc (strlen (string) + 1), string); +} diff --git a/lib/xstrndup.c b/lib/xstrndup.c new file mode 100644 index 00000000..946f3616 --- /dev/null +++ b/lib/xstrndup.c @@ -0,0 +1,31 @@ +/* Copyright (C) 2000, 2002 Free Software Foundation, Inc. + + This program is Open Source software; you can redistribute it and/or + modify it under the terms of the Open Software License version 1.0 as + published by the Open Source Initiative. + + You should have received a copy of the Open Software License along + with this program; if not, you may obtain a copy of the Open Software + License version 1.0 from http://www.opensource.org/licenses/osl.php or + by writing the Open Source Initiative c/o Lawrence Rosen, Esq., + 3001 King Ranch Road, Ukiah, CA 95482. */ + +#ifdef HAVE_CONFIG_H +# include <config.h> +#endif + +#include <string.h> +#include "system.h" + + +/* Return a newly allocated copy of STRING. */ +char * +xstrndup (string, n) + const char *string; + size_t n; +{ + char *res; + size_t len = strnlen (string, n); + *((char *) mempcpy ((res = xmalloc (len + 1)), string, len)) = '\0'; + return res; +} |