Back to index

texmacs  1.0.7.15
hashmap.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : hashmap.cpp
00004 * DESCRIPTION: fixed size hashmaps with reference counting
00005 * COPYRIGHT  : (C) 1999  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license version 3 or later.
00008 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00009 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00010 ******************************************************************************/
00011 
00012 #ifndef HASHMAP_CC
00013 #define HASHMAP_CC
00014 #include "hashmap.hpp"
00015 #define TMPL template<class T, class U>
00016 #define H hashentry<T,U>
00017 
00018 /******************************************************************************
00019 * Hashmap entries
00020 ******************************************************************************/
00021 
00022 TMPL H::hashentry (int code2, T key2, U im2):
00023   code (code2), key (key2), im (im2) {}
00024 
00025 TMPL H::operator tree () {
00026   return tree (ASSOCIATE, as_tree(key), as_tree(im)); }
00027 
00028 TMPL tm_ostream&
00029 operator << (tm_ostream& out, H h) {
00030   out << h.key << "->" << h.im;
00031   return out;
00032 }
00033 
00034 TMPL bool
00035 operator == (H h1, H h2) {
00036   return (h1.code==h2.code) && (h1.key==h2.key) && (h1.im==h2.im);
00037 }
00038 
00039 TMPL bool
00040 operator != (H h1, H h2) {
00041   return (h1.code!=h2.code) || (h1.key!=h2.key) || (h1.im!=h2.im);
00042 }
00043 
00044 /******************************************************************************
00045 * Routines for hashmaps
00046 ******************************************************************************/
00047 
00048 TMPL void
00049 hashmap_rep<T,U>::resize (int n2) {
00050   int i;
00051   int oldn= n;
00052   list<hashentry<T,U> >* olda= a;
00053   n= n2;
00054   a= tm_new_array<list<hashentry<T,U> > > (n);
00055   for (i=0; i<oldn; i++) {
00056     list<hashentry<T,U> > l(olda[i]);
00057     while (!is_nil (l)) {
00058       list<hashentry<T,U> >& newl= a[hash(l->item.key)&(n-1)];
00059       newl= list<hashentry<T,U> > (l->item, newl);
00060       l=l->next;
00061     }
00062   }
00063   tm_delete_array (olda);
00064 }
00065 
00066 TMPL bool
00067 hashmap_rep<T,U>::contains (T x) {
00068   register int hv= hash (x);
00069   list<hashentry<T,U> >  l (a [hv & (n-1)]);
00070   while (!is_nil (l)) {
00071     if (l->item.code == hv && l->item.key == x)
00072       return true;
00073     l= l->next;
00074   }
00075   return false;
00076 }
00077 
00078 TMPL bool
00079 hashmap_rep<T,U>::empty () {
00080   return size==0;
00081 }
00082 
00083 TMPL U&
00084 hashmap_rep<T,U>::bracket_rw (T x) {
00085   register int hv= hash (x);
00086   list<hashentry<T,U> >  l (a [hv & (n-1)]);
00087   while (!is_nil (l)) {
00088     if (l->item.code == hv && l->item.key == x)
00089       return l->item.im;
00090     l= l->next;
00091   }
00092   if (size >= n*max) resize (n<<1);
00093   list<hashentry<T,U> >& rl= a [hv & (n-1)];
00094   rl= list<hashentry<T,U> > (H (hv, x, init), rl);
00095   size ++;
00096   return rl->item.im;
00097 }
00098 
00099 TMPL U
00100 hashmap_rep<T,U>::bracket_ro (T x) {
00101   register int hv= hash (x);
00102   list<hashentry<T,U> >  l (a [hv & (n-1)]);
00103   while (!is_nil (l)) {
00104     if (l->item.code == hv && l->item.key == x)
00105       return l->item.im;
00106     l= l->next;
00107   }
00108   return init;
00109 }
00110 
00111 TMPL void
00112 hashmap_rep<T,U>::reset (T x) {
00113   register int hv= hash (x);
00114   list<hashentry<T,U> > *l= &(a [hv & (n-1)]);
00115   while (!is_nil (*l)) {
00116     if ((*l)->item.code == hv && (*l)->item.key == x) {
00117       *l= (*l)->next;
00118       size --;
00119       if (size < (n>>1) * max) resize (n>>1);
00120       return;
00121     }
00122     l= &((*l)->next);
00123   }
00124 }
00125 
00126 TMPL void
00127 hashmap_rep<T,U>::generate (void (*routine) (T)) {
00128   int i;
00129   for (i=0; i<n; i++) {
00130     list<hashentry<T,U> > l (a[i]);
00131     while (!is_nil (l)) {
00132       routine (l->item.key);
00133       l=l->next;
00134     }
00135   }
00136 }
00137 
00138 TMPL tm_ostream&
00139 operator << (tm_ostream& out, hashmap<T,U> h) {
00140   int i= 0, j= 0, n= h->n, size= h->size;
00141   out << "{ ";
00142   for (; i<n; i++) {
00143     list<hashentry<T,U> > l= h->a[i];
00144     for (; !is_nil (l); l= l->next, j++) {
00145       out << l->item;
00146       if (j != size-1) out << ", ";
00147     }
00148   }
00149   out << " }";
00150   return out;
00151 }
00152 
00153 TMPL hashmap<T,U>::operator tree () {
00154   int i=0, j=0, n=rep->n, size=rep->size;
00155   tree t (COLLECTION, size);
00156   for (; i<n; i++) {
00157     list<hashentry<T,U> > l= rep->a[i];
00158     for (; !is_nil (l); l= l->next, j++)
00159       t[j]= (tree) l->item;
00160   }
00161   return t;
00162 }
00163 
00164 TMPL void
00165 hashmap_rep<T,U>::join (hashmap<T,U> h) {
00166   int i= 0, n= h->n;
00167   for (; i<n; i++) {
00168     list<hashentry<T,U> > l= h->a[i];
00169     for (; !is_nil(l); l= l->next)
00170       bracket_rw (l->item.key)= copy (l->item.im);
00171   }
00172 }
00173 
00174 TMPL bool
00175 operator == (hashmap<T,U> h1, hashmap<T,U> h2) {
00176   if (h1->size != h2->size) return false;
00177   int i= 0, n= h1->n;
00178   for (; i<n; i++) {
00179     list<hashentry<T,U> > l= h1->a[i];
00180     for (; !is_nil(l); l=l->next)
00181       if (h2[l->item.key] != l->item.im) return false;
00182   }
00183   return true;
00184 }
00185 
00186 TMPL bool
00187 operator != (hashmap<T,U> h1, hashmap<T,U> h2) {
00188   return !(h1 == h2);
00189 }
00190 
00191 #undef H
00192 #undef TMPL
00193 #endif // defined HASHMAP_CC