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