1 files changed, 392 insertions, 0 deletions
diff --git a/rtemstoolkit/elftoolchain/libelftc/elftc_string_table.c b/rtemstoolkit/elftoolchain/libelftc/elftc_string_table.c
new file mode 100644
index 0000000..bba9ac6
--- /dev/null
+++ b/rtemstoolkit/elftoolchain/libelftc/elftc_string_table.c
@@ -0,0 +1,392 @@
+/*-
+ * Copyright (c) 2013, Joseph Koshy
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer
+ *    in this position and unchanged.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <sys/param.h>
+#include <sys/queue.h>
+
+#include <assert.h>
+#include <errno.h>
+#include <gelf.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "libelftc.h"
+#include "_libelftc.h"
+
+ELFTC_VCSID("$Id: elftc_string_table.c 2869 2013-01-06 13:29:18Z jkoshy $");
+
+#define	ELFTC_STRING_TABLE_DEFAULT_SIZE			(4*1024)
+#define ELFTC_STRING_TABLE_EXPECTED_STRING_SIZE		16
+#define ELFTC_STRING_TABLE_EXPECTED_CHAIN_LENGTH	8
+#define	ELFTC_STRING_TABLE_POOL_SIZE_INCREMENT		(4*1024)
+
+struct _Elftc_String_Table_Entry {
+	int		ste_idx;
+	SLIST_ENTRY(_Elftc_String_Table_Entry) ste_next;
+};
+
+#define	ELFTC_STRING_TABLE_COMPACTION_FLAG	0x1
+#define	ELFTC_STRING_TABLE_LENGTH(st)		((st)->st_len >> 1)
+#define	ELFTC_STRING_TABLE_CLEAR_COMPACTION_FLAG(st) do {		\
+		(st)->st_len &= ~ELFTC_STRING_TABLE_COMPACTION_FLAG;	\
+	} while (0)
+#define	ELFTC_STRING_TABLE_SET_COMPACTION_FLAG(st) do {			\
+		(st)->st_len |= ELFTC_STRING_TABLE_COMPACTION_FLAG;	\
+	} while (0)
+#define	ELFTC_STRING_TABLE_UPDATE_LENGTH(st, len) do {		\
+		(st)->st_len =					\
+		    ((st)->st_len &				\
+			ELFTC_STRING_TABLE_COMPACTION_FLAG) |	\
+		    ((len) << 1);				\
+	} while (0)
+
+struct _Elftc_String_Table {
+	unsigned int		st_len; /* length and flags */
+	int		st_nbuckets;
+	int		st_string_pool_size;
+	char		*st_string_pool;
+	SLIST_HEAD(_Elftc_String_Table_Bucket,
+	    _Elftc_String_Table_Entry) st_buckets[];
+};
+
+static struct _Elftc_String_Table_Entry *
+elftc_string_table_find_hash_entry(Elftc_String_Table *st, const char *string,
+    int *rhashindex)
+{
+	struct _Elftc_String_Table_Entry *ste;
+	int hashindex;
+	char *s;
+
+	hashindex = libelftc_hash_string(string) % st->st_nbuckets;
+
+	if (rhashindex)
+		*rhashindex = hashindex;
+
+	SLIST_FOREACH(ste, &st->st_buckets[hashindex], ste_next) {
+		s = st->st_string_pool + abs(ste->ste_idx);
+
+		assert(s > st->st_string_pool &&
+		    s < st->st_string_pool + st->st_string_pool_size);
+
+		if (strcmp(s, string) == 0)
+			return (ste);
+	}
+
+	return (NULL);
+}
+
+static int
+elftc_string_table_add_to_pool(Elftc_String_Table *st, const char *string)
+{
+	char *newpool;
+	int len, newsize, stlen;
+
+	len = strlen(string) + 1; /* length, including the trailing NUL */
+	stlen = ELFTC_STRING_TABLE_LENGTH(st);
+
+	/* Resize the pool, if needed. */
+	if (stlen + len >= st->st_string_pool_size) {
+		newsize = roundup(st->st_string_pool_size +
+		    ELFTC_STRING_TABLE_POOL_SIZE_INCREMENT,
+		    ELFTC_STRING_TABLE_POOL_SIZE_INCREMENT);
+		if ((newpool = realloc(st->st_string_pool, newsize)) ==
+		    NULL)
+			return (0);
+		st->st_string_pool = newpool;
+		st->st_string_pool_size = newsize;
+	}
+
+	strcpy(st->st_string_pool + stlen, string);
+	ELFTC_STRING_TABLE_UPDATE_LENGTH(st, stlen + len);
+
+	return (stlen);
+}
+
+Elftc_String_Table *
+elftc_string_table_create(int sizehint)
+{
+	int n, nbuckets, tablesize;
+	struct _Elftc_String_Table *st;
+
+	if (sizehint < ELFTC_STRING_TABLE_DEFAULT_SIZE)
+		sizehint = ELFTC_STRING_TABLE_DEFAULT_SIZE;
+
+	nbuckets = sizehint / (ELFTC_STRING_TABLE_EXPECTED_CHAIN_LENGTH *
+	    ELFTC_STRING_TABLE_EXPECTED_STRING_SIZE);
+
+	tablesize = sizeof(struct _Elftc_String_Table) +
+	    nbuckets * sizeof(struct _Elftc_String_Table_Bucket);
+
+	if ((st = malloc(tablesize)) == NULL)
+		return (NULL);
+	if ((st->st_string_pool = malloc(sizehint)) == NULL) {
+		free(st);
+		return (NULL);
+	}
+
+	for (n = 0; n < nbuckets; n++)
+		SLIST_INIT(&st->st_buckets[n]);
+
+	st->st_len = 0;
+	st->st_nbuckets = nbuckets;
+	st->st_string_pool_size = sizehint;
+	*st->st_string_pool = '\0';
+	ELFTC_STRING_TABLE_UPDATE_LENGTH(st, 1);
+
+	return (st);
+}
+
+void
+elftc_string_table_destroy(Elftc_String_Table *st)
+{
+	int n;
+	struct _Elftc_String_Table_Entry *s, *t;
+
+	for (n = 0; n < st->st_nbuckets; n++)
+		SLIST_FOREACH_SAFE(s, &st->st_buckets[n], ste_next, t)
+		    free(s);
+	free(st->st_string_pool);
+	free(st);
+
+	return;
+}
+
+Elftc_String_Table *
+elftc_string_table_from_section(Elf_Scn *scn, int sizehint)
+{
+	int len;
+	Elf_Data *d;
+	GElf_Shdr sh;
+	const char *s, *end;
+	Elftc_String_Table *st;
+
+	/* Verify the type of the section passed in. */
+	if (gelf_getshdr(scn, &sh) == NULL ||
+	    sh.sh_type != SHT_STRTAB) {
+		errno = EINVAL;
+		return (NULL);
+	}
+
+	if ((d = elf_getdata(scn, NULL)) == NULL ||
+	    d->d_size == 0) {
+		errno = EINVAL;
+		return (NULL);
+	}
+
+	if ((st = elftc_string_table_create(sizehint)) == NULL)
+		return (NULL);
+
+	s = d->d_buf;
+
+	/*
+	 * Verify that the first byte of the data buffer is '\0'.
+	 */
+	if (*s != '\0') {
+		errno = EINVAL;
+		goto fail;
+	}
+
+	end = s + d->d_size;
+
+	/*
+	 * Skip the first '\0' and insert the strings in the buffer,
+	 * in order.
+	 */
+	for (s += 1; s < end; s += len) {
+		if (elftc_string_table_insert(st, s) == 0)
+			goto fail;
+
+		len = strlen(s) + 1; /* Include space for the trailing NUL. */
+	}
+
+	return (st);
+
+fail:
+	if (st)
+		(void) elftc_string_table_destroy(st);
+
+	return (NULL);
+}
+
+const char *
+elftc_string_table_image(Elftc_String_Table *st, size_t *size)
+{
+	char *r, *s, *end;
+	struct _Elftc_String_Table_Entry *ste;
+	struct _Elftc_String_Table_Bucket *head;
+	int copied, hashindex, offset, length, newsize;
+
+	/*
+	 * For the common case of a string table has not seen
+	 * a string deletion, we can just export the current
+	 * pool.
+	 */
+	if ((st->st_len & ELFTC_STRING_TABLE_COMPACTION_FLAG) == 0) {
+		if (size)
+			*size = ELFTC_STRING_TABLE_LENGTH(st);
+		return (st->st_string_pool);
+	}
+
+	/*
+	 * Otherwise, compact the string table in-place.
+	 */
+	assert(*st->st_string_pool == '\0');
+
+	newsize = 1;
+	end = st->st_string_pool + ELFTC_STRING_TABLE_LENGTH(st);
+
+	for (r = s = st->st_string_pool + 1;
+	     s < end;
+	     s += length, r += copied) {
+
+		copied = 0;
+		length = strlen(s) + 1;
+
+		ste = elftc_string_table_find_hash_entry(st, s,
+		    &hashindex);
+		head = &st->st_buckets[hashindex];
+
+		assert(ste != NULL);
+
+		/* Ignore deleted strings. */
+		if (ste->ste_idx < 0) {
+			SLIST_REMOVE(head, ste, _Elftc_String_Table_Entry,
+			    ste_next);
+			free(ste);
+			continue;
+		}
+
+		/* Move 'live' strings up. */
+		offset = newsize;
+		newsize += length;
+		copied = length;
+
+		if (r == s)	/* Nothing removed yet. */
+			continue;
+
+		memmove(r, s, copied);
+
+		/* Update the index for this entry. */
+		ste->ste_idx = offset;
+	}
+
+	ELFTC_STRING_TABLE_CLEAR_COMPACTION_FLAG(st);
+	ELFTC_STRING_TABLE_UPDATE_LENGTH(st, newsize);
+
+	if (size)
+		*size = newsize;
+
+	return (st->st_string_pool);
+}
+
+size_t
+elftc_string_table_insert(Elftc_String_Table *st, const char *string)
+{
+	int hashindex, idx;
+	struct _Elftc_String_Table_Entry *ste;
+
+	hashindex = 0;
+
+	ste = elftc_string_table_find_hash_entry(st, string, &hashindex);
+
+	assert(hashindex >= 0 && hashindex < st->st_nbuckets);
+
+	if (ste == NULL) {
+		if ((ste = malloc(sizeof(*ste))) == NULL)
+			return (0);
+		if ((ste->ste_idx = elftc_string_table_add_to_pool(st,
+			    string)) == 0) {
+			free(ste);
+			return (0);
+		}
+
+		SLIST_INSERT_HEAD(&st->st_buckets[hashindex], ste, ste_next);
+	}
+
+	idx = ste->ste_idx;
+	if (idx < 0) 		/* Undelete. */
+		ste->ste_idx = idx = (- idx);
+
+	return (idx);
+}
+
+size_t
+elftc_string_table_lookup(Elftc_String_Table *st, const char *string)
+{
+	int hashindex, idx;
+	struct _Elftc_String_Table_Entry *ste;
+
+	ste = elftc_string_table_find_hash_entry(st, string, &hashindex);
+
+	assert(hashindex >= 0 && hashindex < st->st_nbuckets);
+
+	if (ste == NULL || (idx = ste->ste_idx) < 0)
+		return (0);
+
+	return (idx);
+}
+
+int
+elftc_string_table_remove(Elftc_String_Table *st, const char *string)
+{
+	int idx;
+	struct _Elftc_String_Table_Entry *ste;
+
+	ste = elftc_string_table_find_hash_entry(st, string, NULL);
+
+	if (ste == NULL || (idx = ste->ste_idx) < 0)
+		return (ELFTC_FAILURE);
+
+	assert(idx > 0 && idx < (int) ELFTC_STRING_TABLE_LENGTH(st));
+
+	ste->ste_idx = (- idx);
+
+	ELFTC_STRING_TABLE_SET_COMPACTION_FLAG(st);
+
+	return (ELFTC_SUCCESS);
+}
+
+const char *
+elftc_string_table_to_string(Elftc_String_Table *st, size_t offset)
+{
+	const char *s;
+
+	s = st->st_string_pool + offset;
+
+	/*
+	 * Check for:
+	 * - An offset value within pool bounds.
+	 * - A non-NUL byte at the specified offset.
+	 * - The end of the prior string at offset - 1.
+	 */
+	if (offset == 0 || offset >= ELFTC_STRING_TABLE_LENGTH(st) ||
+	    *s == '\0' || *(s - 1) != '\0') {
+		errno = EINVAL;
+		return (NULL);
+	}
+
+	return (s);
+}