File broker_list.c¶

File List > broker > broker_list.c
/*
 * 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.
 *
 */


/*
 * link_list.c - This module contains operations for singly linked list.
 *               The list header is a recent appended node.
 */

#ident "$Id$"


#include <stdio.h>
#include <stdlib.h>


#include "cas_common.h"
#include "broker_list.h"


static T_LIST *delete_node (T_LIST * head, T_LIST * del_node, void (*node_dealloc) (T_LIST *));
static int true_func (void *key, void *value);
static void swap_node (T_LIST * node1, T_LIST * node2);


/*
 * name:        link_list_add - append a node to a designated list
 *
 * arguments:   cur_head    - the list header(IN/OUT)
 *              add_key - the key of the node
 *              add_val - the value of the node
 *              assign_func - a function for assigning key and value
 *
 * returns/side-effects:
 *              0 : success
 *      < 0 : error code
 *
 * description: add new node to the list.
 *              created node is new list header.
 *
 * NOTE:
 *  Since the type of 'key' and 'value' of the node is 'void*',
 *  it is only possible to assign value which size is same as void ptr.
 *  For example, if string is copied to 'key', you must allocate memory
 *  in assigning function.
 */
int
link_list_add (T_LIST ** cur_head, void *add_key, void *add_val, int (*assign_func) (T_LIST *, void *, void *))
{
  T_LIST *tmp;
  T_LIST *new_node;
  int error;
  T_LIST *head = *cur_head;

  tmp = (T_LIST *) malloc (sizeof (T_LIST));
  if (tmp == NULL)
    return -1;

  if (head == NULL)
    {
      new_node = tmp;
    }
  else
    {
      *tmp = *head;
      new_node = head;
    }

  error = (*assign_func) (new_node, add_key, add_val);
  if (error < 0)
    {
      FREE_MEM (tmp);
      return error;
    }
  new_node->next = tmp;

  *cur_head = tmp;
  return 0;
}

/*
 * name:        link_list_find
 *
 * arguments:   head - list header
 *              key - key value for list search
 *              cmp_func - comparing function
 *
 * returns/side-effects:
 *              node ptr if exist.
 *      NULL ptr otherwise.
 *
 * description: search list with key value.
 *
 * NOTE:
 */
T_LIST *
link_list_find (T_LIST * head, void *key, void *val, int (*key_cmp_func) (void *, void *),
        int (*val_cmp_func) (void *, void *))
{
  T_LIST *tmp;

  if (head == NULL)
    return NULL;

  if (key_cmp_func == NULL)
    key_cmp_func = true_func;
  if (val_cmp_func == NULL)
    val_cmp_func = true_func;

  tmp = head;
  do
    {
      if ((*key_cmp_func) (tmp->key, key) && (*val_cmp_func) (tmp->value, val))
    return tmp;
      tmp = tmp->next;
    }
  while (tmp != head);

  return NULL;          /* not found */
}

/*
 * name:        link_list_node_delete - delete a node
 *
 * arguments:   head    - list header
 *              key     - key value
 *      cmp_func - comparing function
 *      node_dealloc - 'key', 'value' deallocation function
 *
 * returns/side-effects:
 *              list header ptr after the node is deleted.
 *
 * description: delete one node from list.
 *
 * NOTE:
 *  If 'key' or 'value' has its own memory, the memory must be freed
 *  in 'node_dealloc' function. But, the node container is freed in
 *  this module.
 */
int
link_list_node_delete (T_LIST ** cur_head, void *key, int (*cmp_func) (void *, void *), void (*node_dealloc) (T_LIST *))
{
  T_LIST *tmp;
  T_LIST *del;
  T_LIST *head = *cur_head;

  while (1)
    {
      del = link_list_find (head, key, NULL, cmp_func, NULL);
      if (del == NULL)
    break;

      tmp = delete_node (head, del, node_dealloc);
      *cur_head = head = tmp;
    }


  return 0;
}

/*
 * name:        link_list_node-delete2 - delete a node
 *
 * arguments:   head    - list header
 *              key     - key value
 *      value
 *      key_cmp_func - key comparing function
 *      val_cmp_func - value comparing function
 *      node_dealloc - 'key', 'value' deallocation function
 *
 * returns/side-effects:
 *              list header ptr after the node is deleted.
 *
 * description: delete one node from list.
 *
 * NOTE:
 *  If 'key' or 'value' has its own memory, the memory must be freed
 *  in 'node_dealloc' function. But, the node container is freed in
 *  this module.
 */
int
link_list_node_delete2 (T_LIST ** cur_head, void *key, void *value, int (*key_cmp_func) (void *, void *),
            int (*val_cmp_func) (void *, void *), void (*node_dealloc) (T_LIST *))
{
  T_LIST *tmp;
  T_LIST *del;
  T_LIST *head = *cur_head;

  del = link_list_find (head, key, value, key_cmp_func, val_cmp_func);
  if (del == NULL)
    return -1;

  tmp = delete_node (head, del, node_dealloc);
  *cur_head = tmp;
  return 0;
}

/*
 * name:        link_list_delete - delete list
 *
 * arguments:   head    - list header
 *              node_dealloc - 'key', 'value' deallocation function
 *
 * returns/side-effects:
 *              (T_LIST*) NULL
 *
 * description: delete all nodes of list.
 *
 * NOTE:
 *  If 'key' or 'value' has its own memory, the memory must be freed
 *  in 'node_dealloc' function. But, the node container is freed in
 *  this module.
 */
int
link_list_delete (T_LIST ** cur_head, void (*node_dealloc) (T_LIST *))
{
  T_LIST *head = *cur_head;

  while (head)
    {
      head = delete_node (head, head, node_dealloc);
    }
  *cur_head = NULL;

  return 0;
}

void *
link_list_traverse (T_LIST * head, void *(*traverse_func) (T_LIST *, void *))
{
  T_LIST *tmp;
  void *result = NULL;

  if (head == NULL)
    return NULL;

  tmp = head;
  do
    {
      result = (*traverse_func) (tmp, result);
      tmp = tmp->next;
    }
  while (tmp != head);
  return result;
}

int
link_list_default_assign_func (T_LIST * node, void *key, void *value)
{
  node->key = key;
  node->value = value;
  return 0;
}

int
link_list_default_compare_func (void *key, void *value)
{
  if (key == value)
    return 1;
  return 0;
}


static T_LIST *
delete_node (T_LIST * head, T_LIST * del_node, void (*node_dealloc) (T_LIST *))
{
  T_LIST *new_head;
  T_LIST *free_node;

  if (head == NULL)
    return NULL;

  if (del_node->next == head)
    {
      if (del_node == head)
    {
      free_node = del_node;
      new_head = NULL;
    }
      else
    {
      free_node = del_node->next;
      swap_node (del_node, del_node->next);
      new_head = del_node;
    }
    }
  else
    {
      free_node = del_node->next;
      swap_node (del_node, del_node->next);
      new_head = head;
    }

  if (node_dealloc)
    (*node_dealloc) (free_node);
  FREE_MEM (free_node);

  return new_head;
}

static int
true_func (void *key, void *value)
{
  return 1;
}

static void
swap_node (T_LIST * node1, T_LIST * node2)
{
  T_LIST tmp;

  tmp = *node1;
  *node1 = *node2;
  *node2 = tmp;
}