/*****************************************************************************\
* Copyright (c) 2004 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: events.c 1251 2005-03-06 22:24:29Z morth $ */

#include "system.h"

#include "events.h"

#include "utf8fs/memory.h"

/*
 * This is a red-black tree implementation for handling the file descriptors.
 */

typedef struct fdHandlerNode
{
  int fd;
  fdHandlerFun_t handler;
  void *user;
  struct fdHandlerNode *p, *l, *r;
  unsigned int red:1;
} fdHandlerNode_t;

static fdHandlerNode_t *readTree, *writeTree;
int numFds = 0;

extern int debug;

void events_init (void)
{
  pfree (readTree, NULL);
  readTree = NULL;
  pfree (writeTree, NULL);
  writeTree = NULL;
  numFds = 0;
  events_einit ();
}

int event_channels (void)
{
  return numFds;
}

static void print_tree (fdHandlerNode_t *x, int indent)
{
  if (x)
  {
    fprintf (stderr, "%*s%04d: %s\n", indent, "", x->fd, x->red? "red" : "black");
    print_tree (x->l, indent + 2);
    print_tree (x->r, indent + 2);
  }
  else
    fprintf (stderr, "%*snull: black\n", indent, "");
}

static fdHandlerNode_t *find_fd_or_parent (int fd, fdHandlerNode_t *x)
{
  if (!x)
    return NULL;
  while (x->fd != fd)
  {
    if (x->fd > fd)
    {
      if (!x->l)
	return x;
      x = x->l;
    }
    else
    {
      if (!x->r)
	return x;
      x = x->r;
    }
  }
  return x;
}

static void left_rotate (fdHandlerNode_t *node)
{
  fdHandlerNode_t *x;
  
  x = node->r;
  pfree (node->r, node);
  node->r = pattach (x->l, node);
  if (x->l)
    x->l->p = node;
  x->p = node->p;
  pattach (node, x);
  if (!node->p)
  {
    if (node == readTree)
      readTree = prootify (x);
    else
      writeTree = prootify (x);
  }
  else
  {
    pfree (node, node->p);
    if (node == node->p->l)
      node->p->l = pattach (x, node->p);
    else
      node->p->r = pattach (x, node->p);
  }
  x->l = node;
  node->p = x;
}

static void right_rotate (fdHandlerNode_t *node)
{
  fdHandlerNode_t *x;
  
  x = node->l;
  pfree (node->l, node);
  node->l = pattach (x->r, node);
  if (x->r)
    x->r->p = node;
  x->p = node->p;
  pattach (node, x);
  if (!node->p)
  {
    if (node == readTree)
      readTree = prootify (x);
    else
      writeTree = prootify (x);
  }
  else
  {
    pfree (node, node->p);
    if (node == node->p->l)
      node->p->l = pattach (x, node->p);
    else
      node->p->r = pattach (x, node->p);
  }
  x->r = node;
  node->p = x;
}

static void insert_node (fdHandlerNode_t *node, fdHandlerNode_t *p)
{
  node->p = p;
  
  if (node->fd < p->fd)
    p->l = node;
  else
    p->r = node;
  
  node->red = 1;
  while (node->p->red)
  {
    if (node->p == node->p->p->l)
    {
      p = node->p->p->r;
      if (p && p->red)
      {
	p->red = node->p->red = 0;
	node = p->p;
	if (!node->p)
	  break;
	else
	  node->red = 1;
      }
      else
      {
	if (node == node->p->r)
	{
	  node = node->p;
	  left_rotate (node);
	}
	node->p->red = 0;
	node->p->p->red = 1;
	right_rotate (node->p->p);
      }
    }
    else
    {
      p = node->p->p->l;
      if (p && p->red)
      {
	p->red = node->p->red = 0;
	node = p->p;
	if (!node->p)
	  break;
	else
	  node->red = 1;
      }
      else
      {
	if (node == node->p->l)
	{
	  node = node->p;
	  right_rotate (node);
	}
	node->p->red = 0;
	node->p->p->red = 1;
	left_rotate (node->p->p);
      }
    }
  }
}

static fdHandlerNode_t *insert_read_node (int fd, fdHandlerFun_t handler, void *user, fdHandlerNode_t *p)
{
  fdHandlerNode_t *node = palloc (sizeof (fdHandlerNode_t), p, NULL);
  
  node->fd = fd;
  node->handler = handler;
  node->user = user;
  
  if (p)
    insert_node (node, p);
  else
    readTree = node;
  numFds++;
  if (debug >= 2)
    print_tree (readTree, 0);
  return node;
}

static fdHandlerNode_t *insert_write_node (int fd, fdHandlerFun_t handler, void *user, fdHandlerNode_t *p)
{
  fdHandlerNode_t *node = palloc (sizeof (fdHandlerNode_t), p, NULL);
  
  node->fd = fd;
  node->handler = handler;
  node->user = user;
  
  if (p)
    insert_node (node, p);
  else
    writeTree = node;
  numFds++;
  if (debug >= 2)
    print_tree (writeTree, 0);
  return node;
}

static void delete_fd_node (fdHandlerNode_t *node)
{
  fdHandlerNode_t *x, *y, *p;
  int r;
  
  if (!node->l || !node->r)
  {
    x = node;
    if (x->l)
      y = x->l;
    else
      y = x->r;
    
  }
  else
  {
    x = node->r;
    while (x->l)
      x = x->l;
    
    /*
     * Since we need to delete the node sent in let node and x
     * switch places.
     */
    if (node->p)
    {
      if (node == node->p->l)
	node->p->l = pattach (x, node->p);
      else
	node->p->r = pattach (x, node->p);
      pfree (node, node->p);
    }
    else if (node == readTree)
      readTree = prootify (x);
    else
      writeTree = prootify (x);
    y = node->p;
    if (x->p == node)
      node->p = x;
    else
      node->p = x->p;
    x->p = y;
    
    y = x->r;
    x->l = pattach (node->l, x);
    x->l->p = x;
    if (node->r == x)
      x->r = pattach (node, x);
    else
    {
      x->r = pattach (node->r, x);
      x->r->p = x;
      node->p->l = node;
    }
    r = x->red;
    x->red = node->red;
    node->red = r;
    
    x = node;
  }
  p = x->p;
  if (y)
    y->p = p;
  pfree (x, p);
  if (!p)
  {
    if (x == writeTree)
      writeTree = prootify (y);
    else
      readTree = prootify (y);
    if (y)
      y->red = 0;
  }
  else
  {
    if (x == p->l)
      p->l = pattach (y, p);
    else
      p->r = pattach (y, p);
    if (!x->red)
    {
      while (!y || (y->p && !y->red))
      {
	if (y == p->l)
	{
	  x = p->r;
	  if (x->red)
	  {
	    x->red = 0;
	    p->red = 1;
	    left_rotate (p);
	    x = p->r;
	  }
	  if (!x->r || !x->r->red)
	  {
	    if (!x->l || !x->l->red)
	    {
	      x->red = 1;
	      y = p;
	      p = p->p;
	      continue;
	    }
	    x->l->red = 0;
	    x->red = 1;
	    right_rotate (x);
	    x = p->r;
	  }
	  x->red = p->red;
	  p->red = x->r->red = 0;
	  left_rotate (p);
	  y = NULL;
	  break;
	}
	else
	{
	  x = p->l;
	  if (x->red)
	  {
	    x->red = 0;
	    p->red = 1;
	    right_rotate (p);
	    x = p->l;
	  }
	  if (!x->l || !x->l->red)
	  {
	    if (!x->r || !x->r->red)
	    {
	      x->red = 1;
	      y = p;
	      p = p->p;
	      continue;
	    }
	    x->r->red = 0;
	    x->red = 1;
	    left_rotate (x);
	    x = p->l;
	  }
	  x->red = p->red;
	  p->red = x->l->red = 0;
	  right_rotate (p);
	  y = NULL;
	  break;
	}
      }
      if (y)
	y->red = 0;
    }
  }
  numFds--;
}

int add_read_fd (int fd, fdHandlerFun_t handler, void *user)
{
  fdHandlerNode_t *node;
  
  if (!handler)
  {
    errno = EINVAL;
    return -1;
  }
  
  node = find_fd_or_parent (fd, readTree);
  if (node && node->fd == fd)
  {
    node->handler = handler;
    node->user = user;
    return 0;
  }
  node = insert_read_node (fd, handler, user, node);
  if (!node)
    return -1;
  
  if (events_earf (fd, node))
  {
    delete_fd_node (node);
    if (debug >= 2)
      print_tree (readTree, 0);
    return -1;
  }
  return 0;
}

int add_write_fd (int fd, fdHandlerFun_t handler, void *user)
{
  fdHandlerNode_t *node;
  
  if (!handler)
  {
    errno = EINVAL;
    return -1;
  }
  
  node = find_fd_or_parent (fd, writeTree);
  if (node && node->fd == fd)
  {
    node->handler = handler;
    node->user = user;
    return 0;
  }
  node = insert_write_node (fd, handler, user, node);
  if (!node)
    return -1;
  
  if (events_eawf (fd, node))
  {
    delete_fd_node (node);
    if (debug >= 2)
      print_tree (writeTree, 0);
    return -1;
  }
  return 0;
}

void remove_read_fd (int fd)
{
  fdHandlerNode_t *node;
  
  node = find_fd_or_parent (fd, readTree);
  if (node && node->fd == fd)
  {
    delete_fd_node (node);
    if (debug >= 2)
      print_tree (readTree, 0);
    events_errf (fd);
  }
}

void remove_write_fd (int fd)
{
  fdHandlerNode_t *node;
  
  node = find_fd_or_parent (fd, writeTree);
  if (node && node->fd == fd)
  {
    delete_fd_node (node);
    if (debug >= 2)
      print_tree (writeTree, 0);
    events_erwf (fd);
  }
}

int events_run_handler (int fd, int isWrite, int urgent)
{
  fdHandlerNode_t *node;
  
  node = find_fd_or_parent (fd, isWrite? writeTree : readTree);
  if (node && node->fd == fd)
    return node->handler (fd, node->user, urgent);
  return 0;
}

int events_run_data (void *data, int urgent)
{
  fdHandlerNode_t *node = data;
  
  return node->handler (node->fd, node->user, urgent);
}