Fri, 27 Feb 2009 13:27:09 -0800
6810672: Comment typos
Summary: I have collected some typos I have found while looking at the code.
Reviewed-by: kvn, never
duke@435 | 1 | /* |
duke@435 | 2 | * Copyright 1998-2000 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 | |
duke@435 | 29 | |
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 int (*CmpKey)(const void *key1, const void *key2); |
duke@435 | 39 | typedef int (*Hash)(const void *key); |
duke@435 | 40 | typedef void (*PrintKeyOrValue)(const void *key_or_value); |
duke@435 | 41 | typedef void (*FuncDict)(const void *key, const void *val, Dict *d); |
duke@435 | 42 | |
duke@435 | 43 | class Dict { // Dictionary structure |
duke@435 | 44 | private: |
duke@435 | 45 | class Arena *_arena; // Where to draw storage from |
duke@435 | 46 | class bucket *_bin; // Hash table is array of buckets |
duke@435 | 47 | int _size; // Size (# of slots) in hash table |
duke@435 | 48 | int _cnt; // Number of key-value pairs in hash table |
duke@435 | 49 | const Hash _hash; // Hashing function |
duke@435 | 50 | const CmpKey _cmp; // Key comparison function |
duke@435 | 51 | void doubhash( void ); // Double hash table size |
duke@435 | 52 | |
duke@435 | 53 | public: |
duke@435 | 54 | friend class DictI; // Friendly iterator function |
duke@435 | 55 | |
duke@435 | 56 | // cmp is a key comparision routine. hash is a routine to hash a key. |
duke@435 | 57 | Dict( CmpKey cmp, Hash hash ); |
duke@435 | 58 | Dict( CmpKey cmp, Hash hash, Arena *arena ); |
duke@435 | 59 | void init(); |
duke@435 | 60 | ~Dict(); |
duke@435 | 61 | |
duke@435 | 62 | Dict( const Dict & ); // Deep-copy guts |
duke@435 | 63 | Dict &operator =( const Dict & ); |
duke@435 | 64 | |
duke@435 | 65 | // Zap to empty; ready for re-use |
duke@435 | 66 | void Clear(); |
duke@435 | 67 | |
duke@435 | 68 | // Return # of key-value pairs in dict |
duke@435 | 69 | int Size(void) const { return _cnt; } |
duke@435 | 70 | |
duke@435 | 71 | // Insert inserts the given key-value pair into the dictionary. The prior |
duke@435 | 72 | // value of the key is returned; NULL if the key was not previously defined. |
duke@435 | 73 | const void *Insert(const void *key, const void *val); // A new key-value |
duke@435 | 74 | const void *Delete(void *key); // Delete & return old |
duke@435 | 75 | |
duke@435 | 76 | // Find finds the value of a given key; or NULL if not found. |
duke@435 | 77 | // The dictionary is NOT changed. |
duke@435 | 78 | const void *operator [](const void *key) const; // Do a lookup |
duke@435 | 79 | |
duke@435 | 80 | // == compares two dictionaries; they must have the same keys (their keys |
duke@435 | 81 | // must match using CmpKey) and they must have the same values (pointer |
duke@435 | 82 | // comparison). If so 1 is returned, if not 0 is returned. |
duke@435 | 83 | int operator ==(const Dict &d) const; // Compare dictionaries for equal |
duke@435 | 84 | |
duke@435 | 85 | // Print out the dictionary contents as key-value pairs |
duke@435 | 86 | void print(); |
duke@435 | 87 | void print(PrintKeyOrValue print_key, PrintKeyOrValue print_value); |
duke@435 | 88 | }; |
duke@435 | 89 | |
duke@435 | 90 | // Hashing functions |
duke@435 | 91 | int hashstr(const void *s); // Nice string hash |
twisti@1040 | 92 | // Slimey cheap hash function; no guaranteed performance. Better than the |
duke@435 | 93 | // default for pointers, especially on MS-DOS machines. |
duke@435 | 94 | int hashptr(const void *key); |
twisti@1040 | 95 | // Slimey cheap hash function; no guaranteed performance. |
duke@435 | 96 | int hashkey(const void *key); |
duke@435 | 97 | |
duke@435 | 98 | // Key comparators |
duke@435 | 99 | int cmpstr(const void *k1, const void *k2); |
duke@435 | 100 | // Slimey cheap key comparator. |
duke@435 | 101 | int cmpkey(const void *key1, const void *key2); |
duke@435 | 102 | |
duke@435 | 103 | //------------------------------Iteration-------------------------------------- |
duke@435 | 104 | // The class of dictionary iterators. Fails in the presences of modifications |
duke@435 | 105 | // to the dictionary during iteration (including searches). |
duke@435 | 106 | // Usage: for( DictI i(dict); i.test(); ++i ) { body = i.key; body = i.value;} |
duke@435 | 107 | class DictI { |
duke@435 | 108 | private: |
duke@435 | 109 | const Dict *_d; // Dictionary being iterated over |
duke@435 | 110 | int _i; // Counter over the bins |
duke@435 | 111 | int _j; // Counter inside each bin |
duke@435 | 112 | public: |
duke@435 | 113 | const void *_key, *_value; // Easy access to the key-value pair |
duke@435 | 114 | DictI( const Dict *d ) {reset(d);}; // Create a new iterator |
duke@435 | 115 | void reset( const Dict *dict ); // Reset existing iterator |
duke@435 | 116 | void operator ++(void); // Increment iterator |
duke@435 | 117 | int test(void) { return _i<_d->_size;} // Test for end of iteration |
duke@435 | 118 | }; |
duke@435 | 119 | |
duke@435 | 120 | #endif // _DICT_ |