[80425] branches/gsoc11-rev-upgrade/base/src/libmachista1.0
cal at macports.org
cal at macports.org
Tue Jul 12 10:21:46 PDT 2011
Revision: 80425
http://trac.macports.org/changeset/80425
Author: cal at macports.org
Date: 2011-07-12 10:21:45 -0700 (Tue, 12 Jul 2011)
Log Message:
-----------
rev-upgrade: Added hashmap to libmachista to prevent unnecessary I/O
Modified Paths:
--------------
branches/gsoc11-rev-upgrade/base/src/libmachista1.0/Makefile
branches/gsoc11-rev-upgrade/base/src/libmachista1.0/libmachista.c
branches/gsoc11-rev-upgrade/base/src/libmachista1.0/libmachista.h
Added Paths:
-----------
branches/gsoc11-rev-upgrade/base/src/libmachista1.0/hashmap.c
branches/gsoc11-rev-upgrade/base/src/libmachista1.0/hashmap.h
Modified: branches/gsoc11-rev-upgrade/base/src/libmachista1.0/Makefile
===================================================================
--- branches/gsoc11-rev-upgrade/base/src/libmachista1.0/Makefile 2011-07-12 17:09:21 UTC (rev 80424)
+++ branches/gsoc11-rev-upgrade/base/src/libmachista1.0/Makefile 2011-07-12 17:21:45 UTC (rev 80425)
@@ -1,4 +1,4 @@
-OBJS= libmachista.o
+OBJS= libmachista.o hashmap.o
SHLIB_NAME= libmachista${SHLIB_SUFFIX}
INSTALLDIR= ${DESTDIR}${datadir}/macports/Tcl/libmachista1.0
Added: branches/gsoc11-rev-upgrade/base/src/libmachista1.0/hashmap.c
===================================================================
--- branches/gsoc11-rev-upgrade/base/src/libmachista1.0/hashmap.c (rev 0)
+++ branches/gsoc11-rev-upgrade/base/src/libmachista1.0/hashmap.c 2011-07-12 17:21:45 UTC (rev 80425)
@@ -0,0 +1,295 @@
+/* vim:expandtab:tw=80:ts=2:sts=2:sw=2
+ */
+/*-
+ * Copyright (c) 2011 Christoph Erhardt. 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.
+ * 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 CHRISTOPH ERHARDT ``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 CHRISTOPH ERHARDT OR CONTRIBUTORS 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.
+ */
+/*-
+ * Modified by Clemens Lang to accept values of arbitrary type.
+ */
+
+
+#ifndef _BSD_SOURCE
+ #define _BSD_SOURCE
+#endif
+#ifndef _CRT_NONSTDC_NO_DEPRECATE
+ #define _CRT_NONSTDC_NO_DEPRECATE
+#endif
+
+#include "hashmap.h"
+#include <limits.h>
+#include <stdint.h>
+#include <string.h>
+
+
+static const size_t INITIAL_CAPACITY = 16; /* Must be a power of 2 */
+static const size_t MAXIMUM_CAPACITY = (1U << 31);
+static const float LOAD_FACTOR = 0.75;
+
+
+typedef struct HashMapEntry {
+ char *key;
+ const void *value;
+ struct HashMapEntry *next;
+ uint32_t hash;
+} HashMapEntry;
+
+struct HashMap {
+ HashMapEntry **table;
+ size_t capacity;
+ size_t size;
+ size_t threshold;
+ void (*freeFunc)(const void *);
+};
+
+
+static void setTable(HashMap *map, HashMapEntry **table, size_t capacity) {
+ map->table = table;
+ map->capacity = capacity;
+ map->threshold = (size_t) (capacity * LOAD_FACTOR);
+}
+
+
+static uint32_t doHash(const char key[]) {
+ size_t length;
+ size_t i;
+ uint32_t h = 0;
+ if (key == NULL)
+ return 0;
+ length = strlen(key);
+ for (i = 0; i < length; ++i) {
+ h = (31 * h) + key[i];
+ }
+ h ^= (h >> 20) ^ (h >> 12);
+ return h ^ (h >> 7) ^ (h >> 4);
+}
+
+
+static size_t indexFor(uint32_t hash, size_t length) {
+ return hash & (length - 1);
+}
+
+
+static int isHit(HashMapEntry *e, const char key[], uint32_t hash) {
+ return (e->hash == hash
+ && (e->key == key || (key != NULL && strcmp(e->key, key) == 0)));
+}
+
+
+static void copyOrFree(void (*freeFunc)(const void *),
+ const void *value, const void **valPtr) {
+ if (valPtr != NULL)
+ *valPtr = value;
+ else
+ freeFunc(value);
+}
+
+
+static int updateValue(HashMap *map, HashMapEntry *e, const void *newVal,
+ const void **oldValPtr) {
+ copyOrFree(map->freeFunc, e->value, oldValPtr);
+ e->value = newVal;
+ return 1;
+}
+
+
+/* Creates a hash map. */
+HashMap *hashMapCreate(void (*freeFunc)(const void *)) {
+ HashMapEntry **table;
+ HashMap *map = malloc(sizeof(*map));
+ if (map == NULL)
+ return NULL;
+ table = calloc(INITIAL_CAPACITY, sizeof(*map->table));
+ if (table == NULL) {
+ free(map);
+ return NULL;
+ }
+ setTable(map, table, INITIAL_CAPACITY);
+ map->size = 0;
+ map->freeFunc = freeFunc;
+ return map;
+}
+
+
+/* Inserts a key-value pair into a hash map. */
+int hashMapPut(HashMap *map, const char key[], const void * const value,
+ const void **oldValPtr) {
+
+ HashMapEntry *e;
+ size_t newCapacity;
+ HashMapEntry **newTable;
+ size_t i;
+
+ /* If an entry with the same key exists, update it */
+ uint32_t hash = doHash(key);
+ size_t index = indexFor(hash, map->capacity);
+ for (e = map->table[index]; e != NULL; e = e->next) {
+ if (isHit(e, key, hash) == 0)
+ continue;
+ return updateValue(map, e, value, oldValPtr);
+ }
+
+ /* Create a new entry */
+ e = calloc(1, sizeof(HashMapEntry)); /* Must be zeroed */
+ if (e == NULL)
+ return 0;
+
+ /* Copy key and value into the entry */
+ if (key != NULL) {
+ e->key = strdup(key);
+ if (e->key == NULL) {
+ free(e);
+ return 0;
+ }
+ }
+ if (updateValue(map, e, value, oldValPtr) == 0) {
+ free(e->key);
+ free(e);
+ return 0;
+ }
+
+ /* Insert entry into the table */
+ e->hash = hash;
+ e->next = map->table[index];
+ map->table[index] = e;
+ if (map->size++ < map->threshold)
+ return 1;
+
+ /* If the size exceeds the threshold, double the table's capacity */
+ newCapacity = 2 * map->capacity;
+ if (map->capacity == MAXIMUM_CAPACITY) {
+ map->threshold = UINT_MAX;
+ return 1;
+ }
+ newTable = calloc(newCapacity, sizeof(*newTable));
+ if (newTable == NULL)
+ return 0;
+
+ /* Copy entries from the old table into the new one */
+ for (i = 0; i < map->capacity; ++i) {
+ HashMapEntry *next;
+ for (e = map->table[i]; e != NULL; e = next) {
+ index = indexFor(e->hash, newCapacity);
+ next = e->next;
+ e->next = newTable[index];
+ newTable[index] = e;
+ }
+ }
+
+ /* Release the old table and set the new one */
+ free(map->table);
+ setTable(map, newTable, newCapacity);
+ return 1;
+}
+
+
+/* Performs a hash map lookup. */
+const void *hashMapGet(HashMap *map, const char key[]) {
+ HashMapEntry *e;
+ uint32_t hash = doHash(key);
+ size_t index = indexFor(hash, map->capacity);
+ for (e = map->table[index]; e != NULL; e = e->next) {
+ if (isHit(e, key, hash))
+ return e->value;
+ }
+ return NULL;
+}
+
+
+/* Checks whether a hash map contains an entry with a certain key. */
+int hashMapContainsKey(HashMap *map, const char key[]) {
+ HashMapEntry *e;
+ uint32_t hash = doHash(key);
+ size_t index = indexFor(hash, map->capacity);
+ for (e = map->table[index]; e != NULL; e = e->next) {
+ if (isHit(e, key, hash))
+ return 1;
+ }
+ return 0;
+}
+
+
+/* Removes a key-value pair from a hash map. */
+void hashMapRemove(HashMap *map, const char key[], const void **valPtr) {
+ uint32_t hash = doHash(key);
+ size_t index = indexFor(hash, map->capacity);
+ HashMapEntry *prev = map->table[index];
+ HashMapEntry *e = prev;
+ while (e != NULL) {
+ HashMapEntry *next = e->next;
+ if (isHit(e, key, hash)) {
+ map->size--;
+ if (prev == e)
+ map->table[index] = next;
+ else
+ prev->next = next;
+ break;
+ }
+ prev = e;
+ e = next;
+ }
+ if (e == NULL) {
+ copyOrFree(map->freeFunc, NULL, valPtr);
+ return;
+ }
+ free(e->key);
+ copyOrFree(map->freeFunc, e->value, valPtr);
+ free(e);
+}
+
+
+/* Returns the number of elements stored in a hash map. */
+size_t hashMapSize(const HashMap *map) {
+ return map->size;
+}
+
+
+/* Checks whether a hash map is empty. */
+int hashMapIsEmpty(const HashMap *map) {
+ return (map->size == 0);
+}
+
+
+/* Removes all entries from a hash map. */
+void hashMapClear(HashMap *map) {
+ size_t i;
+ for (i = 0; i < map->capacity; ++i) {
+ HashMapEntry *e;
+ HashMapEntry *next;
+ for (e = map->table[i]; e != NULL; e = next) {
+ free(e->key);
+ map->freeFunc(e->value);
+ next = e->next;
+ free(e);
+ }
+ map->table[i] = NULL;
+ }
+}
+
+
+/* Destroys a hash map. */
+void hashMapDestroy(HashMap *map) {
+ if (map == NULL)
+ return;
+ hashMapClear(map);
+ free(map->table);
+ free(map);
+}
Property changes on: branches/gsoc11-rev-upgrade/base/src/libmachista1.0/hashmap.c
___________________________________________________________________
Added: svn:keywords
+ Id
Added: svn:eol-style
+ native
Added: branches/gsoc11-rev-upgrade/base/src/libmachista1.0/hashmap.h
===================================================================
--- branches/gsoc11-rev-upgrade/base/src/libmachista1.0/hashmap.h (rev 0)
+++ branches/gsoc11-rev-upgrade/base/src/libmachista1.0/hashmap.h 2011-07-12 17:21:45 UTC (rev 80425)
@@ -0,0 +1,135 @@
+/* vim:tw=80:expandtab
+ */
+/**
+ * @file hashmap.h
+ * @brief A hash map implementation in C.
+ * @author Christoph Erhardt <erhardt at cs.fau.de>
+ */
+
+/*-
+ * Copyright (c) 2011 Christoph Erhardt. 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.
+ * 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 CHRISTOPH ERHARDT ``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 CHRISTOPH ERHARDT OR CONTRIBUTORS 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.
+ */
+/*-
+ * Modified by Clemens Lang to accept values of arbitrary type.
+ */
+
+
+#ifndef HASHMAP_H
+#define HASHMAP_H
+
+
+#include <stdlib.h>
+
+
+/** Hash map type. */
+typedef struct HashMap HashMap;
+
+
+/**
+ * @brief Creates a hash map.
+ *
+ * The keys and values managed in the map can be arbitrary C strings.
+ * @param freeFunc Function to call in order to free a stored value
+ * @return Pointer to the newly created hash map, or @c NULL on error.
+ */
+HashMap *hashMapCreate(void (*freeFunc)(const void *));
+
+/**
+ * @brief Inserts a key-value pair into a hash map.
+ *
+ * Both key and value are copied internally, so the caller can reuse the
+ * original variables.
+ * If oldValPtr is @c NULL, the previously stored value corresponding to the key
+ * is freed. Otherwise it is written into @c *valPtr and the caller is
+ * responsible for freeing it.
+ * @param map Hash map.
+ * @param key Key.
+ * @param value Value.
+ * @param oldValPtr Output parameter receiving the previously stored value
+ * corresponding to the key (@c NULL if no mapping existed
+ * before).
+ * @return Nonzero on success, 0 on error.
+ */
+int hashMapPut(HashMap *map, const char key[], const void * const value,
+ const void **oldValPtr);
+
+/**
+ * @brief Performs a hash map lookup.
+ *
+ * The returned value must not be freed or otherwise manipulated by the caller.
+ * @param map Hash map.
+ * @param key Key.
+ * @return Value corresponding to the key on success, @c NULL if no matching
+ * entry was found.
+ */
+const void *hashMapGet(HashMap *map, const char key[]);
+
+/**
+ * @brief Checks whether a hash map contains an entry with a certain key.
+ * @param map Hash map.
+ * @param key Key.
+ * @return Nonzero if the map contains an entry with the given key, 0 if it does
+ * not.
+ */
+int hashMapContainsKey(HashMap *map, const char key[]);
+
+/**
+ * @brief Removes a key-value pair from a hash map and frees the stored key.
+ *
+ * If @c valPtr is @c NULL, the internally stored value corresponding to the key
+ * is freed. Otherwise it is written into @c *valPtr and the caller is
+ * responsible for freeing it.
+ * @param map Hash map.
+ * @param key Key.
+ * @param valPtr Output parameter receiving the internally stored value
+ * corresponding to the key.
+ */
+void hashMapRemove(HashMap *map, const char key[], const void **valPtr);
+
+/**
+ * @brief Returns the number of elements stored in a hash map.
+ * @param map Hash map.
+ * @return Number of elements stored in the map.
+ */
+size_t hashMapSize(const HashMap *map);
+
+/**
+ * @brief Checks whether a hash map is empty.
+ * @param map Hash map.
+ * @return Nonzero if the map contains no entries, 0 otherwise.
+ */
+int hashMapIsEmpty(const HashMap *map);
+
+/**
+ * @brief Removes all entries from a hash map.
+ * @param map Hash map.
+ */
+void hashMapClear(HashMap *map);
+
+/**
+ * @brief Destroys a hash map.
+ * @param map Hash map to be destroyed.
+ */
+void hashMapDestroy(HashMap *map);
+
+
+#endif /* HASHMAP_H */
Modified: branches/gsoc11-rev-upgrade/base/src/libmachista1.0/libmachista.c
===================================================================
--- branches/gsoc11-rev-upgrade/base/src/libmachista1.0/libmachista.c 2011-07-12 17:09:21 UTC (rev 80424)
+++ branches/gsoc11-rev-upgrade/base/src/libmachista1.0/libmachista.c 2011-07-12 17:21:45 UTC (rev 80425)
@@ -48,6 +48,7 @@
#include <libkern/OSAtomic.h>
#include "libmachista.h"
+#include "hashmap.h"
typedef struct macho_input {
const void *data;
@@ -56,10 +57,7 @@
/* This is macho_handle_t. The corresponding typedef is in the header */
struct macho_handle {
- /* this isn't handled as a linked list on purpose, because the mht_results are given out to the
- * user and should not have a next pointer (as it doesn't make any sense in that context */
- size_t mht_result_count;
- macho_t **mht_results;
+ HashMap *result_map;
};
/* Verify that the given range is within bounds. */
@@ -398,11 +396,19 @@
}
/* Parse a (possible Mach-O) file. For a more detailed description, see the header */
-int macho_parse_file(macho_handle_t *handle, const char *filepath, macho_t **res) {
+int macho_parse_file(macho_handle_t *handle, const char *filepath, const macho_t **res) {
int fd;
struct stat st;
void *data;
macho_input_t input_file;
+
+ /* Check hashmap for precomputed results */
+ const macho_t *cached_res = hashMapGet(handle->result_map, filepath);
+ if (cached_res != NULL) {
+ *res = cached_res;
+ return MACHO_SUCCESS;
+ }
+
/* Open input file */
if ((fd = open(filepath, O_RDONLY)) < 0) {
@@ -429,22 +435,19 @@
if (*res == NULL)
return MACHO_EMEM;
- int ret = parse_macho(*res, &input_file);
+ /* The output parameter *res should be read-only for the user of the lib only, but writable for
+ * us */
+ int ret = parse_macho((macho_t *)*res, &input_file);
if (ret == MACHO_SUCCESS) {
- /* TODO: Insert into hashmap for caching */
- macho_t **handle_list = realloc(handle->mht_results, (handle->mht_result_count + 1) * sizeof(*handle->mht_results));
- if (handle_list == NULL) {
- free_macho_t(*res);
+ /* Insert into hashmap for caching */
+ if (0 == hashMapPut(handle->result_map, filepath, *res, NULL)) {
+ free_macho_t((macho_t *)*res);
*res = NULL;
ret = MACHO_EMEM;
- } else {
- handle->mht_results = handle_list;
- handle->mht_result_count++;
- handle->mht_results[handle->mht_result_count - 1] = *res;
}
} else {
/* An error occured, free mt */
- free_macho_t(*res);
+ free_macho_t((macho_t *)*res);
*res = NULL;
}
@@ -460,7 +463,11 @@
macho_handle_t *mht = malloc(sizeof(macho_handle_t));
if (mht == NULL)
return NULL;
- memset(mht, 0, sizeof(mht));
+ mht->result_map = hashMapCreate((void (*)(const void *))free_macho_t);
+ if (mht->result_map == NULL) {
+ free(mht);
+ return NULL;
+ }
return mht;
}
@@ -469,9 +476,7 @@
if (handle == NULL)
return;
- for (size_t i = 0; i < handle->mht_result_count; ++i)
- free_macho_t(handle->mht_results[i]);
- free(handle->mht_results);
+ hashMapDestroy(handle->result_map);
free(handle);
}
Modified: branches/gsoc11-rev-upgrade/base/src/libmachista1.0/libmachista.h
===================================================================
--- branches/gsoc11-rev-upgrade/base/src/libmachista1.0/libmachista.h 2011-07-12 17:09:21 UTC (rev 80424)
+++ branches/gsoc11-rev-upgrade/base/src/libmachista1.0/libmachista.h 2011-07-12 17:21:45 UTC (rev 80425)
@@ -124,9 +124,10 @@
*
* On error, the contents of res are undefined and should not be used. The memory associated with
* the result *res will be free()'d and should thus not be used after calling macho_destroy_handle
- * on the macho_handle_t used for the call.
+ * on the macho_handle_t used for the call. *res should also never be modified or otherwise
+ * free()'d.
*/
-int macho_parse_file(macho_handle_t *handle, const char *filepath, macho_t **res);
+int macho_parse_file(macho_handle_t *handle, const char *filepath, const macho_t **res);
/**
* Returns a string representation of the MACHO_* error code constants
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.macosforge.org/pipermail/macports-changes/attachments/20110712/4f5c1fff/attachment-0001.html>
More information about the macports-changes
mailing list