runtime/hashtable2.h

   1 /*
   2  * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
   7  * Reserved.  This file contains Original Code and/or Modifications of
   8  * Original Code as defined in and that are subject to the Apple Public
   9  * Source License Version 1.1 (the "License").  You may not use this file
  10  * except in compliance with the License.  Please obtain a copy of the
  11  * License at http://www.apple.com/publicsource and read it before using
  12  * this file.
  13  *
  14  * The Original Code and all software distributed under the License are
  15  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  16  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  17  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE OR NON- INFRINGEMENT.  Please see the
  19  * License for the specific language governing rights and limitations
  20  * under the License.
  21  *
  22  * @APPLE_LICENSE_HEADER_END@
  23  */
  24 /*
  25     hashtable2.h
  26     Scalable hash table.
  27     Copyright 1989-1996 NeXT Software, Inc.
  28 */
  29
  30 #warning the API in this header is obsolete
  31
  32 #ifndef _OBJC_LITTLE_HASHTABLE_H_
  33 #define _OBJC_LITTLE_HASHTABLE_H_
  34
  35 #import <objc/objc.h>
  36
  37 /*************************************************************************
  38  *      Hash tables of arbitrary data
  39  *************************************************************************/
  40
  41 /* This module allows hashing of arbitrary data.  Such data must be pointers or integers, and client is responsible for allocating/deallocating this data.  A deallocation call-back is provided.
  42 The objective C class HashTable is prefered when dealing with (key, values) associations because it is easier to use in that situation.
  43 As well-behaved scalable data structures, hash tables double in size when they start becoming full, thus guaranteeing both average constant time access and linear size. */
  44
  45 typedef struct {
  46     uarith_t    (*hash)(const void *info, const void *data);
  47     int         (*isEqual)(const void *info, const void *data1, const void *data2);
  48     void        (*free)(const void *info, void *data);
  49     int         style; /* reserved for future expansion; currently 0 */
  50     } NXHashTablePrototype;
  51
  52 /* the info argument allows a certain generality, such as freeing according to some owner information */
  53 /* invariants assumed by the implementation:
  54         1 - data1 = data2 => hash(data1) = hash(data2)
  55             when data varies over time, hash(data) must remain invariant
  56                     e.g. if data hashes over a string key, the string must not be changed
  57         2- isEqual (data1, data2) => data1= data2
  58  */
  59
  60 typedef struct {
  61     const NXHashTablePrototype  *prototype;
  62     unsigned                    count;
  63     unsigned                    nbBuckets;
  64     void                        *buckets;
  65     const void                  *info;
  66    } NXHashTable;
  67     /* private data structure; may change */
  68
  69 OBJC_EXPORT NXHashTable *NXCreateHashTableFromZone (NXHashTablePrototype prototype, unsigned capacity, const void *info, void *z);
  70 OBJC_EXPORT NXHashTable *NXCreateHashTable (NXHashTablePrototype prototype, unsigned capacity, const void *info);
  71     /* if hash is 0, pointer hash is assumed */
  72     /* if isEqual is 0, pointer equality is assumed */
  73     /* if free is 0, elements are not freed */
  74     /* capacity is only a hint; 0 creates a small table */
  75     /* info allows call backs to be very general */
  76
  77 OBJC_EXPORT void NXFreeHashTable (NXHashTable *table);
  78     /* calls free for each data, and recovers table */
  79
  80 OBJC_EXPORT void NXEmptyHashTable (NXHashTable *table);
  81     /* does not deallocate table nor data; keeps current capacity */
  82
  83 OBJC_EXPORT void NXResetHashTable (NXHashTable *table);
  84     /* frees each entry; keeps current capacity */
  85
  86 OBJC_EXPORT BOOL NXCompareHashTables (NXHashTable *table1, NXHashTable *table2);
  87     /* Returns YES if the two sets are equal (each member of table1 in table2, and table have same size) */
  88
  89 OBJC_EXPORT NXHashTable *NXCopyHashTable (NXHashTable *table);
  90     /* makes a fresh table, copying data pointers, not data itself.  */
  91
  92 OBJC_EXPORT unsigned NXCountHashTable (NXHashTable *table);
  93     /* current number of data in table */
  94
  95 OBJC_EXPORT int NXHashMember (NXHashTable *table, const void *data);
  96     /* returns non-0 iff data is present in table.
  97     Example of use when the hashed data is a struct containing the key,
  98     and when the callee only has a key:
  99         MyStruct        pseudo;
 100         pseudo.key = myKey;
 101         return NXHashMember (myTable, &pseudo)
 102     */
 103
 104 OBJC_EXPORT void *NXHashGet (NXHashTable *table, const void *data);
 105     /* return original table data or NULL.
 106     Example of use when the hashed data is a struct containing the key,
 107     and when the callee only has a key:
 108         MyStruct        pseudo;
 109         MyStruct        *original;
 110         pseudo.key = myKey;
 111         original = NXHashGet (myTable, &pseudo)
 112     */
 113
 114 OBJC_EXPORT void *NXHashInsert (NXHashTable *table, const void *data);
 115     /* previous data or NULL is returned. */
 116
 117 OBJC_EXPORT void *NXHashInsertIfAbsent (NXHashTable *table, const void *data);
 118     /* If data already in table, returns the one in table
 119     else adds argument to table and returns argument. */
 120
 121 OBJC_EXPORT void *NXHashRemove (NXHashTable *table, const void *data);
 122     /* previous data or NULL is returned */
 123
 124 /* Iteration over all elements of a table consists in setting up an iteration state and then to progress until all entries have been visited.  An example of use for counting elements in a table is:
 125     unsigned    count = 0;
 126     MyData      *data;
 127     NXHashState state = NXInitHashState(table);
 128     while (NXNextHashState(table, &state, &data)) {
 129         count++;
 130     }
 131 */
 132
 133 typedef struct {int i; int j;} NXHashState;
 134     /* callers should not rely on actual contents of the struct */
 135
 136 OBJC_EXPORT NXHashState NXInitHashState(NXHashTable *table);
 137
 138 OBJC_EXPORT int NXNextHashState(NXHashTable *table, NXHashState *state, void **data);
 139     /* returns 0 when all elements have been visited */
 140
 141 /*************************************************************************
 142  *      Conveniences for writing hash, isEqual and free functions
 143  *      and common prototypes
 144  *************************************************************************/
 145
 146 OBJC_EXPORT uarith_t NXPtrHash(const void *info, const void *data);
 147     /* scrambles the address bits; info unused */
 148 OBJC_EXPORT uarith_t NXStrHash(const void *info, const void *data);
 149     /* string hashing; info unused */
 150 OBJC_EXPORT int NXPtrIsEqual(const void *info, const void *data1, const void *data2);
 151     /* pointer comparison; info unused */
 152 OBJC_EXPORT int NXStrIsEqual(const void *info, const void *data1, const void *data2);
 153     /* string comparison; NULL ok; info unused */
 154 OBJC_EXPORT void NXNoEffectFree(const void *info, void *data);
 155     /* no effect; info unused */
 156 OBJC_EXPORT void NXReallyFree(const void *info, void *data);
 157     /* frees it; info unused */
 158
 159 /* The two following prototypes are useful for manipulating set of pointers or set of strings; For them free is defined as NXNoEffectFree */
 160 OBJC_EXPORT const NXHashTablePrototype NXPtrPrototype;
 161     /* prototype when data is a pointer (void *) */
 162 OBJC_EXPORT const NXHashTablePrototype NXStrPrototype;
 163     /* prototype when data is a string (char *) */
 164
 165 /* following prototypes help describe mappings where the key is the first element of a struct and is either a pointer or a string.
 166 For example NXStrStructKeyPrototype can be used to hash pointers to Example, where Example is:
 167         typedef struct {
 168             char        *key;
 169             int         data1;
 170             ...
 171             } Example
 172
 173 For the following prototypes, free is defined as NXReallyFree.
 174  */
 175 OBJC_EXPORT const NXHashTablePrototype NXPtrStructKeyPrototype;
 176 OBJC_EXPORT const NXHashTablePrototype NXStrStructKeyPrototype;
 177
 178 /*************************************************************************
 179  *      Unique strings and buffers
 180  *************************************************************************/
 181
 182 /* Unique strings allows C users to enjoy the benefits of Lisp's atoms:
 183 A unique string is a string that is allocated once for all (never de-allocated) and that has only one representant (thus allowing comparison with == instead of strcmp).  A unique string should never be modified (and in fact some memory protection is done to ensure that).  In order to more explicitly insist on the fact that the string has been uniqued, a synonym of (const char *) has been added, NXAtom. */
 184
 185 typedef const char *NXAtom;
 186
 187 OBJC_EXPORT NXAtom NXUniqueString(const char *buffer);
 188     /* assumes that buffer is \0 terminated, and returns
 189      a previously created string or a new string that is a copy of buffer.
 190     If NULL is passed returns NULL.
 191     Returned string should never be modified.  To ensure this invariant,
 192     allocations are made in a special read only zone. */
 193
 194 OBJC_EXPORT NXAtom NXUniqueStringWithLength(const char *buffer, int length);
 195     /* assumes that buffer is a non NULL buffer of at least
 196     length characters.  Returns a previously created string or
 197     a new string that is a copy of buffer.
 198     If buffer contains \0, string will be truncated.
 199     As for NXUniqueString, returned string should never be modified.  */
 200
 201 OBJC_EXPORT NXAtom NXUniqueStringNoCopy(const char *string);
 202     /* If there is already a unique string equal to string, returns the original.
 203     Otherwise, string is entered in the table, without making a copy.  Argument should then never be modified.  */
 204
 205 OBJC_EXPORT char *NXCopyStringBuffer(const char *buffer);
 206     /* given a buffer, allocates a new string copy of buffer.
 207     Buffer should be \0 terminated; returned string is \0 terminated. */
 208
 209 OBJC_EXPORT char *NXCopyStringBufferFromZone(const char *buffer, void *z);
 210     /* given a buffer, allocates a new string copy of buffer.
 211     Buffer should be \0 terminated; returned string is \0 terminated. */
 212
 213 #endif /* _OBJC_LITTLE_HASHTABLE_H_ */