bug-gmp
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

GMP ref count


From: Hans Aberg
Subject: GMP ref count
Date: Fri, 27 Apr 2001 14:14:16 +0200

I made an version of the gpm::integer class with a ref count in it, which I
attach, in case somebody wants to experiment with it. This is the
traditional ref count variation, with a double memory allocation, one for
the ref count object, and one for the _mp_d object. (The C++ class
std::string may have a similar ref count on some compilers.)

I made a template class ref<A> that produces a reference to an object of
class A, based on a reference count then.

Then, it turns out that the simplest way to handle this is to have a class
A which has a proper C++ destructor ~A(); as the type mpz_t does not have
it, I made a class mpz which provides a destructor. It's default
constructor mpz() does not initialize the mpz_t value, because that is done
from the integer class.

The class mpz also has a copy constructor mpz::mpz(const mpz&), which is
needed for the ref<A>::ptr::clone() operator. The latter is needed when
performing a mutative operation on an A, as an ref<A> object may have
several other objects looking on it. If an object is about to be mutated,
one simply throws in a detach() before that mutation, which removes it from
the reference cluster, and produces an independent clone if needed.

There are several different variations on this reference count thing. For
example, in this version the code
  integer r;
  mpz_add(r.value(), x.value(), y.value());
  return r;
the first line "integer r;" will allocate the _mp_d pointer which then may
have to be change by the mpz_add operation. One other variation is that
integer() sets merely a null pointer, which later is allocated at need. One
then ends up with having checks for a null pointer everywhere. On the other
hand, a single memory allocation may take up several tens of cycles, so
this might still be faster.

Also, the code looks as though a lot of function calls will be produced,
but a good compiler will be able to inline them away. (But then debugging
becomes harder.)

-- File gmp -----------------------------------------------------

#ifndef header_gmp
#define header_gmp

#include <iostream>
#include <string>

#include "gmp.h"
#include "gmp-impl.h"


namespace gmp {


typedef int relate;

const relate unrelated = -2;
const relate less = -1;
const relate equal = 0;
const relate greater = 1;

template<class A> // The sign of a number:
inline int sgn(A x) { return (x > 0) - (x < 0); }

inline bool less_equal(relate r) { return r == less || r == equal; }
inline bool greater_equal(relate r) { return r == greater || r == equal; }


class rational;
class floating;


template<class A>
class ref {
  class ptr {
  public:
    A data_;
    mutable unsigned count_;

    ptr() : count_(1) { }
    ~ptr() { }

    ptr* clone() const { return new ptr(*this); }
    ptr* copy() const { ++count_; return const_cast<ptr*>(this); }
    void shed() const { if (--count_ == 0)  delete this; }
  };

  ptr* ptr_;

  ptr* copy() const { return ptr_->copy(); }
  void shed() const { ptr_->shed(); }

public:
  ref() : ptr_(new ptr()) { }
  ~ref() { shed(); }

  ref(const ref& x) : ptr_(x.copy()) { }
  ref& operator=(const ref& x) {
    if (ptr_ != x.ptr_) { shed(); ptr_ = x.copy(); }
    return *this;
  }

  ref(const A& a) : ptr_(new ptr(A)) { }

  void detach() { if (ptr_->count_ > 1) { shed(); ptr_ = ptr_->clone(); } }

  A& data() { return ptr_->data_; }
  const A& data() const { return ptr_->data_; }
};


class mpz {
  mpz_t value_;
public:
  mpz() { } // Note: Not initialized. Must be initialzed by
  ~mpz() { mpz_clear(value_); }

  // The copy constructor and assignment functions are in reality never called:
  mpz(const mpz& x) { mpz_init_set(value_, x.value_); }
  mpz& operator=(const mpz& x) { mpz_set(value_, x.value_); return *this; }

  mpz_t& data() { return value_; }
  const mpz_t& data() const { return value_; }
};


class integer {
public:
  ref<mpz> value_;
  mpz_t& value() { return value_.data().data(); }
  const mpz_t& value() const { return value_.data().data(); }
  void detach() { value_.detach(); }

public:
  integer() { mpz_init(value()); }
  ~integer() { }

  integer(unsigned long int x) { mpz_init_set_ui(value(), x); }
  integer(signed long int x) { mpz_init_set_si(value(), x); }
  integer(double x) { mpz_init_set_d(value(), x); }
  integer(const char* str, int base = 0) { mpz_init_set_str(value(), str,
base); }
  // Make explicit functions, instead of type conversions:
  // integer(const rational& x) { mpz_init_set_q(value(), x); }
  // integer(const floating& x) { mpz_init_set_f(value(), x); }

  integer& operator=(unsigned long int x) { detach(); mpz_set_ui(value(),
x); return *this; }
  integer& operator=(signed long int x) { detach(); mpz_set_si(value(), x);
return *this; }
  integer& operator=(double x) { detach(); mpz_set_d(value(), x); return
*this; }
  integer& operator=(const char* str) { detach(); mpz_set_str(value(), str,
0); return *this; }

  double get_d() const { return mpz_get_d(value()); }
  signed long int get_si() const { return mpz_get_si(value()); }
  unsigned long int get_ui() const { return mpz_get_ui(value()); }
  std::string str(int base = 10) const {
    char* cs = new char[mpz_sizeinbase(value(), base) + 2];
    mpz_get_str(cs, base, value());
    std::string str_r(cs); delete[] cs;
    return str_r;
  }

  relate compare(const integer& x) const { return sgn(mpz_cmp(value(),
x.value())); }

  void swap(integer& x) { detach(); x.detach(); mpz_swap(value(), x.value()); }

  size_t read(std::istream&, int base = 0);

  friend integer operator+(const integer&, const integer&);
  friend integer operator-(const integer&);
  friend integer operator-(const integer&, const integer&);
  friend integer operator*(const integer&, const integer&);

  friend bool operator<(const integer&, const integer&);
  friend bool operator<=(const integer&, const integer&);
  friend bool operator==(const integer&, const integer&);
  friend bool operator!=(const integer&, const integer&);
  friend bool operator>(const integer&, const integer&);
  friend bool operator>=(const integer&, const integer&);


  friend integer abs(const integer&); // Absolute value.

  friend std::istream& operator>>(std::istream&, integer&);
  friend std::ostream& operator<<(std::ostream&, const integer&);
};


inline integer operator+(const integer& x, const integer& y) {
  integer r;  mpz_add(r.value(), x.value(), y.value());  return r;
}

inline integer operator-(const integer& x) {
  integer r;  mpz_neg(r.value(), x.value());  return r;
}

inline integer operator-(const integer& x, const integer& y) {
  integer r;  mpz_sub(r.value(), x.value(), y.value());  return r;
}

inline integer operator*(const integer& x, const integer& y) {
  integer r;  mpz_mul(r.value(), x.value(), y.value());  return r;
}

inline bool operator<(const integer& x, const integer& y)
{  return x.compare(y) == less;  }

inline bool operator<=(const integer& x, const integer& y)
{  return less_equal(x.compare(y));  }

inline bool operator==(const integer& x, const integer& y)
{  return x.compare(y) == equal;  }

inline bool operator!=(const integer& x, const integer& y)
{  return x.compare(y) != equal;  }

inline bool operator>(const integer& x, const integer& y)
{  return x.compare(y) == greater;  }

inline bool operator>=(const integer& x, const integer& y)
{  return greater_equal(x.compare(y));  }


inline integer abs(const integer& x) {
  integer r;  mpz_abs(r.value(), x.value());  return r;
}


inline std::istream& operator>>(std::istream& is, integer& x) {
  x.read(is);  return is;
}

inline std::ostream& operator<<(std::ostream& os, const integer& n) {
  return os << n.str();
}


} // namespace gmp

#endif // header_gmp


-- File gmp.cc ---------------------------------------------------------

#include "gmp"


namespace gmp {


  // Class integer:
static int digit_value_in_base(int c, int base) {
  int digit;

  if (isdigit(c))
    digit = c - '0';
  else if (islower(c))
    digit = c - 'a' + 10;
  else if (isupper(c))
    digit = c - 'A' + 10;
  else
    return -1;

  if (digit < base)
    return digit;
  return -1;
}


size_t integer::read(std::istream& stream, int base) {
  detach(); // Remove *this from reference cluster.
  mpz_ptr x = value();
  char *str;
  size_t alloc_size, str_size;
  int c;
  int negative;
  mp_size_t xsize;
  size_t nread;

  nread = 0;

  /* Skip whitespace.  */
  do
    {
      c = stream.get();
      nread++;
    }
  while (isspace(c));

  negative = 0;
  if (c == '-')
    {
      negative = 1;
      c = stream.get();
      nread++;
    }

  if (digit_value_in_base (c, base == 0 ? 10 : base) < 0)
    return 0;     /* error if no digits */

  /* If BASE is 0, try to find out the base by looking at the initial
     characters.  */
  if (base == 0)
    {
      base = 10;
      if (c == '0')
  {
    base = 8;
    c = stream.get();
    nread++;
    if (c == 'x' || c == 'X')
      {
        base = 16;
        c = stream.get();
        nread++;
      }
    else if (c == 'b' || c == 'B')
      {
        base = 2;
        c = stream.get();
        nread++;
      }
  }
    }

  /* Skip leading zeros.  */
  while (c == '0')
    {
      c = stream.get();
      nread++;
    }

  alloc_size = 100;
  str = (char *) (*_mp_allocate_func) (alloc_size);
  str_size = 0;

  for (;;)
    {
      int dig;
      if (str_size >= alloc_size)
  {
    size_t old_alloc_size = alloc_size;
    alloc_size = alloc_size * 3 / 2;
    str = (char *) (*_mp_reallocate_func) (str, old_alloc_size, alloc_size);
  }
      dig = digit_value_in_base (c, base);
      if (dig < 0)
  break;
      str[str_size++] = dig;
      c = stream.get();
    }

  stream.unget();

  /* Make sure the string is not empty, mpn_set_str would fail.  */
  if (str_size == 0)
    {
      x->_mp_size = 0;
      (*_mp_free_func) (str, alloc_size);
      return nread;
    }

  xsize = (((mp_size_t) (str_size / __mp_bases[base].chars_per_bit_exactly))
     / BITS_PER_MP_LIMB + 2);
  if (x->_mp_alloc < xsize)
    _mpz_realloc (x, xsize);

  /* Convert the byte array in base BASE to our bignum format.  */
  xsize = mpn_set_str (x->_mp_d, (unsigned char *) str, str_size, base);
  x->_mp_size = negative ? -xsize : xsize;

  (*_mp_free_func) (str, alloc_size);
  return str_size + nread;
}


} // namespace gmp


----------------------------------------------------------------------



  Hans Aberg





reply via email to

[Prev in Thread] Current Thread [Next in Thread]