wait_for_graph.c

Go to the documentation of this file.

/*
 * Copyright 2008 Search Solution Corporation
 * Copyright 2016 CUBRID Corporation
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 *
 */

/*
 * wait_for_graph.c - management of Wait-For-Graph
 */

#ident "$Id$"

#if defined(ENABLE_UNUSED_FUNCTION)
#include "config.h"

#include <stddef.h>
#include <assert.h>

#include "error_manager.h"
#include "memory_alloc.h"
#include "wait_for_graph.h"
#include "critical_section.h"
#if defined(SERVER_MODE)
#include "connection_error.h"
#endif /* SERVER_MODE */

/* Prune the number of found cycles in a cycle group */
static const int WFG_PRUNE_CYCLES_IN_CYCLE_GROUP = 10;
static const int WFG_MAX_CYCLES_TO_REPORT = 100;

/* status of a node in WFG */
typedef enum
{
  WFG_NOT_VISITED,
  WFG_ON_STACK,
  WFG_OFF_STACK,
  WFG_RE_ON_STACK,
  WFG_ON_TG_CYCLE
} WFG_STACK_STATUS;

/* structure of an edge in WFG */
typedef struct wfg_edge WFG_EDGE;
struct wfg_edge
{
  int waiter_tran_index;    /* index of waiter transaction */
  int holder_tran_index;    /* index of holder transaction */
  struct wfg_edge *next_holder_edge_p;  /* pointer to next holder */
  struct wfg_edge *next_waiter_edge_p;  /* pointer to next waiter */
};

/* structure of a node in WFG */
typedef struct wfg_node WFG_NODE;
struct wfg_node
{
  WFG_STACK_STATUS status;
  int cycle_group_no;       /* Group no in a cycle */
  /*
   * Fun to call to solve a cycle. If NULL, the transaction will be aborted.
   * Assumption a transaction can be waiting for many transaction,
   * but it can only be waiting in one place.
   */
  int (*cycle_fun) (int tran_index, void *args);
  void *args;           /* Arguments to be passed to cycle_fun */
  WFG_EDGE *first_holder_edge_p;    /* pointer to first holder */
  WFG_EDGE *last_holder_edge_p; /* pointer to last holder */
  WFG_EDGE *first_waiter_edge_p;    /* pointer to first waiter */
  WFG_EDGE *last_waiter_edge_p; /* pointer to last waiter */
};

/* WFG stack to implement non-recursive DFS */
typedef struct wfg_stack WFG_STACK;
struct wfg_stack
{
  int wait_tran_index;      /* current wait node */
  WFG_EDGE *current_holder_edge_p;  /* current holder edge */
};

/* structure to maintain transaction index list for TG table */
typedef struct wfg_trans_list WFG_TRANS_LIST;
struct wfg_trans_list
{
  int tran_index;       /* transaction index */
  struct wfg_trans_list *next;  /* next transaction */
};

/* structure of transaction group table entry */
typedef struct wfg_tran_group WFG_TRAN_GROUP;
struct wfg_tran_group
{
  int num_holders;
  int num_waiters;
  WFG_TRANS_LIST *holder_tran_list_p;   /* transaction group */
  WFG_TRANS_LIST *waiter_tran_list_p;   /* trans waiting for the TG */
};

static WFG_NODE *wfg_Nodes = NULL;  /* ptr to WFG nodes */
static int wfg_Total_nodes = 0; /* # of nodes */
static int wfg_Total_edges = 0; /* # of edges */
static int wfg_Total_waiters = 0;   /* # of waiters */

/* Transaction group table */
static WFG_TRAN_GROUP *wfg_Tran_group = NULL;
static int wfg_Total_tran_groups = 0;

static int wfg_initialize_node (WFG_NODE * node_p);
static int wfg_free_group_list (void);

static int wfg_push_stack (WFG_STACK ** top_p, int node);
static int wfg_pop_stack (WFG_STACK ** top_p, WFG_STACK ** bottom_p);
static int wfg_internal_detect_cycle (THREAD_ENTRY * thread_p, WFG_CYCLE_CASE * cycle_case_p,
                      WFG_CYCLE ** list_cycles_p, const int max_cycles_in_cycle_group,
                      const int max_cycles);
static int wfg_detect_ordinary_cycle (THREAD_ENTRY * thread_p, WFG_CYCLE_CASE * cycle_case_p,
                      WFG_CYCLE ** list_cycles_p, const int max_cycles_in_group, const int max_cycles);
static int wfg_add_waiters_of_tg (int *smallest_onstack, int holder_node, int tg_index);
static int wfg_add_waiters_normal_wfg (int *smallest_onstack, int node_index);
static int wfg_get_all_waiting_and_add_waiter (bool * all_waiting, bool * add_waiter, int tg_index);
static WFG_CYCLE *wfg_detect_tran_group_cycle_internal (WFG_CYCLE_CASE * cycle_case_p, WFG_TRANS_LIST * w_tran_list_p,
                            bool add_waiter, int tg_index, int num_tran_groups_holders);
static int wfg_detect_tran_group_cycle (THREAD_ENTRY * thread_p, WFG_CYCLE_CASE * cycle_case_p,
                    WFG_CYCLE ** list_cycles);

static int wfg_dump_given_cycles (FILE * out_fp, WFG_CYCLE * list_cycles_p);
static void wfg_dump_holder_waiter (FILE * out_fp, int node_index);
static void wfg_dump_holder_waiter_of_tran_group (FILE * out_fp, int group_index);

#if defined(WFG_DEBUG)
static int wfg_valid_tran_index (const int holder_index, const int holder_tran_index, const int waiter_tran_index);
static int check_duplication_holders (const int holder_index, const int *holder_tran_indices, const int num_holders,
                      const int waiter_tran_index);
static int wfg_check_insert_out_edges (const int waiter_tran_index, int num_holders, const int *holder_tran_indeces);
static int wfg_check_remove_out_edges (const int waiter_tran_index, int num_holders, const int *holder_tran_indeces);
#endif /* WFG_DEBUG */

static int wfg_allocate_edges (WFG_EDGE ** first_edge_p, WFG_EDGE ** last_edge_p, const int *holder_tran_indices,
                   const int num_holders, const int waiter_tran_index);
static int wfg_link_edge_holders_waiter_list (WFG_EDGE * first_edge_p, WFG_EDGE * last_edge_p,
                          const int waiter_tran_index);
static int wfg_remove_waiter_list_of_holder_edge (WFG_NODE * node_p, WFG_EDGE ** holder_p);

/*
 * TODO : M2, error check
 * wfg_push_stack : push operation on WFG stack
 *
 * return : NO_ERROR
 *
 *   top_p(IN/OUT) :
 *   node(IN)      :
 */
static int
wfg_push_stack (WFG_STACK ** top_p, int node)
{
  (*top_p)++;
  (*top_p)->wait_tran_index = node;
  (*top_p)->current_holder_edge_p = wfg_Nodes[node].first_holder_edge_p;

  return NO_ERROR;
}

/*
 * wfg_pop_stack : pop operation on WFG stack
 *
 * return : NO_ERROR
 *
 *   top_p(IN/OUT) :
 *   bottom(IN)    :
 */
static int
wfg_pop_stack (WFG_STACK ** top_p, WFG_STACK ** bottom_p)
{
  (*top_p)--;
  if ((*top_p) - (*bottom_p) < 0)
    {
      return ER_FAILED;
    }
  (*top_p)->current_holder_edge_p = (*top_p)->current_holder_edge_p->next_holder_edge_p;

  return NO_ERROR;
}

/*
 * wfg_initialize_node : Initialize WFG_NODE
 *
 * returns : NO_ERROR if all OK, ER_ status otherwise
 *
 *   node_p(out) :
 *
 * Note:
 */
static int
wfg_initialize_node (WFG_NODE * node_p)
{
  if (node_p == NULL)
    {
      return ER_FAILED;
    }

  node_p->cycle_group_no = -1;
  node_p->cycle_fun = NULL;
  node_p->args = NULL;
  node_p->first_holder_edge_p = NULL;
  node_p->last_holder_edge_p = NULL;
  node_p->first_waiter_edge_p = NULL;
  node_p->last_waiter_edge_p = NULL;

  return NO_ERROR;
}

/*
 * wfg_alloc_nodes : Initialize or expand WFG to have num_trans.
 *
 * returns : NO_ERROR if all OK, ER_ status otherwise
 *
 *   num_trans(IN) : number of transactions
 *
 * NOTE: num_trans should not be decreased in succeeding calls, otherwise,
 *       behavior undefined.
 */
int
wfg_alloc_nodes (THREAD_ENTRY * thread_p, const int num_trans)
{
  WFG_NODE *temp_node_p;    /* a temporary pointer to WFG nodes */
  int i;            /* loop counter */
  int error_code = NO_ERROR;

#if defined(WFG_DEBUG)
  if (num_trans < 0)
    {
      er_log_debug (ARG_FILE_LINE, "wfg_alloc: num_trans = %d should NOT be" " negative. Will assume 10\n" num_trans);
      num_trans = 10;
    }
#endif /* WFG_DEBUG */

  if (csect_enter (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      return ER_FAILED;
    }

  /*
   * allocate new nodes
   */
  if (wfg_Nodes == NULL)
    {
      temp_node_p = (WFG_NODE *) malloc (sizeof (WFG_NODE) * num_trans);
      if (temp_node_p == NULL)
    {
      er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, sizeof (WFG_NODE) * num_trans);
      error_code = ER_OUT_OF_VIRTUAL_MEMORY;
      goto end;
    }
    }
  else
    {
      if (num_trans < wfg_Total_nodes)
    {
      error_code = NO_ERROR;
      goto end;
    }
      temp_node_p = (WFG_NODE *) realloc (wfg_Nodes, sizeof (WFG_NODE) * num_trans);
      if (temp_node_p == NULL)
    {
      er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, sizeof (WFG_NODE) * num_trans);
      error_code = ER_OUT_OF_VIRTUAL_MEMORY;
      goto end;
    }
    }

  /* initialize newly allocated nodes */
  for (i = wfg_Total_nodes; i < num_trans; i++)
    {
      error_code = wfg_initialize_node (temp_node_p + i);
      if (error_code != NO_ERROR)
    {
      goto end;
    }
    }

  wfg_Total_nodes = num_trans;
  wfg_Nodes = temp_node_p;

end:
  csect_exit (thread_p, CSECT_WFG);
  return error_code;
}

/*
 * wfg_free_group_list :
 *
 * returns : NO_ERROR if all OK, ER_ status otherwise
 *
 * Note:
 */
static int
wfg_free_group_list (void)
{
  WFG_TRANS_LIST *tran_list_p, *temp_p; /* trans list pointer */
  int i;

  /* free transaction group list */
  for (i = 0; i < wfg_Total_tran_groups; i++)
    {
      for (tran_list_p = wfg_Tran_group[i].holder_tran_list_p; tran_list_p != NULL;)
    {           /* free holders */
      temp_p = tran_list_p;
      tran_list_p = tran_list_p->next;
      free_and_init (temp_p);
    }
      for (tran_list_p = wfg_Tran_group[i].waiter_tran_list_p; tran_list_p != NULL;)
    {           /* free waiters */
      temp_p = tran_list_p;
      tran_list_p = tran_list_p->next;
      free_and_init (temp_p);
    }
    }

  return NO_ERROR;
}

/*
 * wfg_free_nodes : Finish WFG module. The WFG area is freed.
 *
 * returns : NO_ERROR if all OK, ER_ status otherwise
 *
 */
int
wfg_free_nodes (THREAD_ENTRY * thread_p)
{
  WFG_EDGE *edge_p;     /* pointer to a WFG edge */
  void *temp_p;         /* temporary pointer */
  int i;            /* loop counter */
  int error_code = NO_ERROR;

  if (csect_enter (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      return ER_FAILED;
    }

  if (wfg_Total_nodes > 0)
    {
      /* for each node */
      for (i = 0; i < wfg_Total_nodes; i++)
    {
      /* for each edge */
      for (edge_p = wfg_Nodes[i].first_holder_edge_p; edge_p != NULL;)
        {
          temp_p = edge_p;
          edge_p = edge_p->next_holder_edge_p;
          free_and_init (temp_p);
        }
    }
      free_and_init (wfg_Nodes);
      wfg_Total_nodes = wfg_Total_edges = wfg_Total_waiters = 0;
    }

  /* free transaction group list */
  error_code = wfg_free_group_list ();

  csect_exit (thread_p, CSECT_WFG);
  return error_code;
}

#if defined(WFG_DEBUG)
static int
wfg_check_insert_out_edges (const int waiter_tran_index, int num_holders, const int *holder_tran_indeces)
{
  int i;            /* loop counter */
  int error_code = NO_ERROR;

  /*
   * Check for valid arguments
   */
  if (waiter_tran_index < 0 || waiter_tran_index > wfg_Total_nodes - 1)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_insert_out_edges: value" " waiter_tran_index = %d should be between 0 and %d\n"
            " ** OPERATION HAS BEEN IGNORED **\n", waiter_tran_index, wfg_Total_nodes - 1);
      error_code = ER_FAILED;
      goto end;
    }

  for (i = 0; i < num_holders; i++)
    {
      /* Verify for incorrect input */
      error_code = wfg_valid_tran_index (i, holder_tran_indices[i], waiter_tran_index);
      if (error_code != NO_ERROR)
    {
      goto end;
    }

      /* check duplication of holders */
      error_code = check_duplication_holders (i, holder_tran_indeces);
      if (error_code != NO_ERROR)
    {
      goto end;
    }
    }

end:
  return error_code;
}
#endif /* WFG_DEBUG */

/*
 * wfg_insert_out_edges : add edges from the node specified by waiter
 *                        to each node in holders.
 *
 * returns : NO_ERROR if all OK, ER_ status otherwise
 *
 *   waiter_tran_index(IN)   : index of transaction which is waiting
 *   num_holders(IN)         : # of transactions(holders) being waited for
 *   holder_tran_indices(IN) : array of holders
 *   cycle_resolution_fn(IN) : ptr to cycle resoultion function
 *   args(IN)                : arguments of cycle resolution function
 *
 * NOTE: indexes in waiter, holders should fall into the interval
 *       [0, num_trans of the most recent wfg_alloc_nodes()]
 *       Otherwise, behavior is undefined
 *
 */
int
wfg_insert_out_edges (THREAD_ENTRY * thread_p, const int waiter_tran_index, int num_holders,
              const int *holder_tran_indeces, int (*cycle_resolution_fn) (int tran_index, void *args),
              void *args)
{
  WFG_EDGE *first_edge_p;   /* pointer to the first of allocated edges */
  WFG_EDGE *last_edge_p;    /* pointer to the last of allocated edges */
  int error_code = NO_ERROR;

  if (num_holders < 0)
    {
      num_holders = 0;
    }

  if (csect_enter (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      return ER_FAILED;
    }

#if defined(WFG_DEBUG)
  error_code = wfg_check_insert_out_edges (waiter_tran_index, num_holders, holder_tran_indeces);
  if (error_code != NO_ERROR)
    {
      goto end;
    }
#endif /* WFG_DEBUG */


  /* allocate the edges */
  error_code = wfg_allocate_edges (&first_edge_p, &last_edge_p, holder_tran_indeces, num_holders, waiter_tran_index);
  if (error_code != NO_ERROR)
    {
      goto end;
    }
  /*
   * Save the function to call in the case of a cycle.
   */
  wfg_Nodes[waiter_tran_index].cycle_fun = cycle_resolution_fn;
  wfg_Nodes[waiter_tran_index].args = args;

  error_code = wfg_link_edge_holders_waiter_list (first_edge_p, last_edge_p, waiter_tran_index);
  if (error_code != NO_ERROR)
    {
      goto end;
    }

  wfg_Total_edges += num_holders;

end:
  csect_exit (thread_p, CSECT_WFG);

  return error_code;
}

#if defined(WFG_DEBUG)
/*
 * wfg_valid_tran_index :
 *
 * returns : NO_ERROR if all OK, ER_ status otherwise
 *
 *   holder_index(IN)            :
 *   holder_transaction_index(IN) :
 *   waiter_transaction_index(IN) :
 */
static int
wfg_valid_tran_index (const int holder_index, const int holder_tran_index, const int waiter_tran_index)
{
  if (holder_tran_index < 0 || holder_tran_index > wfg_Total_nodes - 1)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_insert_out_edges: value" " holder_tran_indices[%d] = %d should be between 0 and %d\n"
            " ** OPERATION HAS BEEN IGNORED **\n", holder_index, holder_tran_index, wfg_Total_nodes - 1);

      return ER_FAILED;
    }
  if (holder_tran_index == waiter_tran_index)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_insert_out_edges: value" " holder_tran_indices[%d] = %d is equal to waiter_tran_index = %d\n"
            " ** OPERATION HAS BEEN IGNORED **\n", holder_index, holder_tran_index, waiter_tran_index);

      return ER_FAILED;
    }

  return NO_ERROR;
}

/*
 * check_duplication_holders :
 *
 * returns : NO_ERROR if all OK, ER_ status otherwise
 *
 *   holder_index(IN)        :
 *   holder_tran_indices(IN) :
 *   num_holders(IN)         :
 *   waiter_tran_index(IN)   :
 *
 */
static int
check_duplication_holders (const int holder_index, const int *holder_tran_indices, const int num_holders,
               const int waiter_tran_index)
{
  WFG_EDGE *edge_p;
  int i;

  for (i = holder_index + 1; i < num_holders; i++)
    {
      if (holder_tran_indices[holder_index] == holder_tran_indices[i])
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_insert_outedges: value holder_tran_indices[%d] = %d is"
            " duplcated with holder_tran_indices[%d] = %d\n" "** OPERATION HAS BEEN IGNORED **\n",
            holder_index, holder_tran_indices[holder_index], i, holder_tran_indices[i]);
      return ER_FAILED;
    }
    }

  for (edge_p = wfg_Nodes[waiter_tran_index].first_holder_edge_p; edge_p != NULL; edge_p = edge_p->next_holder_edge_p)
    {
      if (holder_tran_indices[holder_index] == edge_p->holder_tran_index)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_insert_outedges: value holder_tran_indices[%d] = %d" " is already a holders\n"
            " ** OPERATION HAS BEEN IGNORED **\n", holder_index, holder_tran_indices[holder_index]);
      return ER_FAILED;
    }
    }

  return NO_ERROR;
}
#endif /* WFG_DEBUG */

/*
 * wfg_allocate_edges  : Allocate and initialize edges to have num_holders
 *
 * returns : NO_ERROR if all OK, ER_ status otherwise
 *
 *   first_edge_p(OUT)      : pointer to the first of allocated edges
 *   last_edge_p(OUT)       : pointer to the last of allocated edges
 *   holder_tran_indices(IN): array of holders
 *   num_holders(IN)        : # of transactions(holders)
 *   waiter_tran_index(IN)  : index of transaction which is waiting
 *
 */
static int
wfg_allocate_edges (WFG_EDGE ** first_edge_p, WFG_EDGE ** last_edge_p, const int *holder_tran_indices,
            const int num_holders, const int waiter_tran_index)
{
  WFG_EDGE *edge_p;
  WFG_EDGE *temp_p;
  int i;

  *first_edge_p = *last_edge_p = NULL;

  for (i = num_holders - 1; i >= 0; i--)
    {
      edge_p = (WFG_EDGE *) malloc (sizeof (WFG_EDGE));
      if (edge_p == NULL)
    {
      /* Deallocate all edges and return a failure */
      while (*first_edge_p != NULL)
        {
          temp_p = *first_edge_p;
          *first_edge_p = (*first_edge_p)->next_holder_edge_p;
          free_and_init (temp_p);
        }

      er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, sizeof (WFG_EDGE));
      return ER_OUT_OF_VIRTUAL_MEMORY;
    }

      /*
       * Note that we are adding the edges in the reverse order to avoid
       * manupulating several pointers.
       */
      edge_p->waiter_tran_index = waiter_tran_index;
      edge_p->holder_tran_index = holder_tran_indices[i];
      edge_p->next_holder_edge_p = *first_edge_p;
      edge_p->next_waiter_edge_p = NULL;

      *first_edge_p = edge_p;
      if (*last_edge_p == NULL)
    {
      *last_edge_p = *first_edge_p;
    }
    }

  return NO_ERROR;
}

/*
 * wfg_link_edge_holders_waiter_list : Link the list to the waiter as
 *                           its holders and link each edge to holders'
 *                           waiter list
 *
 * returns : NO_ERROR if all OK, ER_ status otherwise
 *
 *   first_edge_p(IN)      : pointer to the first of allocated edges
 *   last_edge_p(IN)       : pointer to the last of allocated edges
 *   waiter(IN)            : index of transaction which is waiting
 *
 */
static int
wfg_link_edge_holders_waiter_list (WFG_EDGE * first_edge_p, WFG_EDGE * last_edge_p, const int waiter)
{
  WFG_EDGE *edge_p;
  int holder;

  /*
   * Link the list to the waiter as its holders
   */
  if (first_edge_p != NULL)
    {
      if (wfg_Nodes[waiter].last_holder_edge_p == NULL)
    {
      /* First holder */
      wfg_Nodes[waiter].first_holder_edge_p = first_edge_p;
      wfg_Total_waiters++;
    }
      else
    {
      wfg_Nodes[waiter].last_holder_edge_p->next_holder_edge_p = first_edge_p;
    }
      wfg_Nodes[waiter].last_holder_edge_p = last_edge_p;
    }

  /*
   * Link each edge to holders' waiter list
   */
  for (edge_p = first_edge_p; edge_p; edge_p = edge_p->next_holder_edge_p)
    {
      holder = edge_p->holder_tran_index;
      if (wfg_Nodes[holder].last_waiter_edge_p == NULL)
    {
      /* First waiter */
      wfg_Nodes[holder].first_waiter_edge_p = edge_p;
    }
      else
    {
      wfg_Nodes[holder].last_waiter_edge_p->next_waiter_edge_p = edge_p;
    }
      wfg_Nodes[holder].last_waiter_edge_p = edge_p;
    }

  return NO_ERROR;
}

#if defined(WFG_DEBUG)
static int
wfg_check_remove_out_edges (const int waiter_tran_index, const int num_holders, const int *holder_tran_indices_p)
{
  int error_code = NO_ERROR;
  int i;
  WFG_EDGE *edge_p;     /* An edge */

  /*
   * Check for valid arguments
   */
  if (waiter_tran_index < 0 || waiter_tran_index > wfg_Total_nodes - 1)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_remove_outedges: value waiter = %d should"
            " be between 0 and %d\n ** OPERATION HAS BEEN IGNORED **\n", waiter_tran_index,
            wfg_Total_nodes - 1);

      error_code = ER_FAILED;
      goto end;
    }

  for (i = 0; i < num_holders; i++)
    {
      if (holder_tran_indices_p[i] < 0 || holder_tran_indices_p[i] > wfg_Total_nodes - 1)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_remove_outedges: value holder[%d] = %d"
            " should be between 0 and %d\n ** OPERATION HAS BEEN" " IGNORED **", i, htran_indices_p[i],
            wfg_Total_nodes - 1);
      error_code = ER_FAILED;
      goto end;
    }
      for (edge_p = wfg_Nodes[waiter_tran_index].first_holder_edge_p; edge_p != NULL;
       edge_p = edge_p->next_holder_edge_p)
    {
      if (holder_tran_indices_p[i] == edge_p->holder_tran_index)
        {
          er_log_debug (ARG_FILE_LINE,
                "wfg_remove_outedges:" " value holder[%d] = %d is NOT holder of waiter = %d\n"
                " ** THE HOLDER SKIPPED **", i, htran_indices_p[i], waiter_tran_index);
        }
    }
    }

  return error_code;
}
#endif /* WFG_DEBUG */

/*
 * wfg_remove_waiter_list_of_holder_edge :
 *
 * returns : NO_ERROR if all OK, ER_ status otherwise
 *
 *   node_p(in/out):
 *   holder_p(in/out): pointer to prev. holder edge
 *
 */
static int
wfg_remove_waiter_list_of_holder_edge (WFG_NODE * node_p, WFG_EDGE ** holder_p)
{
  WFG_EDGE **waiter_p;      /* pointer to prev. waiter edge */

  for (waiter_p = &(node_p->first_waiter_edge_p); *waiter_p != NULL; waiter_p = &((*waiter_p)->next_waiter_edge_p))
    {
      if (*waiter_p == *holder_p)
    {
      /* It has been found. Now remove it from the waiter list */
      *waiter_p = (*waiter_p)->next_waiter_edge_p;
      if (*waiter_p == NULL)
        {
          /* the last waiter of this holder edge */
          if (node_p->first_waiter_edge_p == NULL)
        {
          /* No more waiters */
          node_p->last_waiter_edge_p = NULL;
        }
          else
        {
          /* There are still waiters */
          node_p->last_waiter_edge_p =
            (WFG_EDGE *) ((char *) waiter_p - offsetof (WFG_EDGE, next_waiter_edge_p));
        }
        }
      break;
    }
    }

  return NO_ERROR;
}

/*
 * wfg_remove_out_edges : remove edges from the node waiter_tran_index
 *              to each node in holders.
 *              If num_holders <= 0 or holders is NULL, it removes all
 *              outgoing edges of the node waiter_tran_index.
 *
 * returns : NO_ERROR if all OK, ER_ status otherwise
 *
 *   waiter_tran_index(IN)    : index of transaction which is waiting
 *   num_holders(IN)          : # of transactions(holders)
 *   holder_tran_indices_p(IN): array of holders
 *
 * NOTE: indexes in waiter, holders should fall into the interval
 *       [0, num_trans of the most recent wfg_alloc_nodes()]
 *       Otherwise, behavior is undefined
 *
 */
int
wfg_remove_out_edges (THREAD_ENTRY * thread_p, const int waiter_tran_index, const int num_holders,
              const int *holder_tran_indices_p)
{
  int i;            /* loop counter */
  WFG_EDGE *edge_p;     /* An edge */
  WFG_EDGE **prev_holder_p; /* pointer to prev. holder edge */
  int error_code = NO_ERROR;

  if (csect_enter (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      return ER_FAILED;
    }

#if defined(WFG_DEBUG)
  error_code = wfg_check_remove_out_edges (waiter_tran_index, num_holders, holder_tran_indices_p);
  if (error_code != NO_ERROR)
    {
      goto end;
    }
#endif /* WFG_DEBUG */
  for (prev_holder_p = &(wfg_Nodes[waiter_tran_index].first_holder_edge_p); *prev_holder_p != NULL;)
    {
      /* check if the edge is in the given edges */
      if (num_holders > 0 && holder_tran_indices_p != NULL)
    {
      for (i = 0; i < num_holders; i++)
        {
          if (holder_tran_indices_p[i] == (*prev_holder_p)->holder_tran_index)
        {
          break;
        }
        }
    }
      else
    {
      i = num_holders - 1;
    }

      if (i < num_holders)
    {
      /*
       * It was found, remove previous holder from the list of waiters
       * and the holder list.
       */

      /* Remove from waiter list of the holder of edge */
      error_code =
        wfg_remove_waiter_list_of_holder_edge (&wfg_Nodes[(*prev_holder_p)->holder_tran_index], prev_holder_p);
      if (error_code != NO_ERROR)
        {
          goto end;
        }

      /* Remove from holder list of the waiter */
      edge_p = *prev_holder_p;
      *prev_holder_p = (*prev_holder_p)->next_holder_edge_p;
      free_and_init (edge_p);
      wfg_Total_edges--;
    }
      else
    {
      prev_holder_p = &((*prev_holder_p)->next_holder_edge_p);
    }
    }

  if (prev_holder_p == &(wfg_Nodes[waiter_tran_index].first_holder_edge_p))
    {
      /* all outgoing edges are removed */
      wfg_Nodes[waiter_tran_index].last_holder_edge_p = NULL;
      wfg_Total_waiters--;
    }
  else
    {
      wfg_Nodes[waiter_tran_index].last_holder_edge_p =
    (WFG_EDGE *) ((char *) prev_holder_p - offsetof (WFG_EDGE, next_holder_edge_p));
    }

end:
  csect_exit (thread_p, CSECT_WFG);
  return error_code;
}

/*
 * wfg_get_status : get statistic from WFG.
 *
 * returns : NO_ERROR if all OK, ER status otherwise
 *
 *   edges(OUT)   : pointer to room to store # of edges
 *   waiters(OUT) : pointer to room to store # of waiting trans
 *
 */
int
wfg_get_status (int *num_edges_p, int *num_waiters_p)
{
  assert (num_edges_p != NULL);
  assert (num_waiters_p != NULL);

  *num_edges_p = wfg_Total_edges;
  *num_waiters_p = wfg_Total_waiters;

  return NO_ERROR;
}

/*
 * wfg_detect_cycle : finds all elementary cycles in the WFG and
 *                    transaction groups.
 *
 * returns : NO_ERROR if all OK, ER status otherwise
 *
 *   cycle_case(OUT)       : cycle_case.. One of the following values:
 *                           WFG_CYCLE_YES_PRUNE
 *                           WFG_CYCLE_YES
 *                           WFG_CYCLE_NO
 *                           WFG_CYCLE_ERROR
 *   list_cycles_p(IN/OUT) : address to list of cycles
 *                         Cycles is set as a side effect to point to list of
 *                         cycles.
 *
 * NOTE: the caller should be responsible for freeing memory allocated to the
 *       cycles after usage. See wfg_free_cycle()
 */
int
wfg_detect_cycle (THREAD_ENTRY * thread_p, WFG_CYCLE_CASE * cycle_case, WFG_CYCLE ** list_cycles_p)
{
  /* LIMIT the number of cycles */
  return wfg_internal_detect_cycle (thread_p, cycle_case, list_cycles_p, WFG_PRUNE_CYCLES_IN_CYCLE_GROUP,
                    WFG_MAX_CYCLES_TO_REPORT);
}

/*
 * wfg_internal_detect_cycle() : finds all elementary cycles in the WFG and
 *                               transaction groups.
 *
 * returns : NO_ERROR if all OK, ER status otherwise
 *
 *   cycle_case(OUT)       : cycle_case.. One of the following values:
 *                           WFG_CYCLE_YES_PRUNE
 *                           WFG_CYCLE_YES
 *                           WFG_CYCLE_NO
 *                           WFG_CYCLE_ERROR
 *   list_cycles_p(IN/OUT) : address to list of cycles
 *                           Cycles is set as a side effect to point to list of
 *                           cycles.
 *   max_cycles_in_cycle_group(IN) : Prune the number of found cycles
 *                           in a cycle group
 *   max_cycles(IN)        : max cycles to report
 *
 */
static int
wfg_internal_detect_cycle (THREAD_ENTRY * thread_p, WFG_CYCLE_CASE * cycle_case_p, WFG_CYCLE ** list_cycles_p,
               const int max_cycles_in_cycle_group, const int max_cycles)
{
  WFG_CYCLE **next_cycle_p; /* address of pointer to next cycle */
  WFG_CYCLE *ordinary_cycles_p = NULL;  /* ordinary cycles */
  WFG_CYCLE *tran_group_cycles_p = NULL;    /* TG(transaction group) cycles */
  WFG_CYCLE_CASE cycle_tran_group_case;
  int error_code = NO_ERROR;

  *list_cycles_p = NULL;

  error_code =
    wfg_detect_ordinary_cycle (thread_p, cycle_case_p, &ordinary_cycles_p, max_cycles_in_cycle_group, max_cycles);
  if (error_code != NO_ERROR)
    {
      goto error;
    }

  if (ordinary_cycles_p != NULL)
    {
      *list_cycles_p = ordinary_cycles_p;
    }

  error_code = wfg_detect_tran_group_cycle (thread_p, &cycle_tran_group_case, &tran_group_cycles_p);
  if (error_code != NO_ERROR)
    {
      goto error;
    }

  if (tran_group_cycles_p != NULL)
    {
      /* Glue the lists */
      for (next_cycle_p = list_cycles_p; *next_cycle_p != NULL; next_cycle_p = &((*next_cycle_p)->next))
    {
      ;         /* NO-OP */
    }
      *next_cycle_p = tran_group_cycles_p;
    }

  switch (*cycle_case_p)
    {
    case WFG_CYCLE_YES_PRUNE:
      break;

    case WFG_CYCLE_YES:
      if (cycle_tran_group_case == WFG_CYCLE_YES_PRUNE)
    {
      *cycle_case_p = cycle_tran_group_case;
    }
      break;

    case WFG_CYCLE_NO:
      *cycle_case_p = cycle_tran_group_case;
      break;

    default:
      break;
    }

  return NO_ERROR;

error:

  /* free allocated cycles */
  if (ordinary_cycles_p != NULL)
    {
      wfg_free_cycle (ordinary_cycles_p);
    }

  if (tran_group_cycles_p != NULL)
    {
      wfg_free_cycle (tran_group_cycles_p);
    }

  *list_cycles_p = NULL;

  *cycle_case_p = WFG_CYCLE_ERROR;

  return ER_FAILED;
}

/*
 * wfg_free_cycle : free memory allocated to store cycles by wfg_detect_cycle().
 *
 * return : NO_ERROR if all OK, ER status otherwise
 *
 *  list_cycles(IN/OUT) : address to list of cycles
 *
 */
int
wfg_free_cycle (WFG_CYCLE * list_cycles_p)
{
  WFG_CYCLE *current_cycle_p;   /* temp pointer to a WFG_CYCLE node */
  WFG_CYCLE *temp_p;        /* temp variable for current_cycle_p */

  if (list_cycles_p != NULL)
    {
      for (current_cycle_p = list_cycles_p; current_cycle_p != NULL;)
    {
      if (current_cycle_p->waiters != NULL)
        {
          free_and_init (current_cycle_p->waiters);
        }

      temp_p = current_cycle_p;
      current_cycle_p = current_cycle_p->next;
      free_and_init (temp_p);
    }
    }

  return NO_ERROR;
}

/*
 * wfg_print_given_cycles:
 *
 * return : NO_ERROR if all OK, ER status otherwise
 *
 *   out_fp(in) : out file
 *   list_cycles_p(IN) : address to list of cycles
 *
 */
static int
wfg_dump_given_cycles (FILE * out_fp, WFG_CYCLE * list_cycles_p)
{
  int i;
  WFG_CYCLE *current_cycle_p;

  fprintf (out_fp, "----------------- CYCLES ------------------\n");

  /*
   * There are deadlocks, we must select a victim for each cycle. We try
   * to break a cycle by timeing out a transaction whenever is possible.
   * In any other case, we select a victim for an unilaterally abort.
   */

  for (current_cycle_p = list_cycles_p; current_cycle_p != NULL; current_cycle_p = current_cycle_p->next)
    {
      fprintf (out_fp, "Cycle: ");
      for (i = 0; i < current_cycle_p->num_trans; i++)
    {
      if (i > 0)
        {
          fprintf (out_fp, ", ");
          if ((i % 10) == 0)
        {
          fprintf (out_fp, "\n       ");
        }
        }
      fprintf (out_fp, "%d", current_cycle_p->waiters[i].tran_index);
    }
      fprintf (out_fp, "\n");
    }

  return NO_ERROR;
}

/*
 * wfg_dump_holder_waiter:
 *
 * return : NO_ERROR if all OK, ER status otherwise
 *
 *   out_fp(in) : out file
 *   node_index(in):
 *
 */
static void
wfg_dump_holder_waiter (FILE * out_fp, int node_index)
{
  WFG_EDGE *edge_p;

  /* Print holders of node */
  fprintf (out_fp, "\t holders = { ");
  for (edge_p = wfg_Nodes[node_index].first_holder_edge_p; edge_p != NULL; edge_p = edge_p->next_holder_edge_p)
    {
      fprintf (out_fp, "%03d ", edge_p->holder_tran_index);
    }
  fprintf (out_fp, "}\n");

  /* Print waiters of node */
  fprintf (out_fp, "\t\t waiters = { ");
  for (edge_p = wfg_Nodes[node_index].first_waiter_edge_p; edge_p != NULL; edge_p = edge_p->next_waiter_edge_p)
    {
      fprintf (out_fp, "%03d ", edge_p->waiter_tran_index);
    }
  fprintf (out_fp, "}\n");

  if (wfg_Nodes[node_index].last_holder_edge_p == NULL)
    {
      fprintf (out_fp, "\t\t last holder = null,");
    }
  else
    {
      fprintf (stdout, "\t\t last holder = %03d,", wfg_Nodes[node_index].last_holder_edge_p->holder_tran_index);
    }

  if (wfg_Nodes[node_index].last_waiter_edge_p == NULL)
    {
      fprintf (out_fp, "\t\t last waiter = null\n");
    }
  else
    {
      fprintf (out_fp, "\t\t last waiter = %03d\n", wfg_Nodes[node_index].last_waiter_edge_p->waiter_tran_index);
    }
}

/*
 * wfg_dump_holder_waiter_of_tran_group:
 *
 * return : NO_ERROR if all OK, ER status otherwise
 *
 *   out_fp(in) : out file
 *   group_index(in):
 *
 */
static void
wfg_dump_holder_waiter_of_tran_group (FILE * out_fp, int group_index)
{
  WFG_TRANS_LIST *tran_list_p;

  if (wfg_Tran_group[group_index].holder_tran_list_p)
    {
      /* Print holders of TG */
      fprintf (out_fp, "\t holders = { ");
      for (tran_list_p = wfg_Tran_group[group_index].holder_tran_list_p; tran_list_p != NULL;
       tran_list_p = tran_list_p->next)
    {
      fprintf (out_fp, "%d ", tran_list_p->tran_index);
    }
      fprintf (out_fp, "}\n");

      if (wfg_Tran_group[group_index].waiter_tran_list_p)
    {
      /* Print waiters of TG */
      fprintf (out_fp, "\t waiters = { ");
      for (tran_list_p = wfg_Tran_group[group_index].waiter_tran_list_p; tran_list_p != NULL;
           tran_list_p = tran_list_p->next)
        {
          fprintf (out_fp, "%d ", tran_list_p->tran_index);
        }
      fprintf (out_fp, "}\n");
    }
    }
}

/*
 * wfg_dump :
 *
 * return : NO_ERROR if all OK, ER status otherwise
 *
 */
int
wfg_dump (THREAD_ENTRY * thread_p)
{
  int i;
  WFG_CYCLE *cycles_p;
  WFG_CYCLE_CASE cycle_case;

  fprintf (stdout, "--------------- WFG contents --------------\n");
  fprintf (stdout, "total_nodes = %d, total_edges = %d, total_waiters = %d\n", wfg_Total_nodes, wfg_Total_edges,
       wfg_Total_waiters);

  fprintf (stdout, "\n");
  fprintf (stdout, "---------- Ordinary WFG contents ----------\n");

  for (i = 0; i < wfg_Total_nodes; i++)
    {
      fprintf (stdout, "[node_%03d]:", i);
      wfg_dump_holder_waiter (stdout, i);
    }

  if (wfg_Total_tran_groups > 0)
    {
      fprintf (stdout, "\n");
      fprintf (stdout, "------------- WFG_TG contents -------------\n");

      for (i = 0; i < wfg_Total_tran_groups; i++)
    {
      fprintf (stdout, "TG[%d]:\t Num_holders %d, Num_waiters %d\n", i, wfg_Tran_group[i].num_holders,
           wfg_Tran_group[i].num_waiters);

      wfg_dump_holder_waiter_of_tran_group (stdout, i);
    }
    }

  /* Dump all cycles that are currently involved in the system */
  if (wfg_internal_detect_cycle (thread_p, &cycle_case, &cycles_p, -1, -1) == NO_ERROR && cycle_case == WFG_CYCLE_YES)
    {
      fprintf (stdout, "\n");
      wfg_dump_given_cycles (stdout, cycles_p);
      wfg_free_cycle (cycles_p);
    }

  return NO_ERROR;
}

/*
 * wfg_alloc_tran_group :
 *
 * return : if success, non-negative Transaction Group entry index,
 *          otherwise, ER_FAILED  value
 *
 */
int
wfg_alloc_tran_group (THREAD_ENTRY * thread_p)
{
  WFG_TRAN_GROUP *temp_p;   /* temp_p pointer to new TG table */
  size_t bytes;         /* size of new TG table */
  int error_code = NO_ERROR;

  if (csect_enter (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      return ER_FAILED;
    }

  bytes = sizeof (WFG_TRAN_GROUP) * (wfg_Total_tran_groups + 1);
  if (wfg_Total_tran_groups == 0)
    {
      temp_p = (WFG_TRAN_GROUP *) malloc (bytes);
    }
  else
    {
      temp_p = (WFG_TRAN_GROUP *) realloc (wfg_Tran_group, bytes);
    }

  if (temp_p == NULL)
    {
      er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, bytes);
      error_code = ER_OUT_OF_VIRTUAL_MEMORY;
      goto end;
    }

  wfg_Tran_group = temp_p;

  /* initialize the newly allocated entry */
  wfg_Tran_group[wfg_Total_tran_groups].num_holders = 0;
  wfg_Tran_group[wfg_Total_tran_groups].num_waiters = 0;
  wfg_Tran_group[wfg_Total_tran_groups].holder_tran_list_p = NULL;
  wfg_Tran_group[wfg_Total_tran_groups].waiter_tran_list_p = NULL;

  wfg_Total_tran_groups++;

end:
  csect_exit (thread_p, CSECT_WFG);

  return (wfg_Total_tran_groups - 1);
}

/*
 * wfg_insert_holder_tran_group : register the tran_index as a holder
 *                        of the Transaction Group tran_group_index.
 *
 * return : NO_ERROR if all OK, ER status otherwise
 *
 *   tran_group_index(IN)  : Transaction Group entry index
 *   holder_tran_index(IN) : tran_index to be entered
 *
 * NOTE: the behavior on invalid tran_group_index and holder_tran_index,
 *       is undefined.
 *
 */
int
wfg_insert_holder_tran_group (THREAD_ENTRY * thread_p, const int tran_group_index, const int holder_tran_index)
{
  WFG_TRANS_LIST *tran_list_p;  /* temp trans list node pointer */
  int error_code = NO_ERROR;

  /* Create a node for the tran_index and insert it to the TG's holder list */
  tran_list_p = (WFG_TRANS_LIST *) malloc (sizeof (WFG_TRANS_LIST));
  if (tran_list_p == NULL)
    {
      er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, sizeof (WFG_TRANS_LIST));
      return ER_OUT_OF_VIRTUAL_MEMORY;
    }

  if (csect_enter (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      free_and_init (tran_list_p);
      return ER_FAILED;
    }

#if defined(WFG_DEBUG)
  if (tran_group_index < 0 || tran_group_index > wfg_Total_tran_groups - 1)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_tg_insert_holder: value tg_index = %d" " should be between 0 and %d\n"
            "** OPERATION HAS BEEN IGNORED **", tran_group_index, wfg_Total_tran_groups - 1);
      error_code = ER_FAILED;
      goto end;
    }

  if (holder_tran_index < 0 || holder_tran_index > wfg_Total_nodes - 1)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_tg_insert_holder: value htran_index = %d" " should be between 0 and %d\n"
            " ** OPERATION HAS BEEN IGNORED **", holder_tran_index, wfg_Total_nodes - 1);
      error_code = ER_FAILED;
      goto end;
    }

  for (tran_list_p = wfg_Tran_group[tran_group_index].holder_tran_list_p; tran_list_p != NULL;
       tran_list_p = tran_list_p->next)
    if (tran_list_p->tran_index == holder_tran_index)
      {
    er_log_debug (ARG_FILE_LINE,
              "wfg_tg_insert_holder: value" " htran_index = %d is already in holder list\n"
              " ** OPERATION HAS BEEN IGNORED **", tran_index);
    error_code = ER_FAILED;
    goto end;
      }
#endif /* WFG_DEBUG */

  tran_list_p->tran_index = holder_tran_index;
  tran_list_p->next = wfg_Tran_group[tran_group_index].holder_tran_list_p;
  wfg_Tran_group[tran_group_index].holder_tran_list_p = tran_list_p;
  wfg_Tran_group[tran_group_index].num_holders++;

#if defined(WFG_DEBUG)
end:
#endif /* WFG_DEBUG */

  csect_exit (thread_p, CSECT_WFG);

  return error_code;
}

/*
 * wfg_remove_holder_tran_group : delete holder_tran_index from the holder list
 *                        of Transaction Group tran_group_index
 *
 * return : NO_ERROR if all OK, ER status otherwise
 *
 *   tran_group_index(IN)  : Transaction Group entry index
 *   holder_tran_index(IN) : tran_index to be removed
 *
 * NOTE: the behavior on invalid tran_group_index and holder_tran_index,
 *       is undefined.
 *
 */
int
wfg_remove_holder_tran_group (THREAD_ENTRY * thread_p, const int tran_group_index, const int holder_tran_index)
{
  WFG_TRANS_LIST **tran_list_p; /* transaction list node */
  WFG_TRANS_LIST *temp_p;
  int error_code = NO_ERROR;

  if (csect_enter (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      return ER_FAILED;
    }

#if defined(WFG_DEBUG)
  if (tran_group_index < 0 || tran_group_index > wfg_Total_tran_groups - 1)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_tg_remove_holder: value tg_index = %d" " should be between 0 and %d\n"
            " ** OPERATION HAS BEEN IGNORED **", tran_group_index, wfg_Total_tran_groups - 1);
      error_code = ER_FAILED;
      goto end;
    }

  if (holder_tran_index < 0 || holder_tran_index > wfg_Total_nodes - 1)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_tg_remove_holder: value htran_index = %d" " should be between 0 and %d\n"
            " ** OPERATION HAS BEEN IGNORED **", holder_tran_index, wfg_Total_nodes - 1);
      error_code = ER_FAILED;
      goto end;
    }

  for (temp_p = wfg_Tran_group[tran_group_index].holder_tran_list_p; temp_p != NULL; temp_p = temp_p->next)
    {
      if (temp_p->tran_index == holder_tran_index)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_tg_remove_holder: value" " htran_index = %d is NOT in holder list\n"
            " ** OPERATION HAS NO EFFECT **", holder_tran_index);
      error_code = ER_FAILED;
      goto end;
    }
    }
#endif /* WFG_DEBUG */

  if (wfg_Tran_group[tran_group_index].holder_tran_list_p != NULL)
    {
      for (tran_list_p = &wfg_Tran_group[tran_group_index].holder_tran_list_p; *tran_list_p != NULL;
       tran_list_p = &((*tran_list_p)->next))
    {
      if ((*tran_list_p)->tran_index == holder_tran_index)
        {
          /* Remove it, and change the pointer in the previous structure */
          temp_p = *tran_list_p;
          *tran_list_p = (*tran_list_p)->next;
          free_and_init (temp_p);
          wfg_Tran_group[tran_group_index].num_holders--;
          break;
        }
    }
    }

#if defined(WFG_DEBUG)
end:
#endif /* WFG_DEBUG */

  csect_exit (thread_p, CSECT_WFG);

  return error_code;
}

/*
 * wfg_insert_waiter_tran_group : register the tran_index as a waiter
 *                                of the Transaction Group tran_group_index.
 *
 * return : NO_ERROR if all OK, ER status otherwise
 *
 *   tran_group_index(IN)    : Transaction Group entry index
 *   waiter_tran_index(IN)   : tran_index to be entered
 *   cycle_resolution_fn(IN) :
 *   args(IN)                :
 *
 * NOTE: the behavior on invalid tg_index and tran_index, is undefined.
 *
 * The implementation of this function is almost identical as that of
 * wfg_insert_holder_tran_group(). The only difference is that this function
 * replaces holder by waiter.
 *
 */
int
wfg_insert_waiter_tran_group (THREAD_ENTRY * thread_p, const int tran_group_index, const int waiter_tran_index,
                  int (*cycle_resolution_fn) (int tran_index, void *args), void *args)
{
  WFG_TRANS_LIST *tran_list_p;  /* temp trans list node pointer */
  int error_code = NO_ERROR;

  if (csect_enter (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      return ER_FAILED;
    }

#if defined(WFG_DEBUG)
  if (tran_group_index < 0 || tran_group_index > wfg_Total_tran_groups - 1)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_tg_insert_waiter: value tg_index = %d should"
            " be between 0 and %d\n ** OPERATION HAS BEEN IGNORED **", tran_group_index,
            wfg_Total_tran_groups - 1);
      error_code = ER_FAILED;
      goto end;
    }

  if (waiter_tran_index < 0 || waiter_tran_index > wfg_Total_nodes - 1)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_tg_insert_waiter: value tran_index = %d" " should be between 0 and %d\n"
            " ** OPERATION HAS BEEN IGNORED **", waiter_tran_index, wfg_Total_nodes - 1);
      error_code = ER_FAILED;
      goto end;
    }

  for (tran_list_p = wfg_Tran_group[tran_group_index].waiter_tran_list_p; tran_list_p != NULL;
       tran_list_p = tran_list_p->next)
    {
      if (tran_list_p->tran_index == waiter_tran_index)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_tg_insert_waiter: value tran_index = %d" " is already in waiters\n"
            " ** OPERATION HAS BEEN IGNORED **", waiter_tran_index);
      error_code = ER_FAILED;
      goto end;
    }
    }
#endif /* WFG_DEBUG */

  /*
   * allocate a node for the waiter_tran_index and insert it to the TG's waiter
   * list
   */
  tran_list_p = (WFG_TRANS_LIST *) malloc (sizeof (WFG_TRANS_LIST));
  if (tran_list_p == NULL)
    {
      er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, sizeof (WFG_TRANS_LIST));
      error_code = ER_OUT_OF_VIRTUAL_MEMORY;
      goto end;
    }

  tran_list_p->tran_index = waiter_tran_index;
  tran_list_p->next = wfg_Tran_group[tran_group_index].waiter_tran_list_p;
  wfg_Tran_group[tran_group_index].waiter_tran_list_p = tran_list_p;
  wfg_Tran_group[tran_group_index].num_waiters++;

  /* Save the function to call in the case of a cycle. */
  wfg_Nodes[waiter_tran_index].cycle_fun = cycle_resolution_fn;
  wfg_Nodes[waiter_tran_index].args = args;

end:
  csect_exit (thread_p, CSECT_WFG);

  return error_code;
}

/*
 * wfg_remove_waiter_tran_group : delete waiter tran_index from the waiter list
 *                        of Transaction Group tran_group_index
 *
 * return : return : NO_ERROR if all OK, ER status otherwise
 *
 *   tg_index(IN)          : Transaction Group entry index
 *   waiter_tran_index(IN) : tran_index to be removed
 *
 * NOTE: the behavior on invalid tran_group_index and waiter_tran_index,
 *       is undefined.
 *
 * The implementation of this function is almost identical as that of
 * wfg_remove_holder_tran_group(). The only difference is that this function
 * replaces holder by waiter.
 *
 */
int
wfg_remove_waiter_tran_group (THREAD_ENTRY * thread_p, const int tran_group_index, const int waiter_tran_index)
{
  WFG_TRANS_LIST **tran_list_p; /* tran_index list node */
  WFG_TRANS_LIST *temp_p;
  int error_code = NO_ERROR;

  if (csect_enter (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      return ER_FAILED;
    }

#if defined(WFG_DEBUG)
  if (tran_group_index < 0 || tran_group_index > wfg_Total_tran_groups - 1)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_tg_remove_waiter: value tg_index = %d should"
            " be between 0 and %d\n ** OPERATION HAS BEEN IGNORED **", tran_group_index,
            wfg_Total_tran_groups - 1);
      error_code = ER_FAILED;
      goto end;
    }

  if (waiter_tran_index < 0 || waiter_tran_index > wfg_Total_nodes - 1)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_tg_remove_waiter: value tran_index = %d" " should be between 0 and %d\n"
            " ** OPERATION HAS BEEN IGNORED **", waiter_tran_index, wfg_Total_nodes - 1);
      error_code = ER_FAILED;
      goto end;
    }

  for (tran_list_p = &wfg_Tran_group[tran_group_index].waiter_tran_list_p; tran_list_p != NULL;
       tran_list_p = &((*tran_list_p)->next))
    {
      if ((*tran_list_p)->tran_index == waiter_tran_index)
    {
      er_log_debug (ARG_FILE_LINE,
            "wfg_tg_remove_waiter: value tran_index = %d"
            " is NOT in waiters\n ** OPERATION HAS NO EFFECT **", waiter_tran_index);
      error_code = ER_FAILED;
      goto end;
    }
    }
#endif /* WFG_DEBUG */

  for (tran_list_p = &wfg_Tran_group[tran_group_index].waiter_tran_list_p; tran_list_p != NULL;
       tran_list_p = &((*tran_list_p)->next))
    {
      if ((*tran_list_p)->tran_index == waiter_tran_index)
    {
      /* Remove it */
      temp_p = *tran_list_p;
      *tran_list_p = (*tran_list_p)->next;
      free_and_init (temp_p);
      wfg_Tran_group[tran_group_index].num_waiters--;
      break;
    }
    }

#if defined(WFG_DEBUG)
end:
#endif /* WFG_DEBUG */

  csect_exit (thread_p, CSECT_WFG);

  return error_code;
}

/*
 * wfg_detect_ordinary_cycle :finds elementary cycles in the ordinary WFG. I.e.,
 *              these cycles does not include TG related ones.
 *              The function may prune its search for finding more cycles
 *              when many has been found. This is done for space and time
 *              efficiency. The caller has the option to call again after
 *              cleaning some of the dependencies (e.g., aborting some of the
 *              transactions).
 *
 * returns : NO_ERROR if all OK, ER status otherwise
 *
 *   cycle_case(OUT)       : cycle_case.. One of the following values:
 *                           WFG_CYCLE_YES_PRUNE
 *                           WFG_CYCLE_YES
 *                           WFG_CYCLE_NO
 *                           WFG_CYCLE_ERROR
 *   list_cycles_p(IN/OUT) : address to list of cycles, list_cycles_p is set
 *                           as a side effect to point to list of cycles.
 *   max_cycles_in_group(IN) :
 *   max_cycles(IN)        :
 *
 * Note: the caller should be responsible for freeing memory allocated
 *   to the cycles after usage. See wfg_free_cycle()
 */
static int
wfg_detect_ordinary_cycle (THREAD_ENTRY * thread_p, WFG_CYCLE_CASE * cycle_case_p, WFG_CYCLE ** list_cycles_p,
               const int max_cycles_in_group, const int max_cycles)
{
  int i, j;
  WFG_CYCLE **last_cycle_p; /* ptr to addr of the last cycle */
  WFG_STACK *bottom_p = NULL;   /* bottom of WFG stack */
  WFG_STACK *top_p;     /* top of WFG stack */
  WFG_STACK *stack_elem_p;  /* pointer for stack scan */
  WFG_CYCLE *cycle_p = NULL;    /* pointer to the current cycle */
  WFG_WAITER *waiter_p;     /* Waiter transactions in the cycle */
  int htran_index;      /* index of the waiter node of the top edge */
  int cycle_group_no;       /* cycle group number */
  int num_cycles_in_group;
  int num_total_cycles = 0;
  int error_code = NO_ERROR;

  *cycle_case_p = WFG_CYCLE_NO;
  *list_cycles_p = NULL;
  last_cycle_p = list_cycles_p;

  if (csect_enter (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      return ER_FAILED;
    }

  if (wfg_Total_waiters < 2)
    {
      error_code = ER_FAILED;
      goto error;
    }

  for (i = 0; i < wfg_Total_nodes; i++)
    {
      wfg_Nodes[i].status = WFG_NOT_VISITED;
      wfg_Nodes[i].cycle_group_no = -1;
    }

  /* allocate stack for DFS search */
  bottom_p = (WFG_STACK *) malloc (sizeof (WFG_STACK) * wfg_Total_waiters);
  if (bottom_p == NULL)
    {
      er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, sizeof (WFG_STACK) * wfg_Total_waiters);
      error_code = ER_OUT_OF_VIRTUAL_MEMORY;
      goto error;
    }
  top_p = bottom_p - 1;
  cycle_group_no = 0;

  for (i = 0; i < wfg_Total_nodes; i++)
    {
      if (max_cycles > 0 && num_total_cycles > max_cycles)
    {
      /*
       * We have too many cycles already. It is better to return to avoid
       * spending too much time and space among cycle groups
       */
      *cycle_case_p = WFG_CYCLE_YES_PRUNE;
      break;
    }

      if (wfg_Nodes[i].status != WFG_NOT_VISITED)
    {
      continue;
    }

      /* DFS beginning with the current node */
      cycle_group_no++;
      num_cycles_in_group = 0;

      /*
       * Optimization of special case. Used to avoid overhead of stack operations
       */
      if (wfg_Nodes[i].first_holder_edge_p == NULL)
    {
      wfg_Nodes[i].status = WFG_OFF_STACK;
      continue;
    }

      /* start depth-first-search from this node */
      wfg_Nodes[i].status = WFG_ON_STACK;
      wfg_push_stack (&top_p, i);

      while (top_p >= bottom_p)
    {
      /* not empty stack */

    new_top:        /* new top entry is pushed in stack */

      for (; top_p->current_holder_edge_p != NULL;
           top_p->current_holder_edge_p = top_p->current_holder_edge_p->next_holder_edge_p)
        {
          htran_index = top_p->current_holder_edge_p->holder_tran_index;

          switch (wfg_Nodes[htran_index].status)
        {
        case WFG_NOT_VISITED:
          /* untouched node */
          if (wfg_Nodes[htran_index].first_holder_edge_p == NULL)
            {
              wfg_Nodes[htran_index].status = WFG_OFF_STACK;
            }
          else
            {
              /* try the new node */
              wfg_Nodes[htran_index].status = WFG_ON_STACK;
              wfg_push_stack (&top_p, htran_index);
              goto new_top;
            }
          break;

        case WFG_ON_STACK:
          /* a cyclye has been found */

          /* mark this cycle with cycle_group_no */
          wfg_Nodes[htran_index].cycle_group_no = cycle_group_no;

          for (stack_elem_p = top_p; stack_elem_p->wait_tran_index != htran_index; stack_elem_p--)
            {
              wfg_Nodes[stack_elem_p->wait_tran_index].cycle_group_no = cycle_group_no;
            }

          /* construct a cycle */
          cycle_p = (WFG_CYCLE *) malloc (sizeof (WFG_CYCLE));
          if (cycle_p == NULL)
            {
              er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, sizeof (WFG_CYCLE));
              error_code = ER_OUT_OF_VIRTUAL_MEMORY;
              goto error;
            }

          cycle_p->num_trans = (int) ((top_p - stack_elem_p) + 1);
          cycle_p->next = NULL;
          cycle_p->waiters = (WFG_WAITER *) malloc (sizeof (WFG_WAITER) * cycle_p->num_trans);
          if (cycle_p->waiters == NULL)
            {
              er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1,
                  sizeof (WFG_WAITER) * cycle_p->num_trans);
              error_code = ER_OUT_OF_VIRTUAL_MEMORY;
              free_and_init (cycle_p);
              goto error;
            }

          j = 0;
          for (stack_elem_p = top_p, waiter_p = cycle_p->waiters; j < cycle_p->num_trans;
               j++, stack_elem_p--, waiter_p++)
            {
              waiter_p->tran_index = stack_elem_p->wait_tran_index;
              waiter_p->cycle_fun = wfg_Nodes[waiter_p->tran_index].cycle_fun;
              waiter_p->args = wfg_Nodes[waiter_p->tran_index].args;
            }

          *last_cycle_p = cycle_p;
          last_cycle_p = &cycle_p->next;

          num_cycles_in_group++;

          if (max_cycles > 0 && num_total_cycles + num_cycles_in_group >= max_cycles)
            {
              *cycle_case_p = WFG_CYCLE_YES_PRUNE;
            }
          else if (*cycle_case_p == WFG_CYCLE_NO)
            {
              *cycle_case_p = WFG_CYCLE_YES;
            }

          break;

        case WFG_OFF_STACK:
          /* already traversed */
          if (wfg_Nodes[htran_index].cycle_group_no == cycle_group_no)
            {
              /*
               * need to traverse again
               *
               * We will skip on finding more cycles for
               * the current cycle group when we have found many cycles.
               * This is done to avoid finding many many combinations of
               * cycles for the same transactions.
               */

              if ((max_cycles_in_group > 0
               && (num_cycles_in_group > wfg_Total_nodes || num_cycles_in_group >= max_cycles_in_group))
              || (max_cycles > 0 && (num_total_cycles + num_cycles_in_group) >= max_cycles))
            {
              *cycle_case_p = WFG_CYCLE_YES_PRUNE;
              break;
            }

              wfg_Nodes[htran_index].status = WFG_RE_ON_STACK;
              wfg_push_stack (&top_p, htran_index);
              goto new_top;
            }
          break;

        case WFG_RE_ON_STACK:
          /* this cycle has already been detected */
          break;

        default:
#if defined(WFG_DEBUG)
          (void) fprintf (stdout, "wfg_detect_ordinary_cycle():");
          (void) fprintf (stdout, "interal switch error\n");
#endif /* WFG_DEBUG */
          break;
        }
        }

      /* top_p is searched exhaustedly */
      wfg_Nodes[top_p->wait_tran_index].status = WFG_OFF_STACK;
      error_code = wfg_pop_stack (&top_p, &bottom_p);
      if (error_code != NO_ERROR)
        {
          goto error;
        }
    }

      /* empty stack: continue to next cycle group */
      num_total_cycles += num_cycles_in_group;
    }

  free_and_init (bottom_p); /* free stack */

  csect_exit (thread_p, CSECT_WFG);
  return error_code;

error:
  if (*list_cycles_p != NULL)
    {
      wfg_free_cycle (*list_cycles_p);
      *list_cycles_p = NULL;
    }

  if (bottom_p != NULL)
    {
      free_and_init (bottom_p);
    }
  csect_exit (thread_p, CSECT_WFG);

  return error_code;
}

/*
 * wfg_add_waiters_of_tg :
 *
 * returns : NO_ERROR
 *
 *   smallest_onstack(in/out):
 *   holder_node(in):
 *   tg_index(in):
 *
 * Note:
 */
static int
wfg_add_waiters_of_tg (int *smallest_onstack, int holder_node, int tg_index)
{
  WFG_TRANS_LIST *h_tran_list_p;    /* ptr to a trans list node in TG */
  WFG_TRANS_LIST *w_tran_list_p;    /* ptr to a trans list node in TG */
  WFG_TRAN_GROUP *tg_tmp;
  WFG_NODE *w_node_p;

  /*
   * If the node i is a holder of any TG,
   * add the waiters of such TG to it.
   */
  for (; tg_index < wfg_Total_tran_groups; tg_index++)
    {
      tg_tmp = &wfg_Tran_group[tg_index];
      for (h_tran_list_p = tg_tmp->holder_tran_list_p; h_tran_list_p != NULL; h_tran_list_p = h_tran_list_p->next)
    {
      if (h_tran_list_p->tran_index == holder_node)
        {
          break;
        }
    }

      if (h_tran_list_p != NULL)
    {
      /* Add all waiters of the TG */
      for (w_tran_list_p = tg_tmp->waiter_tran_list_p; w_tran_list_p != NULL; w_tran_list_p = w_tran_list_p->next)
        {
          w_node_p = &wfg_Nodes[w_tran_list_p->tran_index];
          if (w_node_p->status == WFG_NOT_VISITED)
        {
          w_node_p->status = WFG_ON_STACK;
          if (*smallest_onstack > w_tran_list_p->tran_index)
            {
              *smallest_onstack = w_tran_list_p->tran_index;
            }
        }
        }
    }
    }

  return NO_ERROR;
}

/*
 * wfg_add_waiters_normal_wfg :
 *
 * returns : NO_ERROR
 *
 *   smallest_onstack(in/out):
 *   node_index(in):
 *
 * Note:
 */
static int
wfg_add_waiters_normal_wfg (int *smallest_onstack, int node_index)
{
  WFG_EDGE *edge_p;     /* loop pointer to edge */

  /* Add the waiters of the normal WFG */
  for (edge_p = wfg_Nodes[node_index].first_waiter_edge_p; edge_p != NULL; edge_p = edge_p->next_waiter_edge_p)
    {
      if (wfg_Nodes[edge_p->waiter_tran_index].status == WFG_NOT_VISITED)
    {
      wfg_Nodes[edge_p->waiter_tran_index].status = WFG_ON_STACK;
      if (*smallest_onstack > edge_p->waiter_tran_index)
        {
          *smallest_onstack = edge_p->waiter_tran_index;
        }
    }
    }

  return NO_ERROR;
}

/*
 * wfg_get_all_waiting_and_add_waiter :
 *
 * returns : NO_ERROR
 *
 *   all_waiting(out):
 *   add_waiter(out):
 *   tg1_index(in):
 *   tg2_index(in):
 *
 * Note:
 */
static int
wfg_get_all_waiting_and_add_waiter (bool * all_waiting, bool * add_waiter, int tg_index)
{
  WFG_TRANS_LIST *w_tran_list_p;    /* ptr to a trans list node in TG */
  WFG_TRANS_LIST *h_tran_list_p;    /* ptr to a trans list node in TG */
  WFG_TRAN_GROUP *tg_tmp;
  WFG_NODE *w_node_p;
  bool tg_connected, tg_all_waiting;
  int i;

  /*
   * If all holders of connected transaction groups are waiting, then
   * we have a deadlock related to TGs. All TG holders will be part
   * of TG elementary cycles.
   */

  *all_waiting = true;
  *add_waiter = true;

  for (i = tg_index; i < wfg_Total_tran_groups && *all_waiting == true; i++)
    {
      tg_tmp = &wfg_Tran_group[i];
      if (i == tg_index)
    {
      tg_connected = true;
    }
      else
    {
      tg_connected = false;
    }
      for (w_tran_list_p = tg_tmp->waiter_tran_list_p; w_tran_list_p != NULL && tg_connected == false;
       w_tran_list_p = w_tran_list_p->next)
    {
      w_node_p = &wfg_Nodes[w_tran_list_p->tran_index];
      if (w_node_p->status != WFG_NOT_VISITED)
        {
          tg_connected = true;
        }
    }

      if (tg_connected == false)
    {
      continue;
    }

      tg_all_waiting = true;
      for (h_tran_list_p = tg_tmp->holder_tran_list_p; h_tran_list_p != NULL && tg_all_waiting == true;
       h_tran_list_p = h_tran_list_p->next)
    {
      if (wfg_Nodes[h_tran_list_p->tran_index].status != WFG_OFF_STACK)
        {
          tg_all_waiting = false;
        }
      else if (w_tran_list_p != NULL && w_tran_list_p->tran_index == h_tran_list_p->tran_index)
        {
          /*
           * The waiter is also a holder. Don't need to add
           * the waiter at a later point.
           */
          *add_waiter = false;
        }
    }
      if (tg_connected == true && tg_all_waiting == false)
    {
      *all_waiting = false;
    }
    }

  return NO_ERROR;
}

/*
 * wfg_get_all_waiting_and_add_waiter :
 *
 * returns : NO_ERROR
 *
 *   all_waiting(out):
 *   add_waiter(out):
 *   tg1_index(in):
 *   tg2_index(in):
 *
 */
static WFG_CYCLE *
wfg_detect_tran_group_cycle_internal (WFG_CYCLE_CASE * cycle_case_p, WFG_TRANS_LIST * w_tran_list_p, bool add_waiter,
                      int tg_index, int num_tran_groups_holders)
{
  WFG_WAITER *waiter_p;     /* Waiter transactions in the cycle */
  WFG_TRANS_LIST *h_tran_list_p;    /* ptr to a trans list node in TG */
  WFG_CYCLE *cycle_p;       /* pointer to the current cycle */
  int i;

  /*
   * Construct the cycle all TG waiters that are part of TG cycles.
   */

  if (*cycle_case_p == WFG_CYCLE_NO)
    {
      *cycle_case_p = WFG_CYCLE_YES;
    }

  cycle_p = (WFG_CYCLE *) malloc (sizeof (WFG_CYCLE));
  if (cycle_p == NULL)
    {
      er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, sizeof (WFG_CYCLE));
      return NULL;
    }

  /* Guess the max for now. We will fix it at the end */
  cycle_p->num_trans = num_tran_groups_holders;

  if (add_waiter == true)
    {
      cycle_p->num_trans++;
    }

  cycle_p->next = NULL;
  cycle_p->waiters = (WFG_WAITER *) malloc (sizeof (WFG_WAITER) * cycle_p->num_trans);
  if (cycle_p->waiters == NULL)
    {
      er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, sizeof (WFG_WAITER) * cycle_p->num_trans);
      free_and_init (cycle_p);
      return NULL;
    }

  /* Add all TG holders that were part of the connected graph. */
  cycle_p->num_trans = 0;
  waiter_p = cycle_p->waiters;

  for (i = tg_index; i < wfg_Total_tran_groups; i++)
    {
      for (h_tran_list_p = wfg_Tran_group[i].holder_tran_list_p; h_tran_list_p != NULL;
       h_tran_list_p = h_tran_list_p->next)
    {
      if (wfg_Nodes[h_tran_list_p->tran_index].status == WFG_OFF_STACK)
        {
          waiter_p->tran_index = h_tran_list_p->tran_index;
          waiter_p->cycle_fun = wfg_Nodes[waiter_p->tran_index].cycle_fun;
          waiter_p->args = wfg_Nodes[waiter_p->tran_index].args;
          cycle_p->num_trans++;
          /*
           * Avoid a possible duplication,
           * it could be part of holder of another TG.
           */
          wfg_Nodes[h_tran_list_p->tran_index].status = WFG_ON_TG_CYCLE;
          waiter_p++;
        }
    }
    }

  /*
   * Add the TG waiter to the cycle. Make sure that the waiter is not
   * also a holder. That is, don't duplicate entries.
   */
  if (add_waiter == true)
    {
      if (wfg_Nodes[w_tran_list_p->tran_index].status == WFG_OFF_STACK)
    {
      wfg_Nodes[w_tran_list_p->tran_index].status = WFG_ON_TG_CYCLE;
      waiter_p->tran_index = w_tran_list_p->tran_index;
      waiter_p->cycle_fun = wfg_Nodes[waiter_p->tran_index].cycle_fun;
      waiter_p->args = wfg_Nodes[waiter_p->tran_index].args;
    }
    }

  return cycle_p;
}

/*
 * wfg_detect_tg_cycle : finds all elementary cycles related with
 *                       Transaction Groups.
 *
 * returns : NO_ERROR if all OK, ER status otherwise
 *
 *   cycle_case(OUT)       : cycle_case. One of the following values:
 *                           WFG_CYCLE_YES_PRUNE
 *                           WFG_CYCLE_YES
 *                           WFG_CYCLE_NO
 *                           WFG_CYCLE_ERROR
 *   list_cycles_p(IN/OUT) : address to list of cycles
 *                           list_cycles is set as a side effect to point
 *                           to list of cycles.
 *
 * NOTE: the caller should be responsible for freeing memory allocated
 *  to the cycles after usage. See wfg_free_cycle()
 *
 * LIMITATIONS:
 *  Current implementation does not return all transactions for each
 *      elementary cycles. Instead, just return holders of TG in cycles.
 */
static int
wfg_detect_tran_group_cycle (THREAD_ENTRY * thread_p, WFG_CYCLE_CASE * cycle_case_p, WFG_CYCLE ** list_cycles_p)
{
  int smallest_onstack;
  int tg1_index, i;
  WFG_CYCLE **last_cycle_p; /* ptr to addr of the last cycle */
  WFG_TRANS_LIST *w_tran_list_p;    /* ptr to a trans list node in TG */
  bool all_waiting;     /* true if all holders are waiting */
  WFG_CYCLE *cycle_p;       /* pointer to the current cycle */
  bool add_waiter;
  int num_tran_groups_holders = 0;  /* Add all holders for all tran groups */
  int error_code = NO_ERROR;

  *cycle_case_p = WFG_CYCLE_NO;

  *list_cycles_p = NULL;
  last_cycle_p = list_cycles_p;

  if (wfg_Total_tran_groups < 1)
    {
      return error_code;
    }

  if (csect_enter (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      return ER_FAILED;
    }

  for (tg1_index = 0; tg1_index < wfg_Total_tran_groups; tg1_index++)
    {
      num_tran_groups_holders += wfg_Tran_group[tg1_index].num_holders;
      if (num_tran_groups_holders > wfg_Total_nodes)
    {
      num_tran_groups_holders = wfg_Total_nodes;
    }
    }

  for (i = 0; i < wfg_Total_nodes; i++)
    {
      wfg_Nodes[i].status = WFG_NOT_VISITED;
    }

  /* Go over each transaction group */
  for (tg1_index = 0; tg1_index < wfg_Total_tran_groups; tg1_index++)
    {
      /*
       * Optimization of special case. Used to avoid overhead of stack operations
       */
      if (wfg_Tran_group[tg1_index].holder_tran_list_p == NULL || wfg_Tran_group[tg1_index].waiter_tran_list_p == NULL)
    {
      continue;
    }

      /*
       * Mark status of TG waiters as WFG_ON_STACK
       */
      for (w_tran_list_p = wfg_Tran_group[tg1_index].waiter_tran_list_p; w_tran_list_p != NULL;
       w_tran_list_p = w_tran_list_p->next)
    {
      /*
       * Skip if it has already been in another TG cycle.
       * Cycle or subcycle has already been listed.
       */
      if (wfg_Nodes[w_tran_list_p->tran_index].status == WFG_ON_TG_CYCLE)
        {
          continue;
        }

      for (i = 0; i < wfg_Total_nodes; i++)
        {
          if (wfg_Nodes[i].status != WFG_ON_TG_CYCLE)
        {
          wfg_Nodes[i].status = WFG_NOT_VISITED;
        }
        }

      wfg_Nodes[w_tran_list_p->tran_index].status = WFG_ON_STACK;
      smallest_onstack = w_tran_list_p->tran_index;

      /* Loop until there is any more new waiters on stack */
      while (smallest_onstack < wfg_Total_nodes)
        {
          i = smallest_onstack;
          smallest_onstack = wfg_Total_nodes;
          for (; i < wfg_Total_nodes && i < smallest_onstack; i++)
        {
          if (wfg_Nodes[i].status == WFG_ON_STACK)
            {
              wfg_add_waiters_of_tg (&smallest_onstack, i, tg1_index);
              wfg_add_waiters_normal_wfg (&smallest_onstack, i);

              /* Indicate that the current node is OFF stack */
              wfg_Nodes[i].status = WFG_OFF_STACK;
            }
        }
        }

      wfg_get_all_waiting_and_add_waiter (&all_waiting, &add_waiter, tg1_index);

      if (all_waiting == true)
        {
          cycle_p =
        wfg_detect_tran_group_cycle_internal (cycle_case_p, w_tran_list_p, add_waiter, tg1_index,
                              num_tran_groups_holders);
          if (cycle_p == NULL)
        {
          goto error;
        }
          *last_cycle_p = cycle_p;
          last_cycle_p = &cycle_p->next;
        }
    }
    }

end:
  csect_exit (thread_p, CSECT_WFG);
  return error_code;

error:
  if (*list_cycles_p != NULL)
    {
      wfg_free_cycle (*list_cycles_p);
      *list_cycles_p = NULL;
    }
  goto end;
}

/*
 * wfg_is_waiting: Find if transaction is waiting for a resource either regular
 *              or Transaction Group resource.
 *
 * returns : NO_ERROR if all OK, ER status otherwise
 *
 */
int
wfg_is_waiting (THREAD_ENTRY * thread_p, const int tran_index)
{
  int i;
  WFG_EDGE *edge_p;
  int error_code = NO_ERROR;

  if (csect_enter_as_reader (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      return ER_FAILED;
    }

  if (wfg_Total_waiters > 0)
    {
      for (i = 0; i < wfg_Total_nodes; i++)
    {
      for (edge_p = wfg_Nodes[i].first_waiter_edge_p; edge_p != NULL; edge_p = edge_p->next_waiter_edge_p)
        {
          if (tran_index == edge_p->waiter_tran_index)
        {
          goto end;
        }
        }
    }
    }

  error_code = wfg_is_tran_group_waiting (thread_p, tran_index);

end:
  csect_exit (thread_p, CSECT_WFG);

  return error_code;
}

/*
 * wfg_is_tran_group_waiting: Find if transaction is waiting for a TG resource.
 *
 * returns : NO_ERROR if all OK, ER status otherwise
 *
 *   tran_index(IN): Transaction index
 *
 */
int
wfg_is_tran_group_waiting (THREAD_ENTRY * thread_p, const int tran_index)
{
  int i;
  WFG_TRANS_LIST *tran_list_p;
  int error_code = ER_FAILED;

  if (csect_enter_as_reader (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      return ER_FAILED;
    }

  for (i = 0; i < wfg_Total_tran_groups; i++)
    {
      for (tran_list_p = wfg_Tran_group[i].waiter_tran_list_p; tran_list_p != NULL; tran_list_p = tran_list_p->next)
    {
      if (tran_index == tran_list_p->tran_index)
        {
          error_code = NO_ERROR;
          goto end;
        }
    }
    }

end:
  csect_exit (thread_p, CSECT_WFG);

  return error_code;
}

/*
 * wfg_get_tran_entries :
 *
 * return : returns : number of tran entries if all OK, ER status otherwise
 *
 *   tran_index(IN) : Transaction index
 *
 */
int
wfg_get_tran_entries (THREAD_ENTRY * thread_p, const int tran_index)
{
  int i, n = 0;

  if (csect_enter_as_reader (thread_p, CSECT_WFG, INF_WAIT) != NO_ERROR)
    {
      return ER_FAILED;
    }

  for (i = 0; i < wfg_Total_nodes; i++)
    {
      WFG_EDGE *e;

      for (e = wfg_Nodes[i].first_holder_edge_p; e; e = e->next_holder_edge_p)
    {
      n += (tran_index == e->waiter_tran_index);
    }
      for (e = wfg_Nodes[i].first_waiter_edge_p; e; e = e->next_waiter_edge_p)
    {
      n += (tran_index == e->waiter_tran_index);
    }
    }

  for (i = 0; i < wfg_Total_tran_groups; i++)
    {
      WFG_TRANS_LIST *tl;

      for (tl = wfg_Tran_group[i].holder_tran_list_p; tl; tl = tl->next)
    {
      n += (tran_index == tl->tran_index);
    }
      for (tl = wfg_Tran_group[i].waiter_tran_list_p; tl; tl = tl->next)
    {
      n += (tran_index == tl->tran_index);
    }
    }

  csect_exit (thread_p, CSECT_WFG);

  return n;
}
#endif /* ENABLE_UNUSED_FUNCTION */