// Memoizer.h -- caches of objects referenced from Jitter
//
// Author: Ian.Piumarta@INRIA.Fr
//
// Last edited: 2000-11-09 15:18:02 by piumarta on emilia.rd.wdi.disney.com


#ifndef _j_Memoizer_h
#define _j_Memoizer_h

#include <stdio.h>
#include <stdlib.h>

#include "Object.h"
#include "xmalloc.h"


// the following pollution appears to come from sysmacros.h
#undef major
#undef minor


// memoizers are indexed by major and minor indices


class MemoIndex
{
private:
  // this used to be two packed unsigned shorts, which egcs managed easily to
  // optimise into something entirely equivalent to the following.  making
  // the packing implicit inside a single unsigned long is for the benefit of
  // lesser compilers, which sometimes seem to have trouble with the concept.
  unsigned long maj_min;

public:
  MemoIndex(unsigned short maj, unsigned short min)
    : maj_min((unsigned long)((maj << 16) | min))
    {
      assert(maj < 4096);
    }

  MemoIndex(unsigned long majmin= 0)
    : maj_min(majmin)
    {
      assert(major() < 4096);
    }

  unsigned int major(void) const { return maj_min >> 16; }
  unsigned int minor(void) const { return maj_min & 0xffff; }

  inline size_t hash(void) const
    {
      return (major() << 2) ^ minor();
    }

  inline bool operator==(const MemoIndex &other) const {
    return maj_min == other.maj_min;
  }

  inline bool operator!=(const MemoIndex &other) const {
    return !operator==(other);
  }

  unsigned long asLong(void) const { return maj_min; }

  char *printString(void)
    {
      static char bufs[4][16];
      static int bidx= 0;
      char *buf= bufs[bidx++ % 4];
      sprintf(buf, "<%04d,%02d>", major(), minor());
      return buf;
    }
};


// In-heap memoizers, subject to GC remapping.
// 
// Note: object hashes are 12 bits wide, so it's pointless trying to
// use a memoizer with more than 4096 buckets.


template <class elt_t>
class Memoizer : public Array
{
protected:
  friend class NativeMemoizer;
  static const size_t BucketCount= 4096; // MUST be power of 2!
  static const size_t BucketSize=  4;

public:
  inline void *operator new(size_t ignored)
    {
      return (void *)Object::allocate(ClassArray, BucketCount);
    }

  inline void operator delete(void *) {}

public:
  Memoizer(const char *type)
    {
      PRINTF(("0x%08x allocate %sMemoizer\n", (int)this, type));
      assert(wordLength() == BucketCount);
      assert(okayFields());
      assert(at(0)->isNil());
      assert(at(BucketCount - 1)->isNil());
    }

  ~Memoizer(void)
    {
      PRINTF(("0x%08x release Memoizer\n", (int)this));
    }

#if 1
  inline bool includes(elt_t *elt) const {
    const unsigned int hash= elt->_hashBits() & (BucketCount - 1);
    assert(hash < BucketCount);
    const Array *bucket= at(hash)->asArray();
    if (bucket->notNil())
      {
	const int size= bucket->wordLength();
	for (int i= 0; i < size; ++i)
	  if (bucket->at(i) == elt) return true;
      }
    return false;
  }
#endif

  inline elt_t *elementAt(MemoIndex index)
    {
      assert(index.major() < BucketCount);
      Array *bucket= at(index.major())->asArray();
      assert(bucket->isArray());
      assert(index.minor() < bucket->wordLength());
      return (elt_t *)(bucket->at(index.minor()));
    }

  // answer the index of elt, adding to the memoizer if necessary

  MemoIndex indexOf(elt_t *elt)
    {
      const unsigned int hash= elt->_hashBits() & (BucketCount - 1);
      assert(hash < BucketCount);
      assert(isArray());
      assert(wordLength() == BucketCount);
      Array *bucket= at(hash)->asArray();
      assert(bucket->isNil() || bucket->isArray());
      if (bucket->notNil())
	{
	  assert(bucket->isArray());
	  const int size= bucket->wordLength();
	  {
	    for (int i= 0; i < size; ++i)
	      {
		const oop probe= bucket->at(i);
		if (probe == elt)
		  return MemoIndex(hash, i);
		if (probe->isNil())
		  {
		    bucket->checkStore(bucket->atPut(i, elt));
		    assert(bucket->okayFields());
		    return MemoIndex(hash, i);
		  }
	      }
	  }
	  // bucket is full: grow it
	  pushRemappableOop(bucket);
	  pushRemappableOop(this);
	  pushRemappableOop(elt);
	  Array *newBucket= Object::allocate(ClassArray, size * 2)->asArray();
	  elt= (elt_t *)popRemappableOop();
	  Array *self= popRemappable(Array);
	  bucket= popRemappable(Array);
	  // assume newBucket is a new object: can use unchecked stores
	  {
	    for (int i= 0; i < size; ++i)
	      newBucket->checkStore(newBucket->atPut(i, bucket->at(i)));
	  }
	  newBucket->checkStore(newBucket->atPut(size, elt));
	  assert(newBucket->okayFields());
	  self->checkStore(self->atPut(hash, newBucket));
	  assert(self->okayFields());
	  newBucket->beRoot();	// PARANOIA
	  return MemoIndex(hash, size);
	}
      // no bucket: create one
      pushRemappableOop(this);
      pushRemappableOop(elt);
      Array *newBucket= Object::allocate(ClassArray, BucketSize)->asArray();
      elt= (elt_t *)popRemappableOop();
      Array *self= popRemappable(Array);
      self->checkStore(self->atPut(hash, newBucket));
      // assume newBucket is a new object: can use unchecked stores
      newBucket->checkStore(newBucket->atPut(0, elt));
      newBucket->beRoot();	// PARANOIA
      assert(newBucket->okayFields());
      assert(self->okayFields());
      return MemoIndex(hash, 0);
    }

  size_t printStatsOn(char *buf)
    {
      size_t nBuckets= 0, nEntries= 0, nBytes= 0;
      for (size_t i= 0; i < BucketCount; ++i)
	{
	  if (at(i)->notNil())
	    {
	      assert(at(i)->isArray());
	      Array *bucket= at(i)->asArray();
	      size_t len= bucket->wordLength();
	      ++nBuckets;
	      nBytes+= (1 + len) * sizeof(oop);
	      for (size_t j= 0; j < len; ++j)
		{
		  if (bucket->at(j)->isNil()) break;
		  ++nEntries;
		}
	    }
	}
      buf+= sprintf(buf, "%5d bkts,%8d byts,%6d ents,%5.1f ents/bkt,%6.1f%% coverage",
		    nBuckets, nBytes, nEntries, (float)nEntries/(float)nBuckets,
		    percent(nBuckets, BucketCount));
      return nBytes + sizeof(Array) + BucketCount * sizeof(oop);
    }

  bool okayMemoizer(void)
    {
#     ifdef NDEBUG
      fatal("NDEBUG is defined");
#     endif
      okayFields();
      size_t nBuckets= 0, nEntries= 0, nBytes= 0;
      oop proto= nilObj;
      for (size_t i= 0; i < BucketCount; ++i)
	{
	  if (at(i)->notNil())
	    {
	      at(i)->okayFields();
	      assert(at(i)->isArray());
	      Array *bucket= at(i)->asArray();
	      size_t len= bucket->wordLength();
	      for (size_t j= 0; j < len; ++j)
		{
		  if (bucket->at(j)->notNil())
		    {
		      at(j)->okayFields();
		      if (proto->notNil())
			assert(at(j)->fetchClass() == proto->fetchClass());
		      else
			proto= at(j);
		    }
		}
	    }
	}
      return true;
    }

}; // class Memoizer<elt_t>


class ClassMemoizer : public Memoizer<Class>
{
public:
  ClassMemoizer(void) : Memoizer<Class>("class") {}
};


class MethodMemoizer : public Memoizer<CompiledMethod>
{
public:
  MethodMemoizer(void) : Memoizer<CompiledMethod>("method") {}
};


class SelectorMemoizer : public Memoizer<Symbol>
{
public:
  SelectorMemoizer(void) : Memoizer<Symbol>("selector") {}
};


// translated code is also memoized, but outside the heap.
// analagous implementation, using malloc() instead of Object::alloc().
// 
// to go from a NativeMethod to the original CompiledMethod, use
// something like this:
// 
//	CM *cMeth= methodMemoizer->at(nMeth->index);
// 
// to translate a method on demand, use something like this:
// 
//	register MemoIndex index= methodMemoizer->indexOf(cMeth);
//	NM *nMeth= nativeMemoizer->atOrNil(index);
//	if (nMeth == 0) {
//	  nativeMemoizer->atPut(index, (nMeth= translate(cMeth)));
//	  nMeth->index= index;
//	}
// 
// to go from a CompiledMethod to an existing NativeMethod, use
// something like this:
// 
//	NM *nMeth= nativeMemoizer->at(methodMemoizer->indexOf(cMeth))
// 
// (be sure to admire how the C++ compiler elides the index entirely ;-)


class CodeBucket
{
  size_t size;
  NativeMethod **bucket;
public:
  CodeBucket(void) : size(0), bucket(0) {}

  ~CodeBucket(void)
    {
      if (bucket != 0)
	{
	  free(bucket);
	  bucket= 0;
	}
    }

  inline NativeMethod *at(unsigned short index) const
    {
      assert(index < size);
      assert(bucket[index] != 0);
      return bucket[index];
    }

  inline NativeMethod *atOrNil(unsigned short index) const
    {
      if (index < size) return bucket[index];
      return 0;
    }

  void atPut(size_t index, NativeMethod *nMeth)
    {
      assert(nMeth != 0);
      if (size == 0)
	{
	  for (size= 1; size <= index; size*= 2);
	  bucket= (NativeMethod **)calloc(size, sizeof(NativeMethod *));
	  if (bucket == 0) fatal("out of memory");
	  PRINTF(("codeCache: new bucket at %p + %d\n", bucket, size));
	}
      else if (index >= size)
	{
	  size_t newSize= size;
	  while (newSize <= index) newSize*= 2;
	  bucket= (NativeMethod **)
	    realloc(bucket, newSize * sizeof(NativeMethod *));
	  if (bucket == 0)
	    fatal("out of memory");
	  for (size_t i= size; i < newSize; ++i)
	    bucket[i]= 0;
	  size= newSize;
	  PRINTF(("codeCache: grow bucket at %p + %d\n", bucket, size));
	}
      bucket[index]= nMeth;
    }

  void flush(size_t index)
    {
      assert(index < size);
      bucket[index]= 0;
    }
};


class NativeMemoizer
{
  static const size_t BucketCount= MethodMemoizer::BucketCount;

public:
  CodeBucket buckets[BucketCount];	// NOTE: static allocation

  NativeMemoizer(void)
    {
      PRINTF(("0x%08x allocate nativeMemoizer\n", (int)this));
    }

  ~NativeMemoizer(void)
    {
      PRINTF(("0x%08x release nativeMemoizer\n", (int)this));
    }

  inline NativeMethod *at(MemoIndex index) const
    {
      assert(index.major() < BucketCount);
      return buckets[index.major()].at(index.minor());
    }

  inline NativeMethod *atOrNil(MemoIndex index) const
    {
      assert(index.major() < BucketCount);
      return buckets[index.major()].atOrNil(index.minor());
    }

  inline void atPut(MemoIndex index, NativeMethod *nMeth)
    {
      assert(index.major() < BucketCount);
      buckets[index.major()].atPut(index.minor(), nMeth);
    }

  inline void flush(MemoIndex index)
    {
      assert(index.major() < BucketCount);
      buckets[index.major()].flush(index.minor());
    }
};


extern ClassMemoizer    *classMemoizer;
extern SelectorMemoizer *selectorMemoizer;
extern MethodMemoizer   *methodMemoizer;
extern NativeMemoizer   *nativeMemoizer;


#endif // _j_Memoizer_h
