Return to hash.h CVS log

Up to [GCC 2.x] / gcc / objc

Annotation of gcc/objc/hash.h, revision 1.1

1.1     ! root        1: /* Hash tables for Objective C method dispatch.
        !             2:    Copyright (C) 1992 Free Software Foundation, Inc.
        !             3: 
        !             4: This file is part of GNU CC.
        !             5: 
        !             6: GNU CC is free software; you can redistribute it and/or modify
        !             7: it under the terms of the GNU General Public License as published by
        !             8: the Free Software Foundation; either version 2, or (at your option)
        !             9: any later version.
        !            10: 
        !            11: GNU CC is distributed in the hope that it will be useful,
        !            12: but WITHOUT ANY WARRANTY; without even the implied warranty of
        !            13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        !            14: GNU General Public License for more details.
        !            15: 
        !            16: You should have received a copy of the GNU General Public License
        !            17: along with GNU CC; see the file COPYING.  If not, write to
        !            18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
        !            19: 
        !            20: /* As a special exception, if you link this library with files
        !            21:    compiled with GCC to produce an executable, this does not cause
        !            22:    the resulting executable to be covered by the GNU General Public License.
        !            23:    This exception does not however invalidate any other reasons why
        !            24:    the executable file might be covered by the GNU General Public License.  */
        !            25: 
        !            26: 
        !            27: #ifndef __hash_INCLUDE_GNU
        !            28: #define __hash_INCLUDE_GNU
        !            29: 
        !            30: #include "mutex.h"
        !            31: 
        !            32: 
        !            33: /*
        !            34:  * This data structure is used to hold items
        !            35:  *  stored in a hash table.  Each node holds 
        !            36:  *  a key/value pair.
        !            37:  *
        !            38:  * Items in the cache are really of type void *.
        !            39:  */
        !            40: typedef struct cache_node
        !            41: {
        !            42:   struct cache_node *next;     /* Pointer to next entry on the list.
        !            43:                                   NULL indicates end of list. */
        !            44:   const void *key;             /* Key used to locate the value.  Used
        !            45:                                   to locate value when more than one
        !            46:                                   key computes the same hash
        !            47:                                   value. */
        !            48:   void *value;                 /* Value stored for the key. */
        !            49: } *node_ptr;
        !            50: 
        !            51: 
        !            52: /*
        !            53:  * This data type is the function that computes a hash code given a key.
        !            54:  * Therefore, the key can be a pointer to anything and the function specific
        !            55:  * to the key type. 
        !            56:  *
        !            57:  * Unfortunately there is a mutual data structure reference problem with this
        !            58:  * typedef.  Therefore, to remove compiler warnings the functions passed to
        !            59:  * hash_new will have to be casted to this type. 
        !            60:  */
        !            61: typedef unsigned int (*hash_func_type)(void *, const void *);
        !            62: 
        !            63: /*
        !            64:  * This data type is the function that compares two hash keys and returns an
        !            65:  * integer greater than, equal to, or less than 0, according as the first
        !            66:  * parameter is lexico-graphically greater than, equal to, or less than the
        !            67:  * second. 
        !            68:  */
        !            69: 
        !            70: typedef int (*compare_func_type)(const void *, const void *);
        !            71: 
        !            72: 
        !            73: /*
        !            74:  * This data structure is the cache.
        !            75:  *
        !            76:  * It must be passed to all of the hashing routines
        !            77:  *   (except for new).
        !            78:  */
        !            79: typedef struct cache
        !            80: {
        !            81:   /* Variables used to implement the hash itself.  */
        !            82:   node_ptr *node_table; /* Pointer to an array of hash nodes.  */
        !            83:   /* Variables used to track the size of the hash table so to determine
        !            84:     when to resize it.  */
        !            85:   unsigned int size; /* Number of buckets allocated for the hash table
        !            86:                        (number of array entries allocated for
        !            87:                        "node_table").  Must be a power of two.  */
        !            88:   unsigned int used; /* Current number of entries in the hash table.  */
        !            89:   unsigned int mask; /* Precomputed mask.  */
        !            90: 
        !            91:   /* Variables used to implement indexing through the hash table.  */
        !            92: 
        !            93:   unsigned int last_bucket; /* Tracks which entry in the array where
        !            94:                               the last value was returned.  */
        !            95:   /* Function used to compute a hash code given a key. 
        !            96:      This function is specified when the hash table is created.  */
        !            97:   hash_func_type    hash_func;
        !            98:   /* Function used to compare two hash keys to see if they are equal.  */
        !            99:   compare_func_type compare_func;
        !           100: } *cache_ptr;
        !           101: 
        !           102: 
        !           103: /* Two important hash tables.  */
        !           104: extern cache_ptr module_hash_table, class_hash_table;
        !           105: 
        !           106: /* Allocate and initialize a hash table.  */ 
        !           107: 
        !           108: cache_ptr hash_new (unsigned int size,
        !           109:                    hash_func_type hash_func,
        !           110:                    compare_func_type compare_func);
        !           111:                        
        !           112: /* Deallocate all of the hash nodes and the cache itself.  */
        !           113: 
        !           114: void hash_delete (cache_ptr cache);
        !           115: 
        !           116: /* Add the key/value pair to the hash table.  If the
        !           117:    hash table reaches a level of fullnes then it will be resized. 
        !           118:                                                    
        !           119:    assert if the key is already in the hash.  */
        !           120: 
        !           121: void hash_add (cache_ptr *cachep, const void *key, void *value);
        !           122:      
        !           123: /* Remove the key/value pair from the hash table.  
        !           124:    assert if the key isn't in the table.  */
        !           125: 
        !           126: void hash_remove (cache_ptr cache, const void *key);
        !           127: 
        !           128: /* Used to index through the hash table.  Start with NULL
        !           129:    to get the first entry.
        !           130:                                                   
        !           131:    Successive calls pass the value returned previously.
        !           132:    ** Don't modify the hash during this operation *** 
        !           133:                                                   
        !           134:    Cache nodes are returned such that key or value can
        !           135:    be extracted.  */
        !           136: 
        !           137: node_ptr hash_next (cache_ptr cache, node_ptr node);
        !           138: 
        !           139: /* Used to return a value from a hash table using a given key.  */
        !           140: 
        !           141: void *hash_value_for_key (cache_ptr cache, const void *key);
        !           142: 
        !           143: 
        !           144: /************************************************
        !           145: 
        !           146:         Useful hashing functions.  
        !           147:         
        !           148:         Declared inline for your pleaseure. 
        !           149:         
        !           150: ************************************************/
        !           151: 
        !           152: /* Calculate a hash code by performing some 
        !           153:    manipulation of the key pointer.  (Use the lowest bits
        !           154:    except for those likely to be 0 due to alignment.)  */
        !           155: 
        !           156: static inline unsigned int 
        !           157: hash_ptr (cache_ptr cache, const void *key)
        !           158: {
        !           159:   return ((unsigned int)key / sizeof (void *)) & cache->mask;
        !           160: }
        !           161: 
        !           162: 
        !           163: /* Calculate a hash code by iterating over a NULL 
        !           164:    terminate string.  */
        !           165: static inline unsigned int 
        !           166: hash_string (cache_ptr cache, const void *key)
        !           167: {
        !           168:   unsigned int ret = 0;
        !           169:   unsigned int ctr = 0;
        !           170:         
        !           171:         
        !           172:   while (*(char*)key) {
        !           173:     ret ^= *(char*)key++ << ctr;
        !           174:     ctr = (ctr + 1) % sizeof (void *);
        !           175:   }
        !           176: 
        !           177:   return ret & cache->mask;
        !           178: }
        !           179: 
        !           180: 
        !           181: /* Compare two pointers for equality.  */
        !           182: static inline int 
        !           183: compare_ptrs (const void *k1, const void *k2)
        !           184: {
        !           185:   return !(k1 - k2);
        !           186: }
        !           187: 
        !           188: 
        !           189: /* Compare two strings.  */
        !           190: static inline int 
        !           191: compare_strings (const void *k1, const void *k2)
        !           192: {
        !           193:   return !strcmp (k1, k2);
        !           194: }
        !           195: 
        !           196: 
        !           197: #endif /* not __hash_INCLUDE_GNU */

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