vlib

Letze Änderung: Freitag   17.03.2006
Plattformunabhängig
Komplette Linked List Lib mit den typischen Operationen (push, pop, reverse, move, sub, insert, remove, get, size, join, print, split, merge, sort)

Lizenz: BSD

/*  Copyright (c) 2004-2006, Philip Busch <broesel@studcs.uni-sb.de>
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions are met:
 *
 *   - Redistributions of source code must retain the above copyright notice,
 *     this list of conditions and the following disclaimer.
 *   - 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.
 *   - Neither the name of the author nor the names of its contributors may
 *     be used to endorse or promote products derived from this software
 *     without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 THE COPYRIGHT OWNER 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 <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>


/* list node */
typedef struct node node;
struct node {
	node *next;
	void *data;
};


/* auxiliary data type for test purposes, used in _create123() and _print() */
typedef struct _data {
	int n;
	char str[1024];
} data;


int
list_push(node **_x, void *_data) {
	node *n = NULL;

	assert(_x != NULL);

	if((n = (node *)malloc(sizeof(node))) == NULL) {
		return(-1);
	} else {
		n->data = _data;
		n->next = *_x;

		*_x = n;
		return(0);
	}
}

void *
list_pop(node **_x) {
	node *n = NULL;
	void *data;
	
	assert(_x != NULL);

	if(*_x == NULL)
		return(NULL);
		
	n = *_x;
	*_x  = n->next;
	data = n->data;
	free(n);

	return(data);
}

int
list_move(node **_dest, node **_src) {
	node *n = NULL;
	
	assert((_dest != NULL) && (_src != NULL));

	if(*_src == NULL)
		return(-1);

	n = *_src;
	*_src = n->next;
	n->next = *_dest;
	*_dest = n;

	return(0);
}

int
list_reverse(node **_x) {
	node *n = NULL;

	assert(_x != NULL);

	while(list_move(&n, _x) >= 0);
	*_x = n;

	return(0);
}

node *
list_sub(const node *_x, int _pos) {
	int i = 0;
	node *n = (node *)_x;

	assert(_x != NULL);

	if(_pos < 0)
		return(NULL);

	while(i++ < _pos) {
		if((n = n->next) == NULL)
			return(NULL);
	}

	return(n);
}

int
list_insert(node **_x, int _pos, void *_data) {
	node *p;

	assert(_x != NULL);

	if(_pos < 0)
		return(-1);
	        
	if(_pos == 0)
	        return(list_push(_x, _data));

	if((p = list_sub(*_x, _pos-1)) == NULL)
		return(-1);

	return(list_push(&(p->next), _data));
}

void *
list_remove(node **_x, int _pos) {
	node *current = *_x;
	node *next = NULL;
	void *data;

	assert(_x != NULL);

	if(_pos < 0)
	        return(NULL);
	
	if(*_x == NULL)
	        return(NULL);

	if(_pos == 0)
	        return(list_pop(_x));

	while(--_pos) {
		current = current->next;
	}

	if((next = current->next) == NULL)
	        return(NULL);
	        
	data = next->data;
	current->next = next->next;

	free(next);
	return(data);
	
	return(0);
}

void *
list_get(const node *_x, int _n) {
	int i = 0;

	while(_x != NULL) {
		if(_n == i++)
		        return(_x->data);
		_x = _x->next;
	}

	return(NULL);
}

size_t
list_size(const node *_x) {
	size_t s = 0;

	for(; _x != NULL; s++, _x = _x->next);
	return(s);
}

node *
list_join(node *_a, node *_b) {
	node *n = _a;

	if(_a == NULL)
	        return(_b);
	        
	while(_a->next != NULL)
	        _a = _a->next;
	        
	_a->next = _b;

	return(n);
}

void
list_print(const node *_a) {
	data *foo;
	int i = 0;

        while(_a != NULL) {
		foo = (data *)_a->data;
		printf("%03d: %3d - %s\n", i++, foo->n, foo->str);
		_a = _a->next;
        }
}

/* hare and tortoise approach / classic Floyd&#146;s Cycle Finding Algorithm */
int
list_split(node **_src, node **_front, node **_back) {
	node *fast, *slow;

	assert((_src != NULL) && (_front != NULL) && (_back != NULL));

	if((*_src == NULL) || ((*_src)->next == NULL)) {
		*_back = NULL;
	} else {
		slow = *_src;
		fast = slow->next;
		
		while(fast != NULL) {
			fast = fast->next;
			if(fast != NULL) {
				slow = slow->next;
				fast = fast->next;
			}
		}
		*_back = slow->next;
		slow->next = NULL;
	}

	*_front = *_src;
	*_src = NULL;
	return(0);
}

int
list_merge(node **_dest, node **_a, node **_b, int _cmp(void *, void *)) {
	node *ret = NULL;
	node **last = &ret;

	assert((_dest != NULL) && (_a != NULL) && (_b != NULL));

	for(;;) {
		if(*_a == NULL) {
			*last = *_b;
			break;
		}

		if(*_b == NULL) {
		        *last = *_a;
		        break;
		}
		
		if(_cmp((*_a)->data, (*_b)->data) <= 0) {
			list_move(last, _a);
		} else {
			list_move(last, _b);
		}
		
		last = &((*last)->next);
	}

	*_dest = ret;
	return(0);
}

int
list_sort(node **_x, int _cmp(void *, void *)) {
	node *l, *r;

	assert(_x != NULL);

	if(*_x == NULL || (*_x)->next == NULL)
	        return(0);

	list_split(_x, &l, &r);

	list_sort(&l, _cmp);
	list_sort(&r, _cmp);
	
	list_merge(_x, &l, &r, _cmp);

	return(0);
}

int
list_copy(const node *_src, node **_dest) {
	assert(_src != NULL);

	*_dest = NULL;

	while(_src) {
		if(list_push(_dest, _src->data)) {
			return(-1);
		} else {
			_src = _src->next;
		}
	}
	return(list_reverse(_dest));
}

int
list_realloc(node *_x, size_t _sz) {
	void *data;

	assert(_x != NULL);

	while(_x) {
		if((data = malloc(_sz)) == NULL) {
			return(-1);
		} else {
			_x->data = memcpy(data, _x->data, _sz);
			_x = _x->next;
		}
	}
	return(0);
}

int
list_dup(node *_src, node **_dest, size_t _sz) {
	assert(_src != NULL);

	if(list_copy(_src, _dest) < 0)
	        return(-1);

	if(list_realloc(*_dest, _sz) < 0)
	        return(-1);
	        
	return(0);
}

void
list_delete(node **_x) {
	assert(_x != NULL);
	
	while(*_x) {
		list_pop(_x);
	}
}

void
list_destroy(node **_x) {
	assert(_x != NULL);

	while(*_x) {
		free(list_pop(_x));
	}
}

void *
list_jump(node **_x) {
	void *data;

	assert(_x != NULL);
	
	if(*_x == NULL)
	        return(NULL);
	        
	data = (*_x)->data;
	*_x = (*_x)->next;
	return(data);
}

node *
list_create123() {
	node *n = NULL;
	data *a=malloc(sizeof(data)),
	     *b=malloc(sizeof(data)),
	     *c=malloc(sizeof(data));

	a->n = 1;
	strcpy(a->str, "foo");
	b->n = 2;
	strcpy(b->str, "bar");
	c->n = 3;
	strcpy(c->str, "snafu");

	list_push(&n, a);
	list_push(&n, b);
	list_push(&n, c);
	return(n);
}

/* auxiliary function for testing list_sort() */
int
cmp(void *_a, void *_b) {
	data *a = (data *)_a, *b = (data *)_b;

	if(a->n < b->n) return(-1);
	if(a->n > b->n) return(1);
	return(0);
}

int main() {
	node *x = NULL;

	x = list_create123();

	list_print(x);
	list_sort(&x, cmp);
	list_print(x);

	return(0);
}

Diskussion zur Linked List lib