duke@435: /* trims@1907: * Copyright (c) 1998, 2000, Oracle and/or its affiliates. All rights reserved. duke@435: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. duke@435: * duke@435: * This code is free software; you can redistribute it and/or modify it duke@435: * under the terms of the GNU General Public License version 2 only, as duke@435: * published by the Free Software Foundation. duke@435: * duke@435: * This code is distributed in the hope that it will be useful, but WITHOUT duke@435: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or duke@435: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License duke@435: * version 2 for more details (a copy is included in the LICENSE file that duke@435: * accompanied this code). duke@435: * duke@435: * You should have received a copy of the GNU General Public License version duke@435: * 2 along with this work; if not, write to the Free Software Foundation, duke@435: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. duke@435: * trims@1907: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA trims@1907: * or visit www.oracle.com if you need additional information or have any trims@1907: * questions. duke@435: * duke@435: */ duke@435: duke@435: #ifndef _DICT_ duke@435: #define _DICT_ duke@435: // Dictionaries - An Abstract Data Type duke@435: duke@435: duke@435: class Dict; duke@435: duke@435: // These dictionaries define a key-value mapping. They can be inserted to, duke@435: // searched or deleted from. They grow and shrink as needed. The key is a duke@435: // pointer to something (or anything which can be stored in a pointer). A duke@435: // key comparison routine determines if two keys are equal or not. A hash duke@435: // function can be provided; if it's not provided the key itself is used duke@435: // instead. A nice string hash function is included. duke@435: typedef int (*CmpKey)(const void *key1, const void *key2); duke@435: typedef int (*Hash)(const void *key); duke@435: typedef void (*PrintKeyOrValue)(const void *key_or_value); duke@435: typedef void (*FuncDict)(const void *key, const void *val, Dict *d); duke@435: duke@435: class Dict { // Dictionary structure duke@435: private: duke@435: class Arena *_arena; // Where to draw storage from duke@435: class bucket *_bin; // Hash table is array of buckets duke@435: int _size; // Size (# of slots) in hash table duke@435: int _cnt; // Number of key-value pairs in hash table duke@435: const Hash _hash; // Hashing function duke@435: const CmpKey _cmp; // Key comparison function duke@435: void doubhash( void ); // Double hash table size duke@435: duke@435: public: duke@435: friend class DictI; // Friendly iterator function duke@435: duke@435: // cmp is a key comparision routine. hash is a routine to hash a key. duke@435: Dict( CmpKey cmp, Hash hash ); duke@435: Dict( CmpKey cmp, Hash hash, Arena *arena ); duke@435: void init(); duke@435: ~Dict(); duke@435: duke@435: Dict( const Dict & ); // Deep-copy guts duke@435: Dict &operator =( const Dict & ); duke@435: duke@435: // Zap to empty; ready for re-use duke@435: void Clear(); duke@435: duke@435: // Return # of key-value pairs in dict duke@435: int Size(void) const { return _cnt; } duke@435: duke@435: // Insert inserts the given key-value pair into the dictionary. The prior duke@435: // value of the key is returned; NULL if the key was not previously defined. duke@435: const void *Insert(const void *key, const void *val); // A new key-value duke@435: const void *Delete(void *key); // Delete & return old duke@435: duke@435: // Find finds the value of a given key; or NULL if not found. duke@435: // The dictionary is NOT changed. duke@435: const void *operator [](const void *key) const; // Do a lookup duke@435: duke@435: // == compares two dictionaries; they must have the same keys (their keys duke@435: // must match using CmpKey) and they must have the same values (pointer duke@435: // comparison). If so 1 is returned, if not 0 is returned. duke@435: int operator ==(const Dict &d) const; // Compare dictionaries for equal duke@435: duke@435: // Print out the dictionary contents as key-value pairs duke@435: void print(); duke@435: void print(PrintKeyOrValue print_key, PrintKeyOrValue print_value); duke@435: }; duke@435: duke@435: // Hashing functions duke@435: int hashstr(const void *s); // Nice string hash twisti@1040: // Slimey cheap hash function; no guaranteed performance. Better than the duke@435: // default for pointers, especially on MS-DOS machines. duke@435: int hashptr(const void *key); twisti@1040: // Slimey cheap hash function; no guaranteed performance. duke@435: int hashkey(const void *key); duke@435: duke@435: // Key comparators duke@435: int cmpstr(const void *k1, const void *k2); duke@435: // Slimey cheap key comparator. duke@435: int cmpkey(const void *key1, const void *key2); duke@435: duke@435: //------------------------------Iteration-------------------------------------- duke@435: // The class of dictionary iterators. Fails in the presences of modifications duke@435: // to the dictionary during iteration (including searches). duke@435: // Usage: for( DictI i(dict); i.test(); ++i ) { body = i.key; body = i.value;} duke@435: class DictI { duke@435: private: duke@435: const Dict *_d; // Dictionary being iterated over duke@435: int _i; // Counter over the bins duke@435: int _j; // Counter inside each bin duke@435: public: duke@435: const void *_key, *_value; // Easy access to the key-value pair duke@435: DictI( const Dict *d ) {reset(d);}; // Create a new iterator duke@435: void reset( const Dict *dict ); // Reset existing iterator duke@435: void operator ++(void); // Increment iterator duke@435: int test(void) { return _i<_d->_size;} // Test for end of iteration duke@435: }; duke@435: duke@435: #endif // _DICT_