runtime/maptable.h

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