/************************************************************************
*
*  The MEMO Package
*
*  There are two files,
*
*  	memo.h contains the declarations needed to access the memo
*  		package.
*
*  	memo.c contains the routines in the memo package.
*
*  The datatypes and routines provided by the package are as follows:
*
*  typedef ???? * MEMO;
*  	a MEMO is a pointer to a block of dynamic storage somewhere.
*
*************************************************************************
* Released to the public domain by its author, Thomas W. Christopher. 
*
* Since this program is in the public domain, it may be copied and
* used without restriction. The author makes no warranties of
* any kind as to the correctness of this material or its 
* suitability for any application. The responsibility for the
* use of this program lies entirely with the user.
*************************************************************************/
#define SGI
#include "memo.h"
#include <stdio.h>
#define NULL 0

#define TABLESIZE 809

#define RUNNING 0
#define GETTING 1 /* executing get or alt */
#define LOOKING 2 /* executing get_copy */
#define WAKING  3 /* being awakened from a wait (by memo_write) */

/************************************************************************
	State Transitions
	-----------------
RUNNING -> GETTING
	Executed by: Self
	At beginning of memo_get, _get_skip, _alt, _alt_skip
	Unconditionally

GETTING -> RUNNING
	Executed by: Self
	In enqueue_get.
	If a memo is found in the folder.

GETTING -> WAKING
	Executed by: Another process, awakening this.
	In do_write.
	If a memo is being written and this is the first process on
the g_queue with its state == GETTING.

WAKING -> RUNNING
	Executed by: Self
	In memo_get, _get_skip, _alt, _alt_skip after waiting upon a
semaphore and being signaled by some other process. That process
changed this process's state from GETTING or LOOKING to WAKING,
placed a pointer to a memo in this process's "delivered" member
and signaled the semaphore.
	Unconditionally upon waking up.

RUNNING -> LOOKING
	Executed by: Self
	At beginning of memo_get_copy.
	Unconditionally.

LOOKING -> RUNNING
	Executed by: Self
	In enqueue_get.
	If a memo is found in the folder.

LOOKING -> WAKING
	Executed by: Another process, awakening this.
	In do_write.
	If a memo is being written and this process is on
the g_queue with its state == LOOKING.

***********************************************************************/

#define BUCKET_OF(_H_) ((_H_)%TABLESIZE)
	/*BUCKET_OF must be used by both (UN)LOCK_TBL and lookup()*/
	/*Two keys that hash into the same bucket MUST lock the same lock*/


#ifdef SGI
#define PARALLEL
#include <sys/types.h>
#include <sys/times.h>
#include <unistd.h>
#include <ulocks.h>

usptr_t *shared_heap = 0;
static struct tms times_buffer;

int share_malloc_init(size_t size)
{
 usconfig(CONF_INITSIZE,size);
 shared_heap = usinit("/dev/zero");
}

int proc_fork_my_id, proc_fork_num;

int proc_fork(num)
{
 pid_t i;
 proc_fork_num = num;
 for (	proc_fork_my_id = num-1;
 	proc_fork_my_id > 0;
 	proc_fork_my_id--) {
 		i = fork();
 		if(i==0) {
 			if (shared_heap != 0) usadd(shared_heap);
 			return proc_fork_my_id;
 		}
 }
 return 0;
}

void proc_join()
{
 int n;
 if (proc_fork_my_id>0) exit(0);
 for (n = proc_fork_num-1; n>0; n--) {
 	wait(NULL);
 }
}


#define spin_lock(_L_) uspsema(*(_L_))
#define spin_unlock(_L_) usvsema(*(_L_))

#define SHARE_MEM_SIZE 1000000
#define SYS_LOCK SEMA4
#define LOCK_TBL(_HASH_) spin_lock(&sys->sys_lock[BUCKET_OF(_HASH_)])
#define UNLOCK_TBL(_HASH_) spin_unlock(&sys->sys_lock[BUCKET_OF(_HASH_)])
#define LOCK_PCB(_PCB_) spin_lock(&_PCB_->lock)
#define UNLOCK_PCB(_PCB_) spin_unlock(&_PCB_->lock)
#define INIT_LOCK(_L_) (_L_)=usnewsema(shared_heap,1)
#define INIT_SYS_LOCKS \
	{int i; for(i=0;i<TABLESIZE;i++) \
		INIT_LOCK(sys->sys_lock[i]); \
	}

typedef usema_t* SEMA4;
#define INIT_SEMA4(_S_,_C_) \
	{*(_S_) = usnewsema(shared_heap,_C_);}
#define WAIT_SEMA4(_S_) uspsema(*(_S_))
#define SIGNAL_SEMA4(_S_) usvsema(*(_S_))

#define PROC_FORK(_NUM_) proc_fork(_NUM_)
#define PROC_JOIN() proc_join()

#define SHARE_MALLOC_INIT(_SZ_) share_malloc_init(_SZ_)
#define SHARE_MALLOC(_SZ_) usmalloc(_SZ_,shared_heap)
#define SHARE_FREE(_PTR_) usfree(_PTR_,shared_heap)

#define INIT_TIMER
#define RAW_TIME times(&times_buffer)
#endif

#ifdef ENCORE
#define PARALLEL
#include <parallel.h>
#define SHARE_MEM_SIZE 1000000
#define SYS_LOCK LOCK /*type of system lock: LOCK or SEMAPHORE*/
#define LOCK_TBL(_HASH_) spin_lock(&sys->sys_lock[BUCKET_OF(_HASH_)])
#define UNLOCK_TBL(_HASH_) spin_unlock(&sys->sys_lock[BUCKET_OF(_HASH_)])
#define LOCK_PCB(_PCB_) spin_lock(&_PCB_->lock)
#define UNLOCK_PCB(_PCB_) spin_unlock(&_PCB_->lock)
#define INIT_LOCK(_L_) spin_init(_L_,PAR_UNLOCKED)
#define INIT_SYS_LOCKS \
	{int i; for(i=0;i<TABLESIZE;i++) \
		INIT_LOCK(&sys->sys_lock[i]); \
	}

#define SEMA4 SEMAPHORE
#define INIT_SEMA4(_S_,_C_) \
	{semaphore_init(_S_,PROCESS_BLOCK); \
	semaphore_set(_S_,_C_);}
#define WAIT_SEMA4(_S_) semaphore_wait(_S_)
#define SIGNAL_SEMA4(_S_) semaphore_signal(_S_)

#define PROC_FORK(_NUM_) proc_fork(_NUM_)
#define PROC_JOIN() proc_join()

#define SHARE_MALLOC_INIT(_SZ_) share_malloc_init(_SZ_)
#define SHARE_MALLOC(_SZ_) share_malloc(_SZ_)
#define SHARE_FREE(_PTR_) share_free(_PTR_)

unsigned int *timer_pointer;
#define INIT_TIMER 	timer_pointer = timer_init();
#define RAW_TIME *timer_pointer
#endif

#ifndef PARALLEL
#define SYS_LOCK char
#define LOCK_TBL(_HASH_)
#define UNLOCK_TBL(_HASH_)
#define LOCK_PCB(_PCB_)
#define UNLOCK_PCB(_PCB_)
#define INIT_LOCK(_L_)
#define INIT_SYS_LOCKS

#define SEMA4 int
#define INIT_SEMA4(_S_,_C_)
#define WAIT_SEMA4(_S_)
#define SIGNAL_SEMA4(_S_)

#define PROC_FORK(_NUM_) 0
#define PROC_JOIN()

#define SHARE_MALLOC_INIT(_SZ_)
#define SHARE_MALLOC(_SZ_) malloc(_SZ_)
#define SHARE_FREE(_PTR_) free(_PTR_)

#define INIT_TIMER
#define RAW_TIME clock()
#endif


typedef struct MEMO_hdr {
	FOLDER_NAME key;
	struct MEMO_hdr *next;
	int len;
	} *MEMO_PTR;

typedef struct PCB_struct {
	int state, my_id;
	MEMO_PTR delivered;
	int which;
#ifdef PARALLEL
	SYS_LOCK lock;
	SEMA4 wait;
#endif
	struct GET_struct *get_chain;
	struct PCB_struct *wake_chain;
	} *PCB;

typedef struct GET_struct {
	FOLDER_NAME key;
	int which;
	unsigned long hash;
	PCB process;
	struct GET_struct *next, *alternate;
	} *GET;

typedef struct folder_struct {
	FOLDER_NAME  key;
	unsigned long hash;
	MEMO_PTR m_hd, m_tl; /*memos*/
	MEMO_PTR d_hd, d_tl; /*delayed memos*/
	GET g_hd, g_tl; /*pending gets*/
	struct folder_struct * next;
	} *FOLDER;

typedef struct {
	int num_workers, num_done;
#ifdef PARALLEL
	SYS_LOCK sys_lock[TABLESIZE];
#endif
	FOLDER table[TABLESIZE];
	} *SYS_CTL;

SYS_CTL sys=NULL;
PCB my_pcb;

MEMO_PTR delay_hd, delay_tl;

SYMBOL symbol_gen = 0x7fffff00;
unsigned long symbol_decr = 0x100;

/************************************************************************
*  	PCB_init(I)
*
*  PCB_init initializes the process control block for its caller.
*  I is the index of the process returned by PROC_FORK.
*
************************************************************************/
static void PCB_init(int I)
{
	my_pcb = (PCB) SHARE_MALLOC(sizeof(*my_pcb));
	my_pcb->state = RUNNING;
	my_pcb->my_id = I;
	my_pcb->delivered = NULL;
	INIT_LOCK(my_pcb->lock);
	my_pcb->which = -1;
	my_pcb->get_chain = NULL;
	my_pcb->wake_chain = NULL;
		/* safe, no one else will try to access this semaphore */
		/* until we try to get a memo: */
	INIT_SEMA4(&my_pcb->wait,0);
}

/************************************************************************
*  	memo_init()
*
*  Memo_init initializes the memo system.  (On the Encore,
*  memo_init calls SHARE_MALLOC_INIT.) The call should be first
*  in main().
*
************************************************************************/
void memo_init(void)
{
	int j;
	if (sys!=NULL) return; /*already executed*/
	SHARE_MALLOC_INIT(SHARE_MEM_SIZE);
	sys = (SYS_CTL) SHARE_MALLOC(sizeof(*sys));
	sys->num_workers = 0;
	for (j=TABLESIZE-1; j>=0; j--)
		sys->table[j] = NULL;
	INIT_SYS_LOCKS;
	delay_hd = delay_tl = NULL;
	PCB_init(0);
	INIT_TIMER
}

/************************************************************************
*  memo_exec(num_workers,argc,argv)
*  	int num_workers,argc;
*	char **argv;
*
*  This forks num_workers+1 processes. The main process, which executed
*  this procedure, is assigned the number 0 and executes the procedure
*  "boss(argc,argv)".  The worker processes are assigned the numbers
*  1 through num_workers and execute procedure "worker()".
*
************************************************************************/
void memo_exec(int num_workers,int argc,char **argv)
{                                              
	int I;
	sys->num_workers = num_workers;
	I = PROC_FORK(num_workers+1);
	if (I>0) {
		PCB_init(I);
		worker();
	} else {
		boss(argc,argv);
	}
	PROC_JOIN();
}

/************************************************************************
*  static unsigned long hash_key(key)
*  	FOLDER_NAME key;
*
*  	Compute the hash number of a folder name.
*
*  Uses a uniform random deviate generator as implemented by Ray Paden.
*
*     h[0] = a * key.S % m
*     h[n+1] = a*(h[n]^key.X[n]) % m
*
*	Each h ^ key.. is folded into the range 1..(2**31)-1.
*
*      Each h[i] is a long integer 1<=h[i]<=2*31-1.
*
*  where
*     a = 48271
*     m = 2**31-1
*  arithmetic is performed such that overflow will not occur.
*
************************************************************************/

#define AA 48271
#define MM 2147483647 /* i.e. 0x7fffffff */
#define QQ 44488
#define RR 3399

static unsigned long hash_key(FOLDER_NAME key)
{
  long h;
  int i;
	h = key.S;
	if (h<=0) h = MM + h;
	if (h<=0) h = MM + h;
	for (i=0; i<NUM_X; i++) {
		h ^= (unsigned) key.X[i];
		if (h<=0) h = MM + h;
		if (h<=0) h = MM + h;
		{long hi,lo,test;
		hi = h / QQ;
		lo = h % QQ;
		test = AA * lo - RR * hi;
		if (test > 0)
			h = test;
		else
			h = test + MM;
		}
	}
 return h;
}
#undef AA
#undef MM
#undef QQ
#undef RR

/************************************************************************
*  static MEMO_PTR copy_memo(m)
*  	MEMO_PTR m;
*
*  	Copy a memo (for memo_look).
************************************************************************/
static MEMO_PTR copy_memo(MEMO_PTR m)
{
	MEMO_PTR c;
	c = (MEMO_PTR) SHARE_MALLOC(sizeof(*m)+m->len);
	memcpy(c,m,sizeof(*m)+m->len);
	c->next =  NULL;
	c->key = (m->key);
	return c;
}

/************************************************************************
*  static keys_eq(key1,key2)
*  	FOLDER_NAME *key1,*key2;
*  Test two folder names for equality.
*  Returns:	1 if they are equal
*  			0 if they are not equal
************************************************************************/
static keys_eq(FOLDER_NAME *key1,FOLDER_NAME *key2)
{
  int i;
  if (key1->S != key2->S) return 0;
  for (i=0; i < NUM_X; i++)
  	if (key1->X[i] != key2->X[i]) return 0;
  return 1;
}

/************************************************************************
*  static FOLDER lookup(key,hash)
*  	FOLDER_NAME key;
*  	unsigned long hash;
*
*  	Given a key and its hash value, look up the folder that
*  contains it creating the folder if not already present.
*
*  Must be executed ONLY between LOCK_TBL and UNLOCK_TBL.
*
*  Lookup will try to free an empty folder. If it is the
*  folder being sought, then it will be used; otherwise it will be
*  removed. But a folder that is removed may be used for the new
*  folder if one is being inserted; it is only actually freed if it
*  isn't being sought, and the one being sought is present. For
*  speed, the test for the first folder being the one sought is
*  solely a comparison of the hash values, not the actual keys.
*  Very infrequently a folder may not be immediately deleted because
*  it has the same key as the one being sought.
*
************************************************************************/
static FOLDER lookup(FOLDER_NAME key, unsigned long hash)
{
  FOLDER *p,f,tmp;
  int b;
  tmp = NULL;
  b = BUCKET_OF(hash);
  p = &sys->table[b];
  f = *p;
  while (f != NULL) {
	if (	f->hash != hash &&
  			f->m_hd == NULL &&
  			f->d_hd == NULL &&
			f->g_hd == NULL) {
		if (tmp!=NULL) SHARE_FREE(tmp);
		tmp = f;
		*p = f->next;
		f = f->next;
	} else if (f->hash == hash && keys_eq(&key,&f->key) ) {
		/*found: move to front */
		*p = f->next;
		f->next = sys->table[b];
		sys->table[b] = f;
		if (tmp != NULL) SHARE_FREE(tmp);
		return f;
	} else {
		p = &f->next;
		f = f->next;
	}
  }
  /*not found*/
  if (tmp != NULL)
  	f = tmp;
  else
	f = (FOLDER) SHARE_MALLOC(sizeof(*f));
  f->next = sys->table[b];
  sys->table[b] = f;
  f->key = key;
  f->hash = hash;
  f->m_hd = f->m_tl = NULL;
  f->d_hd = f->d_tl = NULL;
  f->g_hd = f->g_tl = NULL;
  return f;
}

/************************************************************************
*  static GET build_get(key,which)
*  	FOLDER_NAME  key; int which;
*
*  	Given a key, create a GET structure to use in a get, alt, or
*	get_copy.
*
************************************************************************/
static GET build_get(FOLDER_NAME  key, int which)
{
  GET g;
  g = (GET) SHARE_MALLOC(sizeof(*g));
  g->key = key;
  g->hash = hash_key(key);
  g->process = my_pcb;
  g->which = which;
  g->next = g->alternate = NULL;
  return g;
}

/************************************************************************
*  static enqueue_get(g)
*  	GET g;
*
*  	Put a GET structure into the get queue of its folder. If
*  there is a memo waiting there and this process is marked as
*  GETTING or LOOKING, deliver the memo to this process and change
*  the process state to RUNNING.
*
*  Must NOT be executed between LOCK_TBL and UNLOCK_TBL.
*
************************************************************************/
static enqueue_get(GET g)
{
  FOLDER f;
  LOCK_TBL(g->hash);
  f = lookup(g->key,g->hash);
  /*enqueue Get structure in Folder's queue*/
  g->next = NULL;
  if (f->g_hd != NULL) {
  	f->g_tl->next = g;
	f->g_tl = g;
  } else {
  	f->g_hd = f->g_tl = g;
  }
  /* see if a memo is present */
  /* if so, I get it & set my state RUNNING */
  /* (RUNNING will mean don't wait on a semaphore, keep going)*/
  if (f->m_hd != NULL) {
  	LOCK_PCB(my_pcb);
  	switch (my_pcb->state) {
case GETTING:
		my_pcb->delivered = f->m_hd;
		my_pcb->which = g->which;
		f->m_hd = f->m_hd->next;
		my_pcb->delivered->next = NULL;
		my_pcb->state = RUNNING;
		break;
case LOOKING:
		my_pcb->delivered = copy_memo(f->m_hd);
		my_pcb->which = g->which;
		my_pcb->delivered->next = NULL;
		my_pcb->state = RUNNING;
		break;
default:;
	}
	UNLOCK_PCB(my_pcb);
  }
  UNLOCK_TBL(g->hash);
  return;
}

/************************************************************************
*  static remove_gets(g)
*  	GET g;
*
*  	Remove all the GET structures in the list beginning at g and
*  linked through the alternate fields. All the get structures are
*  freed.
*
*  Must NOT be executed between LOCK_TBL and UNLOCK_TBL.
*
************************************************************************/
static remove_gets(GET g)
{
  GET P,Q,alt_g;
  FOLDER f;
  for (; g!=NULL; g = alt_g) {
  	alt_g = g->alternate;
	LOCK_TBL(g->hash);
	f = lookup(g->key,g->hash);
	for (Q = NULL, P = f->g_hd; P!=NULL;
			Q = P, P = P->next) {
		if (P == g) {
			if (Q==NULL)
				f->g_hd = P->next;
			else
				Q->next = P->next;
			if (g==f->g_tl)
				f->g_tl = Q;
			break;
		}
	}
	UNLOCK_TBL(g->hash);
	SHARE_FREE(g);
  }
  return;
}

/************************************************************************
*  static MEMO_PTR build_memo(key,block_addr,len)
*  	FOLDER_NAME  key; char *block_addr; int len;
*
*  Build a memo.
*
************************************************************************/
static MEMO_PTR build_memo(FOLDER_NAME  key, char *block_addr, int len)
{
	MEMO_PTR m;
	m = (MEMO_PTR) SHARE_MALLOC(sizeof(*m)+len);
	m->key = key;
	m->next = NULL;
	m->len = len;
	memcpy((m+1),block_addr,len);
	return m;
}

/************************************************************************
*  static void wake_up_chain(w)
*  	PCB w;
*  Wake up a chain of processes that have been waiting for a copy
*  of a memo. The chain has been created by pushing processes on a
*  list, so for fairness the chain must be reversed.
************************************************************************/
static void wake_up_chain( PCB w)
{
	PCB p,v;
	v = NULL;
	while (w !=NULL) {
		p = w;
		w = p->wake_chain;
		p->wake_chain = v;
		v = p;
	}
	w = v;
	while (w !=NULL) {
		p = w->wake_chain;
		SIGNAL_SEMA4(&w->wait);
		w = p;
	}
	return;
}

/************************************************************************
*  static void do_write(m)
*  	MEMO_PTR m;
*
*  	Memo_write puts a memo into a shared queue.
*
*************************************************************************/
static void do_write( MEMO_PTR m)
{
	FOLDER f;
	GET g;
	PCB w=NULL; /*stack of processes to wake up*/
	unsigned long h = hash_key(m->key);
	LOCK_TBL(h);
	f = lookup(m->key,h);
	if (f->d_hd != NULL) {
		/*put delayed memos on list to deliver later*/
		if (delay_hd == NULL) {
			delay_hd = f->d_hd;
			delay_tl = f->d_tl;
		} else {
			delay_tl->next = f->d_hd;
			delay_tl = f->d_tl;
		}
		f->d_hd = NULL;
	}
	for (g = f->g_hd; g!=NULL; g = g->next) {
		/*look thru GET list for those awaiting a copy*/
		LOCK_PCB(g->process);
		if (g->process->state == LOOKING) {
			g->process->delivered = copy_memo(m);
			g->process->which = g->which;
			g->process->state = WAKING;
			g->process->wake_chain = w;
			w = g->process;
		}
		UNLOCK_PCB(g->process);
	}
	for (g = f->g_hd; g!=NULL; g = g->next) {
		/*look through the GET list for one process */
		/* wanting to get the only copy*/
		LOCK_PCB(g->process);
		if (g->process->state == GETTING) {
			g->process->delivered = m;
			g->process->which = g->which;
			g->process->state = WAKING;
			UNLOCK_PCB(g->process);
			UNLOCK_TBL(h);
			wake_up_chain(w);
			SIGNAL_SEMA4(&g->process->wait);
			return;
		}
		UNLOCK_PCB(g->process);
	}
	/* if I haven't already delivered the memo itself, */
	/*  enqueue it */
	if (f->m_hd == NULL) {
		f->m_hd = f->m_tl = m;
	} else {
		f->m_tl->next = m;
		f->m_tl = m;
	}
	m->next = NULL;
	UNLOCK_TBL(h);
	wake_up_chain(w);
}

/************************************************************************
*  void memo_write(key,block_addr,len)
*  	FOLDER_NAME  key; char *block_addr; int len;
*
*  	Memo_write puts a memo into a shared queue named by the folder name
*  key. The contents of the memo are the len bytes beginning at
*  address block_addr.
*************************************************************************/
void memo_write( FOLDER_NAME  key, char *block_addr, int len)
{
  MEMO_PTR m;
  m = build_memo(key,block_addr,len);
  do_write(m);
  while (delay_hd != NULL) {
	m = delay_hd;
	delay_hd = m->next;
	m->next = NULL;
	do_write(m);
  }
}

/************************************************************************
*  void memo_write_delayed(key1,key2,block_addr,len)
*  	FOLDER_NAME  key1, key2; char *block_addr; int len;
*
*  Memo_write_delayed behaves like memo_write(key2,block_addr,len) with
*  the following difference: although memo_write_delayed returns
*  immediately, the memo is not actually delivered until one or
*  more memos are present in the folder named key1.
*
*************************************************************************/
void memo_write_delayed(FOLDER_NAME  key1, FOLDER_NAME key2,
                        char *block_addr, int len)
{
  MEMO_PTR p;
  FOLDER f;
  unsigned long int h=hash_key(key1);
  LOCK_TBL(h);
  f = lookup(key1,h);
  if (f->m_hd != NULL) {
  	UNLOCK_TBL(h);
  	memo_write(key2,block_addr,len);
  } else {
	p = build_memo(key2,block_addr,len);
	if (f->d_hd == NULL) {
		f->d_hd = f->d_tl = p;
	} else {
		f->d_tl->next = p;
		f->d_tl = p;
	}
	p->next = NULL;
	UNLOCK_TBL(h);
  }
}

/************************************************************************
*  MEMO memo_get(key)
*  	FOLDER_NAME key;
*
*  	Memo_get gets a pointer to a memo removed from the shared
*  queue named by key. The length of the body of the memo
*  can be found by calling memo_len(). Memo_get blocks until there
*  is a memo present in the queue. The memo is removed from the
*  queue. To access the body of the memo, do something like:
*  	struct something *p;
*   FOLDER_NAME whatever;
*  	...
*  	p = (struct something *)memo_get(whatever);
*  	...
*************************************************************************/
#ifdef PARALLEL
MEMO memo_get(FOLDER_NAME key)
{
  unsigned long hash;
  FOLDER f;
  GET g;
  g = build_get(key,0);
  my_pcb->state = GETTING;
  enqueue_get(g);
  if (my_pcb->state != RUNNING) {
	WAIT_SEMA4(&my_pcb ->wait);
	my_pcb->state = RUNNING;
  }
  remove_gets(g);
  return my_pcb->delivered+1;
}
#endif

/************************************************************************
*  MEMO memo_get_copy(key)
*  	FOLDER_NAME key;
*
*  	Memo_get_copy is the same as memo_get except that the memo
*  is not removed from the queue.
*************************************************************************/
#ifdef PARALLEL
MEMO memo_get_copy(FOLDER_NAME key)
{
  unsigned long hash;
  FOLDER f;
  GET g;
  g = build_get(key,0);
  my_pcb->state = LOOKING;
  enqueue_get(g);
  if (my_pcb->state != RUNNING) {
	WAIT_SEMA4(&my_pcb ->wait);
	my_pcb->state = RUNNING;
  }
  remove_gets(g);
  return my_pcb->delivered+1;
}
#endif

/************************************************************************
*  MEMO memo_get_skip(key)
*  	FOLDER_NAME key;
*
*  	Memo_get_skip is the same as memo_get except that if there
*  is no memo immediately available, it does not block, but returns
*  a NULL pointer.
*************************************************************************/
MEMO memo_get_skip(FOLDER_NAME key)
{
  unsigned long hash;
  FOLDER f;
  GET g;
  g = build_get(key,0);
  my_pcb->state = GETTING;
  my_pcb->delivered = NULL;
  enqueue_get(g);
  remove_gets(g);
  if (my_pcb->state==WAKING) {
	WAIT_SEMA4(&my_pcb ->wait);
  }
  my_pcb->state = RUNNING;
  return my_pcb->delivered?my_pcb->delivered+1:NULL;
}

/************************************************************************
*  MEMO memo_get_copy_skip(key)
*  	FOLDER_NAME key;
*
*  	Memo_get_copy_skip is the same as memo_get_copy except that if there
*  is no memo immediately available, it does not block, but returns
*  a NULL pointer.
*************************************************************************/
MEMO memo_get_copy_skip(FOLDER_NAME key)
{
  unsigned long hash;
  FOLDER f;
  GET g;
  g = build_get(key,0);
  my_pcb->state = LOOKING;
  my_pcb->delivered = NULL;
  enqueue_get(g);
  remove_gets(g);
  if (my_pcb->state==WAKING) {
	WAIT_SEMA4(&my_pcb ->wait);
  }
  my_pcb->state = RUNNING;
  return my_pcb->delivered?my_pcb->delivered+1:NULL;
}

/************************************************************************
*  MEMO memo_alt(key_list,len_key_list,which)
*  	FOLDER_NAME key_list[]; int len_key_list, *which;
*
*  	This is a version of memo_get that will return a memo taken
*  from one or a list of alternative queues. Parameter key_list
*  points to an array of folder names. As with memo_get, memo_alt blocks
*  until a memo can be returned. Memo_alt removes the memo from its
*  folder. Result parameter 'which' will be set to indicate the position
*  of the folder name in key_list. To find out the name of the queue
*  from which the memo was removed, use key_list[which] or memo_key().
*  An example:
*
*  	FOLDER_NAME keys[2],key;
*  	MEMO m;
*	int i;
*  	...
*  	m = memo_alt(keys,2,&i);
*  	key = keys[i];
*	switch (i) {
*		...
*	}
*  	...
*************************************************************************/
#ifdef PARALLEL
MEMO memo_alt( FOLDER_NAME key_list[], int len_key_list, int *which)
{
  GET g,list;
  int i;
  list = NULL;
  my_pcb->state = GETTING;
  for ( i = 0; i < len_key_list; i++ ) {
	  g = build_get(key_list[i],i);
	  g->alternate = list;
	  list = g;

	  enqueue_get(g);
	  if (my_pcb->state == RUNNING) {
		remove_gets(list);

		*which = my_pcb->which;
		return my_pcb->delivered+1;
	  } else if (my_pcb->state == WAKING) {

		break;
	  }

  }
  WAIT_SEMA4(&my_pcb ->wait);
  my_pcb->state = RUNNING;

  remove_gets(list);

  *which = my_pcb->which;
  return my_pcb->delivered+1;
}
#endif

/************************************************************************
*  MEMO memo_alt_skip(key_list,len_key_list,which)
*  	FOLDER_NAME *key_list; int len_key_list, *which;
*
*  	This is a version of memo_get_skip that will return a memo
*  taken from one or a list of alternative queues. The names of the
*  queues to be examined for memos are the folder names in the
*  array key_list points to. As with memo_get_skip, memo_alt_skip
*  returns NULL if a memo can not immediately be returned.
*  Memo_alt_skip removes the memo from its queue. To find out the
*  name of the queue from which the memo was removed, use
*  memo_key().  An example:
*
*
*  	FOLDER_NAME keys[3];
*  	MEMO m;
*	int i;
*  	...
*  	m = memo_alt_skip(keys,3,&i);
*  	if (m!=NULL) {
*  		switch (i) {
*  		...
*		}
*  	}
*  	...
*************************************************************************/
MEMO memo_alt_skip(FOLDER_NAME key_list[], int len_key_list, int *which)
{
  GET g,list;
  int i;
  list = NULL;
  my_pcb->state = GETTING;
  my_pcb->delivered = NULL;
  my_pcb->which = -1;
  for ( i = 0; i < len_key_list; i++ ) {
	  g = build_get(key_list[i],i);
	  g->alternate = list;
	  list = g;

	  enqueue_get(g);
	  if (my_pcb->state == RUNNING) {
		remove_gets(list);

		*which = my_pcb->which;
		return my_pcb->delivered+1;
	  } else if (my_pcb->state == WAKING) {

		break;
	  }

  }
  LOCK_PCB(my_pcb);
  if (my_pcb->state == WAKING) {
	my_pcb->state = RUNNING;
	UNLOCK_PCB(my_pcb);
		/*no actual wait, whoever set state=WAKING signaled the semaphore*/
	WAIT_SEMA4(&my_pcb->wait);
  } else {
	my_pcb->state = RUNNING;
	/*otherwise state == GETTING*/
	UNLOCK_PCB(my_pcb);
  }
  remove_gets(list);
  *which = my_pcb->which;
  return my_pcb->delivered?my_pcb->delivered+1:NULL;
}

/************************************************************************
*  void memo_free(memo)
*  	MEMO memo;
*
*  	This procedure frees the storage that a memo occupies. Use
*  it instead of free or share_free for MEMO pointers.
*************************************************************************/
void memo_free(MEMO memo)
{
        MEMO_PTR m = (MEMO_PTR)memo;
        
	if (m==NULL) return;
	m--;
	SHARE_FREE(m);
	return;
}

/************************************************************************
*  int memo_len(memo)
*  	MEMO memo;
*
*  	This function returns the length of the body of a memo.
*************************************************************************/
int memo_len(MEMO memo)
{
        MEMO_PTR m = (MEMO_PTR)memo;
	return (m-1)->len;
}

/************************************************************************
*  FOLDER_NAME *memo_key(memo)
*  	MEMO memo;
*
*  	This function returns a pointer to the name of the queue a
*  memo was removed or copied from by memo_get... or memo_alt....
*  Do not change this name or try to use it after calling
*  memo_free(memo), memo_put..., or memo_replace....
*************************************************************************/
FOLDER_NAME *memo_key(MEMO memo)
{
        MEMO_PTR m = (MEMO_PTR)memo;
	return &(m-1)->key;
}

/************************************************************************
*  int memo_get_my_id(void)
*
*  	This function returns an integer value representing the id
*  of the process assigned by the memo system.
*************************************************************************/
int memo_get_my_id(void)
{
	return my_pcb->my_id;
}

/************************************************************************
*  int memo_num_workers(void)
*
*  	This function returns an integer value indicating the total
*  number of workers started by memo_init().
*************************************************************************/
int memo_num_workers(void)
{
	return sys->num_workers;
}

/************************************************************************
*  SYMBOL memo_symbol(void)
*     This function generates a unique SYMBOL. It will not be the
*  same as the value returned by any other call to memo_symbol(), nor to
*  any "small" integer (unless the system has run for a very long
*  time).
*************************************************************************/
SYMBOL memo_symbol(void)
{
	symbol_gen -= symbol_decr;
	return symbol_gen+symbol_decr+my_pcb->my_id;
}

/************************************************************************
*  unsigned long int memo_clock(void)
*
*  	This function returns an integer value indicating the
*  raw value of the system clock.
*************************************************************************/
unsigned long int memo_clock(void)
{
	return (unsigned long int) RAW_TIME;
}

/************************************************************************
*  memo_put(key,memo)
*       FOLDER_NAME key; MEMO memo;
*     This is the same as memo_write, except that the already
*  existing memo structure is used, rather than a new one being
*  created.
*************************************************************************/
void memo_put(FOLDER_NAME key, MEMO memo)
{
  MEMO_PTR m;
  m = (MEMO_PTR)memo-1;
  m->key = key;
  do_write(m);
  while (delay_hd != NULL) {
	m = delay_hd;
	delay_hd = m->next;
	m->next = NULL;
	do_write(m);
  }
}

/************************************************************************
*  memo_put_delayed(key1,key2,memo)
*       FOLDER_NAME key1, key2; MEMO memo;
*     Memo_put_delayed behaves like memo_put(key2,memo) with the
*  following difference: although memo_put_delayed returns
*  immediately, the memo is not actually delivered until one or more
*  memos are present in the folder named key1.
*************************************************************************/
void memo_put_delayed(FOLDER_NAME key1,FOLDER_NAME key2, MEMO memo)
{
  MEMO_PTR m=(MEMO_PTR)memo;
  MEMO_PTR p=(MEMO_PTR)memo-1;
  FOLDER f;
  unsigned long int h = hash_key(key1);
  LOCK_TBL(h);
  f = lookup(key1,h);
  if (f->m_hd != NULL) {
  	UNLOCK_TBL(h);
  	memo_put(key2,m);
  } else {
	if (f->d_hd == NULL) {
		f->d_hd = f->d_tl = p;
	} else {
		f->d_tl->next = p;
		f->d_tl = p;
	}
	p->next = NULL;
	UNLOCK_TBL(h);
  }
}

/************************************************************************
*  MEMO memo_alloc(len)
*       int len;
*     This routine allocates a MEMO structure of the specified
*  length. It can be used to avoid double copying, first into a user
*  buffer and then into a memo. It should be sent by calling
*  memo_put or memo_put_delayed.
*************************************************************************/
MEMO memo_alloc(int len)
{
	MEMO_PTR m;
	int i;
	m = (MEMO_PTR) SHARE_MALLOC(sizeof(*m)+len);
	/* initialize? */
	m->key.S = 0L;
	for (i = NUM_X - 1; i>=0; i--) m->key.X[i] = 0L;
	m->next = NULL;
	m->len = len;
	return m+1;
}

/************************************************************************
*  memo_replace(memo)
*       MEMO memo;
*     This procedure replaces the memo in the folder it was taken
*  from. It is undefined if the memo was created by memo_alloc.
*************************************************************************/
void memo_replace(MEMO memo)
{
        MEMO_PTR m = (MEMO_PTR)memo;
	memo_put( (m - 1)->key, m );
}

/************************************************************************
*  int memo_present(key)
*       FOLDER_NAME key;
*     This function returns TRUE (non-zero) if there is a memo present
*	in the folder named by key and FALSE (zero) otherwise. Viewed another
*	way, memo_present returns TRUE if memo_get_skip would have returned
*	a memo and FALSE if it wouldn't.
*************************************************************************/
int memo_present(FOLDER_NAME key)
{
  FOLDER f;
  unsigned long int h = hash_key(key);
  LOCK_TBL(h);
  f = lookup(key,h);
  if (f->m_hd != NULL) {
  	UNLOCK_TBL(h);
  	return 1;
  } else {
	UNLOCK_TBL(h);
	return 0;
  }
}