Adding upstream version 1.23.0.upstream/1.23.0upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 209 insertions, 0 deletions

diff --git a/src/roff/troff/dictionary.cpp b/src/roff/troff/dictionary.cpp
new file mode 100644
index 0000000..08afbd3
--- /dev/null
+++ b/src/roff/troff/dictionary.cpp
@@ -0,0 +1,209 @@
+// -*- C++ -*-
+/* Copyright (C) 1989-2020 Free Software Foundation, Inc.
+     Written by James Clark (jjc@jclark.com)
+
+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 3 of the License, or
+(at your option) any later version.
+
+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
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program.  If not, see <http://www.gnu.org/licenses/>. */
+
+
+#include "troff.h"
+#include "dictionary.h"
+
+// is 'p' a good size for a hash table
+
+static int is_good_size(unsigned int p)
+{
+  const unsigned int SMALL = 10;
+  unsigned int i;
+  for (i = 2; i <= p/2; i++)
+    if (p % i == 0)
+      return 0;
+  for (i = 0x100; i != 0; i <<= 8)
+    if (i % p <= SMALL || i % p > p - SMALL)
+      return 0;
+  return 1;
+}
+
+dictionary::dictionary(int n) : size(n), used(0), threshold(0.5), factor(1.5)
+{
+  table = new association[n];
+}
+
+// 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)
+{
+  int i;
+  for (i = int(s.hash() % size); 
+       table[i].v != 0;
+       i == 0 ? i = size - 1: --i)
+    if (s == table[i].s) {
+      if (v != 0) {
+	void *temp = table[i].v;
+	table[i].v = v;
+	return temp;
+      }
+      else
+	return table[i].v;
+    }
+  if (v == 0)
+    return 0;
+  ++used;
+  table[i].v = v;
+  table[i].s = s;
+  if ((double)used/(double)size >= threshold || used + 1 >= size) {
+    int old_size = size;
+    size = int(size*factor);
+    while (!is_good_size(size))
+      ++size;
+    association *old_table = table;
+    table = new association[size];
+    used = 0;
+    for (i = 0; i < old_size; i++)
+      if (old_table[i].v != 0)
+	(void)lookup(old_table[i].s, old_table[i].v);
+    delete[] old_table;
+  }
+  return 0;
+}
+
+void *dictionary::lookup(const char *p)
+{
+  symbol s(p, MUST_ALREADY_EXIST);
+  if (s.is_null())
+    return 0;
+  else
+    return lookup(s);
+}
+
+// see Knuth, Sorting and Searching, p527, Algorithm R
+  
+void *dictionary::remove(symbol s)
+{
+  // this relies on the fact that we are using linear probing
+  int i;
+  for (i = int(s.hash() % size);
+       table[i].v != 0 && s != table[i].s;
+       i == 0 ? i = size - 1: --i)
+    ;
+  void *p = table[i].v;
+  while (table[i].v != 0) {
+    table[i].v = 0;
+    int j = i;
+    int r;
+    do {
+      --i;
+      if (i < 0)
+	i = size - 1;
+      if (table[i].v == 0)
+	break;
+      r = int(table[i].s.hash() % size);
+    } while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
+    table[j] = table[i];
+  }
+  if (p != 0)
+    --used;
+  return p;
+}
+
+dictionary_iterator::dictionary_iterator(dictionary &d) : dict(&d), i(0)
+{
+}
+
+int dictionary_iterator::get(symbol *sp, void **vp)
+{
+  for (; i < dict->size; i++)
+    if (dict->table[i].v) {
+      *sp = dict->table[i].s;
+      *vp = dict->table[i].v;
+      i++;
+      return 1;
+    }
+  return 0;
+}
+
+object_dictionary_iterator::object_dictionary_iterator(object_dictionary &od)
+: di(od.d)
+{
+}
+
+object::object() : rcount(0)
+{
+}
+
+object::~object()
+{
+}
+
+void object::add_reference()
+{
+  rcount += 1;
+}
+
+void object::remove_reference()
+{
+  if (--rcount == 0)
+    delete this;
+}
+
+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->add_reference();
+  obj = (object *)d.lookup(nm, obj);
+  if (obj)
+    obj->remove_reference();
+}
+
+void object_dictionary::rename(symbol oldnm, symbol newnm)
+{
+  object *obj = (object *)d.remove(oldnm);
+  if (obj) {
+    obj = (object *)d.lookup(newnm, obj);
+    if (obj)
+      obj->remove_reference();
+  }
+}
+
+void object_dictionary::remove(symbol nm)
+{
+  object *obj = (object *)d.remove(nm);
+  if (obj)
+    obj->remove_reference();
+}
+
+// Return non-zero if oldnm was defined.
+
+int object_dictionary::alias(symbol newnm, symbol oldnm)
+{
+  object *obj = (object *)d.lookup(oldnm);
+  if (obj) {
+    obj->add_reference();
+    obj = (object *)d.lookup(newnm, obj);
+    if (obj)
+      obj->remove_reference();
+    return 1;
+  }
+  return 0;
+}