2 * Copyright (c) 2014 - 2017 Steffen (Daode) Nurpmeso <steffen@sdaoden.eu>.
4 * Copyright (C) 1989 - 1992, 2001, 2004
5 * Free Software Foundation, Inc.
6 * Written by James Clark (jjc@jclark.com)
8 * This is free software; you can redistribute it and/or modify it under
9 * the terms of the GNU General Public License as published by the Free
10 * Software Foundation; either version 2, or (at your option) any later
13 * This is distributed in the hope that it will be useful, but WITHOUT ANY
14 * WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 * You should have received a copy of the GNU General Public License along
19 * with groff; see the file COPYING. If not, write to the Free Software
20 * Foundation, 51 Franklin St - Fifth Floor, Boston, MA 02110-1301, USA.
24 #include "troff-config.h"
26 #include "dictionary.h"
29 // is `p' a good size for a hash table
31 static int is_good_size(unsigned int p
)
33 const unsigned int SMALL
= 10;
35 for (i
= 2; i
<= p
/2; i
++)
38 for (i
= 0x100; i
!= 0; i
<<= 8)
39 if (i
% p
<= SMALL
|| i
% p
> p
- SMALL
)
44 dictionary::dictionary(int n
) : size(n
), used(0), threshold(0.5), factor(1.5)
46 table
= new association
[n
];
49 // see Knuth, Sorting and Searching, p518, Algorithm L
50 // we can't use double-hashing because we want a remove function
52 void *dictionary::lookup(symbol s
, void *v
)
55 for (i
= int(s
.hash() % size
);
57 i
== 0 ? i
= size
- 1: --i
)
58 if (s
== table
[i
].s
) {
60 void *temp
= table
[i
].v
;
72 if ((double)used
/(double)size
>= threshold
|| used
+ 1 >= size
) {
74 size
= int(size
*factor
);
75 while (!is_good_size(size
))
77 association
*old_table
= table
;
78 table
= new association
[size
];
80 for (i
= 0; i
< old_size
; i
++)
81 if (old_table
[i
].v
!= 0)
82 (void)lookup(old_table
[i
].s
, old_table
[i
].v
);
88 void *dictionary::lookup(const char *p
)
90 symbol
s(p
, MUST_ALREADY_EXIST
);
97 // see Knuth, Sorting and Searching, p527, Algorithm R
99 void *dictionary::remove(symbol s
)
101 // this relies on the fact that we are using linear probing
103 for (i
= int(s
.hash() % size
);
104 table
[i
].v
!= 0 && s
!= table
[i
].s
;
105 i
== 0 ? i
= size
- 1: --i
)
107 void *p
= table
[i
].v
;
108 while (table
[i
].v
!= 0) {
118 r
= int(table
[i
].s
.hash() % size
);
119 } while ((i
<= r
&& r
< j
) || (r
< j
&& j
< i
) || (j
< i
&& i
<= r
));
127 dictionary_iterator::dictionary_iterator(dictionary
&d
) : dict(&d
), i(0)
131 int dictionary_iterator::get(symbol
*sp
, void **vp
)
133 for (; i
< dict
->size
; i
++)
134 if (dict
->table
[i
].v
) {
135 *sp
= dict
->table
[i
].s
;
136 *vp
= dict
->table
[i
].v
;
143 object_dictionary_iterator::object_dictionary_iterator(object_dictionary
&od
)
148 object::object() : rcount(0)
156 void object::add_reference()
161 void object::remove_reference()
167 object_dictionary::object_dictionary(int n
) : d(n
)
171 object
*object_dictionary::lookup(symbol nm
)
173 return (object
*)d
.lookup(nm
);
176 void object_dictionary::define(symbol nm
, object
*obj
)
178 obj
->add_reference();
179 obj
= (object
*)d
.lookup(nm
, obj
);
181 obj
->remove_reference();
184 void object_dictionary::rename(symbol oldnm
, symbol newnm
)
186 object
*obj
= (object
*)d
.remove(oldnm
);
188 obj
= (object
*)d
.lookup(newnm
, obj
);
190 obj
->remove_reference();
194 void object_dictionary::remove(symbol nm
)
196 object
*obj
= (object
*)d
.remove(nm
);
198 obj
->remove_reference();
201 // Return non-zero if oldnm was defined.
203 int object_dictionary::alias(symbol newnm
, symbol oldnm
)
205 object
*obj
= (object
*)d
.lookup(oldnm
);
207 obj
->add_reference();
208 obj
= (object
*)d
.lookup(newnm
, obj
);
210 obj
->remove_reference();