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