text: /*
   * Copyright 2010 Andrea Mazzoleni. All rights reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   *
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   *
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in the
   *    documentation and/or other materials provided with the distribution.
   *
   * THIS SOFTWARE IS PROVIDED BY ANDREA MAZZOLENI AND CONTRIBUTORS ``AS IS''
   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   * ARE DISCLAIMED.  IN NO EVENT SHALL ANDREA MAZZOLENI OR CONTRIBUTORS BE
   * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
   * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
   * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
   * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
   * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
   * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   * POSSIBILITY OF SUCH DAMAGE.
   */
  
  #include "ssm/ext/tommyds/tommylist.h"
  #include "ssm/ext/tommyds/tommychain.h"
  
  void tommy_list_concat(tommy_list* first, tommy_list* second)
  {
  	tommy_node* first_head;
  	tommy_node* first_tail;
  	tommy_node* second_head;
  
  	if (tommy_list_empty(second)) {
  		return;
  	}
  
  	if (tommy_list_empty(first)) {
  		*first = *second;
  		return;
  	}
  
  	first_head = tommy_list_head(first);
  	second_head = tommy_list_head(second);
  	first_tail = tommy_list_tail(first);
  
  	/* set the "circular" prev list */
  	first_head->prev = second_head->prev;
  	second_head->prev = first_tail;
  
  	/* set the "0 terminated" next list */
  	first_tail->next = second_head;
  }
  
  /** \internal
   * Setup a list.
   */
  tommy_inline void tommy_list_set(tommy_list* list, tommy_node* head, tommy_node* tail)
  {
  	head->prev = tail;
  	tail->next = 0;
  	*list = head;
  }
  
  void tommy_list_sort(tommy_list* list, tommy_compare_func* cmp)
  {
  	tommy_chain chain;
  	tommy_node* head;
  
  	if (tommy_list_empty(list))
  		return;
  
  	head = tommy_list_head(list);
  
  	/* create a chain from the list */
  	chain.head = head;
  	chain.tail = head->prev;
  
  	tommy_chain_mergesort(&chain, cmp);
  
  	/* restore the list */
  	tommy_list_set(list, chain.head, chain.tail);
  }
  
  