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     __OSX_DEPRECATED(10.0, 10.1, "NXMapTable is deprecated") \
  35     __IOS_UNAVAILABLE __TVOS_UNAVAILABLE                     \
  36     __WATCHOS_UNAVAILABLE __BRIDGEOS_UNAVAILABLE
  37 #else
  38 #   define OBJC_MAP_AVAILABILITY
  39 #endif
  40
  41 #include <objc/objc.h>
  42
  43 __BEGIN_DECLS
  44
  45 /***************        Definitions             ***************/
  46
  47     /* 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.
  48     NX_MAPNOTAKEY (-1) is used internally as a marker, and therefore keys must always be different from -1.
  49     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. */
  50
  51 typedef struct _NXMapTable {
  52     /* private data structure; may change */
  53     const struct _NXMapTablePrototype   * _Nonnull prototype;
  54     unsigned    count;
  55     unsigned    nbBucketsMinusOne;
  56     void        * _Nullable buckets;
  57 } NXMapTable OBJC_MAP_AVAILABILITY;
  58
  59 typedef struct _NXMapTablePrototype {
  60     unsigned    (* _Nonnull hash)(NXMapTable * _Nonnull,
  61                                   const void * _Nullable key);
  62     int         (* _Nonnull isEqual)(NXMapTable * _Nonnull,
  63                                      const void * _Nullable key1,
  64                                      const void * _Nullable key2);
  65     void        (* _Nonnull free)(NXMapTable * _Nonnull,
  66                                   void * _Nullable key,
  67                                   void * _Nullable value);
  68     int         style; /* reserved for future expansion; currently 0 */
  69 } NXMapTablePrototype OBJC_MAP_AVAILABILITY;
  70
  71     /* invariants assumed by the implementation:
  72         A - key != -1
  73         B - key1 == key2 => hash(key1) == hash(key2)
  74             when key varies over time, hash(key) must remain invariant
  75             e.g. if string key, the string must not be changed
  76         C - isEqual(key1, key2) => key1 == key2
  77     */
  78
  79 #define NX_MAPNOTAKEY   ((void * _Nonnull)(-1))
  80
  81 /***************        Functions               ***************/
  82
  83 OBJC_EXPORT NXMapTable * _Nonnull
  84 NXCreateMapTableFromZone(NXMapTablePrototype prototype,
  85                          unsigned capacity, void * _Nullable z)
  86     OBJC_MAP_AVAILABILITY;
  87
  88 OBJC_EXPORT NXMapTable * _Nonnull
  89 NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity)
  90     OBJC_MAP_AVAILABILITY;
  91     /* capacity is only a hint; 0 creates a small table */
  92
  93 OBJC_EXPORT void
  94 NXFreeMapTable(NXMapTable * _Nonnull table)
  95     OBJC_MAP_AVAILABILITY;
  96     /* call free for each pair, and recovers table */
  97
  98 OBJC_EXPORT void
  99 NXResetMapTable(NXMapTable * _Nonnull table)
 100     OBJC_MAP_AVAILABILITY;
 101     /* free each pair; keep current capacity */
 102
 103 OBJC_EXPORT BOOL
 104 NXCompareMapTables(NXMapTable * _Nonnull table1, NXMapTable * _Nonnull table2)
 105     OBJC_MAP_AVAILABILITY;
 106     /* Returns YES if the two sets are equal (each member of table1 in table2, and table have same size) */
 107
 108 OBJC_EXPORT unsigned
 109 NXCountMapTable(NXMapTable * _Nonnull table)
 110     OBJC_MAP_AVAILABILITY;
 111     /* current number of data in table */
 112
 113 OBJC_EXPORT void * _Nullable
 114 NXMapMember(NXMapTable * _Nonnull table, const void * _Nullable key,
 115             void * _Nullable * _Nonnull value) OBJC_MAP_AVAILABILITY;
 116     /* return original table key or NX_MAPNOTAKEY.  If key is found, value is set */
 117
 118 OBJC_EXPORT void * _Nullable
 119 NXMapGet(NXMapTable * _Nonnull table, const void * _Nullable key)
 120     OBJC_MAP_AVAILABILITY;
 121     /* return original corresponding value or NULL.  When NULL need be stored as value, NXMapMember can be used to test for presence */
 122
 123 OBJC_EXPORT void * _Nullable
 124 NXMapInsert(NXMapTable * _Nonnull table, const void * _Nullable key,
 125             const void * _Nullable value)
 126     OBJC_MAP_AVAILABILITY;
 127     /* override preexisting pair; Return previous value or NULL. */
 128
 129 OBJC_EXPORT void * _Nullable
 130 NXMapRemove(NXMapTable * _Nonnull table, const void * _Nullable key)
 131     OBJC_MAP_AVAILABILITY;
 132     /* previous value or NULL is returned */
 133
 134 /* 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:
 135     unsigned    count = 0;
 136     const MyKey *key;
 137     const MyValue       *value;
 138     NXMapState  state = NXInitMapState(table);
 139     while(NXNextMapState(table, &state, &key, &value)) {
 140         count++;
 141     }
 142 */
 143
 144 typedef struct {int index;} NXMapState OBJC_MAP_AVAILABILITY;
 145     /* callers should not rely on actual contents of the struct */
 146
 147 OBJC_EXPORT NXMapState
 148 NXInitMapState(NXMapTable * _Nonnull table)
 149     OBJC_MAP_AVAILABILITY;
 150
 151 OBJC_EXPORT int
 152 NXNextMapState(NXMapTable * _Nonnull table, NXMapState * _Nonnull state,
 153                const void * _Nullable * _Nonnull key,
 154                const void * _Nullable * _Nonnull value)
 155     OBJC_MAP_AVAILABILITY;
 156     /* returns 0 when all elements have been visited */
 157
 158 /***************        Conveniences            ***************/
 159
 160 OBJC_EXPORT const NXMapTablePrototype NXPtrValueMapPrototype
 161     OBJC_MAP_AVAILABILITY;
 162     /* hashing is pointer/integer hashing;
 163       isEqual is identity;
 164       free is no-op. */
 165 OBJC_EXPORT const NXMapTablePrototype NXStrValueMapPrototype
 166     OBJC_MAP_AVAILABILITY;
 167     /* hashing is string hashing;
 168       isEqual is strcmp;
 169       free is no-op. */
 170 OBJC_EXPORT const NXMapTablePrototype NXObjectMapPrototype
 171     OBJC2_UNAVAILABLE;
 172     /* for objects; uses methods: hash, isEqual:, free, all for key. */
 173
 174 __END_DECLS
 175
 176 #endif /* _OBJC_MAPTABLE_H_ */