Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
       3             :  *
       4             :  * Redistribution and use in source and binary forms, with or without
       5             :  * modification, are permitted provided that the following conditions
       6             :  * are met:
       7             :  *
       8             :  * 1. Redistributions of source code must retain the above copyright
       9             :  *    notice, this list of conditions and the following disclaimer.
      10             :  *
      11             :  * 2. Redistributions in binary form must reproduce the above copyright
      12             :  *    notice, this list of conditions and the following disclaimer in the
      13             :  *    documentation and/or other materials provided with the distribution.
      14             :  *
      15             :  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
      16             :  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
      17             :  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
      18             :  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
      19             :  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
      20             :  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
      21             :  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
      22             :  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
      23             :  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
      24             :  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
      25             :  * POSSIBILITY OF SUCH DAMAGE.
      26             :  */
      27             : 
      28             : #include "tommylist.h"
      29             : #include "tommychain.h"
      30             : 
      31             : /** \internal
      32             :  * Setup a list.
      33             :  */
      34        1691 : tommy_inline void tommy_list_set(tommy_list* list, tommy_node* head, tommy_node* tail)
      35             : {
      36        1691 :         head->prev = tail;
      37        1691 :         tail->next = 0;
      38        1691 :         *list = head;
      39        1691 : }
      40             : 
      41        2481 : void tommy_list_sort(tommy_list* list, tommy_compare_func* cmp)
      42             : {
      43             :         tommy_chain chain;
      44             :         tommy_node* head;
      45             : 
      46        2481 :         if (tommy_list_empty(list))
      47         790 :                 return;
      48             : 
      49        1691 :         head = tommy_list_head(list);
      50             : 
      51             :         /* create a chain from the list */
      52        1691 :         chain.head = head;
      53        1691 :         chain.tail = head->prev;
      54             : 
      55        1691 :         tommy_chain_mergesort(&chain, cmp);
      56             : 
      57             :         /* restore the list */
      58        1691 :         tommy_list_set(list, chain.head, chain.tail);
      59             : }
      60             :