Return to VHashAssoc.c CVS log

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

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

1.1     ! root        1: #include "check.h"
        !             2: 
        !             3: // This may look like C code, but it is really -*- C++ -*-
        !             4: /* 
        !             5: Copyright (C) 1988 Free Software Foundation
        !             6:     written by Doug Lea ([email protected])
        !             7: 
        !             8: This file is part of GNU CC.
        !             9: 
        !            10: GNU CC is distributed in the hope that it will be useful,
        !            11: but WITHOUT ANY WARRANTY.  No author or distributor
        !            12: accepts responsibility to anyone for the consequences of using it
        !            13: or for whether it serves any particular purpose or works at all,
        !            14: unless he says so in writing.  Refer to the GNU CC General Public
        !            15: License for full details.
        !            16: 
        !            17: Everyone is granted permission to copy, modify and redistribute
        !            18: GNU CC, but only under the conditions described in the
        !            19: GNU CC General Public License.   A copy of this license is
        !            20: supposed to have been given to you along with GNU CC so you
        !            21: can know your rights and responsibilities.  It should be in a
        !            22: file named COPYING.  Among other things, the copyright notice
        !            23: and this notice must be preserved on all copies.  
        !            24: */
        !            25: 
        !            26: /* GNU hash tables converted to demonstrate PT */
        !            27: 
        !            28: template <class T, class U> class VHashAssocNode
        !            29: {
        !            30: public:
        !            31:   T                     key;
        !            32:   U                     cont;
        !            33:   char                  status;
        !            34: };
        !            35: 
        !            36: 
        !            37: template <class T, class U> class VHashAssocTrav ;
        !            38: 
        !            39: 
        !            40: template <class T, class U> class VHashAssoc
        !            41: {
        !            42:   friend class          VHashAssocTrav<T,U> ;
        !            43: 
        !            44:   VHashAssocNode<T,U> * tab;
        !            45:   int                   size;
        !            46:   int                   cnt;
        !            47: 
        !            48: public:
        !            49:   static unsigned int (*key_hash_function)(T &);
        !            50:   int  (* key_key_equality_function )(T&, T&);
        !            51: 
        !            52:   unsigned int          key_hash(T& a);
        !            53:   int                   key_key_eq(T&a, T& b);    
        !            54: 
        !            55:                         VHashAssoc(int sz);
        !            56:                         VHashAssoc(VHashAssoc& a);
        !            57:                         ~VHashAssoc();
        !            58: 
        !            59:   VHashAssoc&     operator = (VHashAssoc& a);
        !            60: 
        !            61:   int                   count();
        !            62:   int                   empty();
        !            63:   int                   full();
        !            64:   int                   capacity();
        !            65: 
        !            66:   void                  clear();
        !            67:   void                  resize(int newsize);
        !            68: 
        !            69:   U&                  operator [] (T& k);
        !            70:   int                   contains(T& key);
        !            71:   int                   del(T& key);
        !            72: 
        !            73: 
        !            74:   void                  apply(void f(U& v));
        !            75:   void                  error(const char* msg);
        !            76: };
        !            77: 
        !            78: template <class T, class U> class VHashAssocTrav
        !            79: {
        !            80:   VHashAssoc<T,U>*      h;
        !            81:   int                   pos;
        !            82: 
        !            83: 
        !            84: public:
        !            85:                         VHashAssocTrav(VHashAssoc<T,U>& l);
        !            86:                         ~VHashAssocTrav();
        !            87:   int                   null();
        !            88:   int                   valid();
        !            89:                         operator void* ();
        !            90:   int                   operator ! ();
        !            91:   void                  advance();
        !            92:   void                  reset();
        !            93:   void                  reset(VHashAssoc<T,U>& l);
        !            94:   T&                    key();
        !            95:   U&                  get();
        !            96: };
        !            97: 
        !            98: template <class T, class U>  unsigned int VHashAssoc<T,U>::key_hash(T& a)
        !            99: {
        !           100:   return (*VHashAssoc<T,U>::key_hash_function)(a);
        !           101: }
        !           102: 
        !           103: template <class T, class U>   int VHashAssoc<T,U>::key_key_eq(T&a, T& b)
        !           104: {
        !           105:   return (*VHashAssoc<T,U>::key_key_equality_function)(a, b);
        !           106: }
        !           107: 
        !           108: 
        !           109: template <class T, class U>  VHashAssoc<T,U>::~VHashAssoc()
        !           110: {
        !           111:   delete [size] tab;
        !           112: }
        !           113: 
        !           114: template <class T, class U>  VHashAssoc<T,U>::count()
        !           115: {
        !           116:   return cnt;
        !           117: }
        !           118: 
        !           119: template <class T, class U>  VHashAssoc<T,U>::empty()
        !           120: {
        !           121:   return cnt == 0;
        !           122: }
        !           123: 
        !           124: template <class T, class U>  VHashAssoc<T,U>::full()
        !           125: {
        !           126:   return cnt == size;
        !           127: }
        !           128: 
        !           129: template <class T, class U>  VHashAssoc<T,U>::capacity()
        !           130: {
        !           131:   return size;
        !           132: }
        !           133: 
        !           134: template <class T, class U>  VHashAssocTrav<T,U>::VHashAssocTrav(VHashAssoc<T,U>& a)
        !           135: {
        !           136:   h = &a;
        !           137:   reset();
        !           138: }
        !           139: 
        !           140: template <class T, class U>  void VHashAssocTrav<T,U>::reset(VHashAssoc<T,U>& a)
        !           141: {
        !           142:   h = &a;
        !           143:   reset();
        !           144: }
        !           145: 
        !           146: 
        !           147: template <class T, class U>  VHashAssocTrav<T,U>::~VHashAssocTrav() {}
        !           148: 
        !           149: template <class T, class U>  VHashAssocTrav<T,U>::null()
        !           150: {
        !           151:   return pos < 0;
        !           152: }
        !           153: 
        !           154: template <class T, class U>  VHashAssocTrav<T,U>::valid()
        !           155: {
        !           156:   return pos >= 0;
        !           157: }
        !           158: 
        !           159: template <class T, class U>   VHashAssocTrav<T,U>::operator void* ()
        !           160: {
        !           161:   return (pos < 0)? 0 : this;
        !           162: }
        !           163: 
        !           164: template <class T, class U>  VHashAssocTrav<T,U>::operator ! ()
        !           165: {
        !           166:   return (pos < 0);
        !           167: }
        !           168: 
        !           169: 
        !           170: template <class T, class U>  T & VHashAssocTrav<T,U>::key()
        !           171: {
        !           172:   if (pos < 0)
        !           173:     h->error("operation on null traverser");
        !           174:   return h->tab[pos].key;
        !           175: }
        !           176: 
        !           177: template <class T, class U> U & VHashAssocTrav<T,U>::get()
        !           178: {
        !           179:   if (pos < 0)
        !           180:     h->error("operation on null traverser");
        !           181:   return h->tab[pos].cont;
        !           182: }
        !           183: 
        !           184: enum  {EMPTYCELL, VALIDCELL, DELETEDCELL } ;
        !           185: 
        !           186: 
        !           187: // error handling
        !           188: 
        !           189: 
        !           190: 
        !           191: template <class T, class U>void VHashAssoc<T,U>::error(const char* msg)
        !           192: {
        !           193:    // (*VHashAssoc_error_handler)(msg);
        !           194: }
        !           195: 
        !           196: template <class T, class U>VHashAssoc<T,U>::VHashAssoc(int sz)
        !           197: {
        !           198:   tab = new VHashAssocNode<T,U>[size = sz];
        !           199:   for (int i = 0; i < size; ++i) tab[i].status = EMPTYCELL;
        !           200:   cnt = 0;
        !           201: }
        !           202: 
        !           203: template <class T, class U>VHashAssoc<T,U>::VHashAssoc(VHashAssoc<T,U>& a)
        !           204: {
        !           205:   tab = new VHashAssocNode<T,U>[size = a.size];
        !           206:   for (int i = 0; i < size; ++i) tab[i].status = EMPTYCELL;
        !           207:   cnt = 0;
        !           208:   for (VHashAssocTrav<T,U> p(a); p; p.advance())
        !           209:     (*this)[p.key()] = p.get();
        !           210: }
        !           211: 
        !           212: template <class T, class U> VHashAssoc<T,U>& VHashAssoc<T,U>::operator =
        !           213: (VHashAssoc<T,U>& a)
        !           214: {
        !           215:   if (a.tab != tab)
        !           216:   {
        !           217:     clear();
        !           218:     delete [size] tab;
        !           219:     tab = new VHashAssocNode<T,U>[size = a.size];
        !           220:     for (int i = 0; i < size; ++i) tab[i].status = EMPTYCELL;
        !           221:     cnt = 0;
        !           222:     for (VHashAssocTrav<T,U> p(a); p; p.advance())
        !           223:       (*this)[p.key()] = p.get();
        !           224:   }
        !           225:   return *this;
        !           226: }
        !           227: 
        !           228: /* 
        !           229:  * hashing method: double hash based on high bits of hash fct,
        !           230:  * followed by linear probe. Can't do too much better if Assoc
        !           231:  * sizes not constrained to be prime.
        !           232: */
        !           233: 
        !           234: 
        !           235: static inline doublehashinc(unsigned int h, int s)
        !           236: {
        !           237:   return ((h / s) % s) >> 1;
        !           238: }
        !           239: 
        !           240: 
        !           241: template <class T, class U>U& VHashAssoc<T,U>::operator [](T & key)
        !           242: {
        !           243:   int bestspot = -1;
        !           244:   unsigned int hashval = key_hash(key);
        !           245:   int h = hashval % size;
        !           246:   for (int i = 0; i <= size; ++i)
        !           247:   {
        !           248:     if (tab[h].status == EMPTYCELL)
        !           249:     {
        !           250:       if (bestspot < 0) bestspot = h;
        !           251:       tab[bestspot].key = key;
        !           252:       tab[bestspot].status = VALIDCELL;
        !           253:       ++cnt;
        !           254:       return tab[bestspot].cont;
        !           255:     }
        !           256:     else if (tab[h].status == DELETEDCELL)
        !           257:     {
        !           258:       if (bestspot < 0) bestspot = h;
        !           259:     }
        !           260:     else if (key_key_eq(tab[h].key, key))
        !           261:       return tab[h].cont;
        !           262:     if (i == 0)
        !           263:       h = (h + doublehashinc(hashval, size)) % size;
        !           264:     else if (++h >= size)
        !           265:       h -= size;
        !           266:   }
        !           267:   error("cannot add to full Assoc table");
        !           268:   return tab[0].cont ; // suppress warning message
        !           269: }
        !           270: 
        !           271: 
        !           272: template <class T, class U>int VHashAssoc<T,U>::contains(T & key)
        !           273: {
        !           274:   unsigned int hashval = key_hash(key);
        !           275:   int h = hashval % size;
        !           276:   for (int i = 0; i <= size; ++i)
        !           277:   {
        !           278:     if (tab[h].status == EMPTYCELL)
        !           279:       return 0;
        !           280:     else if (tab[h].status == VALIDCELL && key_key_eq(tab[h].key, key))
        !           281:       return 1;
        !           282:     if (i == 0)
        !           283:       h = (h + doublehashinc(hashval, size)) % size;
        !           284:     else if (++h >= size)
        !           285:       h -= size;
        !           286:   }
        !           287:   return 0;
        !           288: }
        !           289: 
        !           290: template <class T, class U>int VHashAssoc<T,U>::del(T & key)
        !           291: {
        !           292:   unsigned int hashval = key_hash(key);
        !           293:   int h = hashval % size;
        !           294:   for (int i = 0; i <= size; ++i)
        !           295:   {
        !           296:     if (tab[h].status == EMPTYCELL)
        !           297:       return 0;
        !           298:     else if (tab[h].status == VALIDCELL && key_key_eq(tab[h].key, key))
        !           299:     {
        !           300:       tab[h].status = DELETEDCELL;
        !           301:       --cnt;
        !           302:       return 1;
        !           303:     }
        !           304:     if (i == 0)
        !           305:       h = (h + doublehashinc(hashval, size)) % size;
        !           306:     else if (++h >= size)
        !           307:       h -= size;
        !           308:   }
        !           309:   return 0;
        !           310: }
        !           311: 
        !           312: /*
        !           313: template <class T, class U>void VHashAssoc<T,U>::apply(UProcedure f)
        !           314: {
        !           315:   for (int i = 0; i < size; ++i)
        !           316:     if (tab[i].status == VALIDCELL)
        !           317:       (*f)(tab[i].cont);
        !           318: }
        !           319: */
        !           320: 
        !           321: template <class T, class U>void VHashAssoc<T,U>::clear()
        !           322: {
        !           323:   for (int i = 0; i < size; ++i)
        !           324:     tab[i].status = EMPTYCELL;
        !           325:   cnt = 0;
        !           326: }
        !           327: 
        !           328: template <class T, class U>void VHashAssoc<T,U>::resize(int newsize)
        !           329: {
        !           330:   if (newsize < cnt)
        !           331:     error("requested resize too small");
        !           332:   VHashAssocNode<T,U>* oldtab = tab;
        !           333:   int oldsize = size;
        !           334:   tab = new VHashAssocNode<T,U>[size = newsize];
        !           335:   for (int i = 0; i < size; ++i) 
        !           336:     tab[i].status = EMPTYCELL;
        !           337:   cnt = 0;
        !           338:   for (i = 0; i < oldsize; ++i)
        !           339:     if (oldtab[i].status == VALIDCELL)
        !           340:       (*this)[oldtab[i].key] = oldtab[i].cont;
        !           341:   delete [oldsize] oldtab;
        !           342: }
        !           343: 
        !           344: template <class T, class U>void VHashAssocTrav<T,U>::reset()
        !           345: {
        !           346:   for (pos = 0; pos < h->size; ++pos)
        !           347:     if (h->tab[pos].status == VALIDCELL)
        !           348:       return;
        !           349:   pos = -1;
        !           350: }
        !           351: 
        !           352: template <class T, class U>void VHashAssocTrav<T,U>::advance()
        !           353: {
        !           354:   if (pos < 0)
        !           355:     return;
        !           356:   for (pos++; pos < h->size; ++pos)
        !           357:     if (h->tab[pos].status == VALIDCELL)
        !           358:       return;
        !           359:   pos = -1;
        !           360: }
        !           361: 
        !           362:   
        !           363: const int size = 100 ;
        !           364: 
        !           365: 
        !           366: unsigned int f(int & i) { return i ; }
        !           367: 
        !           368: unsigned int f1(char & i) { return (int)i ; }
        !           369: 
        !           370: int  g(int& k1, int& k2){
        !           371:   return (k1 == k2) ;
        !           372: }
        !           373: 
        !           374: int  g1(char & k1, char & k2){
        !           375:   return (k1 == k2) ;
        !           376: }
        !           377: 
        !           378: 
        !           379: 
        !           380: 
        !           381: VHashAssoc<int, int> foo(2*size) ;
        !           382: 
        !           383:   
        !           384: main () {
        !           385: 
        !           386: 
        !           387:   start_test(__FILE__) ;
        !           388: 
        !           389:   foo.key_hash_function = f ;
        !           390:   foo.key_key_equality_function= g ;
        !           391:   // populate the hash
        !           392:   for (int i = 0 ; ! foo.full() ; i++)
        !           393:     foo[i] = i ;
        !           394: 
        !           395:   for (i = 0 ; i < size ; i++) {
        !           396:     check(foo.contains(i)) ;
        !           397:     check(foo[i] == i) ;
        !           398:   }
        !           399: 
        !           400:   foo.resize(size * 4) ;
        !           401:   
        !           402: // repeat the tests, resizing should not have impacted it any
        !           403:   for (i = 0 ; i < size ; i++) {
        !           404:     check(foo.contains(i)) ;
        !           405:     check(foo[i] == i) ;
        !           406:     check (foo.del(i)) ;
        !           407:     check(!foo.contains(i)) ;
        !           408:   }
        !           409:   {
        !           410:   // try another one
        !           411:   VHashAssoc<char, char *> foo(2*size) ;
        !           412:   foo.key_hash_function = f1 ;
        !           413:   foo.key_key_equality_function= g1 ;
        !           414:   // populate the hash
        !           415:   for (char i = 0 ; ! foo.full() ; i++) {
        !           416:     char *p = new char ;
        !           417:     *p = i ;
        !           418:     foo[i] = p  ;
        !           419:   }
        !           420: 
        !           421:   for (i = 0 ; i < size ; i++) {
        !           422:     check(foo.contains(i)) ;
        !           423:     check(*(foo[i]) == i) ;
        !           424:   }
        !           425: 
        !           426:   foo.resize(size * 4) ;
        !           427:   
        !           428: // repeat the tests, resizing should not have impacted it any
        !           429:   for (i = 0 ; i < size ; i++) {
        !           430:     check(foo.contains(i)) ;
        !           431:     check(*(foo[i]) == i) ;
        !           432:     check (foo.del(i)) ;
        !           433:     check(!foo.contains(i)) ;
        !           434:   }
        !           435: }
        !           436: 
        !           437:   end_test() ;
        !           438: 
        !           439: }
        !           440:   

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