145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/** 245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \file libyasm/hamt.h 345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \brief Hash Array Mapped Trie (HAMT) functions. 445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \license 645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * Copyright (C) 2001-2007 Peter Johnson 745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * Redistribution and use in source and binary forms, with or without 945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * modification, are permitted provided that the following conditions 1045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * are met: 1145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 1. Redistributions of source code must retain the above copyright 1245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * notice, this list of conditions and the following disclaimer. 1345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 2. Redistributions in binary form must reproduce the above copyright 1445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * notice, this list of conditions and the following disclaimer in the 1545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * documentation and/or other materials provided with the distribution. 1645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * 1745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND OTHER CONTRIBUTORS ``AS IS'' 1845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR OTHER CONTRIBUTORS BE 2145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 2245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 2345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 2445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 2545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 2645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 2745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * POSSIBILITY OF SUCH DAMAGE. 2845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \endlicense 2945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 3045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifndef YASM_HAMT_H 3145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define YASM_HAMT_H 3245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 3345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#ifndef YASM_LIB_DECL 3445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define YASM_LIB_DECL 3545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 3645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 3745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/** Hash array mapped trie data structure (opaque type). */ 3845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgtypedef struct HAMT HAMT; 3945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/** Hash array mapped trie entry (opaque type). */ 4045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgtypedef struct HAMTEntry HAMTEntry; 4145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 4245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/** Create new, empty, HAMT. error_func() is called when an internal error is 4345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * encountered--it should NOT return to the calling function. 4445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param nocase nonzero if HAMT should be case-insensitive 4545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param error_func function called on internal error 4645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \return New, empty, hash array mapped trie. 4745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 4845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 4945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgHAMT *HAMT_create(int nocase, /*@exits@*/ void (*error_func) 5045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org (const char *file, unsigned int line, const char *message)); 5145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 5245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/** Delete HAMT and all data associated with it. Uses deletefunc() to delete 5345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * each data item. 5445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param hamt Hash array mapped trie 5545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param deletefunc Data deletion function 5645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 5745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 5845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgvoid HAMT_destroy(/*@only@*/ HAMT *hamt, 5945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org void (*deletefunc) (/*@only@*/ void *data)); 6045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 6145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/** Insert key into HAMT, associating it with data. 6245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * If the key is not present in the HAMT, inserts it, sets *replace to 1, and 6345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * returns the data passed in. 6445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * If the key is already present and *replace is 0, deletes the data passed 6545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * in using deletefunc() and returns the data currently associated with the 6645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * key. 6745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * If the key is already present and *replace is 1, deletes the data currently 6845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * associated with the key using deletefunc() and replaces it with the data 6945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * passed in. 7045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param hamt Hash array mapped trie 7145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param str Key 7245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param data Data to associate with key 7345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param replace See above description 7445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param deletefunc Data deletion function if data is replaced 7545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \return Data now associated with key. 7645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 7745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 7845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/*@dependent@*/ void *HAMT_insert(HAMT *hamt, /*@dependent@*/ const char *str, 7945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /*@only@*/ void *data, int *replace, 8045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org void (*deletefunc) (/*@only@*/ void *data)); 8145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 8245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/** Search for the data associated with a key in the HAMT. 8345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param hamt Hash array mapped trie 8445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param str Key 8545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \return NULL if key/data not present in HAMT, otherwise associated data. 8645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 8745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 8845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/*@dependent@*/ /*@null@*/ void *HAMT_search(HAMT *hamt, const char *str); 8945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 9045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/** Traverse over all keys in HAMT, calling function on each data item. 9145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param hamt Hash array mapped trie 9245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param d Data to pass to each call to func. 9345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param func Function to call 9445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \return Stops early (and returns func's return value) if func returns a 9545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * nonzero value; otherwise 0. 9645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 9745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 9845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgint HAMT_traverse(HAMT *hamt, /*@null@*/ void *d, 9945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org int (*func) (/*@dependent@*/ /*@null@*/ void *node, 10045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /*@null@*/ void *d)); 10145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 10245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/** Get the first entry in a HAMT. 10345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param hamt Hash array mapped trie 10445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \return First entry in HAMT, or NULL if HAMT is empty. 10545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 10645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 10745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgconst HAMTEntry *HAMT_first(const HAMT *hamt); 10845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 10945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/** Get the next entry in a HAMT. 11045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param prev Previous entry in HAMT 11145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \return Next entry in HAMT, or NULL if no more entries. 11245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 11345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 11445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/*@null@*/ const HAMTEntry *HAMT_next(const HAMTEntry *prev); 11545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 11645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/** Get the corresponding data for a HAMT entry. 11745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \param entry HAMT entry (as returned by HAMT_first() and HAMT_next()) 11845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org * \return Corresponding data item. 11945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org */ 12045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgYASM_LIB_DECL 12145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgvoid *HAMTEntry_get_data(const HAMTEntry *entry); 12245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 12345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#endif 124