Return to hash.c CVS log

Up to [Research Unix] / researchv10no / cmd / cfront / ptcfront

Annotation of researchv10no/cmd/cfront/ptcfront/hash.c, revision 1.1

1.1     ! root        1: /* ident "@(#)ctrans:src/hash.c        1.2" */
        !             2: /*
        !             3:     $Header: /usr2/odi/libmisc/RCS/hash.C,v 1.11 90/03/22 09:24:07 sam Exp $
        !             4: 
        !             5:     Copyright (c) 1989 by Object Design, Inc., Burlington, Mass.
        !             6:     All rights reserved.
        !             7: 
        !             8: */
        !             9: 
        !            10: #include <stdio.h>
        !            11: #include "hash.h" 
        !            12: #include <osfcn.h>
        !            13: 
        !            14: #define EMPTY   0
        !            15: #define VALID   1
        !            16: #define DELETED 2
        !            17: 
        !            18: void default_Hash_error_handler(const char* msg)
        !            19: {
        !            20:   fprintf(stderr, "Fatal Hash error: %s\n", msg) ;
        !            21:   exit(1) ;
        !            22: }
        !            23: 
        !            24: Error_Proc Hash_error_handler = default_Hash_error_handler ;
        !            25: 
        !            26: Error_Proc set_Hash_error_handler(Error_Proc f)
        !            27: {
        !            28:   Error_Proc old = Hash_error_handler ;
        !            29:   Hash_error_handler = f ;
        !            30:   return old ;
        !            31: }
        !            32: 
        !            33: void Hash::error(const char* msg)
        !            34: {
        !            35:   (*Hash_error_handler)(msg) ;
        !            36: }
        !            37: 
        !            38: Hash::Hash(int sz= DEFAULT_INITIAL_HASH_SIZE)
        !            39: {
        !            40:   tab = new HashTableEntry[size = sz] ;
        !            41:   for (int i = 0; i < size; ++i) tab[i].status = EMPTY ;
        !            42:   entry_count = 0 ;
        !            43: }
        !            44: 
        !            45: Hash::Hash(Hash& a)
        !            46: {
        !            47:   tab = new HashTableEntry[size = a.size] ;
        !            48: 
        !            49:   key_hash_function = a.key_hash_function ;
        !            50:   key_key_equality_function = a.key_key_equality_function ;
        !            51: 
        !            52:   for (int i = 0; i < size; ++i) tab[i].status = EMPTY ;
        !            53:   entry_count = 0 ;
        !            54:   for (HashWalker p(a); p; p.advance())
        !            55:     (*this)[p.key()] = p.get() ;
        !            56: }
        !            57: 
        !            58: Hash& Hash::operator = (Hash& a)
        !            59: {
        !            60:   if (a.tab != tab)
        !            61:   {
        !            62:     clear() ;
        !            63:     delete [size] tab ;
        !            64:     tab = new HashTableEntry[size = a.size] ;
        !            65:     for (int i = 0; i < size; ++i) tab[i].status = EMPTY ;
        !            66:     entry_count = 0 ;
        !            67:     for (HashWalker p(a); p; p.advance())
        !            68:       (*this)[p.key()] = p.get() ;
        !            69:   }
        !            70:   return *this ;
        !            71: }
        !            72: 
        !            73: /* 
        !            74:  * hashing method: double hash based on high bits of hash fct,
        !            75:  * followed by linear probe. Can't do too much better if Assoc
        !            76:  * sizes not constrained to be prime.
        !            77: */
        !            78: 
        !            79: 
        !            80: static inline doublehashinc(unsigned int h, int s)
        !            81: {
        !            82:   return ((h / s) % s) >> 1 ;
        !            83: }
        !            84: 
        !            85: // IWBNI we knew whether we were being called as an lvalue or rvalue.
        !            86: // If the former, then we wouldn't have to scan through the whole
        !            87: // table just to tell if we should rehash or not.  Sigh.
        !            88: int& Hash::operator [](int key)
        !            89: {
        !            90:   unsigned int hashval = key_hash(key) ;
        !            91:   while (1)
        !            92:     {
        !            93:       int bestspot = -1 ;
        !            94:       int h = hashval % size ;
        !            95:       for (int i = 0; i <= size; ++i)
        !            96:        {
        !            97:          if (tab[h].status == EMPTY)
        !            98:            {
        !            99:              // resize if the hash table is more than 87.5% full
        !           100:              if (entry_count > ((size>>1)+(size>>2)+(size>>3)))
        !           101:                // resize and insert again
        !           102:                break ;
        !           103:              if (bestspot < 0) bestspot = h ;
        !           104:              tab[bestspot].key = key ;
        !           105:              tab[bestspot].status = VALID ;
        !           106:              ++entry_count ;
        !           107:              return tab[bestspot].cont ;
        !           108:            }
        !           109:          else if (tab[h].status == DELETED)
        !           110:            {
        !           111:              if (bestspot < 0) bestspot = h ;
        !           112:            }
        !           113:          else if (key_key_eq(tab[h].key, key))
        !           114:            return tab[h].cont ;
        !           115:          if (i == 0)
        !           116:            h = (h + doublehashinc(hashval, size)) % size ;
        !           117:          else if (++h >= size)
        !           118:            h -= size ;
        !           119:        }
        !           120:       resize(size << 1)  ;
        !           121:     }
        !           122: }
        !           123: 
        !           124: /* This seems convoluted, but it does whatever you want without
        !           125:    redundant probing of the hash table. */
        !           126: 
        !           127: void Hash::action (int key, int val, insert_action what,
        !           128:                   int& found, int& old_val)
        !           129: {
        !           130:   unsigned int hashval = key_hash(key) ;
        !           131:   while (1)
        !           132:     {
        !           133:       int bestspot = -1 ;
        !           134:       int h = hashval % size ;
        !           135:       for (int i = 0; i <= size; ++i)
        !           136:        {
        !           137:          if (tab[h].status == EMPTY)
        !           138:            {
        !           139:              // resize if the hash table is more than 87.5% full
        !           140:              if (entry_count > ((size>>1)+(size>>2)+(size>>3)))
        !           141:                // resize and insert again
        !           142:                break ;
        !           143:              if (bestspot < 0) bestspot = h ;
        !           144:              found = 0;
        !           145:              if(what != probe) {
        !           146:                tab[bestspot].key = key ;
        !           147:                tab[bestspot].status = VALID ;
        !           148:                ++entry_count ;
        !           149:                tab[bestspot].cont = val;
        !           150:              } 
        !           151:              return;
        !           152:            }
        !           153:          else if (tab[h].status == DELETED)
        !           154:            {
        !           155:              if (bestspot < 0) bestspot = h ;
        !           156:            }
        !           157:          else if (key_key_eq(tab[h].key, key)) {
        !           158:            found = 1;
        !           159:            old_val = tab[h].cont;
        !           160:            if(what == replace) 
        !           161:              tab[h].cont = val;
        !           162:            return;
        !           163:          }
        !           164:          if (i == 0)
        !           165:            h = (h + doublehashinc(hashval, size)) % size ;
        !           166:          else if (++h >= size)
        !           167:            h -= size ;
        !           168:        }
        !           169:       resize(size << 1)  ;
        !           170:     }
        !           171: }
        !           172: 
        !           173: int Hash::contains(int key)
        !           174: {
        !           175:   unsigned int hashval = key_hash(key) ;
        !           176:   int h = hashval % size ;
        !           177:   for (int i = 0; i <= size; ++i)
        !           178:   {
        !           179:     if (tab[h].status == EMPTY)
        !           180:       return 0 ;
        !           181:     else if (tab[h].status == VALID && key_key_eq(tab[h].key, key))
        !           182:       return 1 ;
        !           183:     if (i == 0)
        !           184:       h = (h + doublehashinc(hashval, size)) % size ;
        !           185:     else if (++h >= size)
        !           186:       h -= size ;
        !           187:   }
        !           188:   return 0 ;
        !           189: }
        !           190: 
        !           191: int Hash::del(int key)
        !           192: {
        !           193:   unsigned int hashval = key_hash(key) ;
        !           194:   int h = hashval % size ;
        !           195:   for (int i = 0; i <= size; ++i)
        !           196:   {
        !           197:     if (tab[h].status == EMPTY)
        !           198:       return 0 ;
        !           199:     else if (tab[h].status == VALID && key_key_eq(tab[h].key, key))
        !           200:     {
        !           201:       tab[h].status = DELETED ;
        !           202:       --entry_count ;
        !           203:       return 1 ;
        !           204:     }
        !           205:     if (i == 0)
        !           206:       h = (h + doublehashinc(hashval, size)) % size ;
        !           207:     else if (++h >= size)
        !           208:       h -= size ;
        !           209:   }
        !           210:   return 0 ;
        !           211: }
        !           212: 
        !           213: void Hash::apply(intProc f)
        !           214: {
        !           215:   for (int i = 0; i < size; ++i)
        !           216:     if (tab[i].status == VALID)
        !           217:       (*f)(tab[i].cont) ;
        !           218: }
        !           219: 
        !           220: void Hash::clear()
        !           221: {
        !           222:   for (int i = 0; i < size; ++i)
        !           223:     tab[i].status = EMPTY ;
        !           224:   entry_count = 0 ;
        !           225: }
        !           226: 
        !           227: void Hash::resize(int newsize)
        !           228: {
        !           229:   if (newsize < entry_count)
        !           230:     error("requested resize too small") ;
        !           231:   HashTableEntry* oldtab = tab ;
        !           232:   int oldsize = size ;
        !           233:   tab = new HashTableEntry[size = newsize] ;
        !           234:   for (int i = 0; i < size; ++i) 
        !           235:     tab[i].status = EMPTY ;
        !           236:   entry_count = 0 ;
        !           237:   for (i = 0; i < oldsize; ++i)
        !           238:     if (oldtab[i].status == VALID)
        !           239:       (*this)[oldtab[i].key] = oldtab[i].cont ;
        !           240:   delete [oldsize] oldtab ;
        !           241: }
        !           242: 
        !           243: void HashWalker::reset()
        !           244: {
        !           245:   for (pos = 0; pos < h->size; ++pos)
        !           246:     if (h->tab[pos].status == VALID)
        !           247:       return ;
        !           248:   pos = -1 ;
        !           249: }
        !           250: 
        !           251: void HashWalker::advance()
        !           252: {
        !           253:   if (pos < 0)
        !           254:     return ;
        !           255:   for (pos++; pos < h->size; ++pos)
        !           256:     if (h->tab[pos].status == VALID)
        !           257:       return ;
        !           258:   pos = -1 ;
        !           259: }
        !           260: 
        !           261: /*
        !           262: unsigned int foo(int bar) {return bar;}
        !           263: int baz(int a, int b) {return a == b;}
        !           264: 
        !           265: main()
        !           266: {
        !           267:   Hash vh(10)  ;
        !           268:   HashWalker vt(vh)  ;
        !           269:   int i  ;
        !           270: 
        !           271:   vh.key_hash_function = &foo  ;
        !           272:   vh.key_key_equality_function = baz  ;
        !           273:   printf("Capacity=%d \n", vh.capacity()) ;
        !           274:   for (i=0; i<500; i+= 5)
        !           275:     {
        !           276:       vh[i] = i * i  ;
        !           277:     }
        !           278:   vt.reset() ;
        !           279:   while (vt.valid())
        !           280:     {
        !           281:       printf("key=%d, data=%d\t", vt.key(), vt.get());
        !           282:       vt.advance()  ;
        !           283:     }
        !           284:   for (i=0; i<500; i+= 10)
        !           285:     {
        !           286:       vh.del (i) ;
        !           287:       printf("After delete: %d\n", vh[i]);
        !           288:     }
        !           289:   printf("\n-----------------\n") ;
        !           290:   vt.reset() ;
        !           291:   while (vt.valid())
        !           292:     {
        !           293:       printf("key=%d, data=%d\t", vt.key(), vt.get());
        !           294:       vt.advance()  ;
        !           295:     }
        !           296: }
        !           297: 
        !           298: */

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