Thu, 19 Mar 2009 09:13:24 -0700
Merge
duke@435 | 1 | /* |
duke@435 | 2 | * Copyright 1997-2003 Sun Microsystems, Inc. All Rights Reserved. |
duke@435 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
duke@435 | 4 | * |
duke@435 | 5 | * This code is free software; you can redistribute it and/or modify it |
duke@435 | 6 | * under the terms of the GNU General Public License version 2 only, as |
duke@435 | 7 | * published by the Free Software Foundation. |
duke@435 | 8 | * |
duke@435 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
duke@435 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
duke@435 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
duke@435 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
duke@435 | 13 | * accompanied this code). |
duke@435 | 14 | * |
duke@435 | 15 | * You should have received a copy of the GNU General Public License version |
duke@435 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
duke@435 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
duke@435 | 18 | * |
duke@435 | 19 | * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
duke@435 | 20 | * CA 95054 USA or visit www.sun.com if you need additional information or |
duke@435 | 21 | * have any questions. |
duke@435 | 22 | * |
duke@435 | 23 | */ |
duke@435 | 24 | |
duke@435 | 25 | #ifndef _DICT_ |
duke@435 | 26 | #define _DICT_ |
duke@435 | 27 | // Dictionaries - An Abstract Data Type |
duke@435 | 28 | //INTERFACE |
duke@435 | 29 | class ostream; |
duke@435 | 30 | class Dict; |
duke@435 | 31 | |
duke@435 | 32 | // These dictionaries define a key-value mapping. They can be inserted to, |
duke@435 | 33 | // searched or deleted from. They grow and shrink as needed. The key is a |
duke@435 | 34 | // pointer to something (or anything which can be stored in a pointer). A |
duke@435 | 35 | // key comparison routine determines if two keys are equal or not. A hash |
duke@435 | 36 | // function can be provided; if it's not provided the key itself is used |
duke@435 | 37 | // instead. A nice string hash function is included. |
duke@435 | 38 | typedef int32 (*CmpKey)(const void *key1, const void *key2); |
duke@435 | 39 | typedef int (*Hash)(const void *key); |
duke@435 | 40 | typedef void (*FuncDict)(const void *key, const void *val, Dict *d); |
duke@435 | 41 | |
duke@435 | 42 | class Dict : public ResourceObj { // Dictionary structure |
duke@435 | 43 | private: |
duke@435 | 44 | class Arena *_arena; // Where to draw storage from |
duke@435 | 45 | class bucket *_bin; // Hash table is array of buckets |
duke@435 | 46 | uint _size; // Size (# of slots) in hash table |
duke@435 | 47 | uint32 _cnt; // Number of key-value pairs in hash table |
duke@435 | 48 | const Hash _hash; // Hashing function |
duke@435 | 49 | const CmpKey _cmp; // Key comparison function |
duke@435 | 50 | void doubhash( void ); // Double hash table size |
duke@435 | 51 | |
duke@435 | 52 | public: |
duke@435 | 53 | friend class DictI; // Friendly iterator function |
duke@435 | 54 | |
duke@435 | 55 | // cmp is a key comparision routine. hash is a routine to hash a key. |
duke@435 | 56 | Dict( CmpKey cmp, Hash hash ); |
duke@435 | 57 | Dict( CmpKey cmp, Hash hash, Arena *arena, int size=16 ); |
duke@435 | 58 | ~Dict(); |
duke@435 | 59 | |
duke@435 | 60 | Dict( const Dict & ); // Deep-copy guts |
duke@435 | 61 | Dict &operator =( const Dict & ); |
duke@435 | 62 | |
duke@435 | 63 | // Zap to empty; ready for re-use |
duke@435 | 64 | void Clear(); |
duke@435 | 65 | |
duke@435 | 66 | // Return # of key-value pairs in dict |
duke@435 | 67 | uint32 Size(void) const { return _cnt; } |
duke@435 | 68 | |
duke@435 | 69 | // Insert inserts the given key-value pair into the dictionary. The prior |
duke@435 | 70 | // value of the key is returned; NULL if the key was not previously defined. |
duke@435 | 71 | void *Insert(void *key, void *val, bool replace = true); // A new key-value |
duke@435 | 72 | void *Delete(void *key); // Delete & return old |
duke@435 | 73 | |
duke@435 | 74 | // Find finds the value of a given key; or NULL if not found. |
duke@435 | 75 | // The dictionary is NOT changed. |
duke@435 | 76 | void *operator [](const void *key) const; // Do a lookup |
duke@435 | 77 | |
duke@435 | 78 | // == compares two dictionaries; they must have the same keys (their keys |
duke@435 | 79 | // must match using CmpKey) and they must have the same values (pointer |
duke@435 | 80 | // comparison). If so 1 is returned, if not 0 is returned. |
duke@435 | 81 | int32 operator ==(const Dict &d) const; // Compare dictionaries for equal |
duke@435 | 82 | |
duke@435 | 83 | // Print out the dictionary contents as key-value pairs |
duke@435 | 84 | void print(); |
duke@435 | 85 | }; |
duke@435 | 86 | |
duke@435 | 87 | // Hashing functions |
duke@435 | 88 | int hashstr(const void *s); // Nice string hash |
twisti@1040 | 89 | // Slimey cheap hash function; no guaranteed performance. Better than the |
duke@435 | 90 | // default for pointers, especially on MS-DOS machines. |
duke@435 | 91 | int hashptr(const void *key); |
twisti@1040 | 92 | // Slimey cheap hash function; no guaranteed performance. |
duke@435 | 93 | int hashkey(const void *key); |
duke@435 | 94 | |
duke@435 | 95 | // Key comparators |
duke@435 | 96 | int32 cmpstr(const void *k1, const void *k2); |
duke@435 | 97 | // Slimey cheap key comparator. |
duke@435 | 98 | int32 cmpkey(const void *key1, const void *key2); |
duke@435 | 99 | |
duke@435 | 100 | //------------------------------Iteration-------------------------------------- |
duke@435 | 101 | // The class of dictionary iterators. Fails in the presences of modifications |
duke@435 | 102 | // to the dictionary during iteration (including searches). |
duke@435 | 103 | // Usage: for( DictI i(dict); i.test(); ++i ) { body = i.key; body = i.value;} |
duke@435 | 104 | class DictI { |
duke@435 | 105 | private: |
duke@435 | 106 | const Dict *_d; // Dictionary being iterated over |
duke@435 | 107 | uint _i; // Counter over the bins |
duke@435 | 108 | uint _j; // Counter inside each bin |
duke@435 | 109 | public: |
duke@435 | 110 | const void *_key, *_value; // Easy access to the key-value pair |
duke@435 | 111 | DictI( const Dict *d ) {reset(d);}; // Create a new iterator |
duke@435 | 112 | void reset( const Dict *dict ); // Reset existing iterator |
duke@435 | 113 | void operator ++(void); // Increment iterator |
duke@435 | 114 | int test(void) { return _i<_d->_size;} // Test for end of iteration |
duke@435 | 115 | }; |
duke@435 | 116 | |
duke@435 | 117 | #endif // _DICT_ |