Return to hash.h CVS log

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

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

1.1       root        1: /* Hash tables for Objective C method dispatch.
1.1.1.2 ! root        2:    Copyright (C) 1993 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
                     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: 
1.1.1.2 ! root       30: #ifdef IN_GCC
        !            31: #include "gstddef.h"
        !            32: #else
        !            33: #include "stddef.h"
        !            34: #endif
1.1       root       35: 
                     36: /*
                     37:  * This data structure is used to hold items
                     38:  *  stored in a hash table.  Each node holds 
                     39:  *  a key/value pair.
                     40:  *
                     41:  * Items in the cache are really of type void *.
                     42:  */
                     43: typedef struct cache_node
                     44: {
                     45:   struct cache_node *next;     /* Pointer to next entry on the list.
                     46:                                   NULL indicates end of list. */
                     47:   const void *key;             /* Key used to locate the value.  Used
                     48:                                   to locate value when more than one
                     49:                                   key computes the same hash
                     50:                                   value. */
                     51:   void *value;                 /* Value stored for the key. */
                     52: } *node_ptr;
                     53: 
                     54: 
                     55: /*
                     56:  * This data type is the function that computes a hash code given a key.
                     57:  * Therefore, the key can be a pointer to anything and the function specific
                     58:  * to the key type. 
                     59:  *
                     60:  * Unfortunately there is a mutual data structure reference problem with this
                     61:  * typedef.  Therefore, to remove compiler warnings the functions passed to
                     62:  * hash_new will have to be casted to this type. 
                     63:  */
                     64: typedef unsigned int (*hash_func_type)(void *, const void *);
                     65: 
                     66: /*
                     67:  * This data type is the function that compares two hash keys and returns an
                     68:  * integer greater than, equal to, or less than 0, according as the first
                     69:  * parameter is lexico-graphically greater than, equal to, or less than the
                     70:  * second. 
                     71:  */
                     72: 
                     73: typedef int (*compare_func_type)(const void *, const void *);
                     74: 
                     75: 
                     76: /*
                     77:  * This data structure is the cache.
                     78:  *
                     79:  * It must be passed to all of the hashing routines
                     80:  *   (except for new).
                     81:  */
                     82: typedef struct cache
                     83: {
                     84:   /* Variables used to implement the hash itself.  */
                     85:   node_ptr *node_table; /* Pointer to an array of hash nodes.  */
                     86:   /* Variables used to track the size of the hash table so to determine
                     87:     when to resize it.  */
                     88:   unsigned int size; /* Number of buckets allocated for the hash table
                     89:                        (number of array entries allocated for
                     90:                        "node_table").  Must be a power of two.  */
                     91:   unsigned int used; /* Current number of entries in the hash table.  */
                     92:   unsigned int mask; /* Precomputed mask.  */
                     93: 
                     94:   /* Variables used to implement indexing through the hash table.  */
                     95: 
                     96:   unsigned int last_bucket; /* Tracks which entry in the array where
                     97:                               the last value was returned.  */
                     98:   /* Function used to compute a hash code given a key. 
                     99:      This function is specified when the hash table is created.  */
                    100:   hash_func_type    hash_func;
                    101:   /* Function used to compare two hash keys to see if they are equal.  */
                    102:   compare_func_type compare_func;
                    103: } *cache_ptr;
                    104: 
                    105: 
                    106: /* Two important hash tables.  */
                    107: extern cache_ptr module_hash_table, class_hash_table;
                    108: 
                    109: /* Allocate and initialize a hash table.  */ 
                    110: 
                    111: cache_ptr hash_new (unsigned int size,
                    112:                    hash_func_type hash_func,
                    113:                    compare_func_type compare_func);
                    114:                        
                    115: /* Deallocate all of the hash nodes and the cache itself.  */
                    116: 
                    117: void hash_delete (cache_ptr cache);
                    118: 
                    119: /* Add the key/value pair to the hash table.  If the
                    120:    hash table reaches a level of fullnes then it will be resized. 
                    121:                                                    
                    122:    assert if the key is already in the hash.  */
                    123: 
                    124: void hash_add (cache_ptr *cachep, const void *key, void *value);
                    125:      
                    126: /* Remove the key/value pair from the hash table.  
                    127:    assert if the key isn't in the table.  */
                    128: 
                    129: void hash_remove (cache_ptr cache, const void *key);
                    130: 
                    131: /* Used to index through the hash table.  Start with NULL
                    132:    to get the first entry.
                    133:                                                   
                    134:    Successive calls pass the value returned previously.
                    135:    ** Don't modify the hash during this operation *** 
                    136:                                                   
                    137:    Cache nodes are returned such that key or value can
                    138:    be extracted.  */
                    139: 
                    140: node_ptr hash_next (cache_ptr cache, node_ptr node);
                    141: 
                    142: /* Used to return a value from a hash table using a given key.  */
                    143: 
                    144: void *hash_value_for_key (cache_ptr cache, const void *key);
                    145: 
                    146: 
                    147: /************************************************
                    148: 
                    149:         Useful hashing functions.  
                    150:         
1.1.1.2 ! root      151:         Declared inline for your pleasure.
1.1       root      152:         
                    153: ************************************************/
                    154: 
                    155: /* Calculate a hash code by performing some 
                    156:    manipulation of the key pointer.  (Use the lowest bits
                    157:    except for those likely to be 0 due to alignment.)  */
                    158: 
1.1.1.2 ! root      159: static inline unsigned int
1.1       root      160: hash_ptr (cache_ptr cache, const void *key)
                    161: {
1.1.1.2 ! root      162:   return ((size_t)key / sizeof (void *)) & cache->mask;
1.1       root      163: }
                    164: 
                    165: 
                    166: /* Calculate a hash code by iterating over a NULL 
                    167:    terminate string.  */
                    168: static inline unsigned int 
                    169: hash_string (cache_ptr cache, const void *key)
                    170: {
                    171:   unsigned int ret = 0;
                    172:   unsigned int ctr = 0;
                    173:         
                    174:         
                    175:   while (*(char*)key) {
                    176:     ret ^= *(char*)key++ << ctr;
                    177:     ctr = (ctr + 1) % sizeof (void *);
                    178:   }
                    179: 
                    180:   return ret & cache->mask;
                    181: }
                    182: 
                    183: 
                    184: /* Compare two pointers for equality.  */
                    185: static inline int 
                    186: compare_ptrs (const void *k1, const void *k2)
                    187: {
                    188:   return !(k1 - k2);
                    189: }
                    190: 
                    191: 
                    192: /* Compare two strings.  */
                    193: static inline int 
                    194: compare_strings (const void *k1, const void *k2)
                    195: {
                    196:   return !strcmp (k1, k2);
                    197: }
                    198: 
                    199: 
                    200: #endif /* not __hash_INCLUDE_GNU */

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