#ifndef CGPERF_KEYWORD_LIST_C
#define CGPERF_KEYWORD_LIST_C
#include <stdlib.h>

#include "keyword.h"
#include "keyword_list.h"
/*------------------------------------------------------------------------------------------------*/
#include "namespace/keyword.h"
#include "namespace/keyword_list.h"
/*------------------------------------------------------------------------------------------------*/
/*{{{ kwl_new */
static struct Keyword_List *kwl_new(struct Keyword *kw)
{
	struct Keyword_List *t;

	t = calloc(1, sizeof(*t));
	t->kw = kw;
	return t;
}/*}}}*/
/*{{{ kwextl_del */
static void kwl_del(struct Keyword_List *t)
{
	free(t);
}/*}}}*/
/*{{{ delete_list */
static void delete_list(struct Keyword_List *list)
{
	loop {
		struct Keyword_List *next;

		if (list == 0)
			break;
		next = list->next;
		kwl_del(list);
		list = next;
	}
}/*}}}*/
/*{{{ copy_list_ext */
static struct Keyword_List *copy_list(struct Keyword_List *list)
{
	struct Keyword_List *result;
	struct Keyword_List **lastp;

	lastp = &result;
	loop {
		struct Keyword_List *new_cons;

		if (list == 0)
			break;
		new_cons = kwl_new(list->kw);
		*lastp = new_cons;
		lastp = &new_cons->next;
		list = list->next;
	}
	*lastp = 0;
	return result;
}/*}}}*/
/*{{{ mergesort_list */
/*
 * Sorts a linear list, given a comparison function.
 * Note: This uses a variant of mergesort that is *not* a stable sorting algorithm.
 */
static struct Keyword_List *mergesort_list(struct Keyword_List *list, bool (*less)(
							struct Keyword *kw1, struct Keyword *kw2))
{
	struct Keyword_List *middle;
	struct Keyword_List *tmp;
	struct Keyword_List *right_half;

	if (list == 0 || list->next == 0)
    		/* List of length 0 or 1. Nothing to do. */
		return list;
	middle = list;
	tmp = list->next;
	loop {
		tmp = tmp->next;
		if (tmp == 0)
			break;
		tmp = tmp->next;
		middle = middle->next;;
		if (tmp == 0)
			break;
	}
	/*
	 * Cut the list into two halves.
	 * If the list has n elements, the left half has ceiling(n/2) elements and the right half
	 * has floor(n/2) elements.
	 */
	right_half = middle->next;
	middle->next = 0;
	return merge(mergesort_list(list, less), mergesort_list(right_half, less), less);
}/*}}}*/
/*{{{ merge */
static struct Keyword_List *merge(struct Keyword_List *list1, struct Keyword_List *list2, bool
					(*less)(struct Keyword *kw1, struct Keyword *kw2))
{
	struct Keyword_List *result;
	struct Keyword_List **resultp;

	resultp = &result;
	loop {
		if (list1 == 0) {
			*resultp = list2;
			break;
		}
		if (list2 == 0) {
			*resultp = list1;
			break;
		}
		if (less(list2->kw, list1->kw)) {
			*resultp = list2;
			resultp = &list2->next;
			/*
			 * We would have a stable sorting if the next line would read: list2 =
			 * *resultp;
			 */
			list2 = list1;
			list2 = *resultp;
		} else {
			*resultp = list1;
			resultp = &list1->next;
			list1 = *resultp;
		}
	}
	return result;
}/*}}}*/
/*------------------------------------------------------------------------------------------------*/
#define EPILOG
#include "namespace/keyword.h"
#include "namespace/keyword_list.h"
#undef EPILOG
/*------------------------------------------------------------------------------------------------*/
#endif