/*****************************************************************************\
* Copyright (c) 2002 Pelle Johansson.                                         *
* All rights reserved.                                                        *
*                                                                             *
* This file is part of the moftpd package. Use and distribution of            *
* this software is governed by the terms in the file LICENCE, which           *
* should have come with this package.                                         *
\*****************************************************************************/

/* $moftpd: memory.c 1224 2004-10-28 22:42:00Z morth $ */

#include "system.h"

#include "memory.h"

#ifdef DEBUG
extern int debug;
static void DOBUG (const char *fmt, ...)
{
  va_list ap;
  
  va_start (ap, fmt);
  vsyslog (LOG_DEBUG, fmt, ap);
  va_end (ap);
}
#undef DEBUG
#define DEBUG(level, msg) if (debug >= level) DOBUG msg
#define DEXPR(x) x
#else
#define DEBUG(level, msg)
#define DEXPR(x)
#endif

#define stringHashSize 31 // gcc chokes on const int

static memory_t *tMem;
static memdata_t *stringHash[stringHashSize];
static unsigned char randVals[256];
static unsigned int sweepMark;
static memdata_t *memChain, *rootChain;

void mem_init (void)
{
  int fd = open ("/dev/urandom", O_RDONLY);
  ssize_t j;
  int i;
  
  i = 256;
  if (fd >= 0)
  {
    for (; i > 0; i -= j)
    {
      j = read (fd, randVals + 256 - i, (size_t)i);
      if (j < 0)
	break;
    }
    (void)close (fd);
  }
  
  if (i)
  {
    srand ((unsigned int)time (NULL));
    for (; i > 0; i--)
      randVals[256 - i] = random ();
  }
}

void *talloc(size_t sz)
{
  memory_t *mem = calloc(1, sz + sizeof(memory_t) * pNumTempLinks);
  
  if(!mem)
    return NULL;
  
  mem[pNextTemp].link = tMem;
  tMem = mem;
  
  DEBUG (2, ("talloc: %p", mem + pNumTempLinks));
  
  return mem + pNumTempLinks;
}

void *trealloc(void *ptr, size_t sz)
{
  memory_t *mem = (memory_t*)ptr - pNumTempLinks, *res, *pmem, *nmem;
  
  if (!ptr)
    return talloc (sz);
  
  nmem = mem[pNextTemp].link;
  res = realloc(mem, sz + sizeof(memory_t) * pNumTempLinks);
  
  if (res == mem)
    return res + pNumTempLinks;
  
  DEBUG (2, ("trealloc: %p -> %p", mem + pNumTempLinks, res + pNumTempLinks));
  
  if(mem == tMem)
  {
    if(res)
      tMem = res;
    else
      tMem = nmem;
  }
  else
  {
    for (pmem = tMem; pmem[pNextTemp].link && pmem[pNextTemp].link != mem;
	 pmem = pmem->link)
      ;
    if (pmem[pNextTemp].link)
    {
      if(res)
	pmem[pNextTemp].link = res;
      else
	pmem[pNextTemp].link = nmem;
    }
  }
  
  if(res)
    return res + pNumTempLinks;
  return NULL;
}

char *tstring(const char *str)
{
  char *res;
  
  if (!str)
    return NULL;
  
  res = talloc (strlen (str) + 1);
  if(res)
    strcpy(res, str);
  
  return res;
}

static void mark_memory (memdata_t *mem)
{
  memory_t *cmem, *nmem;
  
  if (mem->mark == sweepMark)
    return;
  mem->mark = sweepMark;
  if (mem->isHashed)
    return;
  for (cmem = mem->firstChild.link; cmem; cmem = nmem)
  {
    nmem = cmem[pNextChild].link;
#ifdef MEMORY_LOCATION
    if (cmem[pLocation].ptr && *cmem[pLocation].ptr != mem + 1)
    {
      pfree (cmem[pChild].data + 1, mem + 1);
      continue;
    }
#endif
    mark_memory (cmem[pChild].data);
  }
}

void tfree_all(void)
{
  memory_t *nmem;
  memdata_t *chain, *pchain;
#ifdef MEMORY_LOCATION
  memory_t *mem, *pmem;
#endif
  
  while(tMem)
  {
    nmem = tMem[pNextTemp].link;
    DEBUG (2, ("tfree: %p", tMem + pNumTempLinks));
    free (tMem);
    tMem = nmem;
  }
  
  sweepMark ^= 1;
#ifdef MEMORY_LOCATION
  pchain = NULL;
#endif
  chain = rootChain;
  while (chain)
  {
#ifdef MEMORY_LOCATION
    if (chain->firstParent.link)
    {
      pmem = NULL;
      for (mem = chain->firstParent.link; mem; mem = nmem)
      {
	nmem = mem[pNextParent].link;
	if (mem[pLocation].ptr && *mem[pLocation].ptr != chain + 1)
	{
	  if (pmem)
	    pmem[pNextParent].link = nmem;
	  else
	    chain->firstParent.link = nmem;
	  free (pmem);
	}
	else
	  pmem = mem;
      }
      if (!chain->firstParent.link)
      {
	if (pchain)
	{
	  pchain->next = chain->next;
	  DEBUG (3, ("tfree: %p->next -> %p", pchain, pchain->next));
	}
	else
	  rootChain = chain->next;
	DEBUG (2, ("collected: %p", chain + 1));
	pfree (chain + 1, (void*)-1);
	if (pchain)
	  chain = pchain->next;
	else
	  chain = memChain;
	continue;
      }
    }
#endif
    mark_memory (chain);
#ifdef MEMORY_LOCAIION
    pchain = chain;
#endif
    chain = chain->next;
  }
  pchain = NULL;
  chain = memChain;
  while (chain)
  {
    if (chain->mark != sweepMark)
    {
      if (pchain)
      {
	pchain->next = chain->next;
	DEBUG (3, ("tfree: %p->next -> %p", pchain, pchain->next));
      }
      else
	memChain = chain->next;
      DEBUG (2, ("collected: %p", chain + 1));
      pfree (chain + 1, (void*)-1);
      if (pchain)
	chain = pchain->next;
      else
	chain = memChain;
    }
    else
    {
      pchain = chain;
      chain = chain->next;
    }
  }
}

void *proot(
#ifdef MEMORY_LOCATION
      void **loc
#else
      void
#endif
      )
{
#ifdef MEMORY_LOCATION
  return palloc (1, NULL, NULL, loc);
#else
  return palloc(1, NULL, NULL);
#endif
}

void *palloc(size_t sz, /*@null@*/void *parent, /*@null@*/void (*deallocator)(void *ptr)
#ifdef MEMORY_LOCATION
      , void **loc
#endif
      )
{
  memdata_t *mem = calloc (1, sz + sizeof (memdata_t));
  
  if(!mem)
    return NULL;
  
  mem->mark = sweepMark;
  mem->deallocator = deallocator;
  mem->next = rootChain;
  DEBUG (3, ("palloc: %p->next -> %p", mem, mem->next));
  rootChain = mem;
  
  DEBUG (2, ("palloc: %p", mem + 1));
  
  if (!parent)
    return mem + 1;
  
  return pattach (mem + 1, parent
#ifdef MEMORY_LOCATION
        , loc
#endif
        );
}

void *prealloc(void *ptr, size_t sz)
{
  memdata_t *mem = (memdata_t*)ptr - 1, *res;
  memory_t *plink = mem->firstParent.link, *clink = mem->firstChild.link,
    *nlink;
  memdata_t *chain;
  
  res = realloc (mem, sz + sizeof (memdata_t));
  
  if (res == mem)
    return res + 1;
  
  DEBUG (2, ("prealloc: %p -> %p", mem + 1, res + 1));
  
  if (mem == rootChain)
    rootChain = res;
  else if (mem == memChain)
    memChain = res;
  else
  {
    for (chain = rootChain; chain && chain->next != mem; chain = chain->next)
      ;
    if (!chain)
      for (chain = memChain; DEXPR (chain &&) chain->next != mem; chain = chain->next)
	;
#ifdef DEBUG
    if (!chain)
      DEBUG (1, ("prealloc: %p not found in chain.", mem + 1));
#endif
    chain->next = res;
    DEBUG (3, ("prealloc: %p->next -> %p", chain, chain->next));
  }
  while(clink)
  {
    nlink = clink[pNextChild].link;
    if(res)
    {
      clink[pParent].data = res;
#ifdef MEMORY_LOCATION
      if (clink[pLocation].ptr)
      {
	void **newptr = (char*)res + ((char*)clink[pLocation].ptr - (char*)mem);
	
	if (*newptr == clink[pChild].data + 1)
	  clink[pLocation].ptr = newptr;
      }
#endif
    }
    else
      pfree(clink[pChild].data + 1, ptr);
    clink = nlink;
  }
  while(plink)
  {
    nlink = plink[pNextParent].link;
    if(res)
    {
      plink[pChild].data = res;
#ifdef MEMORY_LOCATION
      if (*plink[pLocation].ptr == mem + 1)
	*plink[pLocation].ptr = res + 1;
#endif
    }
#ifdef MEMORY_LOCATION
    else if (plink[pParent])
#else
    else
#endif
    {
      if (plink[pParent].data->firstChild.link == plink)
	plink[pParent].data->firstChild.link = plink[pNextChild].link;
      else
      {
	for (clink = plink[pParent].data->firstChild.link;
	     clink[pNextChild].link != plink; clink = clink[pNextChild].link)
	  ;
	clink[pNextChild].link = plink[pNextChild].link;
      }
      DEBUG (2, ("prealloc: unlink %p -> %p", plink[pParent], plink[pChild]));
      free (plink);
    }
    plink = nlink;
  }
  
  if(res)
    return res + 1;
  return NULL;
}

void *pattach(/*@null@*/void *child, void *parent
#ifdef MEMORY_LOCATION
      , /*@null@*/void **loc
#endif
      )
{
  memdata_t *pmem = (memdata_t*)parent - 1;
  memdata_t *cmem = (memdata_t*)child - 1;
  memory_t *mem;
  memdata_t *chain;
  
  if(!child)
    return NULL;
#ifdef MEMORY_LOCATION
  if (!parent && !loc)
    return child;
#else
  if (!parent)
    return child;
#endif
#ifdef DEBUG
#ifdef MEMORY_LOCATION
  if (parent)
#endif
  {
    if (pmem->isHashed)
    {
      DEBUG (1, ("pattach: parent %p is hashed (child %p)", parent, child));
      return NULL;
    }
    
    for(mem = cmem->firstParent.link; mem; mem = mem[pNextParent].link)
    {
      if(mem[pParent].data == pmem)
	DEBUG (2, ("pattach: %p -> %p already linked.", parent, child));
#ifdef MEMORY_LOCATION
      if (!mem[pParent].data && *mem[pLocation].ptr == child)
	DEBUG (2, ("pattach: %p is located root.", child));
#endif
    }
  }
#endif
  
  mem = malloc((size_t)(sizeof(memory_t) * pNumLinkLinks));
  if(mem)
  {
    DEBUG (2, ("pattach: linking %p -> %p", parent, child));
    mem[pNextParent].link = cmem->firstParent.link;
    mem[pNextChild].link = pmem->firstChild.link;
#ifdef MEMORY_LOCATION
    if (parent)
      mem[pParent].data = pmem;
    else
      mem[pParent].data = NULL;
#else
    mem[pParent].data = pmem;
#endif
    mem[pChild].data = cmem;
#ifdef MEMORY_LOCATION
    mem[pLocation].ptr = loc;
    if (loc)
      *loc = child;
#endif
    cmem->firstParent.link = mem;
    pmem->firstChild.link = mem;
  }
  else
    DEBUG (1, ("pattach: malloc failed for %p -> %p: %m", parent, child));
  
#ifdef MEMORY_LOCATION
  if (parent)
#else
  if (!mem || !mem[pNextParent].link)
#endif
  {
    if (cmem == rootChain)
    {
      DEBUG (2, ("pattach: Unrooting %p", child));
      rootChain = cmem->next;
      cmem->next = memChain;
      DEBUG (3, ("pattach: %p->next -> %p", cmem, cmem->next));
      memChain = cmem;
    }
    else
    {
      for (chain = rootChain; chain && chain->next != cmem; chain = chain->next)
	;
      if (chain)
      {
	DEBUG (2, ("pattach: Unrooting %p", child));
	chain->next = cmem->next;
	DEBUG (3, ("prealloc: %p->next -> %p", chain, chain->next));
	cmem->next = memChain;
	DEBUG (3, ("prealloc: %p->next -> %p", cmem, cmem->next));
	memChain = cmem;
      }
    }
  }
  
  return child;
}

void *padopt(void *child, void *oldparent, void *newparent
#ifdef MEMORY_LOCATION
      , void **newloc
#endif
      )
{
  memdata_t *opmem = (memdata_t*)oldparent - 1;
  memdata_t *npmem = (memdata_t*)newparent - 1;
  memdata_t *cmem = (memdata_t*)child - 1;
  memory_t *mem, *ccmem = NULL, *pcmem, *ppmem;
  int i;
  
  if (!child)
    return NULL;
  if (!newparent || npmem->isHashed)
    return child;
  
  pcmem = NULL;
  i = 0;
  for(mem = cmem->firstParent.link; mem && i < 3; mem = mem[pNextParent].link)
  {
    if(!(i & 1))
      ccmem = mem;
    if(mem[pParent].data == npmem)
      i |= 2;
    else if(mem[pParent].data == opmem)
      i |= 1;
    if(!(i & 1))
      pcmem = mem;
  }
  
  switch(i)
  {
  case 0:
    DEBUG (1, ("padopt: No old link %p -> %p.", oldparent, child));
    return pattach (child, newparent
#ifdef MEMORY_LOCATION
	  , newloc
#endif
          );
  case 3:
    DEBUG (1, ("padopt: Both %p and %p linked to %p.", oldparent, newparent, child));
    /* fallthrough */
  case 1:
    /* This is the one we _should_ get. */
    DEBUG (2, ("padopt: %p adopting %p from %p.", newparent, child, oldparent));
    if(ccmem == opmem->firstChild.link)
      opmem->firstChild.link = ccmem[pNextChild].link;
    else
    {
      for(ppmem = opmem->firstChild.link; DEXPR (ppmem[pNextChild].link &&)
		ppmem[pNextChild].link != ccmem; ppmem = ppmem[pNextChild].link)
	;
#ifdef DEBUG
      if(!ppmem[pNextChild].link)
      {
	DEBUG (1, ("padopt: Couldn't find link to child in old parent."));
	return child;
      }
#endif
      ppmem[pNextChild].link = ccmem[pNextChild].link;
    }
    ccmem[pNextChild].link = npmem->firstChild.link;
    ccmem[pParent].data = npmem;
#ifdef MEMORY_LOCATION
    ccmem[pLocation].ptr = newloc;
    if (newloc)
      *newloc = child;
#endif
    npmem->firstChild.link = ccmem;
    return child;
  default:
    DEBUG (1, ("padopt: %p is already parent of %p and %p isn't.", newparent, child, oldparent));
    return pattach (child, newparent
#ifdef MEMORY_LOCATION
	  , newloc
#endif
	  );
  }
}

void *prootify (void *ptr)
{
  memdata_t *mem = (memdata_t*)ptr - 1, *pmem;
  
  if (!ptr)
    return NULL;
  
  while (mem->firstParent.link)
  {
    DEBUG (2, ("prootify: %p has parent %p.", ptr, mem->firstParent.link[pParent].data + 1));
    pfree (ptr, mem->firstParent.link[pParent].data + 1);
  }
  
  if (mem == memChain)
    memChain = mem->next;
  else
  {
    pmem = memChain;
    while (pmem && pmem->next != mem)
      pmem = pmem->next;
    if (!pmem)
    {
#ifdef DEBUG
      if (mem == rootChain)
	pmem = mem;
      else
      {
	pmem = rootChain;
	while (pmem && pmem->next != mem)
	  pmem = pmem->next;
      }
      if (pmem)
      {
	DEBUG (1, ("prootify: %p already root.", ptr));
      }
      else
	DEBUG (1, ("prootify: %p not found in chain.", ptr));
#endif
      return ptr;
    }
    pmem->next = mem->next;
    DEBUG (3, ("prootify: %p->next -> %p.", pmem, pmem->next));
  }
  DEBUG (2, ("prootify: rooting %p.", ptr));
  mem->next = rootChain;
  DEBUG (3, ("prootify: %p->next -> %p.", mem, mem->next));
  rootChain = mem;
  return ptr;
}

void pfree(void *child, void *parent)
{
  memdata_t *cmem = (memdata_t*)child - 1;
  memdata_t *pmem = (memdata_t*)parent - 1;
  memory_t *mem, *pcmem, *ppmem;
  memhash_t *hash, *phash;
  memdata_t *chain;
  
  if(!child)
    return;
  
  pcmem = NULL;
  if (parent && parent != (void*)-1)
  {
#ifdef DEBUG
    if (pmem->isHashed)
    {
      DEBUG (1, ("pfree: Parent %p is hashed (child %p).", parent, child));
      return;
    }
#endif
    
    for (mem = cmem->firstParent.link; mem; mem = mem[pNextParent].link)
    {
      if(mem[pParent].data == pmem)
	break;
      pcmem = mem;
    }
    if (!mem)
    {
#ifdef DEBUG
      DEBUG (1, ("pfree: Parent %p not found in child %p.", parent, child));
      ppmem = NULL;
      for (mem = pmem->firstChild.link; mem; mem = mem[pNextChild].link)
      {
	if (mem[pChild].data == cmem)
	  break;
	ppmem = mem;
      }
      if (mem)
      {
	DEBUG (1, ("pfree: but child found in parent."));
	ppmem[pNextChild].link = mem[pNextChild].link;
	free (mem);
      }
#endif
      return;
    }
    
    if (mem == pmem->firstChild.link)
      pmem->firstChild.link = mem[pNextChild].link;
    else
    {
      for (ppmem = pmem->firstChild.link; DEXPR (ppmem[pNextChild].link &&)
	     ppmem[pNextChild].link != mem; ppmem = ppmem[pNextChild].link)
	;
#ifdef DEBUG
      if (!ppmem[pNextChild].link)
	DEBUG (1, ("pfree: Child %p not found in parent %p.", child, parent));
#endif
      ppmem[pNextChild].link = mem[pNextChild].link;
    }
    if (pcmem)
      pcmem[pNextParent].link = mem[pNextParent].link;
    else
      cmem->firstParent.link = mem[pNextParent].link;
    
    DEBUG (2, ("pfree: Unlinking %p -> %p.", parent, child));
    free(mem);
  }
  else
  {
    DEBUG (2, ("pfree: Really freeing %p.", child));
    if (cmem->isHashed)
    {
      hash = cmem->firstChild.hash;
      if (*hash->bucket && (*hash->bucket)->firstChild.hash == hash)
	*hash->bucket = hash->next;
      else
      {
	for (phash = (*hash->bucket)->firstChild.hash; phash->next &&
	       phash->next->firstChild.hash != hash;
	     phash = phash->next->firstChild.hash)
	  ;
#ifdef DEBUG
	if (!phash)
	  DEBUG (1, ("%p not found in bucket.", child));
#endif
	phash->next = hash->next;
	DEBUG (3, ("pfree: %p->next -> %p", phash, phash->next));
	free (cmem->firstChild.hash);
      }
    }
    else
    {
      while(cmem->firstChild.link)
	pfree (cmem->firstChild.link[pChild].data + 1, child);
    }
    while ((ppmem = cmem->firstParent.link))
    {
#ifdef MEMORY_LOCATION
      if (!ppmem[pParent].data)
      {
	cmem->firstParent.link = ppmem[pNextParent].link;
	free (ppmem);
      }
      else
#endif
	pfree (child, ppmem[pParent].data + 1);
    }
    if (parent != (void*)-1)
    {
      if (cmem == rootChain)
	rootChain = cmem->next;
      else if (cmem == memChain)
	memChain = cmem->next;
      else
      {
	for (chain = rootChain; chain && chain->next != cmem; chain = chain->next)
	  ;
	if (!chain)
	  for (chain = memChain; DEXPR (chain &&) chain->next != cmem; chain = chain->next)
	    ;
#ifdef DEBUG
	if (!chain)
	  DEBUG (1, ("%p not found in chain.", child));
#endif
	chain->next = cmem->next;
	DEBUG (3, ("pfree: %p->next -> %p", chain, chain->next));
      }
    }
    if (cmem->deallocator)
      cmem->deallocator (child);
    free(cmem);
  }
}

void *pchild(const void *parent, const void *prevChild)
{
  const memdata_t *const pmem = (memdata_t*)parent - 1;
  
  if (!parent)
    return NULL;
  
  if(prevChild)
  {
    const memdata_t *const cmem = (memdata_t*)prevChild - 1;
    const memory_t *mem;
    
    /*
     * Most nodes tend to have more children
     * than parents, so usually it should be faster to search for the
     * parent in the child's list.
     */
    for(mem = cmem->firstParent.link; mem; mem = mem[pNextParent].link)
      if(mem[pParent].data == pmem)
      {
	if(mem[pNextChild].link)
	  return mem[pNextChild].link[pChild].data + 1;
	return NULL;
      }
  }
  else if(pmem->firstChild.link)
    return pmem->firstChild.link[pChild].data + 1;
  return NULL;
}

int plinked (const void *child, const void *parent)
{
  const memdata_t *pmem = (memdata_t*)parent - 1;
  const memdata_t *cmem = (memdata_t*)child - 1;
  const memory_t *mem;
  
  if (!child || !parent)
    return 0;
  
  for (mem = cmem->firstParent.link; mem; mem = mem[pNextParent].link)
  {
    if(mem[pParent].data == pmem)
      return 1;
  }
  return 0;
}

int pnparents (const void *child)
{
  const memdata_t *cmem = (memdata_t*)child - 1;
  const memory_t *mem;
  int res;
  
  if (!child)
    return 0;
  
  res = 0;
  for (mem = cmem->firstParent.link; mem; mem = mem[pNextParent].link)
    res++;
  
  return res;
}

char *pstring(const char *str, void *parent)
{
  int hval = 0;
  const unsigned char *sp = (unsigned char*)str;
  memdata_t *mem;
  char *res;
  
  if (!str)
    return NULL;
  
  while (*sp)
  {
    hval += randVals[(*sp + ((char*)sp - str)) & 0xFF];
    sp++;
  }
  hval %= stringHashSize;
  
  mem = stringHash[hval];
  while (mem)
  {
    if (!strcmp ((char*)(mem + 1), str))
      return (char*)pattach (mem + 1, parent);
    mem = mem->firstChild.hash->next;
  }
  
  res = palloc ((char*)sp - str + 1, parent, NULL);
  
  if (res)
  {
    strcpy (res, str);
    mem = (memdata_t*)res - 1;
    mem->firstChild.hash = malloc (sizeof (memhash_t));
    if (mem->firstChild.hash)
    {
      mem->isHashed = 1;
      mem->firstChild.hash->bucket = &stringHash[hval];
      mem->firstChild.hash->next = stringHash[hval];
      DEBUG (3, ("pstring: %p->next -> %p", mem->firstChild.hash, mem->firstChild.hash->next));
      stringHash[hval] = mem;
    }
  }
  
  return res;
}