/* Copyright (C) 1989, 1990 Free Software Foundation, Inc.
Written by James Clark (jjc@jclark.uucp)
This file is part of groff.
groff is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 1, or (at your option) any later
groff is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
You should have received a copy of the GNU General Public License along
with groff; see the file LICENSE. If not, write to the Free Software
Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
// is `p' a good size for a hash table
static int is_good_size(int p
)
for (unsigned i
= 2; i
<= p
/2; i
++)
for (i
= 0x100; i
!= 0; i
<<= 8)
if (i
% p
<= SMALL
|| i
% p
> p
- SMALL
)
dictionary::dictionary(int n
) : threshold(0.5), factor(1.5), used(0), size(n
)
table
= new association
[n
];
for (int i
= 0; i
< n
; i
++)
// see Knuth, Sorting and Searching, p518, Algorithm L
// we can't use double-hashing because we want a remove function
void *dictionary::lookup(symbol s
, void *v
)
for (int i
= s
.hash() % size
;
i
== 0 ? i
= size
- 1: --i
)
if ((double)used
/(double)size
>= threshold
|| used
+ 1 >= size
) {
while (!is_good_size(size
))
association
*old_table
= table
;
table
= new association
[size
];
for (i
= 0; i
< old_size
; i
++)
(void)lookup(old_table
[i
].s
, old_table
[i
].v
);
void *dictionary::lookup(const char *p
)
symbol
s(p
, MUST_ALREADY_EXIST
);
// see Knuth, Sorting and Searching, p527, Algorithm R
void *dictionary::remove(symbol s
)
// this relies on the fact that we are using linear probing
for (int i
= s
.hash() % size
;
table
[i
].v
!= 0 && s
!= table
[i
].s
;
i
== 0 ? i
= size
- 1: --i
)
while (table
[i
].v
!= 0) {
r
= table
[i
].s
.hash() % size
;
} while ((i
<= r
&& r
< j
) || (j
< i
&& i
<= r
));
dictionary_iterator::dictionary_iterator(dictionary
&d
) : dict(&d
), i(0)
int dictionary_iterator::get(symbol
*sp
, void **vp
)
for (; i
< dict
->size
; i
++)
object_dictionary_iterator::object_dictionary_iterator(object_dictionary
&od
)
object::object() : rcount(0)
void object::add_reference()
void object::remove_reference()
object_dictionary::object_dictionary(int n
) : d(n
)
object
*object_dictionary::lookup(symbol nm
)
return (object
*)d
.lookup(nm
);
void object_dictionary::define(symbol nm
, object
*obj
)
obj
= (object
*)d
.lookup(nm
, obj
);
void object_dictionary::rename(symbol oldnm
, symbol newnm
)
object
*obj
= (object
*)d
.remove(oldnm
);
obj
= (object
*)d
.lookup(newnm
, obj
);
void object_dictionary::remove(symbol nm
)
object
*obj
= (object
*)d
.remove(nm
);
// Return non-zero if oldnm was defined.
int object_dictionary::alias(symbol newnm
, symbol oldnm
)
object
*obj
= (object
*)d
.lookup(oldnm
);
obj
= (object
*)d
.lookup(newnm
, obj
);