Return to hash.c CVS log

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

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

1.1     ! root        1: /*
        !             2:     $Header: /usr2/odi/libmisc/RCS/hash.C,v 1.11 90/03/22 09:24:07 sam Exp $
        !             3: 
        !             4:     Copyright (c) 1989 by Object Design, Inc., Burlington, Mass.
        !             5:     All rights reserved.
        !             6: 
        !             7: */
        !             8: 
        !             9: #include <stdio.h>
        !            10:     /* att.change ??? #include <objectstore/hash.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: unsigned int foo(int bar) {return bar;}
        !           262: int baz(int a, int b) {return a == b;}
        !           263: 
        !           264: main()
        !           265: {
        !           266:   Hash vh(10)  ;
        !           267:   HashWalker vt(vh)  ;
        !           268:   int i  ;
        !           269: 
        !           270:   vh.key_hash_function = &foo  ;
        !           271:   vh.key_key_equality_function = baz  ;
        !           272:   printf("Capacity=%d \n", vh.capacity()) ;
        !           273:   for (i=0; i<500; i+= 5)
        !           274:     {
        !           275:       vh[i] = i * i  ;
        !           276:     }
        !           277:   vt.reset() ;
        !           278:   while (vt.valid())
        !           279:     {
        !           280:       printf("key=%d, data=%d\t", vt.key(), vt.get());
        !           281:       vt.advance()  ;
        !           282:     }
        !           283:   for (i=0; i<500; i+= 10)
        !           284:     {
        !           285:       vh.del (i) ;
        !           286:       printf("After delete: %d\n", vh[i]);
        !           287:     }
        !           288:   printf("\n-----------------\n") ;
        !           289:   vt.reset() ;
        !           290:   while (vt.valid())
        !           291:     {
        !           292:       printf("key=%d, data=%d\t", vt.key(), vt.get());
        !           293:       vt.advance()  ;
        !           294:     }
        !           295: }
        !           296: 
        !           297: */
        !           298: 
        !           299: const static char rcsinfo[]= "$Header";
        !           300: const static char copyright[]="Copyright (c) 1989 by Object Design, Inc., Burlington, Mass.";
        !           301: 
        !           302: 
        !           303: /*
        !           304:    $Log:       hash.C,v $
        !           305: Revision 1.11  90/03/22  09:24:07  sam
        !           306: 1) Modified the hash tables to resize themselves when they are 87.5% 
        !           307: full rather than when they overflowed as before. The previous strategy
        !           308: resulted in ~O(n) probes immediately before the resize.
        !           309: 
        !           310: 2) Bug fix: When a hash table was resized, it held on to the location 
        !           311: of the deleted entry(in bestspot), and used it after the resizing to 
        !           312: insert a new entry, although the deleted entry had been moved as 
        !           313: a result of the resizing.
        !           314: 
        !           315: Revision 1.10  90/01/11  13:45:53  dlw
        !           316: Use stdio instead of AT&T streams.
        !           317: ,
        !           318: 
        !           319: Revision 1.9  90/01/11  13:18:10  benson
        !           320: include paths.
        !           321: 
        !           322: Revision 1.8  90/01/10  13:05:15  cwl
        !           323: *** empty log message ***
        !           324: 
        !           325: Revision 1.7  90/01/09  14:59:37  cwl
        !           326: remove lines which set size prior to doing a resize
        !           327: 
        !           328: Revision 1.6  89/09/27  11:53:46  sam
        !           329: the copy constructor for Hash needed to initialize the now non-static members
        !           330: key_hash_function and key_key_equality_function, so that the members of the
        !           331: argument hash can be copied over.
        !           332: 
        !           333: Revision 1.5  89/08/15  15:17:41  cwl
        !           334: fix resizing problem
        !           335: 
        !           336: Revision 1.4  89/08/15  14:54:31  root
        !           337: *** empty log message ***
        !           338: 
        !           339: Revision 1.3  89/07/11  09:04:32  benson
        !           340: add Hash::action which avoids the pitfalls and inefficiencies
        !           341: of [] and contains.
        !           342: 
        !           343: Revision 1.2  89/06/28  11:42:04  benson
        !           344: declare exit by including osfcn.h
        !           345: 
        !           346: Revision 1.1  89/05/22  13:26:17  cwl
        !           347: Initial revision
        !           348: 
        !           349: Revision 1.1  89/05/12  14:26:40  cwl
        !           350: Initial revision
        !           351: 
        !           352: 
        !           353:    end_log
        !           354: */
        !           355: 
        !           356: 

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