Return to hash.h CVS log

Up to [Apple XNU] / GNUtools / cc / objc

Annotation of GNUtools/cc/objc/hash.h, revision 1.1

1.1     ! root        1: /* Hash tables for Objective C method dispatch.
        !             2:    Copyright (C) 1993 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: #ifdef IN_GCC
        !            31: #include "gstddef.h"
        !            32: #else
        !            33: #include "stddef.h"
        !            34: #endif
        !            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:         
        !           151:         Declared inline for your pleasure.
        !           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: 
        !           159: static inline unsigned int
        !           160: hash_ptr (cache_ptr cache, const void *key)
        !           161: {
        !           162:   return ((size_t)key / sizeof (void *)) & cache->mask;
        !           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:   if (k1 == k2)
        !           197:     return 1;
        !           198:   else if (k1 == 0 || k2 == 0)
        !           199:     return 0;
        !           200:   else
        !           201:     return !strcmp (k1, k2);
        !           202: }
        !           203: 
        !           204: 
        !           205: #endif /* not __hash_INCLUDE_GNU */

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