list.c

* A ncurses user interface. * Network statistics to view the amount of packets and data in many

/* List 
*  This program is free software; you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation; either version 2 of the License, or
*  (at your option) any later version.
*
*  This program 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 General Public License
*  along with this program; if not, write to the Free Software
*  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
* Author:
*	NAME:	James Stevenson
*	EMAIL:	[e-mail]
*	WWW:	http://www.stev.org
*/


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

#include "list.h"

#define LIST_BLK 4096		/* this is a blk size to save malloc's and realloc's */


/**
 *	list_bsearch - binary split search on the list
 *	@p: A valid pointer to a sorted list
 *	@data: data to try to find
 *
 *	A binary split search the list must be sorted
 *	a valid index in the list is returned
 *	< 0 is returned on an error or nothing found
 *	if the list is not sorted it uses the function
 *	list_lsearch
 */
int list_bsearch(struct list_t *p, void *data) {
	int top, bot, mid, ret;

	if (!p->func_cmp)
		return -1;

	if (!p->sorted) /* we must be sorted to use this */
		list_lsearch(p, data);

	if (p->length < 1)
		return -1;	/* we dont have any records */

	bot = 0;			/* the bottom is always 0 */
	top = p->length;	/* not p->array[top] will crash */
	mid = top / 2;		/* setup the middle */
	/* lets do a simple bsearch :) */
	while(bot < mid) {
		if (0 == (ret = p->func_cmp(p->array[mid], data)))
			return mid;	/* we found it */
		if (ret < 0) { /* we need to move into the top half */
			bot = mid;			/* we now know that it has to be higher than the middle */
			/* top stays unchanged */
			mid = (top - bot) / 2 + bot;	/* the new middle */
		} else { /* we are moving down the list */
			/* bottom stays the same */
			top = mid;			/* we know it cannot be higher that top */
			mid = (top - bot) / 2 + bot;
		}
	}

	/* if we get here there is only 1 record left */
	if (p->func_cmp(p->array[0], data) == 0)
		return 0;

	return -1;
}

/**
 *	list_lsearch - a loop search
 *	@p: A valid pointer to a sorted list
 *	@data: data to try to find
 *
 *	runs thought the list until a match is found
 *	a valid index in the list is returned
 *	< 0 is returned on an error or nothing found
 */
int list_lsearch(struct list_t *p, void *data) {
	int i;
	if (!p->func_cmp)
		return -1;
	/* run though until we find one */
	for(i=0;i<p->length;i++)
		if (p->func_cmp(p->array[i], data) == 0)
			return i;
	
	return -2; /* if we get to here we did not find a record */	
}


/**
 *	list_bsort - run a bubble sort on the list
 *	@p: a valid pointer to a list
 *
 *	setcmp must have already be used on the list
 *	< 0 is returned if an error occurs
 */
int list_bsort(struct list_t *p) {
	int y, x;
	void *tmp;
	if (!p->func_cmp)
		return -1; /* opps somebody forgot to set the function */
	/* simple bubble sort */
	for(y=0;y<p->length;y++) {
		for(x=0;x<p->length;x++) {
			if (p->func_cmp(p->array[y], p->array[x]) < 0) {
				/* just swap the vars */
				tmp = p->array[x];
				p->array[x] = p->array[y];
				p->array[y] = tmp;
			}
		} /* end for x */
	} /* end for y */
	p->sorted = 1;	/* it should now be sorted */
	return 0;
}

/**
 *	list_insert - insert an item into the list
 *	@p: A valid pointer
 *	@n: the place where you want to insert
 *	@data: pointer to data that you want to insert
 *
 *	returns < 0 on error
 *	the number of items in the list
 */
int list_insert(struct list_t *p, int n, void *data) {
	int c;
	if (n > p->length)	/* n can be == p->length */
		return -1;	/* n is out of range */

	if (n == p->length)	/* means put it at the end */
		return list_add(p, data);
	
	if (list_realloc(p, p->length + 1) < 0)
		return -1;	/* the list does not have space to put things */

	/* this seems to corrupt memory 
	memmove(&p->array[n + 1], &p->array[n], (p->length - n - 1) * sizeof(p->array) );
	so do this instead */
	c = p->length;
	while(c > n) {
		p->array[c] = p->array[c - 1];
		c--;
	}	

	p->array[n] = data;
	p->length++;
	p->sorted = 0;	/* we might not be sorted any more */
	return p->length;
}

/**
 *	list_del - deletes an item from the list
 *	@p:	A valid pointer to the list
 *	@n: the item number you want to delete
 *
 *	Deletes an item from the list
 *	returns < 0 if an error occurs
 */
int list_del(struct list_t *p, int n) {
	if (n >= p->length)
		return -1;	/* not a valid range */
	memmove(&p->array[n], &p->array[n + 1], (p->length - 1 - n) * sizeof(p->array) );
	/* FIXME need list_shrink */
	p->length--;
	return p->length;
}
/**
 *	list_get - Gets an item from the list
 *	@p:	A valiv pointer to a list
 *	@n: the item number you want
 *
 *	returns a pointer
 *	or NULL if an error occured
 */
void *list_get(struct list_t *p, int n) {
	if (n >= p->length)
		return NULL;
	return p->array[n];
}


/**
 *	list_add_lsort - Add an item to the list + sort
 *	@p: A valid pointer to a list
 *	@data: pointer to data to add
 *
 *	Add a record to the list and sort it faster than
 *	list_add + list_sort
 *	user list_add_bsort if possible
 *	returns the number of items in the list on success
 *	< 0 if an error occured
 */
int list_add_lsort(struct list_t *p, void *data) {
	int i, ret, issort;

	if (!p->func_cmp)
		return -1;

	for(i=0;i<p->length;i++) {
		ret = p->func_cmp(p->array[i], data);
		if (ret > 0) {
			issort = p->sorted;	/* need to store this because list_insert modifies it */
			ret = list_insert(p, i, data);
			p->sorted = issort;	/* restores the origanl vale */
			return ret;
		}
	}
	/* if we get this far we just add it */
	/* because it is the last one on the list */
	return list_add(p, data);
}

/**
 *	list_add - Adds and item to the list
 *	@p: A valid pointer to a list
 *	@data: a pointer to the data to add
 *
 *	Adds an item to the list
 *	returns the number in the list on success
 *	< 0 if an error occurs
 */
int list_add(struct list_t *p, void *data) {
	if (list_realloc(p, p->length + 1) < 0)
			return -1;	/* the list does not have space to put things */
		
	/* We have enough space to put stuff */
	p->array[p->length] = data;	/* p->length is always 1 ahead */
	p->sorted = 0;				/* it wont be sorted any more */
	return ++p->length;
}

/**
 *	list_realloc - make the list bigger
 *	@p: a valid pointer to the list
 *	@nlength: the length the list must hold
 *
 *	This will make the list big enough to hold
 *	nlength items
 *	returns < 0 on error
 *	>0 on success
 *	0 never gets returned
 */
inline int list_realloc(struct list_t *p, int nlength) {
	void **narray;	/* placement for new array */
	
	/* nlength must be >= than the amount of alloced memory so */
	/* mlength * LIST_BLK contains the amount of space for items */
	if (nlength > p->mlength * LIST_BLK) {
		narray = realloc(p->array, sizeof(p->array) * (LIST_BLK * ++p->mlength));
		if (!narray) { /* check is we failed */
			p->mlength--;
			return -1;
		}
		p->array = narray;	/* copy the new pointer over */
		return 1;
	}
	/* if we get to here then it worked */
	return 0;
}

/**
 *	list_length - the length of the list
 *	@p:	a valid pointer to a list
 *
 *	returns the length of the list
 */
inline int list_length(struct list_t *p) {
	return p->length;
}

/**
 *	list_setcmp - set the compare function for searchs
 *	@p:	a valid pointer to a list
 *	@cmp: a pointer to a compare function
 *
 *	does not return a value
 *	the function must be of type
 *	(const void *c1, const void *c2)
 */
void list_setcmp(struct list_t *p, int (*cmp) (const void *c1, const void *c2) ) {
	p->func_cmp = cmp;
	return;
}

/**
 *	list_init - get a pointer for a new list
 *
 *	returns a new pointer to a list
 *	returns NULL if an error occurs
 */
struct list_t *list_init() {
	struct list_t *tmp;
	tmp = malloc( sizeof(struct list_t));
	if (!tmp)
		return NULL; /* opps OOM */

	/* set up each of the vars */
	tmp->length = 0;
	tmp->mlength = 1;
	tmp->func_cmp = NULL;
	tmp->sorted = 1; /* this list is sorted if it has no entries */

	/* alloc to the total number of blocks * blocksize and * sizeof(void *) */
	tmp->array = malloc( sizeof(tmp->array) * (LIST_BLK * tmp->mlength) );
	if (!tmp->array)
		goto free_out;	/* opps OOM */

	return tmp;	/* it worked */
free_out:		/* something bad happened */
	free(tmp);	/* this has been alloced */
	return NULL;	/* return NULL pointer */
}

/**
 *	list_free - free a list
 *	@p:	A valid pointer to a list
 *
 *	returns < 0 on error
 */
int list_free(struct list_t *p) {
	/* just free off a few thigns and return 0 */
	free(p->array);
	free(p);
	return 0;
}