runtime/maptable.h

   1 /*
   2  * Copyright (c) 1999-2003, 2006-2007 Apple Inc.  All Rights Reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 /*      maptable.h
  24         Scalable hash table of mappings.
  25         Bertrand, August 1990
  26         Copyright 1990-1996 NeXT Software, Inc.
  27 */
  28
  29 #ifndef _OBJC_MAPTABLE_H_
  30 #define _OBJC_MAPTABLE_H_
  31
  32 #ifndef _OBJC_PRIVATE_H_
  33 #   define OBJC_MAP_AVAILABILITY \
  34     OBJC_OSX_DEPRECATED_OTHERS_UNAVAILABLE(10.0, 10.1, "NXMapTable is deprecated")
  35 #else
  36 #   define OBJC_MAP_AVAILABILITY
  37 #endif
  38
  39 #include <objc/objc.h>
  40
  41 __BEGIN_DECLS
  42
  43 /***************        Definitions             ***************/
  44
  45     /* This module allows hashing of arbitrary associations [key -> value].  Keys and values must be pointers or integers, and client is responsible for allocating/deallocating this data.  A deallocation call-back is provided.
  46     NX_MAPNOTAKEY (-1) is used internally as a marker, and therefore keys must always be different from -1.
  47     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. */
  48
  49 typedef struct _NXMapTable {
  50     /* private data structure; may change */
  51     const struct _NXMapTablePrototype   * _Nonnull prototype;
  52     unsigned    count;
  53     unsigned    nbBucketsMinusOne;
  54     void        * _Nullable buckets;
  55 } NXMapTable OBJC_MAP_AVAILABILITY;
  56
  57 typedef struct _NXMapTablePrototype {
  58     unsigned    (* _Nonnull hash)(NXMapTable * _Nonnull,
  59                                   const void * _Nullable key);
  60     int         (* _Nonnull isEqual)(NXMapTable * _Nonnull,
  61                                      const void * _Nullable key1,
  62                                      const void * _Nullable key2);
  63     void        (* _Nonnull free)(NXMapTable * _Nonnull,
  64                                   void * _Nullable key,
  65                                   void * _Nullable value);
  66     int         style; /* reserved for future expansion; currently 0 */
  67 } NXMapTablePrototype OBJC_MAP_AVAILABILITY;
  68
  69     /* invariants assumed by the implementation:
  70         A - key != -1
  71         B - key1 == key2 => hash(key1) == hash(key2)
  72             when key varies over time, hash(key) must remain invariant
  73             e.g. if string key, the string must not be changed
  74         C - isEqual(key1, key2) => key1 == key2
  75     */
  76
  77 #define NX_MAPNOTAKEY   ((void * _Nonnull)(-1))
  78
  79 /***************        Functions               ***************/
  80
  81 OBJC_EXPORT NXMapTable * _Nonnull
  82 NXCreateMapTableFromZone(NXMapTablePrototype prototype,
  83                          unsigned capacity, void * _Nullable z)
  84     OBJC_MAP_AVAILABILITY;
  85
  86 OBJC_EXPORT NXMapTable * _Nonnull
  87 NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity)
  88     OBJC_MAP_AVAILABILITY;
  89     /* capacity is only a hint; 0 creates a small table */
  90
  91 OBJC_EXPORT void
  92 NXFreeMapTable(NXMapTable * _Nonnull table)
  93     OBJC_MAP_AVAILABILITY;
  94     /* call free for each pair, and recovers table */
  95
  96 OBJC_EXPORT void
  97 NXResetMapTable(NXMapTable * _Nonnull table)
  98     OBJC_MAP_AVAILABILITY;
  99     /* free each pair; keep current capacity */
 100
 101 OBJC_EXPORT BOOL
 102 NXCompareMapTables(NXMapTable * _Nonnull table1, NXMapTable * _Nonnull table2)
 103     OBJC_MAP_AVAILABILITY;
 104     /* Returns YES if the two sets are equal (each member of table1 in table2, and table have same size) */
 105
 106 OBJC_EXPORT unsigned
 107 NXCountMapTable(NXMapTable * _Nonnull table)
 108     OBJC_MAP_AVAILABILITY;
 109     /* current number of data in table */
 110
 111 OBJC_EXPORT void * _Nullable
 112 NXMapMember(NXMapTable * _Nonnull table, const void * _Nullable key,
 113             void * _Nullable * _Nonnull value) OBJC_MAP_AVAILABILITY;
 114     /* return original table key or NX_MAPNOTAKEY.  If key is found, value is set */
 115
 116 OBJC_EXPORT void * _Nullable
 117 NXMapGet(NXMapTable * _Nonnull table, const void * _Nullable key)
 118     OBJC_MAP_AVAILABILITY;
 119     /* return original corresponding value or NULL.  When NULL need be stored as value, NXMapMember can be used to test for presence */
 120
 121 OBJC_EXPORT void * _Nullable
 122 NXMapInsert(NXMapTable * _Nonnull table, const void * _Nullable key,
 123             const void * _Nullable value)
 124     OBJC_MAP_AVAILABILITY;
 125     /* override preexisting pair; Return previous value or NULL. */
 126
 127 OBJC_EXPORT void * _Nullable
 128 NXMapRemove(NXMapTable * _Nonnull table, const void * _Nullable key)
 129     OBJC_MAP_AVAILABILITY;
 130     /* previous value or NULL is returned */
 131
 132 /* 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:
 133     unsigned    count = 0;
 134     const MyKey *key;
 135     const MyValue       *value;
 136     NXMapState  state = NXInitMapState(table);
 137     while(NXNextMapState(table, &state, &key, &value)) {
 138         count++;
 139     }
 140 */
 141
 142 typedef struct {int index;} NXMapState OBJC_MAP_AVAILABILITY;
 143     /* callers should not rely on actual contents of the struct */
 144
 145 OBJC_EXPORT NXMapState
 146 NXInitMapState(NXMapTable * _Nonnull table)
 147     OBJC_MAP_AVAILABILITY;
 148
 149 OBJC_EXPORT int
 150 NXNextMapState(NXMapTable * _Nonnull table, NXMapState * _Nonnull state,
 151                const void * _Nullable * _Nonnull key,
 152                const void * _Nullable * _Nonnull value)
 153     OBJC_MAP_AVAILABILITY;
 154     /* returns 0 when all elements have been visited */
 155
 156 /***************        Conveniences            ***************/
 157
 158 OBJC_EXPORT const NXMapTablePrototype NXPtrValueMapPrototype
 159     OBJC_MAP_AVAILABILITY;
 160     /* hashing is pointer/integer hashing;
 161       isEqual is identity;
 162       free is no-op. */
 163 OBJC_EXPORT const NXMapTablePrototype NXStrValueMapPrototype
 164     OBJC_MAP_AVAILABILITY;
 165     /* hashing is string hashing;
 166       isEqual is strcmp;
 167       free is no-op. */
 168 OBJC_EXPORT const NXMapTablePrototype NXObjectMapPrototype
 169     OBJC2_UNAVAILABLE;
 170     /* for objects; uses methods: hash, isEqual:, free, all for key. */
 171
 172 __END_DECLS
 173
 174 #endif /* _OBJC_MAPTABLE_H_ */