[digraphanalysis-cvs] digraphanalysis/src node.c, node.h, list.c, list.h, main.c, main.h, keydata.c, keydata.h, pgpkey.c, pgpkey.h,

[Jeff B. <jb...@us...>]

Update of /cvsroot/digraphanalysis/digraphanalysis/src
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv24866/digraphanalysis/src

Modified Files:
	list.c list.h main.c main.h 
Added Files:
	node.c node.h 
Removed Files:
	keydata.c keydata.h pgpkey.c pgpkey.h 
Log Message:
merging branch:JBREKER into MAIN


--- NEW FILE: node.h ---
/* $Id: node.h,v 1.2 2005/04/14 03:24:28 jbreker Exp $
 *
 * Copyright (C) 2005 Jeff Breker <jb...@sy...>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#ifndef _NODE_H_
#define _NODE_H_

#include "list.h"

struct pgpkey_s
{
	char *keyid;
	float msd;
	char *name;
	struct list_t *signatures;
};

typedef struct pgpkey_s pgpkey_t;

int pgpkey_compare(void *, void *);
int pgpkey_compare_msd(void *, void *);
unsigned int pgpkey_distance(pgpkey_t *, pgpkey_t *);
void pgpkey_msd(pgpkey_t *, struct list_t *);
pgpkey_t *pgpkey_new(char *, char *);

#endif /* _NODE_H_ */

--- keydata.c DELETED ---

--- pgpkey.c DELETED ---

Index: main.h
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/main.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** main.h	18 Mar 2005 20:42:22 -0000	1.1
--- main.h	14 Apr 2005 03:24:28 -0000	1.2
***************
*** 23,33 ****
  
  #include "list.h"
! #include "pgpkey.h"
  
! int analyze_key(pgpkey_t *, list_t *, list_t *, list_t *, list_t *, list_t *);
! int do_analysis(list_t *, char *);
! void output_file(pgpkey_t *, list_t *, list_t *, list_t *, list_t *);
! list_t *parse_keyring(char *);
! void print_list(FILE *, list_t *);
  void usage(void);
  int wot_compare(void *, void *);
--- 23,33 ----
  
  #include "list.h"
! #include "node.h"
  
! int analyze_key(pgpkey_t *, struct list_t *, struct list_t *, struct list_t *, struct list_t *, struct list_t *);
! int do_analysis(struct list_t *, char *);
! void output_file(pgpkey_t *, struct list_t *, struct list_t *, struct list_t *, struct list_t *);
! struct list_t *parse_keyring(void);
! void print_list(FILE *, struct list_t *);
  void usage(void);
  int wot_compare(void *, void *);

--- pgpkey.h DELETED ---

Index: list.h
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/list.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** list.h	18 Mar 2005 20:42:22 -0000	1.1
--- list.h	14 Apr 2005 03:24:28 -0000	1.2
***************
*** 17,49 ****
  
  #ifndef _LIST_H_
- 
  #define _LIST_H_
  
! struct node_s
! {
! 	void *object;
! 	struct node_s *next, *prev;
! };
  
! struct list_s
  {
! 	int (*compare) (void *, void *);
! 	unsigned int size;
! 	struct node_s *head, *tail;
  };
  
! typedef struct list_s list_t;
! typedef struct node_s node_t;
  
! int list_add_object(list_t *, void *);
! list_t *list_duplicate(list_t *);
! void *list_find_object(list_t *, void *);
! void list_free(list_t *);
! list_t *list_merge_list(list_t *, list_t *);
! list_t *list_new(int (*) (void *, void *));
! node_t *list_new_node(void *, node_t *, node_t *);
! void list_remove(list_t *, void *);
! list_t *list_resort(list_t *);
! list_t *list_union(list_t *, list_t *);
  
  #endif
--- 17,43 ----
  
  #ifndef _LIST_H_
  #define _LIST_H_
  
! #include <sys/queue.h>
  
! struct node_t
  {
! 	void *object;
! 	LIST_ENTRY(node_t) entries;
  };
  
! LIST_HEAD(list_t, node_t);
  
! void		*list_add_object(struct list_t *, void *, int (*)(void *, void *));
! struct list_t	*list_duplicate(struct list_t *, int (*)(void *, void *));
! void		*list_find_object(struct list_t *, void *, int (*)(void *, void *));
! void		 list_free(struct list_t *);
! struct list_t	*list_merge_list(struct list_t *, struct list_t *, int (*)(void *, void *));
! struct list_t	*list_new();
! struct node_t	*list_new_node(void *);
! void		 list_remove(struct list_t *, void *, int (*)(void *, void *));
! struct list_t	*list_resort(struct list_t *, int (*)(void *, void *));
! unsigned int	 list_size(struct list_t *);
! struct list_t	*list_union(struct list_t *, struct list_t *, int (*)(void *, void *));
  
  #endif

--- keydata.h DELETED ---

Index: list.c
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/list.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** list.c	18 Mar 2005 20:42:22 -0000	1.1
--- list.c	14 Apr 2005 03:24:28 -0000	1.2
***************
*** 16,19 ****
--- 16,21 ----
   */
  
+ #include <sys/queue.h>
+ 
  #include <errno.h>
  #include <stdio.h>
***************
*** 23,97 ****
  
  /* Returns:
!  *	-1 on error
!  *	 0 if object was not added (ie a compare() call returned 0 with one of the already present objects)
!  *	 1 if the object was added
!  *
!  * This might be more usefull if we returned the object that is in the list or NULL on error
   */
! int list_add_object(list_t *list, void *object)
  {
  	int i;
! 	node_t *iter;
! 
! 	iter = list->head;
! 
! 	if(iter == NULL)
! 	{
! 		if((list->head = list->tail = list_new_node(object, NULL, NULL)) == NULL)
! 			return -1;
! 		++(list->size);
  
! 		return 1;
! 	}
! 	while(iter->next != NULL)
! 	{
! 		if((i = list->compare(object, iter->object)) < 0)
  		{
! 			if((iter = list_new_node(object, iter, iter->prev)) == NULL)
! 				return -1;
! 			if(iter->prev == NULL)
! 				list->head = iter;
  			else
! 				iter->prev->next = iter;
! 			iter->next->prev = iter;
! 			++(list->size);
! 			return 1;
  		}
- 		else
- 			if(i == 0)
- 				return 0;
- 		iter = iter->next;
- 	}
- 	if((i = list->compare(object, iter->object)) < 0)
- 	{
- 		if((iter = list_new_node(object, iter, iter->prev)) == NULL)
- 			return -1;
- 		if(iter->prev == NULL)
- 			list->head = iter;
- 		else
- 			iter->prev->next = iter;
- 		iter->next->prev = iter;
- 		++(list->size);
- 		return 1;
- 	}
- 	else
- 		if(i == 0)
- 			return 0;
- 	if((iter->next = list->tail = list_new_node(object, NULL, iter)) == NULL)
- 		return -1;
- 	++(list->size);
  
! 	return 1;
  }
  
  /* Returns NULL on error
   */
! list_t *list_duplicate(list_t *list)
  {
! 	list_t *ret_list;
  
! 	if((ret_list = list_new(list->compare)) == NULL)
  		return NULL;
! 	if(list_merge_list(ret_list, list) == NULL)
  		return NULL;
  
--- 25,71 ----
  
  /* Returns:
!  * 	object that is in the list or NULL on error
   */
! void *list_add_object(struct list_t *list, void *object, int (*compare)(void *, void *))
  {
  	int i;
! 	struct node_t *iter, *tmpnode;
  
! 	tmpnode = list_new_node(object);
! 	if(LIST_EMPTY(list))
! 		LIST_INSERT_HEAD(list, tmpnode, entries);
! 	else
! 		LIST_FOREACH(iter, list, entries)
  		{
! 			if((i = compare(object, iter->object)) < 0)
! 			{
! 				if(iter == LIST_FIRST(list))
! 				{
! 					LIST_INSERT_HEAD(list, tmpnode, entries);
! 				}
! 				else
! 					LIST_INSERT_BEFORE(iter, tmpnode, entries);
! 				break;
! 			}
  			else
! 				if(i == 0)
! 					return iter->object;
! 				else
! 					if(LIST_NEXT(iter, entries) == NULL)
! 						LIST_INSERT_AFTER(iter, tmpnode, entries);		
  		}
  
! 	return object;
  }
  
  /* Returns NULL on error
   */
! struct list_t *list_duplicate(struct list_t *list, int (*compare)(void *, void *))
  {
! 	struct list_t *ret_list;
  
! 	if((ret_list = list_new()) == NULL)
  		return NULL;
! 	if(list_merge_list(ret_list, list, compare) == NULL)
  		return NULL;
  
***************
*** 99,139 ****
  }
  
! void list_free(list_t *list)
  {
! 	node_t *iter;
  
! 	iter = list->head;
  
  	while(iter != NULL)
  	{
! 		list->head = iter->next;
! 		free(iter);
! 		iter = list->head;
  	}
  
! 	free(list);
! 	list = NULL;
! 
! 	return;
  }
  
! void *list_find_object(list_t *list, void *object)
  {
! 	int i;
! 	node_t *iter;
  
! 	iter = list->head;
  
  	while(iter != NULL)
  	{
! 		if((i = list->compare(iter->object, object)) == 0)
! 			return iter->object;
! 		else
! 			if(i > 0)
! 				break;
! 		iter = iter->next;
  	}
  
! 	return NULL;
  }
  
--- 73,113 ----
  }
  
! void *list_find_object(struct list_t *list, void *object, int (*compare)(void *, void*))
  {
! 	int i;
! 	struct node_t *iter;
  
! 	iter = LIST_FIRST(list);
  
  	while(iter != NULL)
  	{
! 		if((i = compare(iter->object, object)) == 0)
! 			return iter->object;
! 		else
! 			if(i > 0)
! 				break;
! 		iter = LIST_NEXT(iter, entries);
  	}
  
! 	return NULL;
  }
  
! void list_free(struct list_t *list)
  {
! 	struct node_t *iter;
  
! 	iter = LIST_FIRST(list);
  
  	while(iter != NULL)
  	{
! 		LIST_FIRST(list) = LIST_NEXT(iter, entries);
! 		free(iter);
! 		iter = LIST_FIRST(list);
  	}
  
! 	free(list);
! 	list = NULL;
! 
! 	return;
  }
  
***************
*** 142,157 ****
   *	list1 on success
   */
! list_t *list_merge_list(list_t *list1, list_t *list2)
  {
! 	node_t *iter;
! 
! 	iter = list2->head;
  
! 	while(iter != NULL)
! 	{
! 		if(list_add_object(list1, iter->object) == -1)
! 			return NULL;
! 		iter = iter->next;
! 	}
  
  	return list1;
--- 116,125 ----
   *	list1 on success
   */
! struct list_t *list_merge_list(struct list_t *list1, struct list_t *list2, int (*compare)(void *, void *))
  {
! 	struct node_t *iter;
  
! 	LIST_FOREACH(iter, list2, entries)
! 		list_add_object(list1, iter->object, compare);
  
  	return list1;
***************
*** 160,173 ****
  /* Returns NULL on error
   */
! list_t *list_new(int (*compare) (void *, void *))
  {
! 	list_t *list;
  
! 	if((list = (list_t *) malloc(sizeof(list_t))) == NULL)
  		return NULL;
  
! 	list->compare = compare;
! 	list->size = 0;
! 	list->head = list->tail = NULL;
  
  	return list;
--- 128,139 ----
  /* Returns NULL on error
   */
! struct list_t *list_new()
  {
! 	struct list_t *list;
  
! 	if((list = (struct list_t *) malloc(sizeof(struct list_t))) == NULL)
  		return NULL;
  
! 	LIST_INIT(list);
  
  	return list;
***************
*** 176,213 ****
  /* Returns NULL on error
   */
! node_t *list_new_node(void *object, node_t *next, node_t *prev)
  {
! 	node_t *node;
  
! 	if((node = (node_t *) malloc(sizeof(node_t))) == NULL)
  		return NULL;
  
  	node->object = object;
- 	node->next = next;
- 	node->prev = prev;
  
  	return node;
  }
  
! void list_remove(list_t *list, void *object)
  {
! 	node_t *iter;
  	int i;
  
! 	iter = list->head;
  
  	while(iter != NULL)
  	{
! 		if((i = list->compare(iter->object, object)) == 0)
  		{
! 			--(list->size);
! 			if(iter->next != NULL)
! 				iter->next->prev = iter->prev;
! 			else
! 				list->tail = iter->prev;
! 			if(iter->prev != NULL)
! 				iter->prev->next = iter->next;
  			else
! 				list->head = iter->next;
  			free(iter);
  			break;
--- 142,172 ----
  /* Returns NULL on error
   */
! struct node_t *list_new_node(void *object)
  {
! 	struct node_t *node;
  
! 	if((node = (struct node_t *) malloc(sizeof(struct node_t))) == NULL)
  		return NULL;
  
  	node->object = object;
  
  	return node;
  }
  
! void list_remove(struct list_t *list, void *object, int (*compare)(void *, void *))
  {
! 	struct node_t *iter;
  	int i;
  
! 	iter = LIST_FIRST(list);
  
  	while(iter != NULL)
  	{
! 		if((i = compare(iter->object, object)) == 0)
  		{
! 			if(iter == LIST_FIRST(list))
! 				LIST_FIRST(list) = LIST_NEXT(iter, entries);
  			else
! 				LIST_REMOVE(iter, entries);
  			free(iter);
  			break;
***************
*** 216,220 ****
  			if(i < 0)
  				break;
! 		iter = iter->next;
  	}
  
--- 175,179 ----
  			if(i < 0)
  				break;
! 		iter = LIST_NEXT(iter, entries);
  	}
  
***************
*** 223,240 ****
  
  /* Optimize with quicksort or heapsort I think */ 
! list_t *list_resort(list_t *list)
  {
! 	node_t *iter, *tmpiter;
  
! 	iter = list->head;
! 	list->head = list->tail = NULL; 
! 	list->size = 0;
  
  	while(iter != NULL)
  	{
! 		if(list_add_object(list, iter->object) == -1)
! 			return NULL;
  		tmpiter = iter;
! 		iter = iter->next;
  		free(tmpiter);
  	}
--- 182,197 ----
  
  /* Optimize with quicksort or heapsort I think */ 
! struct list_t *list_resort(struct list_t *list, int (*compare)(void *, void *))
  {
! 	struct node_t *iter, *tmpiter;
  
! 	iter = LIST_FIRST(list);
! 	LIST_FIRST(list) = NULL; 
  
  	while(iter != NULL)
  	{
! 		list_add_object(list, iter->object, compare);
  		tmpiter = iter;
! 		iter = LIST_NEXT(iter, entries);
  		free(tmpiter);
  	}
***************
*** 243,259 ****
  }
  
  /* Return
   *	NULL on error
   *	list on success
   */
! list_t *list_union(list_t *list1, list_t *list2)
  {
! 	list_t *list;
  
! 	if((list = list_new(list1->compare)) == NULL)
  		return NULL;
  
! 	if(list_merge_list(list, list1) == NULL)
! 		return NULL;
! 	return list_merge_list(list, list2);
  } 
--- 200,226 ----
  }
  
+ unsigned int list_size(struct list_t *list)
+ {
+ 	unsigned int i = 0;
+ 	struct node_t *iter;
+ 
+ 	LIST_FOREACH(iter, list, entries)
+ 		++i;
+ 
+ 	return i;
+ }
  /* Return
   *	NULL on error
   *	list on success
   */
! struct list_t *list_union(struct list_t *list1, struct list_t *list2, int (*compare)(void *, void *))
  {
! 	struct list_t *list;
  
! 	if(((list = list_new()) == NULL) ||
! 	   (list_merge_list(list, list1, compare) == NULL) ||
! 	   (list_merge_list(list, list2, compare) == NULL))
  		return NULL;
  
! 	return list;
  } 

Index: main.c
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/main.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** main.c	19 Mar 2005 03:29:05 -0000	1.2
--- main.c	14 Apr 2005 03:24:28 -0000	1.3
***************
*** 20,78 ****
  
  #include <ctype.h>
  #include <libgen.h>
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  #include <unistd.h>
  
- #include "keydata.h"
  #include "list.h"
  #include "main.h"
! #include "pgpkey.h"
  
! int analyze_key(pgpkey_t *key, list_t *keys, list_t *nnlist, list_t *nslist, list_t *snlist, list_t *sslist)
  {
! 	node_t *iter;
  
! 	iter = keys->head;
  	pgpkey_msd(key, keys);
  
  	while(iter != NULL)
  	{
! 		if(list_find_object(key->signatures, iter->object) != NULL)
! 		{
! 			if(list_find_object(((pgpkey_t *) iter->object)->signatures, key) != NULL)
! 			{
! 				if(list_add_object(sslist, iter->object) == -1)
! 				{
! 					return -1;
! 				}
! 			}
  			else
! 			{
! 				if(list_add_object(nslist, iter->object) == -1)
! 				{
! 					return -1;
! 				}
! 			}
! 		}
  		else
! 		{
! 			if(list_find_object(((pgpkey_t *) iter->object)->signatures, key) != NULL)
! 			{
! 				if(list_add_object(snlist, iter->object) == -1)
! 				{
! 					return -1;
! 				}
! 			}
  			else
! 			{
! 				if(list_add_object(nnlist, iter->object) == -1)
! 				{
! 					return -1;
! 				}
! 			}
! 		}
! 		iter = iter->next;
  	}
  
--- 20,55 ----
  
  #include <ctype.h>
+ #include <err.h>
  #include <libgen.h>
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
+ #include <sysexits.h>
  #include <unistd.h>
  
  #include "list.h"
  #include "main.h"
! #include "node.h"
  
! int analyze_key(pgpkey_t *key, struct list_t *keys, struct list_t *nnlist, struct list_t *nslist, struct list_t *snlist, struct list_t *sslist)
  {
! 	struct node_t *iter;
  
! 	iter = LIST_FIRST(keys);
  	pgpkey_msd(key, keys);
  
  	while(iter != NULL)
  	{
! 		if(list_find_object(key->signatures, iter->object, pgpkey_compare) != NULL)
! 			if(list_find_object(((pgpkey_t *) iter->object)->signatures, key, pgpkey_compare) != NULL)
! 				list_add_object(sslist, iter->object, pgpkey_compare);
  			else
! 				list_add_object(nslist, iter->object, pgpkey_compare);
  		else
! 			if(list_find_object(((pgpkey_t *) iter->object)->signatures, key, pgpkey_compare) != NULL)
! 				list_add_object(snlist, iter->object, pgpkey_compare);
  			else
! 				list_add_object(nnlist, iter->object, pgpkey_compare);
! 		iter = LIST_NEXT(iter, entries);
  	}
  
***************
*** 84,88 ****
   * Return -1 on error
   */
! int do_analysis(list_t *keys1, char *outputdir)
  {
  	char	*dir;
--- 61,65 ----
   * Return -1 on error
   */
! int do_analysis(struct list_t *keys1, char *outputdir)
  {
  	char	*dir;
***************
*** 90,95 ****
  	float	last_msd;
  	int	i, j, k;
! 	list_t	*keys2, *tmplist1, *tmplist2, *wots, *nnlist, *nslist, *snlist, *sslist;
! 	node_t	*iter1, *iter2;
  	pgpkey_t	*key;
  	struct stat	*sb;
--- 67,72 ----
  	float	last_msd;
  	int	i, j, k;
! 	struct list_t	*keys2, *tmplist1, *tmplist2, *wots, *nnlist, *nslist, *snlist, *sslist;
! 	struct node_t	*iter1, *iter2;
  	pgpkey_t	*key;
  	struct stat	*sb;
***************
*** 110,120 ****
  
  	/* Iterate through the list of keys, analyzing the key and outputting its file */
! 	iter1 = keys1->head;
! 	while(iter1 != NULL)
  	{
! 		nnlist = list_new(&pgpkey_compare);
! 		nslist = list_new(&pgpkey_compare);
! 		snlist = list_new(&pgpkey_compare);
! 		sslist = list_new(&pgpkey_compare);
  		analyze_key(iter1->object, keys1, nnlist, nslist, snlist, sslist);
  		output_file(iter1->object, nnlist, nslist, snlist, sslist);
--- 87,96 ----
  
  	/* Iterate through the list of keys, analyzing the key and outputting its file */
! 	LIST_FOREACH(iter1, keys1, entries)
  	{
! 		nnlist = list_new();
! 		nslist = list_new();
! 		snlist = list_new();
! 		sslist = list_new();
  		analyze_key(iter1->object, keys1, nnlist, nslist, snlist, sslist);
  		output_file(iter1->object, nnlist, nslist, snlist, sslist);
***************
*** 123,164 ****
  		list_free(snlist);
  		list_free(sslist);
- 		iter1 = iter1->next;
  	}
  	iter1 = NULL;
  
  	/* Pull apart the list of keys and seperate them into lists where all the keys can reach one another */
! 	keys2 = list_duplicate(keys1);
! 	wots = list_new(&wot_compare);
! 	while(keys2->head != NULL)
  	{
! 		if(((tmplist1 = list_new(&pgpkey_compare_msd)) == NULL) ||
! 				((tmplist2 = list_new(&pgpkey_compare_msd)) == NULL) ||
! 				(list_add_object(tmplist1, keys2->head->object) == -1))
  			return -1;
! 		list_remove(keys2, keys2->head->object);
! 		while(tmplist1->size != tmplist2->size)
  		{
  			list_free(tmplist2);
! 			if((tmplist2 = list_duplicate(tmplist1)) == NULL)
  				return -1;
! 			iter1 = tmplist2->head;
  			while(iter1 != NULL)
  			{
! 				iter2 = ((pgpkey_t *) iter1->object)->signatures->head;
  				while(iter2 != NULL)
  				{
  					if(pgpkey_distance(iter2->object, iter1->object) != 0)
  					{
! 						if(list_add_object(tmplist1, iter2->object) == -1)
! 							return -1;
! 						list_remove(keys2, iter2->object);
  					}
! 					iter2 = iter2->next;
  				}
! 				iter1 = iter1->next;
  			}
  		}
! 		if(list_add_object(wots, tmplist1) == -1)
! 			return -1;
  		list_free(tmplist2);
  		tmplist2 = NULL;
--- 99,137 ----
  		list_free(snlist);
  		list_free(sslist);
  	}
  	iter1 = NULL;
  
  	/* Pull apart the list of keys and seperate them into lists where all the keys can reach one another */
! 	keys2 = list_duplicate(keys1, &pgpkey_compare);
! 	wots = list_new();
! 	while(!LIST_EMPTY(keys2))
  	{
! 		if(((tmplist1 = list_new()) == NULL) ||
! 				((tmplist2 = list_new()) == NULL))
  			return -1;
! 		list_add_object(tmplist1, LIST_FIRST(keys2)->object, &pgpkey_compare_msd);
! 		list_remove(keys2, LIST_FIRST(keys2)->object, &pgpkey_compare);
! 		while(list_size(tmplist1) != list_size(tmplist2))
  		{
  			list_free(tmplist2);
! 			if((tmplist2 = list_duplicate(tmplist1, &pgpkey_compare_msd)) == NULL)
  				return -1;
! 			iter1 = LIST_FIRST(tmplist2);
  			while(iter1 != NULL)
  			{
! 				iter2 = LIST_FIRST(((pgpkey_t *) iter1->object)->signatures);
  				while(iter2 != NULL)
  				{
  					if(pgpkey_distance(iter2->object, iter1->object) != 0)
  					{
! 						list_add_object(tmplist1, iter2->object, &pgpkey_compare_msd);
! 						list_remove(keys2, iter2->object, &pgpkey_compare);
  					}
! 					iter2 = LIST_NEXT(iter2, entries);
  				}
! 				iter1 = LIST_NEXT(iter1, entries);
  			}
  		}
! 		list_add_object(wots, tmplist1, &wot_compare);
  		list_free(tmplist2);
  		tmplist2 = NULL;
***************
*** 173,189 ****
  	filep = fopen("report.html", "w");
  	fprintf(filep, "<html><body>\n");
! 	while(wots->head != NULL)
  	{
! 		iter1 = wots->head;
  		/* If the size of this web of trust is 1 then the remaining are of size 1, so group them all together */
! 		if(((list_t *) iter1->object)->size == 1)
  			break;
  		fprintf(filep, "<div class=\"wottable\"><div class=\"wottable_title\">Web Of Trust %d</div>\n", i);
  		fprintf(filep, "<table><tr><td>Rank</td><td>KeyID</td><td>Name</td><td>MSD</td></tr>\n");
  
! 		tmplist1 = (list_t *) iter1->object;
! 		while(tmplist1->head != NULL)
  		{
! 			iter2 = tmplist1->head;
  			key = (pgpkey_t *) iter2->object;
  			if(key->msd != last_msd)
--- 146,162 ----
  	filep = fopen("report.html", "w");
  	fprintf(filep, "<html><body>\n");
! 	while(LIST_FIRST(wots) != NULL)
  	{
! 		iter1 = LIST_FIRST(wots);
  		/* If the size of this web of trust is 1 then the remaining are of size 1, so group them all together */
! 		if(list_size(((struct list_t *) iter1->object)) == 1)
  			break;
  		fprintf(filep, "<div class=\"wottable\"><div class=\"wottable_title\">Web Of Trust %d</div>\n", i);
  		fprintf(filep, "<table><tr><td>Rank</td><td>KeyID</td><td>Name</td><td>MSD</td></tr>\n");
  
! 		tmplist1 = (struct list_t *) iter1->object;
! 		while(LIST_FIRST(tmplist1) != NULL)
  		{
! 			iter2 = LIST_FIRST(tmplist1);
  			key = (pgpkey_t *) iter2->object;
  			if(key->msd != last_msd)
***************
*** 197,206 ****
  			free(dir);
  			dir = NULL;
! 			list_remove(tmplist1, key);
  			key = NULL;
  		}
  		fprintf(filep, "</table></div>\n");
  		tmplist1 = iter1->object;
! 		list_remove(wots, tmplist1);
  		list_free(tmplist1);
  		tmplist1 = NULL;
--- 170,179 ----
  			free(dir);
  			dir = NULL;
! 			list_remove(tmplist1, key, &pgpkey_compare_msd);
  			key = NULL;
  		}
  		fprintf(filep, "</table></div>\n");
  		tmplist1 = iter1->object;
! 		list_remove(wots, tmplist1, &wot_compare);
  		list_free(tmplist1);
  		tmplist1 = NULL;
***************
*** 218,222 ****
  		while(iter1 != NULL)
  		{
! 			iter2 = ((list_t *) iter1->object)->head;
  			key = (pgpkey_t *) iter2->object;
  			dir = (char *) malloc(3);
--- 191,195 ----
  		while(iter1 != NULL)
  		{
! 			iter2 = LIST_FIRST(((struct list_t *) iter1->object));
  			key = (pgpkey_t *) iter2->object;
  			dir = (char *) malloc(3);
***************
*** 225,229 ****
  			fprintf(filep, "<tr><td><a href=\"%s/%s\">%s</a></td><td>%s</td></tr>\n", dir, key->keyid + 8, key->keyid + 8, key->name);
  			free(dir);
! 			iter1 = iter1->next;
  		}
  		fprintf(filep, "</table></div>\n");
--- 198,202 ----
  			fprintf(filep, "<tr><td><a href=\"%s/%s\">%s</a></td><td>%s</td></tr>\n", dir, key->keyid + 8, key->keyid + 8, key->name);
  			free(dir);
! 			iter1 = LIST_NEXT(iter1, entries);
  		}
  		fprintf(filep, "</table></div>\n");
***************
*** 236,252 ****
  }
  
  int main(int argc, char **argv)
  {
  	char c;
- 	char *keyring = NULL;
  	char *outputdir = NULL;
! 	list_t *keys;
  
! 	while ((c = getopt(argc, argv, "k:o:")) != -1)
  		switch (c)
  		{
- 		case 'k':
- 			keyring = optarg;
- 			break;
  		case 'o':
  			outputdir = optarg;
--- 209,244 ----
  }
  
+ char *get_field()
+ {
+ 	char c, *string;
+ 	size_t size = 0;
+ 
+ 	while(((c = getchar()) != ':') && (c != EOF))
+ 	{
+ 		if(!isdigit(c))
+ 			errx(EX_DATAERR, "Invalid data input!\n");
+ 		size = size * 10;
+ 		size = size + c - '0';
+ 	}
+ 	if(c == EOF)
+ 		errx(EX_DATAERR, "Unexpected termination of data input!\n");
+ 	++size;
+ 	string = (char *) malloc(size);
+ 	if(string == NULL)
+ 		return NULL;
+ 	fgets(string, size, stdin);
+ 	*(string + size) = '\0';
+ 	return string;
+ }
+ 
  int main(int argc, char **argv)
  {
  	char c;
  	char *outputdir = NULL;
! 	struct list_t *keys;
  
! 	while ((c = getopt(argc, argv, "o:")) != -1)
  		switch (c)
  		{
  		case 'o':
  			outputdir = optarg;
***************
*** 263,267 ****
  	}
  
! 	keys = parse_keyring(keyring);
  	do_analysis(keys, outputdir);
  
--- 255,259 ----
  	}
  
! 	keys = parse_keyring();
  	do_analysis(keys, outputdir);
  
***************
*** 269,278 ****
  }
  
! void output_file(pgpkey_t *key, list_t *nnlist, list_t *nslist, list_t *snlist, list_t *sslist)
  {
  	char *file_dir;
  	FILE *filep;
! 	list_t *tmp_list;
  	struct stat *sb;
  
  	file_dir = (char *) malloc(3);
--- 261,271 ----
  }
  
! void output_file(pgpkey_t *key, struct list_t *nnlist, struct list_t *nslist, struct list_t *snlist, struct list_t *sslist)
  {
  	char *file_dir;
  	FILE *filep;
! 	struct list_t *tmp_list;
  	struct stat *sb;
+ 	unsigned int tmp_size;
  
  	file_dir = (char *) malloc(3);
***************
*** 296,308 ****
  
  	fprintf(filep, "Signatures to this key:\n");
! 	tmp_list = list_union(nslist, sslist);
  	print_list(filep, tmp_list);
! 	fprintf(filep, " Total: %u signature%s to this key from this set.\n\n", tmp_list->size, ((tmp_list->size == 1)?"":"s"));
  	list_free(tmp_list);
  
  	fprintf(filep, "Signatures from this key:\n");
! 	tmp_list = list_union(snlist, sslist);
  	print_list(filep, tmp_list);
! 	fprintf(filep, " Total: %u signature%s from this key to this set.\n\n", tmp_list->size, ((tmp_list->size == 1)?"":"s"));
  	list_free(tmp_list);
  
--- 289,303 ----
  
  	fprintf(filep, "Signatures to this key:\n");
! 	tmp_list = list_union(nslist, sslist, &pgpkey_compare);
  	print_list(filep, tmp_list);
! 	tmp_size = list_size(tmp_list);
! 	fprintf(filep, " Total: %u signature%s to this key from this set.\n\n", tmp_size, ((tmp_size == 1)?"":"s"));
  	list_free(tmp_list);
  
  	fprintf(filep, "Signatures from this key:\n");
! 	tmp_list = list_union(snlist, sslist, &pgpkey_compare);
  	print_list(filep, tmp_list);
! 	tmp_size = list_size(tmp_list);
! 	fprintf(filep, " Total: %u signature%s from this key to this set.\n\n", tmp_size, ((tmp_size == 1)?"":"s"));
  	list_free(tmp_list);
  
***************
*** 311,327 ****
  	fprintf(filep, "This key has not signed, nor been signed by:\n");
  	print_list(filep, nnlist);
! 	fprintf(filep, " Total: %u key%s in this set.\n\n", nnlist->size, ((nnlist->size == 1)?"":"s"));
  
  	fprintf(filep, "This key has not signed, but has been signed by:\n");
  	print_list(filep, nslist);
! 	fprintf(filep, " Total: %u key%s in this set.\n\n", nslist->size, ((nslist->size == 1)?"":"s"));
  
  	fprintf(filep, "This key has signed, but has not been signed by:\n");
  	print_list(filep, snlist);
! 	fprintf(filep, " Total: %u key%s in this set.\n\n", snlist->size, ((snlist->size == 1)?"":"s"));
  
  	fprintf(filep, "This key has signed and has been signed by:\n");
  	print_list(filep, sslist);
! 	fprintf(filep, " Total: %u key%s in this set.\n\n", sslist->size, ((sslist->size == 1)?"":"s"));
  
  	fclose(filep);
--- 306,326 ----
  	fprintf(filep, "This key has not signed, nor been signed by:\n");
  	print_list(filep, nnlist);
! 	tmp_size = list_size(nnlist);
! 	fprintf(filep, " Total: %u key%s in this set.\n\n", tmp_size, ((tmp_size == 1)?"":"s"));
  
  	fprintf(filep, "This key has not signed, but has been signed by:\n");
  	print_list(filep, nslist);
! 	tmp_size = list_size(nslist);
! 	fprintf(filep, " Total: %u key%s in this set.\n\n", tmp_size, ((tmp_size == 1)?"":"s"));
  
  	fprintf(filep, "This key has signed, but has not been signed by:\n");
  	print_list(filep, snlist);
! 	tmp_size = list_size(snlist);
! 	fprintf(filep, " Total: %u key%s in this set.\n\n", tmp_size, ((tmp_size == 1)?"":"s"));
  
  	fprintf(filep, "This key has signed and has been signed by:\n");
  	print_list(filep, sslist);
! 	tmp_size = list_size(sslist);
! 	fprintf(filep, " Total: %u key%s in this set.\n\n", tmp_size, ((tmp_size == 1)?"":"s"));
  
  	fclose(filep);
***************
*** 331,424 ****
  }
  
! list_t *parse_keyring(char *keyring)
  {
! 	size_t size;
! 	char *command1 = "gpg --list-sigs --with-colons --no-default-keyring --keyring ";
! 	char *command2;
! 	FILE *filep;
! 	keydata_t *key;
! 	pgpkey_t *public_key, *tmp_key, *tmp2_key;
! 	list_t *keys;
! 	int key_was_added;
! 
! 	public_key = NULL;
! 	keys = list_new(&pgpkey_compare);
! 	if(keyring == NULL)
! 		filep = stdin;
! 	else
! 	{
! 		size = strlen(command1) + strlen(keyring);
! 		command2 = (char *) malloc(size);
! 
! 		strncpy(command2, command1, size);
! 		*(command2 + size) = '\0';
! 		strncat(command2, keyring, size - strlen(command2));
  
! 		filep = popen(command2, "r");
! 	}
  
! 	key = keydata_new();
! 	while(strcmp(key->type, "nul") == 0)
! 	{
! 		key = keydata_read(filep);
! 	}
! 	while(strcmp(key->type, "eof") != 0)
  	{
! 		if(strcmp(key->type, "pub") == 0)
! 		{
! 			public_key = pgpkey_new(key->keyid, key->name);
! 			key_was_added = list_add_object(keys, public_key);
! 			if(key_was_added == 0)
! 			{
! 				tmp_key = list_find_object(keys, public_key);
! 				list_free(public_key->signatures);
! 				free(public_key->name);
! 				free(public_key->keyid);
! 				free(public_key);
! 				public_key = tmp_key;
! 			}
! 		}
! 		if(strcmp(key->type, "sig") == 0)
  		{
! 			if(public_key == NULL)
! 				fprintf(stderr, "Missing public key, skipping signature!\n");
! 			else
  			{
! 				tmp_key = pgpkey_new(key->keyid, key->name);
! 				key_was_added = list_add_object(keys, tmp_key);
! 				if(key_was_added == 0)
  				{
! 					tmp2_key = list_find_object(keys, tmp_key);
! 					list_free(tmp_key->signatures);
! 					free(tmp_key->name);
! 					free(tmp_key->keyid);
! 					free(tmp_key);
! 					tmp_key = tmp2_key;
  				}
- 				list_add_object(public_key->signatures, tmp_key);	
  			}
  		}
! 		if(strcmp(key->type, "sub") == 0)
! 			public_key = NULL;
! 		key = keydata_read(filep);
  	}
  
! 	if(keyring != NULL)
! 		pclose(filep);
  	return keys;
  }
  
! void print_list(FILE *filep, list_t *list)
  {
! 	node_t *node;
  
! 	node = list->head;
  
! 	while(node != NULL)
  	{
! 		fprintf(filep, "  %s %s\n", ((pgpkey_t *) node->object)->keyid + 8, ((pgpkey_t *) node->object)->name);
! 		node = node->next;
  	}
- 
  	return;
  
--- 330,414 ----
  }
  
! struct list_t *parse_keyring()
  {
! 	char c, type, *field1, *field2;
! 	pgpkey_t *key1, *key2, *tmpkey;
! 	struct list_t *keys;
  
! 	keys = list_new();
  
! 	for(c = type = getchar(); c == 'e' || c == 'n'; c = type = getchar())
  	{
! 		if(((c = getchar()) != ':') && (c != EOF))
! 			errx(EX_DATAERR, "Invalid character, %c (ASCII: %d), encountered!\n", c, c);
! 		if(c == EOF)
! 			break;
! 		if((field1 = get_field()) == NULL)
! 			errx(EX_OSERR, "Cannot allocate memory!\n");
! 		if(*field1 == EOF)
! 			break;
! 		if(((c = getchar()) != ':') && (c != EOF))
! 			errx(EX_DATAERR, "Invalid character, %c (ASCII: %d), encountered!\n", c, c);
! 		if(c == EOF)
! 			break;
! 		if((field2 = get_field()) == NULL)
! 			errx(EX_OSERR, "Cannot allocate memory!\n");
! 		if(*field2 == EOF)
! 			break;
! 		if(((c = getchar()) != '\n') && (c != EOF))
! 			errx(EX_DATAERR, "Invalid character, %c (ASCII: %d), encountered!\n", c, c);
! 
! 		if(type == 'n')
  		{
! 			tmpkey = pgpkey_new(field1, field2);
! 			free(field1);
! 			if((key1 = list_add_object(keys, tmpkey, &pgpkey_compare)) != tmpkey)
  			{
! 				free(tmpkey);
! 				if(*(key1->name) == '\0')
  				{
! 					key1->name = field2;
! 					field2 = NULL;
  				}
  			}
  		}
! 		else
! 		{
! 			tmpkey = pgpkey_new(field1, "");
! 			free(field1);
! 			if((key1 = list_add_object(keys, tmpkey, &pgpkey_compare)) != tmpkey)
! 				free(tmpkey);
! 			tmpkey = pgpkey_new(field2, "");
! 			free(field2);
! 			if((key2 = list_add_object(keys, tmpkey, &pgpkey_compare)) != tmpkey)
! 				free(tmpkey);
! 			list_add_object(key2->signatures, key1, &pgpkey_compare);
! 		}
! 
! 
! 		if(c == EOF)
! 			break;
  	}
  
! 	if(c != EOF)
! 		errx(EX_DATAERR, "Invalid character, %c (ASCII: %d), encountered!\n", c, c);
! 
  	return keys;
  }
  
! void print_list(FILE *filep, struct list_t *list)
  {
! 	struct node_t *node;
  
! 	pgpkey_t *key;
! 	char *keyid, *name;
  
! 	LIST_FOREACH(node, list, entries)
  	{
! 		key = (pgpkey_t *) node->object;
! 		keyid = key->keyid + 8;
! 		name = key->name;
! 		fprintf(filep, "  %s %s\n", keyid, name);
  	}
  	return;
  
***************
*** 429,433 ****
  	extern char *__progname;
  
! 	fprintf(stderr, "usage: %s [-k pubring.gpg] -o output_directory\n", __progname);
  	return;
  }
--- 419,423 ----
  	extern char *__progname;
  
! 	fprintf(stderr, "usage: %s -o output_directory\n", __progname);
  	return;
  }
***************
*** 435,447 ****
  int wot_compare(void *obj1, void *obj2)
  {
! 	list_t *wot1 = obj1;
! 	list_t *wot2 = obj2;
  
  	if(wot1 == wot2)
  		return 0;
  
! 	if(wot1->size == wot2->size)
! 		return wot1->compare(wot1->head->object, wot2->head->object);
  
! 	return wot2->size - wot1->size;
  }
--- 425,438 ----
  int wot_compare(void *obj1, void *obj2)
  {
! 	struct list_t *wot1 = obj1;
! 	struct list_t *wot2 = obj2;
! 	unsigned int wot1size, wot2size;
  
  	if(wot1 == wot2)
  		return 0;
  
! 	if((wot1size = list_size(wot1)) == (wot2size = list_size(wot2)))
! 		return pgpkey_compare(LIST_FIRST(wot1)->object, LIST_FIRST(wot2)->object);
  
! 	return wot2size - wot1size;
  }

--- NEW FILE: node.c ---
/* $Id: node.c,v 1.2 2005/04/14 03:24:28 jbreker Exp $
 *
 * Copyright (C) 2005 Jeff Breker <jb...@sy...>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

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

#include "list.h"
#include "node.h"

int pgpkey_compare(void *key1, void *key2)
{
	return strcmp(((pgpkey_t *) key1)->keyid, ((pgpkey_t *) key2)->keyid);
}

int pgpkey_compare_msd(void *key1, void *key2)
{
	float tmp;

	tmp = ((pgpkey_t *) key1)->msd - ((pgpkey_t *) key2)->msd;
	if(tmp == (float) 0)
		return strcmp(((pgpkey_t *) key1)->keyid, ((pgpkey_t *) key2)->keyid);
	else
		if(tmp > (float) 0)
			return 1;
		else
			return (-1);
}


unsigned int pgpkey_distance(pgpkey_t *keyto, pgpkey_t *keyfrom)
{
	unsigned int distance;
	unsigned int last_known_size, tmpsize;
	struct list_t *traversed_keys, *tmp_keys;
	struct node_t *tmp_node;

	traversed_keys = list_new();
	last_known_size = 0;
	distance = 1;

	list_merge_list(traversed_keys, keyto->signatures, &pgpkey_compare);
	while((tmpsize = list_size(traversed_keys)) != last_known_size)
	{
		if(list_find_object(traversed_keys, keyfrom, &pgpkey_compare) != NULL)
			return distance;
		last_known_size = tmpsize;
		++distance;
		tmp_keys = traversed_keys;
		tmp_node = LIST_FIRST(tmp_keys);
		traversed_keys = list_new();
		while(tmp_node != NULL)
		{
			list_add_object(traversed_keys, tmp_node->object, &pgpkey_compare);
			list_merge_list(traversed_keys, ((pgpkey_t *) tmp_node->object)->signatures, &pgpkey_compare);
			tmp_node = LIST_NEXT(tmp_node, entries);
		}
	}

	return 0;
}

void pgpkey_msd(pgpkey_t *key, struct list_t *keys)
{
	unsigned int distance, i, num_keys;
	struct node_t *iter;

	distance = 0;
	num_keys = 0;
	iter = LIST_FIRST(keys);

	while(iter != NULL)
	{
		i = pgpkey_distance(key, (pgpkey_t *) iter->object);
		if(i > 0)
		{
			distance += i;
			num_keys++;
		}
		iter = LIST_NEXT(iter, entries);
	}

	key->msd = ((float) distance) / ((float) num_keys);
	return;
}

pgpkey_t *pgpkey_new(char *keyid, char *name)
{
	pgpkey_t *pgpkey;

	pgpkey = (pgpkey_t *) malloc(sizeof(pgpkey_t));
	pgpkey->keyid = (char *) malloc(17);
	strncpy(pgpkey->keyid, keyid, 16);
	*(pgpkey->keyid + 16) = '\0';
	pgpkey->name = (char *) malloc(strlen(name) + 1);
	strncpy(pgpkey->name, name, strlen(name));
	*(pgpkey->name + strlen(name)) = '\0';
	pgpkey->signatures = list_new();
	pgpkey->msd = 0;

	return pgpkey;
}