Return to maptable.h CVS log

Up to [Apple Darwin 0.x] / objc

Annotation of objc/maptable.h, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.