1 /** 2 * \file libyasm/hamt.h 3 * \brief Hash Array Mapped Trie (HAMT) functions. 4 * 5 * \license 6 * Copyright (C) 2001-2007 Peter Johnson 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND OTHER CONTRIBUTORS ``AS IS'' 18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR OTHER CONTRIBUTORS BE 21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 27 * POSSIBILITY OF SUCH DAMAGE. 28 * \endlicense 29 */ 30 #ifndef YASM_HAMT_H 31 #define YASM_HAMT_H 32 33 #ifndef YASM_LIB_DECL 34 #define YASM_LIB_DECL 35 #endif 36 37 /** Hash array mapped trie data structure (opaque type). */ 38 typedef struct HAMT HAMT; 39 /** Hash array mapped trie entry (opaque type). */ 40 typedef struct HAMTEntry HAMTEntry; 41 42 /** Create new, empty, HAMT. error_func() is called when an internal error is 43 * encountered--it should NOT return to the calling function. 44 * \param nocase nonzero if HAMT should be case-insensitive 45 * \param error_func function called on internal error 46 * \return New, empty, hash array mapped trie. 47 */ 48 YASM_LIB_DECL 49 HAMT *HAMT_create(int nocase, /*@exits@*/ void (*error_func) 50 (const char *file, unsigned int line, const char *message)); 51 52 /** Delete HAMT and all data associated with it. Uses deletefunc() to delete 53 * each data item. 54 * \param hamt Hash array mapped trie 55 * \param deletefunc Data deletion function 56 */ 57 YASM_LIB_DECL 58 void HAMT_destroy(/*@only@*/ HAMT *hamt, 59 void (*deletefunc) (/*@only@*/ void *data)); 60 61 /** Insert key into HAMT, associating it with data. 62 * If the key is not present in the HAMT, inserts it, sets *replace to 1, and 63 * returns the data passed in. 64 * If the key is already present and *replace is 0, deletes the data passed 65 * in using deletefunc() and returns the data currently associated with the 66 * key. 67 * If the key is already present and *replace is 1, deletes the data currently 68 * associated with the key using deletefunc() and replaces it with the data 69 * passed in. 70 * \param hamt Hash array mapped trie 71 * \param str Key 72 * \param data Data to associate with key 73 * \param replace See above description 74 * \param deletefunc Data deletion function if data is replaced 75 * \return Data now associated with key. 76 */ 77 YASM_LIB_DECL 78 /*@dependent@*/ void *HAMT_insert(HAMT *hamt, /*@dependent@*/ const char *str, 79 /*@only@*/ void *data, int *replace, 80 void (*deletefunc) (/*@only@*/ void *data)); 81 82 /** Search for the data associated with a key in the HAMT. 83 * \param hamt Hash array mapped trie 84 * \param str Key 85 * \return NULL if key/data not present in HAMT, otherwise associated data. 86 */ 87 YASM_LIB_DECL 88 /*@dependent@*/ /*@null@*/ void *HAMT_search(HAMT *hamt, const char *str); 89 90 /** Traverse over all keys in HAMT, calling function on each data item. 91 * \param hamt Hash array mapped trie 92 * \param d Data to pass to each call to func. 93 * \param func Function to call 94 * \return Stops early (and returns func's return value) if func returns a 95 * nonzero value; otherwise 0. 96 */ 97 YASM_LIB_DECL 98 int HAMT_traverse(HAMT *hamt, /*@null@*/ void *d, 99 int (*func) (/*@dependent@*/ /*@null@*/ void *node, 100 /*@null@*/ void *d)); 101 102 /** Get the first entry in a HAMT. 103 * \param hamt Hash array mapped trie 104 * \return First entry in HAMT, or NULL if HAMT is empty. 105 */ 106 YASM_LIB_DECL 107 const HAMTEntry *HAMT_first(const HAMT *hamt); 108 109 /** Get the next entry in a HAMT. 110 * \param prev Previous entry in HAMT 111 * \return Next entry in HAMT, or NULL if no more entries. 112 */ 113 YASM_LIB_DECL 114 /*@null@*/ const HAMTEntry *HAMT_next(const HAMTEntry *prev); 115 116 /** Get the corresponding data for a HAMT entry. 117 * \param entry HAMT entry (as returned by HAMT_first() and HAMT_next()) 118 * \return Corresponding data item. 119 */ 120 YASM_LIB_DECL 121 void *HAMTEntry_get_data(const HAMTEntry *entry); 122 123 #endif 124
