--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/findslot.c	Sat Dec 06 04:37:03 1997 +0000
@@ -0,0 +1,491 @@
+/*--------------------------------------------------------------------------
+NETREK II -- Paradise
+
+Permission to use, copy, modify, and distribute this software and its
+documentation, or any derivative works thereof, for any NON-COMMERCIAL
+purpose and without fee is hereby granted, provided that this copyright
+notice appear in all copies.  No representations are made about the
+suitability of this software for any purpose.  This software is provided
+"as is" without express or implied warranty.
+
+    Xtrek Copyright 1986                            Chris Guthrie
+    Netrek (Xtrek II) Copyright 1989                Kevin P. Smith
+                                                    Scott Silvey
+    Paradise II (Netrek II) Copyright 1993          Larry Denys
+                                                    Kurt Olsen
+                                                    Brandon Gillespie
+--------------------------------------------------------------------------*/
+
+
+#include "config.h"
+#include <stdio.h>
+#include <sys/types.h>
+#include <sys/ipc.h>
+#include <sys/shm.h>
+#include <errno.h>
+#include <pwd.h>
+#include <string.h>
+#include <ctype.h>
+#include "defs.h"
+#include "struct.h"
+#include "data.h"
+#include "packets.h"
+#include "shmem.h"
+
+int grabslot( /* int */ );
+void mapWaitCount( /* int */ );
+
+
+extern int isClientDead();
+extern unsigned int sleep();
+extern int sendQueuePacket();
+extern int flushSockBuf();
+
+int
+findslot(overload, homeaway)
+  int overload;
+  enum HomeAway homeaway;
+{
+  int i;
+
+  i = grabslot(overload, homeaway);
+  players[i].p_pos = -1;
+  memset(&players[i].p_stats, 0, sizeof(struct stats));
+  players[i].p_stats.st_tticks = 1;
+#if 0
+  for (j = 0; j < 95; j++)
+  {
+    players[i].p_stats.st_keymap[j] = j + 32;
+  }
+  players[i].p_stats.st_keymap[95] = 0;
+#endif
+  players[i].p_stats.st_flags = ST_INITIAL;
+  return (i);
+}
+
+static int 
+allocate_slot(homeaway, overload, allocate)
+  enum HomeAway homeaway;
+  int overload;
+  int allocate;
+{
+  int i;
+  if (overload)
+  {
+    for (i = MAXPLAYER - 1; i >= 0; i--)
+    {
+      if (players[i].p_status == PFREE)
+      {
+	if (allocate)
+	{
+	  players[i].p_status = POUTFIT;
+	  players[i].p_team = NOBODY;
+	}
+	return i;
+      }
+    }
+  }
+  else
+  {
+#ifdef LEAGUE_SUPPORT
+    if (status2->league)
+    {
+      /*
+       * for league play, make sure one team doesn't crowd out the other.
+       */
+      int count = 0;
+      for (i = 0; i < MAXPLAYER; i++)
+      {
+	if (players[i].p_status == PFREE)
+	  continue;
+	if (players[i].p_homeaway == homeaway)
+	  count++;
+      }
+      if (count * 2 >= MAXPLAYER - configvals->ntesters)
+	return -1;		/* our team is full */
+    }
+#endif
+    for (i = 0; i < MAXPLAYER - configvals->ntesters; i++)
+    {
+      if (players[i].p_status == PFREE)
+      {
+	if (allocate)
+	{
+	  players[i].p_status = POUTFIT;
+	  players[i].p_team = NOBODY;
+	}
+	return i;
+      }
+    }
+  }
+  return -1;
+}
+#if 0
+static int 
+ImAllowed(slotnum, homeaway)
+  int slotnum;
+  enum HomeAway homeaway;
+{
+#ifdef LEAGUE_SUPPORT
+  int half;
+  if (!status2->league)
+    return 1;
+
+  half = (MAXPLAYER - configvals->ntesters) / 2;
+  return (homeaway == AWAY) ? (slotnum < half) :
+    (slotnum >= half);
+#else
+  return 1;
+#endif
+}
+#endif
+/*
+ * The following code for grabslot() is really bizarre, and needs an
+ * explaination.
+ * 
+ * Basically, the queue works like this:  Each process that needs to wait takes
+ * a number, and when that number comes up, the process enters the game.
+ * status->count is the next number to take for a new process, and
+ * status->wait is the current process being served.
+ * 
+ * However, this is not enough to determine exactly how many people are waiting,
+ * because people may drop out.  So, 3 more variables are added,
+ * status->request posts a request of some sort to all of the other
+ * processes, and status->number is the process posting the request. Also,
+ * status->answer is available for any kind of response needed from the other
+ * processes.  (Needless to say, only one process can make a request at any
+ * one time).
+ * 
+ * Every process will wait for a second (sleep(1)), and then check the queue
+ * status, do what is appropriate, and repeat.
+ * 
+ * Above and beyond this, processes may die, and not report it (for whatever
+ * reason, and every process waiting on the queue watches the behavior of
+ * every other supposed process to make sure it is still alive).
+ * 
+ * When a space opens up, and the person who holds the number currently being
+ * served does not respond, then the processes argue over who deserves to get
+ * in next.  The first process to decide that no one is going to take the
+ * free slot says that his number is the next on to be served. He waits for
+ * anyone to disagree with him.  Any other processes which notice that their
+ * number is lower than the number being served claim that their number is
+ * the next one to be served.  They also wait for anyone to disagree with
+ * them.  Eventually, everyone is done waiting, and the process with the
+ * lowest count will be served.
+ * 
+ * Variables: status->wait:  	Number being served. status->count:	Next
+ * number to take.
+ * 
+ * status->request:	Process request. (status->number) (status->answer)
+ * REQFREE:	No requests pending. REQWHO:		How many people are
+ * before me?  In this case, every process in from of this process (whose
+ * position is recorded in status->number) increments status->answer.
+ * REQDEAD:	I am leaving the queue (Either to quit, or enter game).  Any
+ * process whose position is higher than this process will note that they are
+ * closer to the top of the queue.
+ * 
+ * (Local) waitWin:	The window. qwin:	The quit half of waitWin.
+ * countWin:	The count half of waitWin. count:	My number (Position
+ * in queue). pseudocount: Number of people in front of me (-1 means I don't
+ * know). myRequest:	This keeps track of requests I've made.  If it is non
+ * zero, then this is the number of times I will leave it there before I get
+ * my answer (if there is one), and reset status->request. idie:	This
+ * is set to one if I need to leave the queue.  When I get a chance, I will
+ * submit my request, and leave. wearein:	This is the slot we grabbed
+ * to enter the game.  If it is -1, then we haven't got a slot yet.  If we
+ * can grab a slot, then wearein is set to the slot #, and idie is set to 1.
+ * 
+ * Because we need to monitor other processes, the following variables also
+ * exist:
+ * 
+ * oldcount:	The number that was being served last time I looked. waits:
+ * Number of times I've seen oldcount as the number being served. If a
+ * position opens in the game, and no one takes it for a while, we assume
+ * that someone died. lastRequest:	The last request I have seen.
+ * lastNumber:	The process making this request. reqCount:	Number of
+ * times I've seen this request.  If I see this request 9 times, I assume it
+ * is obsolete, and I reset it.
+ */
+
+int
+grabslot(overload, homeaway)
+  int overload;			/* Indicates a request for a tester's slot. */
+  enum HomeAway homeaway;
+{
+  int count;			/* My number */
+  int oldcount;			/* Number that was being served last check */
+  int i;
+  int waits;			/* # times I have waited for someone else to
+				 * act */
+  int oldwait;			/* Number being served last check */
+  int pseudocount = -1;		/* Count on queue for sake of person waiting */
+  int myRequest = 0;		/* To keep track of any request I'm making */
+  int lastRequest = 0;		/* Last request I've seen */
+  int lastNumber = 0;		/* Last person making request */
+  int reqCount = 0;		/* Number of times I've seen this */
+  int idie = 0;			/* Do I want to die? */
+  int wearein = -1;		/* Slot we got in the game */
+  int rep = 0;
+
+  /* If other players waiting, we get in line behind them */
+  if (!overload && status->wait != status->count)
+  {
+    count = status->count++;
+  }
+  else
+  {
+    /* Get in game if posible */
+#if 1
+    i = allocate_slot(homeaway, overload, 1);
+    if (i >= 0)
+      return i;
+#else
+    if (overload)
+      for (i = MAXPLAYER - 1; i >= 0; i--)
+      {
+	if (players[i].p_status == PFREE)
+	{			/* We have a free slot */
+	  players[i].p_status = POUTFIT;	/* possible race code */
+	  players[i].p_team = NOBODY;
+	  return (i);
+	}
+      }
+    else
+      for (i = 0; i < MAXPLAYER - configvals->ntesters; i++)
+      {
+	if (ImAllowed(i, homeaway)
+	    && players[i].p_status == PFREE)
+	{			/* We have a free slot */
+	  players[i].p_status = POUTFIT;	/* possible race code */
+	  players[i].p_team = NOBODY;
+	  return (i);
+	}
+      }
+#endif
+    /* Game full.  We will wait. */
+    count = status->count++;
+  }
+  waits = 0;
+  oldwait = -1;
+  oldcount = status->wait;
+
+  /* For count = 0,1,2  I know that it is right */
+  if (count - status->wait < 1)
+  {
+    pseudocount = count - status->wait;
+  }
+  for (;;)
+  {
+    /* Send packets occasionally to see if he is accepting... */
+    if (rep++ % 10 == 0)
+    {
+      mapWaitCount(pseudocount);
+    }
+    if (isClientDead())
+    {
+      if (count == status->count - 1)
+      {
+	status->count--;
+	exit(0);
+      }
+      /* If we are at top, decrease it */
+      if (count == status->wait)
+      {
+	status->wait++;
+      }
+      idie = 1;
+      /* break;		warning, function has return e and return */
+      exit(0);
+    }
+    if (status->wait != oldcount)
+    {
+      mapWaitCount(pseudocount);
+      oldcount = status->wait;
+    }
+    /* To mimize process overhead and aid synchronization */
+    sleep(1);
+    /* Message from daemon that it died */
+    if (status->count == 0)
+      exit(0);
+    /* I have a completed request? */
+    if (myRequest != 0 && --myRequest == 0)
+    {
+      if (idie && status->request == REQDEAD)
+      {
+	status->request = REQFREE;
+	/* Out of queue, into game */
+	if (wearein != -1)
+	{
+	  return (wearein);
+	}
+	exit(0);
+      }
+      pseudocount = status->answer;
+      status->request = REQFREE;
+      if (pseudocount > 18)
+	idie = 1;
+      mapWaitCount(pseudocount);
+    }
+    /* Tell the world I am going bye bye */
+    if (idie && status->request == REQFREE)
+    {
+      status->request = REQDEAD;
+      status->number = count;
+      myRequest = 4;
+    }
+    /* Should I request a count for # of people waiting? */
+    if (pseudocount == -1 && status->request == REQFREE)
+    {
+      status->request = REQWHO;
+      status->number = count;
+      status->answer = 0;
+      myRequest = 4;
+      /* I give people 4 seconds to respond */
+    }
+    /* Is someone else making a request? */
+    if (status->request != REQFREE && myRequest == 0)
+    {
+      if (status->request == lastRequest &&
+	  status->number == lastNumber)
+      {
+	reqCount++;
+	/* 9 occurances of the same request implies that the process */
+	/* died.  I will reset request. */
+	if (reqCount > 8)
+	{
+	  status->request = REQFREE;
+	}
+      }
+      else
+      {
+	lastRequest = status->request;
+	lastNumber = status->number;
+	reqCount = 1;
+	if (lastRequest == REQWHO)
+	{
+	  if (count < lastNumber)
+	  {
+	    status->answer++;
+	  }
+	}
+	else if (lastRequest == REQDEAD)
+	{
+	  if (count > lastNumber && pseudocount != -1)
+	  {
+	    pseudocount--;
+	    mapWaitCount(pseudocount);
+	  }
+	}
+      }
+    }
+    /* If someone raised wait too high, I claim that I * am next in line */
+    if (status->wait > count && !idie)
+    {
+      status->wait = count;
+      /* Give people a chance to correct me */
+      sleep(2);
+    }
+#if 1
+    if (idie)
+      continue;
+    if (count == status->wait)
+    {
+      i = allocate_slot(homeaway, overload, 1);
+      if (i < 0)
+	continue;
+      status->wait++;
+      wearein = i;
+      idie = 1;
+    }
+    else
+    {
+      i = allocate_slot(homeaway, overload, 0);
+      if (i < 0)
+	continue;
+      if (oldwait == status->wait)
+      {
+	waits++;
+      }
+      else
+      {
+	oldwait = status->wait;
+	waits = 1;
+      }
+      /* If this is our fifth wait (5 sec), then something is */
+      /* wrong.  We assume someone died, and fix this problem */
+      if (waits == 5 && !idie)
+      {
+	/* I want to be next in line, so I say so. */
+	status->wait = count;
+	/* And I allow someone to correct me if I'm wrong */
+	sleep(2);
+	waits = 0;
+      }
+
+    }
+#else
+    for (i = 0; i < MAXPLAYER - configvals->ntesters; i++)
+    {
+      /* If we want to die anyway, we have no right looking for */
+      /* a free slot */
+      if (idie)
+	break;
+      if (ImAllowed(i, homeaway) && players[i].p_status == PFREE)
+      {
+	/* If I am next in line... */
+	if (count == status->wait)
+	{
+	  players[i].p_status = POUTFIT;
+	  players[i].p_team = NOBODY;
+	  /* Increase count for next player */
+	  status->wait++;
+	  /* I should check idie, but maybe he wants in, eh? */
+	  wearein = i;
+	  idie = 1;
+	  break;
+	}
+	else
+	{
+	  if (oldwait == status->wait)
+	  {
+	    waits++;
+	  }
+	  else
+	  {
+	    oldwait = status->wait;
+	    waits = 1;
+	  }
+	  /* If this is our fifth wait (5 sec), then something is */
+	  /* wrong.  We assume someone died, and fix this problem */
+	  if (waits == 5 && !idie)
+	  {
+	    /* I want to be next in line, so I say so. */
+	    status->wait = count;
+	    /* And I allow someone to correct me if I'm wrong */
+	    sleep(2);
+	    waits = 0;
+	  }
+	  break;
+	}
+      }
+    }
+#endif
+    /* this location is skipped if we didn't find a slot */
+  }
+}
+
+void
+mapWaitCount(count)
+  unsigned int count;
+{
+  if (count == -1)
+    return;
+
+  sendQueuePacket((short) count);
+  blk_flag = 1;
+  updateMOTD();
+  blk_flag = 0;
+
+  undeferDeferred();		/* send the MOTD through the TCP buffers */
+  flushSockBuf();
+}