Return to hash.h CVS log

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

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

1.1       root        1: /* Hash tables for Objective C method dispatch.
1.1.1.5 ! root        2:    Copyright (C) 1993, 1995 Free Software Foundation, Inc.
1.1       root        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
1.1.1.5 ! root       18: the Free Software Foundation, 59 Temple Place - Suite 330,
        !            19: Boston, MA 02111-1307, USA.  */
1.1       root       20: 
                     21: /* As a special exception, if you link this library with files
                     22:    compiled with GCC to produce an executable, this does not cause
                     23:    the resulting executable to be covered by the GNU General Public License.
                     24:    This exception does not however invalidate any other reasons why
                     25:    the executable file might be covered by the GNU General Public License.  */
                     26: 
                     27: 
                     28: #ifndef __hash_INCLUDE_GNU
                     29: #define __hash_INCLUDE_GNU
                     30: 
1.1.1.4   root       31: #include <stddef.h>
1.1       root       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
1.1.1.5 ! root       66:  * parameter is lexicographically greater than, equal to, or less than the
1.1       root       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
1.1.1.5 ! root      117:    hash table reaches a level of fullness then it will be resized. 
1.1       root      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:         
1.1.1.2   root      148:         Declared inline for your pleasure.
1.1       root      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: 
1.1.1.2   root      156: static inline unsigned int
1.1       root      157: hash_ptr (cache_ptr cache, const void *key)
                    158: {
1.1.1.2   root      159:   return ((size_t)key / sizeof (void *)) & cache->mask;
1.1       root      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: {
1.1.1.3   root      193:   if (k1 == k2)
                    194:     return 1;
                    195:   else if (k1 == 0 || k2 == 0)
                    196:     return 0;
                    197:   else
                    198:     return !strcmp (k1, k2);
1.1       root      199: }
                    200: 
                    201: 
                    202: #endif /* not __hash_INCLUDE_GNU */

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