← Back to branch summary

~ubuntu-branches/ubuntu/hardy/texmacs/hardy

« back to all changes in this revision

Viewing changes to src/Classes/Compound/hashmap.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Ralf Treinen
  • Date: 2004-04-19 20:34:00 UTC
  • Revision ID: james.westby@ubuntu.com-20040419203400-g4e34ih0315wcn8v
Tags: upstream-1.0.3-R2
Import upstream version 1.0.3-R2

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/Classes/Compound/hashmap.cpp
 
1
 
 
2
/******************************************************************************
 
3
* MODULE     : hashmap.cpp
 
4
* DESCRIPTION: fixed size hashmaps with reference counting
 
5
* COPYRIGHT  : (C) 1999  Joris van der Hoeven
 
6
*******************************************************************************
 
7
* This software falls under the GNU general public license and comes WITHOUT
 
8
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
 
9
* If you don't have this file, write to the Free Software Foundation, Inc.,
 
10
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 
11
******************************************************************************/
 
12
 
 
13
#ifndef HASHMAP_CC
 
14
#define HASHMAP_CC
 
15
#include "hashmap.hpp"
 
16
#define TMPL template<class T, class U>
 
17
#define H hashentry<T,U>
 
18
 
 
19
/******************************************************************************
 
20
* Hashmap entries
 
21
******************************************************************************/
 
22
 
 
23
TMPL H::hashentry (T key2, U im2): key (key2), im (im2) {}
 
24
 
 
25
TMPL H::operator tree () {
 
26
  return tree (ASSOCIATE, as_tree(key), as_tree(im)); }
 
27
 
 
28
TMPL ostream&
 
29
operator << (ostream& out, H h) {
 
30
  out << h.key << "->" << h.im;
 
31
  return out;
 
32
}
 
33
 
 
34
TMPL bool
 
35
operator == (H h1, H h2) {
 
36
  return (h1.key==h2.key) && (h1.im==h2.im);
 
37
}
 
38
 
 
39
TMPL bool
 
40
operator != (H h1, H h2) {
 
41
  return (h1.key!=h2.key) || (h1.im!=h2.im);
 
42
}
 
43
 
 
44
/******************************************************************************
 
45
* Routines for hashmaps
 
46
******************************************************************************/
 
47
 
 
48
TMPL void
 
49
hashmap_rep<T,U>::resize (int n2) {
 
50
  int i;
 
51
  int oldn= n;
 
52
  list<hashentry<T,U> >* olda= a;
 
53
  n= n2;
 
54
  a= new list<hashentry<T,U> >[n];
 
55
  for (i=0; i<oldn; i++) {
 
56
    list<hashentry<T,U> > l(olda[i]);
 
57
    while (!nil (l)) {
 
58
      list<hashentry<T,U> >& newl= a[hash(l->item.key)&(n-1)];
 
59
      newl= list<hashentry<T,U> > (l->item, newl);
 
60
      l=l->next;
 
61
    }
 
62
  }
 
63
  delete[] olda;
 
64
}
 
65
 
 
66
TMPL bool
 
67
hashmap_rep<T,U>::contains (T x) {
 
68
  list<hashentry<T,U> >  l (a[hash(x)&(n-1)]);
 
69
  while (!nil (l)) {
 
70
    if (l->item.key==x) return true;
 
71
    l= l->next;
 
72
  }
 
73
  return false;
 
74
}
 
75
 
 
76
TMPL bool
 
77
hashmap_rep<T,U>::empty () {
 
78
  return size==0;
 
79
}
 
80
 
 
81
TMPL U&
 
82
hashmap_rep<T,U>::bracket_rw (T x) {
 
83
  register int hv= hash(x);
 
84
  list<hashentry<T,U> >  l (a[hv&(n-1)]);
 
85
  while (!nil (l)) {
 
86
    if (l->item.key==x) return l->item.im;
 
87
    l= l->next;
 
88
  }
 
89
  if (size>=n*max) resize (n<<1);
 
90
  list<hashentry<T,U> >& rl= a[hv&(n-1)];
 
91
  rl= list<hashentry<T,U> > (H (x, init), rl);
 
92
  size ++;
 
93
  return rl->item.im;
 
94
}
 
95
 
 
96
TMPL U
 
97
hashmap_rep<T,U>::bracket_ro (T x) {
 
98
  list<hashentry<T,U> >  l (a[hash(x)&(n-1)]);
 
99
  while (!nil (l)) {
 
100
    if (l->item.key==x) return l->item.im;
 
101
    l= l->next;
 
102
  }
 
103
  return init;
 
104
}
 
105
 
 
106
TMPL void
 
107
hashmap_rep<T,U>::reset (T x) {
 
108
  list<hashentry<T,U> > *l= &(a[hash(x)&(n-1)]);
 
109
  while (!nil (*l)) {
 
110
    if ((*l)->item.key==x) {
 
111
      *l=(*l)->next;
 
112
      size --;
 
113
      if (size<(n>>1)*max) resize (n>>1);
 
114
      return;
 
115
    }
 
116
    l= &((*l)->next);
 
117
  }
 
118
}
 
119
 
 
120
TMPL void
 
121
hashmap_rep<T,U>::generate (void (*routine) (T)) {
 
122
  int i;
 
123
  for (i=0; i<n; i++) {
 
124
    list<hashentry<T,U> > l (a[i]);
 
125
    while (!nil (l)) {
 
126
      routine (l->item.key);
 
127
      l=l->next;
 
128
    }
 
129
  }
 
130
}
 
131
 
 
132
TMPL ostream&
 
133
operator << (ostream& out, hashmap<T,U> h) {
 
134
  int i=0, j=0, n=h->n, size=h->size;
 
135
  out << "{ ";
 
136
  for (; i<n; i++) {
 
137
    list<hashentry<T,U> > l=h->a[i];
 
138
    for (; !nil(l); l=l->next, j++) {
 
139
      out << l->item;
 
140
      if (j!=size-1) out << ", ";
 
141
    }
 
142
  }
 
143
  out << " }";
 
144
  return out;
 
145
}
 
146
 
 
147
TMPL hashmap<T,U>::operator tree () {
 
148
  int i=0, j=0, n=rep->n, size=rep->size;
 
149
  tree t (COLLECTION, size);
 
150
  for (; i<n; i++) {
 
151
    list<hashentry<T,U> > l=rep->a[i];
 
152
    for (; !nil(l); l=l->next, j++)
 
153
      t[j]= (tree) l->item;
 
154
  }
 
155
  return t;
 
156
}
 
157
 
 
158
TMPL void
 
159
hashmap_rep<T,U>::join (hashmap<T,U> h) {
 
160
  int i=0, n=h->n;
 
161
  for (; i<n; i++) {
 
162
    list<hashentry<T,U> > l=h->a[i];
 
163
    for (; !nil(l); l=l->next)
 
164
      bracket_rw (l->item.key)= copy (l->item.im);
 
165
  }
 
166
}
 
167
 
 
168
TMPL bool
 
169
operator == (hashmap<T,U> h1, hashmap<T,U> h2) {
 
170
  if (h1->size != h2->size) return false;
 
171
  int i=0, n=h1->n;
 
172
  for (; i<n; i++) {
 
173
    list<hashentry<T,U> > l=h1->a[i];
 
174
    for (; !nil(l); l=l->next)
 
175
      if (h2[l->item.key] != l->item.im) return false;
 
176
  }
 
177
  return true;
 
178
}
 
179
 
 
180
TMPL bool
 
181
operator != (hashmap<T,U> h1, hashmap<T,U> h2) {
 
182
  return !(h1 == h2);
 
183
}
 
184
 
 
185
#undef H
 
186
#undef TMPL
 
187
#endif // defined HASHMAP_CC