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