tdebase/ksysguard/CContLib/ccont.c

/*
    Lightweight C Container Library
   
	Copyright (c) 2002 Tobias Koenig <tokoe@kde.org>

	Original code was written by Chris Schlaeger <cs@kde.org>
    
    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public License
    along with this library; see the file COPYING.LIB.  If not, write to
    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
    Boston, MA 02110-1301, USA.

*/

#include "ccont.h"

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

struct container_info {
	INDEX count;
	CONTAINER currentNode;
};

typedef struct container_info T_CONTAINER_INFO;
typedef struct container_info* CONTAINER_INFO;

#define rpterr(x) fprintf(stderr, "%s\n", x)

CONTAINER new_ctnr(void)
{
	CONTAINER_INFO info;
	CONTAINER rootNode;

	rootNode = (CONTAINER)malloc(sizeof(T_CONTAINER));

	info = (CONTAINER_INFO)malloc(sizeof(T_CONTAINER_INFO));
	info->count = 0;
	info->currentNode = rootNode;

	rootNode->next = rootNode;
	rootNode->prev = rootNode;
	rootNode->data = info;

	return rootNode;
}

void zero_destr_ctnr(CONTAINER rootNode, DESTR_FUNC destr_func)
{
	INDEX counter;

	if (rootNode == NIL || destr_func == NIL) {
		rpterr("destr_ctnr: NIL argument");
		return;
	}

	for (counter = level_ctnr(rootNode); counter > -1; --counter)
		destr_func(pop_ctnr(rootNode));

	if (rootNode->data)
		free(rootNode->data);

	free(rootNode);
	rootNode = 0;

	return;
}

INDEX level_ctnr(CONTAINER rootNode)
{
	if (rootNode == NIL) {
		rpterr("level_ctnr: NIL argument");
		return -1;
	}

	return ((CONTAINER_INFO)rootNode->data)->count;
}

void insert_ctnr(CONTAINER rootNode, void* object, INDEX pos)
{
	CONTAINER it;
	INDEX counter = 0;
	
	if (rootNode == NIL || object == NIL) {
		rpterr("insert_ctnr: NIL argument");
		return;
	}

	for (it = rootNode->next; it != rootNode; it = it->next) {
		if (counter == pos) {
			CONTAINER newNode = (CONTAINER)malloc(sizeof(T_CONTAINER));

			newNode->prev = it;
			newNode->next = it->next;
			it->next->prev = newNode;
			it->next = newNode;

			newNode->data = object;
			((CONTAINER_INFO)rootNode->data)->count++;
			return;
		}

		counter++;
	}
}

void push_ctnr(CONTAINER rootNode, void* object)
{
	CONTAINER newNode;

	if (rootNode == NIL || object == NIL) {
		rpterr("push_ctnr: NIL argument");
		return;
	}

	newNode = (CONTAINER)malloc(sizeof(T_CONTAINER));
	newNode->next = rootNode;
	newNode->prev = rootNode->prev;
	rootNode->prev->next = newNode;
	rootNode->prev = newNode;

	newNode->data = object;
	((CONTAINER_INFO)rootNode->data)->count++;
}

void* remove_at_ctnr(CONTAINER rootNode, INDEX pos)
{
	CONTAINER it;
	INDEX counter = 0;
	void* retval;
	
	if (rootNode == NIL) {
		rpterr("remove_ctnr: NIL argument");
		return NIL;
	}

	for (it = rootNode->next; it != rootNode; it = it->next) {
		if (counter == pos) {
			retval = it->data;

			it->prev->next = it->next;
			it->next->prev = it->prev;

			free(it);

			((CONTAINER_INFO)rootNode->data)->count--;
			return retval;
		}

		counter++;
	}

	return NIL;
}

void* pop_ctnr(CONTAINER rootNode)
{
	CONTAINER ptr;
	void* retval;

	if (rootNode == NIL) {
		rpterr("pop_ctnr: NIL argument");
		return NIL;
	}

	if (rootNode->next == rootNode)
		return NIL;

	ptr = rootNode->next;	
	retval = ptr->data;

	rootNode->next = ptr->next;
	ptr->next->prev = rootNode;

	((CONTAINER_INFO)rootNode->data)->count--;

	free(ptr);

	return retval;
}

void* get_ctnr(CONTAINER rootNode, INDEX pos)
{
	CONTAINER it;
	INDEX counter = 0;

	if (rootNode == NIL) {
		rpterr("get_ctnr: NIL argument");
		return NIL;
	}

	for (it = rootNode->next; it != rootNode; it = it->next) {
		if (counter == pos)
			return it->data;

		counter++;
	}

	return NIL;
}

INDEX search_ctnr(CONTAINER rootNode, COMPARE_FUNC compare_func, void* pattern)
{
	CONTAINER it;
	INDEX counter = 0;

	if (rootNode == NIL || compare_func == NIL || pattern == NIL) {
		rpterr("search_ctnr: NIL argument");
		return -1;
	}
	
	for (it = rootNode->next; it != rootNode; it = it->next) {
		if (compare_func(pattern, it->data) == 0)
			return counter;

		counter++;
	}

	return -1;
}

void swop_ctnr(CONTAINER rootNode, INDEX pos1, INDEX pos2)
{
	CONTAINER it, node1, node2;
	INDEX counter = 0;
	int found = 0;
	void* tmpData;

	if (rootNode == NIL) {
		rpterr("swop_ctnr: NIL argument");
		return;
	}

	if (pos1 == pos2)
		return;

	/**
	 * it is a bit hackish because of the 'goto' but it's fast
	 * since we have to run through the list only once
	 */
	for (it = rootNode->next; it != rootNode; it = it->next) {
		if (counter == pos1) {
			node1 = it;
			if (found)
				goto swapIt;
			else
				found = 1;
		}
		if (counter == pos2) {
			node2 = it;
			if (found)
				goto swapIt;
			else
				found = 1;
		}

		counter++;
	}	

	return;

swapIt:
	tmpData = node1->data;
	node1->data = node2->data;
	node2->data = tmpData;
	return;
}

void bsort_ctnr(CONTAINER rootNode, COMPARE_FUNC compare_func)
{
	INDEX right, i, level, last;

	if (rootNode == NIL || compare_func == NIL) {
		rpterr("destr_ctnr: NIL argument");
		return;
	}

	last = level = level_ctnr(rootNode);
	do
	{
		right = last;
		last = 0;
		for (i = 1; i < right; i++)
			if (compare_func(get_ctnr(rootNode, i - 1), get_ctnr(rootNode, i)) > 0)
				swop_ctnr(rootNode, i - 1, last = i);
	} while (last > 0);
}

void* first_ctnr(CONTAINER rootNode)
{
	if (rootNode == NIL) {
		rpterr("first_ctnr: NIL argument");
		return NIL;
	}
	
	if (rootNode->next == rootNode)
		return NIL;

	((CONTAINER_INFO)rootNode->data)->currentNode = rootNode->next;

	return rootNode->next->data;
}

void* next_ctnr(CONTAINER rootNode)
{
	CONTAINER_INFO info;

	if (rootNode == NIL) {
		rpterr("next_ctnr: NIL argument");
		return NIL;
	}

	info = (CONTAINER_INFO)rootNode->data;

	if (info->currentNode->next == rootNode)
		return NIL;

	info->currentNode = info->currentNode->next;

	return info->currentNode->data;
}

void* remove_ctnr(CONTAINER rootNode)
{
	CONTAINER currentNode, tmp;
	CONTAINER_INFO info;
	void* retval;
	
	if (rootNode == NIL) {
		rpterr("remove_curr_ctnr: NIL argument");
		return NIL;
	}

	info = (CONTAINER_INFO)rootNode->data;
	currentNode = info->currentNode;

	if (currentNode == rootNode) { /* should never happen */
		rpterr("remove_curr_ctnr: delete root node");
		return NIL;
	}

	retval = currentNode->data;
	tmp = currentNode->prev;

	currentNode->prev->next = currentNode->next;
	currentNode->next->prev = currentNode->prev;

	free(currentNode);

	info->count--;
	info->currentNode = tmp;

	return retval;
}