libbanshee/engine/hash.h

   1 /*
   2  * Copyright (c) 2000-2001
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. Neither the name of the University nor the names of its contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18  * 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 REGENTS OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  *
  29  */
  30
  31 #ifndef HASH_H
  32 #define HASH_H
  33
  34 #include <regions.h>
  35 #include "bool.h"
  36 /*#include "hash_info.h"*/ /* Includes hash_key, hash_data typedef */
  37 #include "linkage.h"
  38
  39 EXTERN_C_BEGIN
  40
  41 typedef void *hash_key;
  42 typedef void *hash_data;
  43
  44 /* Function to hash a key */
  45 typedef int (*hash_fn)(hash_key k);
  46
  47 /* Function returning true iff k1 and k2 are equal */
  48 typedef bool (*keyeq_fn)(hash_key k1, hash_key k2);
  49
  50 /* Function applied to elts in the hash table */
  51 typedef void (*hash_apply_fn)(hash_key k, hash_data d, void *arg);
  52
  53 /* Function mapped to elts in the hash table */
  54 typedef hash_data (*hash_map_fn)(hash_key k, hash_data d, void *arg);
  55
  56 typedef struct Hash_table *hash_table;
  57
  58 /* Make a new hash table, with size buckets initially. */
  59 hash_table make_hash_table(region rhash, int size, hash_fn hash,
  60                            keyeq_fn cmp, bool internal_rgn);
  61
  62 /* Make a hash table for strings. */
  63 hash_table make_string_hash_table(region rhash, int size, bool internal_rgn);
  64
  65 /* Zero out ht.  Doesn't reclaim bucket space. */
  66 void hash_table_reset(hash_table ht) deletes;
  67
  68 /* Delete ht and internal memory associated with it. The top level pointer
  69  must still be deleted. */
  70 void hash_table_delete(hash_table ht) deletes;
  71
  72 /* Return the number of entries in ht */
  73 int hash_table_size(hash_table ht);
  74
  75
  76 /* Lookup k in ht.  If d is not NULL, returns corresponding data in *d.
  77    Function result is TRUE if the k was in ht, false otherwise. */
  78 bool hash_table_lookup(hash_table ht, hash_key k, hash_data *d);
  79
  80 /* Add k:d to ht.  If k was already in ht, replace old entry by k:d.
  81    Rehash if necessary.  Returns TRUE if k was not already in ht. */
  82 bool hash_table_insert(hash_table ht, hash_key k, hash_data d) deletes;
  83
  84 /* Remove mapping for k in ht.  Returns TRUE if k was in ht. */
  85 bool hash_table_remove(hash_table ht, hash_key k);
  86
  87 /* Return a copy of ht, allocated in rhash */
  88 hash_table hash_table_copy(region rhash, hash_table ht);
  89
  90 /* Apply f to all elements of ht, in some arbitrary order */
  91 void hash_table_apply(hash_table ht, hash_apply_fn f, void *arg);
  92
  93 /* Map f to all elements on ht, creating a new hash table */
  94 hash_table hash_table_map(hash_table ht, hash_map_fn f, void *arg);
  95
  96 typedef struct bucket *bucket;
  97 typedef struct
  98 {
  99   hash_table ht;
 100   int i;
 101   bucket cur;
 102 } hash_table_scanner; /* Opaque type!  Do not modify fields. */
 103
 104 /* Begin scanning ht */
 105 void hash_table_scan(hash_table ht, hash_table_scanner *);
 106
 107 /* Get next elt in table, storing the elt in *k and *d if k and d are
 108    non-NULL, respectively.  Returns TRUE if there is a next elt, FALSE
 109    otherwise. */
 110 bool hash_table_next(hash_table_scanner *, hash_key *k, hash_data *d);
 111
 112 /* Total order on hash table keys, only uesd for hash_table_scan_sorted */
 113 typedef int (*keycmp_fn)(hash_key k1, hash_key k2);
 114
 115 struct sorted_entry
 116 {
 117   hash_key k;
 118   hash_data d;
 119 };
 120
 121 typedef struct
 122 {
 123   region r;
 124   int i;
 125   int size;
 126   struct sorted_entry *entries;
 127 } hash_table_scanner_sorted;
 128
 129 /* Begin scanning ht in sorted order according to f */
 130 void hash_table_scan_sorted(hash_table ht, keycmp_fn f,
 131                             hash_table_scanner_sorted *htss);
 132
 133 /* Just like hash_table_next, but scans in sorted order */
 134 bool hash_table_next_sorted(hash_table_scanner_sorted *htss, hash_key *k,
 135                             hash_data *d) deletes;
 136
 137
 138 EXTERN_C_END
 139
 140 #endif