xlib_playground

list.c (3930B)

---

 #include <stdio.h>
 #include <stdlib.h>
 
 #include "list.h"
 
 
 static int __lqsort(List *p, List *tail,
 	int (* cmp)(void *, void *));
 static void __lprint(List *p, List *tail, void (* pfnc)(void *));
 
 static int list_count = 0;
 
 /*
  * Laddfront() adds item in front of List p.
  * Returns NULL if error occured.
  */
 List *
 laddfront(List *p, void *item)
 {
 	if (item == NULL) {
 		// TODO: should print some message ??
 		//fprintf(stderr, "laddfront: Error. Item is NULL\n");
 		return NULL;
 	}
 
 	List *newlp;
 	if((newlp = (List *)malloc(sizeof(List))) == NULL) {
 		fprintf(stderr, "laddfront: Error. Could not allocate memory.\n");
 		return NULL;
 	}
 	list_count++;
 	newlp->item = item;
 	newlp->next = p;
 	return newlp;
 }
 
 /*
  * Lfree() frees List *p. Its items should be freed elsewhere.
  */
 void
 lfree(List *p)
 {
 	List *q;
 	for (q = p; q != NULL; q = p) {
 		p = q->next;
 		free(q);
 		list_count--;
 	}
 }
 
 /*
  * Lfreei() frees List *p. Its items are freed using ifree().
  */
 void
 lfreei(List *p, void (* ifree)(void *))
 {
 	List *q;
 	for (q = p; q != NULL; q = p) {
 		p = q->next;
 		ifree(q->item);
 		free(q);
 		list_count--;
 	}
 }
 
 int
 get_list_count(void)
 {
 	return list_count;
 }
 
 void
 lprint(List *p, void (* pfnc)(void *))
 {
 	__lprint(p, NULL, pfnc);
 }
 
 void
 __lprint(List *p, List *tail, void (* pfnc)(void *))
 {
 	if (p == NULL) {
 		printf("\n");
 	}
 	for (;p != tail && p != NULL; p = p->next) {
 		if (p->item == NULL) {
 			fprintf(stderr, "__lprint: Error. Item is NULL\n");
 			return;
 		}
 		(*pfnc)(p->item);
 		printf("%s", p->next == tail ? "\n" : "->");
 	}
 	if (p != tail) {
 		fprintf(stderr, "__lprint: Warning. Tail not found in the list.\n");
 	}
 }
 
 /*
  * Bubble sort. returns -1 if error occured, 0 if succeed.
  */
 int
 lbsort(List *p, int (* cmp)(void *, void *))
 {
 	List *q;
 
 	for (;p != NULL && p->next != NULL; p = p->next) {
 		for (q = p->next; q != NULL; q = q->next) {
 			if (p->item == NULL || q->item == NULL) {
 				fprintf(stderr, "lbsort: Error. List without item.\n");
 				return -1;
 			}
 			if (cmp(p->item, q->item) > 0) {
 				lswap(p, q);
 			}
 		}
 	}
 	return 0;
 }
 
 /*
  * Quick sort
  * Lqsort() sorts entire List p, according to the results of cmp().
  * __lqsort() sorts the List from p to the item before tail.
  * Tail can be NULL. This case __lqsort() sorts entire List.
  * Returns 0 if succeed, -1 if error occured.
  */
 int
 lqsort(List *p, int (* cmp)(void *, void *))
 {
 	return __lqsort(p, NULL, cmp);
 }
 
 static int
 __lqsort(List *p, List *tail, int (* cmp)(void *, void *))
 {
 	if (p == tail || p->next == tail)
 		return 0;
 
 	List *pivot, *q, *last;
 	int i;
 
 	/* select the pivot randomly */
 	for (i = 0, q = p; q != tail; q = q->next) {
 		if (rand() % ++i == 0)
 			pivot = q;
 	}
 
 	lswap(p, pivot);
 	last = p;
 	for (q = p->next; q != tail; q = q->next) {
 		if (p->item == NULL || q->item == NULL) {
 			fprintf(stderr, "lbsort: Error. List without item.\n");
 			return -1;
 		}
 		if (cmp(p->item, q->item) > 0) {
 			last = last->next;
 			lswap(last, q);
 		}
 	}
 	lswap(p, last);
 
 	__lqsort(last->next, tail, cmp);
 	__lqsort(p, last, cmp);
 
 	return 0;
 }
 
 void
 lswap(List *p, List *q)
 {
 	if (p == NULL || q == NULL)
 		return;
 	void *tmp;
 	tmp = p->item;
 	p->item = q->item;
 	q->item = tmp;
 }
 
 /*
  * Leqa() returns 1 if two Lists are identicall, 0 if not.
  * Only checks the address of each items.
  */
 int
 leqa(List *p, List *q)
 {
 	for (;p != NULL && q != NULL; p = p->next, q = q->next) {
 		if (p->item != q->item)
 			return 0;
 	}
 	if (p == NULL && q == NULL)
 		return 1;
 	return 0;
 }
 
 /*
  * Leqi() returns 1 if two Lists are identicall, 0 if not.
  * Compares each items with eq().
  */
 int
 leqi(List *p, List *q, int (*eq)(void *, void*))
 {
 	for (;p != NULL && q != NULL; p = p->next, q = q->next) {
 		if (!eq(p->item, q->item))
 			return 0;
 	}
 	if (p == NULL && q == NULL)
 		return 1;
 	return 0;
 }
 
 unsigned long int
 llen(List *p)
 {
 	unsigned long len = 0;
 	for (; p != NULL; p = p->next)
 		len++;
 	return len;
 }