389-ds-base/ldap/servers/plugins/replication/tests/dnp_sim3.c

/** BEGIN COPYRIGHT BLOCK
 * 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; version 2 of the License.
 * 
 * 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 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.
 * 
 * In addition, as a special exception, Red Hat, Inc. gives You the additional
 * right to link the code of this Program with code not covered under the GNU
 * General Public License ("Non-GPL Code") and to distribute linked combinations
 * including the two, subject to the limitations in this paragraph. Non-GPL Code
 * permitted under this exception must only link to the code of this Program
 * through those well defined interfaces identified in the file named EXCEPTION
 * found in the source code files (the "Approved Interfaces"). The files of
 * Non-GPL Code may instantiate templates or use macros or inline functions from
 * the Approved Interfaces without causing the resulting work to be covered by
 * the GNU General Public License. Only Red Hat, Inc. may make changes or
 * additions to the list of Approved Interfaces. You must obey the GNU General
 * Public License in all respects for all of the Program code and other code used
 * in conjunction with the Program except the Non-GPL Code covered by this
 * exception. If you modify this file, you may extend this exception to your
 * version of the file, but you are not obligated to do so. If you do not wish to
 * provide this exception without modification, you must delete this exception
 * statement from your version and license this file solely under the GPL without
 * exception. 
 * 
 * 
 * Copyright (C) 2001 Sun Microsystems, Inc. Used by permission.
 * Copyright (C) 2005 Red Hat, Inc.
 * All rights reserved.
 * END COPYRIGHT BLOCK **/

#ifdef HAVE_CONFIG_H
#  include <config.h>
#endif

/* dnp_simulation.c - this file varifies the correctness of dnp algorithm
                      by generating random sequences of operations, applying
                      the algorithm and outputing the result

   usage: dnp_sim [-h] [-n <number of simulations> ] [-v] [-f <output file>]
		-h - print usage information.
		-n <number of simulations> - how many simulations to perform; default - 1.
		-v - verbose mode (prints full entry state after each operation execution)
		-f <output file> - file where results are stored; by default results are
						   printed to the screen.
		-o <op file> - file that contains operation sequence to execute; by default,
					   random sequence is generated.
 */

#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <memory.h>
#include <string.h>
#include <time.h>
#include <windows.h>

#define MAX_OPS			18	/* maximum number of operations in a simulation */
#define MAX_VALS		10	/* maximum number of values is entry or dn */
#define MAX_ATTR_NAME	16	/* max length of the attribute name */
#define NOT_PRESENT		-1
#define SV_ATTR_NAME	"sv_attr"	/* name of the singlevalued attribute */
#define MV_ATTR_NAME	"mv_attr"	/* name of the multivalued attribute */

/* data types */

/* value */
typedef struct value_state
{
	int value_index;			/* value */
	int presence_csn;			/* last time at which we know the value was present */
	int delete_csn;				/* last attempt to delete this value */
	int present;				/* flag that tells whether the value is present */
} Value_State;

/* shared attribute state */
typedef struct attr_state
{
	int	delete_csn;				/* last deletion csn */
	int present;				/* flag that tells whether the attribute is present */
}Attr_State;

/* singlevalued attribute */
typedef struct sv_attr_state
{
	Attr_State  attr_state;		/* shared attribute state */
	Value_State current_value;	/* current attribute value */
	Value_State *pending_value;	/* latest pending value */
} SV_Attr_State;

/* maltivalued attribute */
typedef struct mv_attr_state
{
	Attr_State  attr_state;			/* shared attribute state */
	Value_State values [MAX_VALS];	/* latest pending value */
	int value_count;				/* number of values in the array */
} MV_Attr_State;

/* node of dn_csn_list */
typedef struct dn_csn
{
	int csn;						/* dn csn */
	int sv_attr;					/* is this single valued or multivalued attr */
	int value_index;				/* dn value */
} Dn_Csn;

typedef struct entry_state
{
	Dn_Csn	dn_csns [MAX_VALS + 1];	/* list of dn csns for this entry */
	int		dn_csn_count;			/* csn of the current dn */
	SV_Attr_State sv_attr;			/* singlevalued attribute */
	MV_Attr_State mv_attr;			/* singlevalued attribute */
} Entry_State;

typedef enum
{
	OP_ADD_VALUE,
	OP_DELETE_VALUE,
	OP_RENAME_ENTRY,
	OP_DELETE_ATTR,
	OP_END
} Operation_Type;

typedef struct operation
{
	Operation_Type type;			/* operation type */	
	int csn;						/* operation csn */
	int sv_attr;					/* is this applied to singlevalued attribute */
	int value_index;				/* value to add, remove or rename from */	
	int delete_old_rdn;				/* rename only */
	int old_rdn_sv_attr;			/* is oldrdn a singlevalued attribute */
	int old_rdn_value_index;		/* index of old_rdn */
}Operation;

typedef struct simulator_params
{
	int runs;			/* number of runs */
	FILE *fout;			/* output file */
	int value_count;	/* number of values */
	int	verbose;		/* verbose mode */
	Operation *ops;		/* operation sequence to apply */
	int op_count;
}Simulator_Params;


/* gloabl data */
Simulator_Params sim;
char *g_values[] =
{
	"v",
	"u",
	"w",
	NULL	
};

/* forward declarations */

/* initialization */
void process_cmd (int argc, char **argv);
void set_default_sim_params ();
int  count_values ();
void parse_operations_file (char *name);
void parse_operation (char *line, int pos);
int value2index (char *value);
void print_usage ();

/* simulation run */
void run_simulation ();
void generate_operations (Operation **ops, int *op_count);
void generate_operation (Operation *op, int csn);
int* generate_operation_order (int op_count, int seq_num);
void apply_operation_sequence (Operation *ops, int op_count, int *order, Entry_State *entry);	
void init_entry_state (Entry_State *entry);
void init_sv_attr_state (SV_Attr_State *sv_attr);
void init_mv_attr_state (MV_Attr_State *mv_attr);
void init_value_state (Value_State *val, int seq_num);
void free_operations (Operation **ops);
int ** new_perm_table (int op_count);
void free_perm_table (int ***perm_table, int op_count);
int get_perm_count (int op_count);	
void generate_perm_table (int *elements, int element_count, int static_part,
						  int **perm_table);
void apply_operation (Entry_State *entry, Operation *op);
void apply_add_operation (Entry_State *entry, Operation *op);
void apply_value_delete_operation (Entry_State *entry, Operation *op);
void apply_attr_delete_operation (Entry_State *entry, Operation *op);
void apply_rename_operation (Entry_State *entry, Operation *op);
void resolve_mv_attr_state (Entry_State *entry, Value_State *value);
void resolve_sv_attr_state (Entry_State *entry, Value_State *value);
void purge_sv_attr_state (Entry_State *entry);
void purge_mv_attr_state (Entry_State *entry, Value_State *value);
int value_distinguished_at_csn (Entry_State *entry, int sv_attr, Value_State *value, int csn);

/* state comparison */
int compare_entry_state (Entry_State *entry1, Entry_State *entry2, int run);
int compare_entry_state_quick (Entry_State *entry1, Entry_State *entry2, int run);
int compare_sv_attr_state_quick (SV_Attr_State *sv_attr1, SV_Attr_State *sv_attr2, int run);
int compare_mv_attr_state_quick (MV_Attr_State *mv_attr1, MV_Attr_State *mv_attr2, int run);
int compare_sv_attr_state (SV_Attr_State *sv_attr1, SV_Attr_State *sv_attr2, int run);
int compare_mv_attr_state (MV_Attr_State *mv_attr1, MV_Attr_State *mv_attr2, int run);
int compare_value_state (Value_State *value1, Value_State *value2, int run);

/* dnc_csn handling */
int dn_csn_add (Entry_State *entry, int sv_attr, int value_index, int csn);

/* data tracing */
void dump_operations (Operation *ops, int op_count, int *order);
void dump_operation (Operation *op);		
void dump_perm_table (int **perm_table, int op_count);
void dump_entry_state (Entry_State *entry);
void dump_sv_attr_state (SV_Attr_State *sv_attr);
void dump_mv_attr_state (MV_Attr_State *mv_attr);
void dump_value_state (Value_State *value, int sv_attr);
void dump_dn_csn_list (Entry_State *entry);

/* misc functions */
int max_val (int a, int b);

int main (int argc, char **argv)
{
	int i;
	
	process_cmd (argc, argv);

	for (i = 0; i < sim.runs; i++)
	{
		fprintf (sim.fout, "*******running simulation #%d ...\n\n", i+1);
		run_simulation ();
		fprintf (sim.fout, "\n*******done with simulation #%d ...\n\n", i+1);
	}

	if (sim.fout != stdout)
		fclose (sim.fout);

	return 0;
}

void process_cmd (int argc, char **argv)
{
	int i;

	set_default_sim_params ();

	if (argc == 1)
	{
		return;
	}

	if (strcmp (argv[1], "-h") == 0)	/* print help */
	{
		print_usage ();
		exit (0);
	}

	i = 1;
	while (i < argc)
	{
		if (strcmp (argv[i], "-v") == 0)	/* verbose mode */
		{
			sim.verbose = 1;
			i ++;
		}
		else if (strcmp (argv[i], "-n") == 0)
		{
			if (i < argc - 1)
			{
				int runs = atoi (argv[i + 1]);
				if (runs > 0)
					sim.runs = runs;
				i+=2;
			}
			else
			{
				/* ONREPL print warning */
				i++;
			}
		}
		else if (strcmp (argv[i], "-f") == 0)  /* output file */
		{
			if (i < argc - 1)
			{
				FILE *f = fopen (argv[i + 1], "w");
				if (f == 0)
				{
					printf ("failed to open output file; error - %s, using stdout\n", 
							strerror(errno));
				}
				else
				{
					/* ONREPL print warning */
					sim.fout = f;
				}

				i += 2;
			}	
			else
				i++;
		}
		else if (strcmp (argv[i], "-o") == 0)  /* file with operation sequence */
		{
			if (i < argc - 1) 
			{
				parse_operations_file (argv[i+1]);
				i += 2;				
			}
			else
			{
				/* ONREPL print warning */
				i ++;
			}
		}
		else /* unknown option */
		{
			printf ("unknown option - %s; ignored\n", argv[i]);
			i ++;
		}
			
	}	
}

void set_default_sim_params ()
{
	memset (&sim, 0, sizeof (sim));
	sim.runs = 1;
	sim.fout = stdout;
	sim.value_count = count_values ();
}

/* file format: <operation count>
				add <attribute> <value>
				delete <attribute>[ <value>]
				rename to <attribute> <value>[ delete <attribute> <value>]

	all spaces are significant
 */
void parse_operations_file (char *name)
{
	FILE *file = fopen (name, "r");
	char line [256];
	int i;

	if (file == NULL)
	{
		printf ("failed to open operations file %s: error = %d\n", name, errno);
		print_usage ();
		exit (1);
	}

	i = 0;
	while (fgets (line, sizeof (line), file))
	{
		if (i == 0)
		{
			/* read operation count */
			sim.op_count = atoi (line);
			if (sim.op_count < 1 || sim.op_count > MAX_OPS/2)
			{
				printf ("invalid operation count - %d; value must be between 1 and %d\n",
						 sim.op_count, MAX_OPS/2);
				print_usage ();
				exit (1);
			}
			else
			{
				sim.ops = (Operation*)malloc (sim.op_count * sizeof (Operation));
			}
		}
		else
		{	
			if (strlen (line) == 0)	 /* skip empty lines */
				continue;
			parse_operation (line, i);
		}

		i ++;			
	}	
}

#define ADD_KEYWORD				"add "
#define DELETE_KEYWORD			"delete "
#define RENAME_KEYWORD			"rename to "
#define DELET_OLD_RDN_KEYWORD	" delete "

void parse_operation (char *line, int i)
{
	int rc = 0;
	char *pos;
	char buff [64];

	sim.ops [i - 1].csn = i;

	if (line[strlen(line) - 1] == '\n')
		line[strlen(line) - 1] = '\0';		

	/* add <attribute> <value> */
	if (strncmp (line, ADD_KEYWORD, strlen (ADD_KEYWORD)) == 0)
	{
		sim.ops [i - 1].type = OP_ADD_VALUE;
		pos = strchr (&line[strlen (ADD_KEYWORD)], ' ');
		if (pos == NULL)
		{
			rc = -1;
			goto done;
		}

		memset (buff, 0, sizeof (buff));
		strncpy (buff, &line[strlen (ADD_KEYWORD)], pos - &line[strlen (ADD_KEYWORD)]); 
		sim.ops [i - 1].sv_attr = strcmp (buff, MV_ATTR_NAME);
		sim.ops [i - 1].value_index = value2index (pos + 1);					
	}
	/* delete <attribute>[ <value>] */
	else if (strncmp (line, DELETE_KEYWORD, strlen (DELETE_KEYWORD)) == 0)
	{
		pos = strchr (&line[strlen (DELETE_KEYWORD)], ' ');
		if (pos == NULL)	/* delete attribute version */
		{
			sim.ops [i - 1].type = OP_DELETE_ATTR;
			sim.ops [i - 1].sv_attr = strcmp (&line[strlen (DELETE_KEYWORD)], 
												  MV_ATTR_NAME);
		}
		else	/* delete value version */
		{
			memset (buff, 0, sizeof (buff));
			sim.ops [i - 1].type = OP_DELETE_VALUE;
			strncpy (buff, &line[strlen (DELETE_KEYWORD)], 
					 pos - &line[strlen (DELETE_KEYWORD)]);
			sim.ops [i - 1].sv_attr = strcmp (buff, MV_ATTR_NAME);
			sim.ops [i - 1].value_index = value2index (pos + 1);
		}
	}
	/* rename to <attribute> <valued>[ delete <attribute> <value>] */
	else if (strncmp (line, RENAME_KEYWORD, 10) == 0)
	{		
		char *pos2;

		sim.ops [i - 1].type = OP_RENAME_ENTRY;

		pos = strchr (&line[strlen (RENAME_KEYWORD)], ' ');
		if (pos == NULL)
		{
			rc = -1;
			goto done;
		}
		
		memset (buff, 0, sizeof (buff));
		strncpy (buff, &line[strlen (RENAME_KEYWORD)], pos - &line[strlen (RENAME_KEYWORD)]); 
		sim.ops [i - 1].sv_attr = strcmp (buff, MV_ATTR_NAME);		

		pos2 = strstr (pos + 1, DELET_OLD_RDN_KEYWORD);
		if (pos2 == NULL)	/* no delete old rdn part */
		{
			sim.ops [i - 1].value_index = value2index (pos + 1);			
			sim.ops [i - 1].delete_old_rdn = 0;
		}
		else
		{
			memset (buff, 0, sizeof (buff));
			strncpy (buff, pos + 1, pos2 - pos - 1);
			sim.ops [i - 1].value_index = value2index (buff);
			pos2 += strlen (DELET_OLD_RDN_KEYWORD);
			pos = strchr (pos2, ' ');
			if (pos == NULL)
			{
				rc = -1;
				goto done;
			}

			memset (buff, 0, sizeof (buff));
			strncpy (buff, pos2, pos - pos2);
			sim.ops [i - 1].delete_old_rdn = 1;
			sim.ops [i - 1].old_rdn_sv_attr = strcmp (buff, MV_ATTR_NAME);
			sim.ops [i - 1].old_rdn_value_index = value2index (pos + 1);
		}
	}
	else
	{
		/* error */
		rc = -1;
	}	

done:
	if (rc)
	{
		/* invalid line */
		printf ("invalid operation: %s\n", line);
		exit (1);
	}
}
int value2index (char *value)
{
	int i;

	for (i = 0; i < sim.value_count; i++)
	{
		if (strcmp (g_values[i], value) == 0)
			return i;
	}

	return -1;
}

void print_usage ()
{
	printf ("usage: dnp_sim [-h] [-n <number of simulations> ] [-v] [-f <output file>]\n"
			"\t-h - print usage information\n"
			"\t-n <number of simulations>; default - 1\n"
			"\t-v - verbose mode\n"
			"\t-f <output file> - by default, results are printed to the screen\n"
			"\t-o <op file> - file that contains operation sequence to execute;\n"
			"\tby default, random sequence is generated.\n");
}

int count_values ()
{
	int i;
	
	for (i = 0; g_values[i]; i++);

	return i;
}

void run_simulation ()
{
	int *order;
	int i;
	int perm_count;
	Entry_State entry_first, entry_current;
	int error = 0;

	init_entry_state (&entry_first);
	fprintf (sim.fout, "initial entry state :\n");
	dump_entry_state (&entry_first);

	if (sim.ops == NULL)
	{
		generate_operations (&sim.ops, &sim.op_count);
	}
	fprintf (sim.fout, "initial operation set:\n");
	dump_operations (sim.ops, sim.op_count, NULL/* order */);

	perm_count = get_perm_count (sim.op_count);
	for (i = 0; i < perm_count; i++)
	{
		fprintf (sim.fout, "--------------------------------\n");	
		fprintf (sim.fout, "simulation run %d\n", i + 1);
		fprintf (sim.fout, "--------------------------------\n");	
		order = generate_operation_order (sim.op_count, i);	
		if (i == 0)
			apply_operation_sequence (sim.ops, sim.op_count, order, &entry_first);	
		else
		{
			apply_operation_sequence (sim.ops, sim.op_count, order, &entry_current);	
			error |= compare_entry_state (&entry_first, &entry_current, i + 1);
		}	
	} 	

	switch (error)
	{
		case 0: fprintf (sim.fout, "all runs left the entry in the same state\n");
				break;
		case 1: fprintf (sim.fout, "while value presence is consistent across all runs, "
						"the exact state does not match\n");
				break;
		case 3:	fprintf (sim.fout, "the runs left entries in an inconsistent state\n");
				break;
	}

	free_operations (&sim.ops);
}

void generate_operations (Operation **ops, int *op_count)
{
	int i;

	/* generate number operations in the sequence */
	*op_count = slapi_rand () % (MAX_OPS / 2) + 1;
	*ops	= (Operation *)malloc (*op_count * sizeof (Operation));

	for (i = 0; i < *op_count; i ++)
	{
		generate_operation (&((*ops)[i]), i + 1);
	}
}			  

void generate_operation (Operation *op, int csn)
{
	/* generate operation type */
	op->type = slapi_rand () % OP_END;
	op->csn = csn;

	/* choose if the operation applies to the single value or
	   the multivalued attribute */
	op->sv_attr = slapi_rand () % 2;

	/* generate value to which operation applies */
	op->value_index = slapi_rand () % sim.value_count;

	if (op->type == OP_RENAME_ENTRY)
	{
		op->delete_old_rdn = slapi_rand () % 2;
		if (op->delete_old_rdn)
		{
			op->old_rdn_sv_attr = slapi_rand () % 2;
			op->old_rdn_value_index = slapi_rand () % sim.value_count;

			while (op->old_rdn_sv_attr == op->sv_attr &&
				   op->old_rdn_value_index == op->value_index)
			{
				op->old_rdn_sv_attr = slapi_rand () % 2;
				op->old_rdn_value_index = slapi_rand () % sim.value_count;
			}
		}
	}
}

int* generate_operation_order (int op_count, int seq_num)
{
	static int **perm_table = NULL;

	/* first request - generate pemutation table */
	if (seq_num == 0)
	{
		int elements [MAX_OPS];
		int i;

		if (perm_table)
			free_perm_table (&perm_table, op_count);
		perm_table = new_perm_table (op_count);

		for (i = 0; i < op_count; i++)
			elements [i] = i;

		generate_perm_table	(elements, op_count, 0 /* static part */,
							 perm_table);
	}
	
	return perm_table [seq_num];
}

void apply_operation_sequence (Operation *ops, int op_count, int *order, Entry_State *entry)
{
	int i;

	init_entry_state (entry);

	if (!sim.verbose)
	{
		if (!sim.verbose)
		{
			fprintf (sim.fout, "operation_sequence for this run:\n");
			dump_operations (ops, op_count, order);
		}
	}

	for (i = 0; i < op_count; i++)
	{
		apply_operation (entry, &(ops [order[i]]));
	}

	if (!sim.verbose)
	{
		fprintf (sim.fout, "final entry state :\n");
		dump_entry_state (entry);
	}
}

void init_entry_state (Entry_State *entry)
{
	memset (entry, 0, sizeof (*entry));
	entry->dn_csn_count = 1;

	init_sv_attr_state (&entry->sv_attr);
	init_mv_attr_state (&entry->mv_attr);
}

void init_sv_attr_state (SV_Attr_State *sv_attr)
{
	memset (sv_attr, 0, sizeof (*sv_attr));
	sv_attr->attr_state.delete_csn = NOT_PRESENT;
	sv_attr->attr_state.present = 1;
	init_value_state (&sv_attr->current_value, 1);	
}

void init_mv_attr_state (MV_Attr_State *mv_attr)
{
	int i;

	memset (mv_attr, 0, sizeof (*mv_attr));
	mv_attr->attr_state.delete_csn = NOT_PRESENT;
	mv_attr->attr_state.present = 1;
	mv_attr->value_count = sim.value_count;
	
	for (i = 0; i < mv_attr->value_count; i++)
	{
		init_value_state (&(mv_attr->values[i]), i);
	}
}

void init_value_state (Value_State *val, int seq_num)
{
	memset (val, 0, sizeof (*val));
	val->value_index = seq_num;	
	val->present = 1;
	val->delete_csn = NOT_PRESENT;
}

void apply_operation (Entry_State *entry, Operation *op)
{
	switch (op->type)
	{
		case OP_ADD_VALUE:		apply_add_operation (entry, op);
								break;
			
		case OP_DELETE_VALUE:	apply_value_delete_operation (entry, op);
								break;
		
		case OP_DELETE_ATTR:	apply_attr_delete_operation (entry, op);
								break;
				
		case OP_RENAME_ENTRY:	apply_rename_operation (entry, op);
								break;
	}

	if (sim.verbose)
	{	
		fprintf (sim.fout, "operation: ");
		dump_operation (op);
		fprintf (sim.fout, "\n");
		dump_entry_state (entry);
	}
}

void free_operations (Operation **ops)
{
	free (*ops);
	*ops = NULL;
}

int **new_perm_table (int op_count)
{
	int i;
	int **perm_table;
	int perm_count = get_perm_count (op_count);

	perm_table = (int**)malloc (perm_count * sizeof (int*));
	for (i = 0; i < perm_count; i ++)
		perm_table [i] = (int*) malloc (op_count * sizeof (int));

	return perm_table;	
}

void free_perm_table (int ***perm_table, int op_count)
{
	int i;
	int perm_count = get_perm_count (op_count);

	for (i = 0; i < perm_count; i ++)
		free ((*perm_table)[i]);

	free (*perm_table);
	*perm_table = NULL;
}

void generate_perm_table (int *elements, int element_count, int static_part,
						  int **perm_table)
{
	int i;
	int elements_copy [MAX_OPS];
	int start_pos;

	if (element_count - 1 == static_part)
	{
		memcpy (*perm_table, elements, element_count * sizeof (int));
		return;
	}

	start_pos = 0;
	for (i = 0; i < element_count - static_part; i ++)
	{
		memcpy (elements_copy, elements, element_count * sizeof (int));
		elements_copy [static_part] = elements [static_part + i];
		elements_copy [static_part + i] = elements [static_part];
		generate_perm_table (elements_copy, element_count, static_part + 1, 
							 &perm_table [start_pos]);
		start_pos += get_perm_count (element_count - static_part - 1);
	}
}

int get_perm_count (int op_count)
{
	int i;
	int perm_count = 1;

	for (i = 2; i <= op_count; i ++)
		perm_count *= i;

	return perm_count;		
}

void apply_add_operation (Entry_State *entry, Operation *op)
{
	if (op->sv_attr)
	{
		Value_State *val;
		Value_State temp_val;

		if (op->value_index == entry->sv_attr.current_value.value_index)
		{
			val = &entry->sv_attr.current_value;
		}
		else if (entry->sv_attr.pending_value && 
                 op->value_index == entry->sv_attr.pending_value->value_index)
		{
			val = entry->sv_attr.pending_value;
		}
		else /* new value */
		{
			init_value_state (&temp_val, op->value_index);
			val = &temp_val;			
		}

		if (val->presence_csn < op->csn)
			val->presence_csn = op->csn;

		resolve_sv_attr_state (entry, val);	
	}
	else
	{
		if (entry->mv_attr.values[op->value_index].presence_csn < op->csn)
		{
			entry->mv_attr.values[op->value_index].presence_csn = op->csn;
			resolve_mv_attr_state (entry, &(entry->mv_attr.values[op->value_index]));
		}
	}
}

void apply_value_delete_operation (Entry_State *entry, Operation *op)
{
	if (op->sv_attr)
	{
		if (entry->sv_attr.attr_state.delete_csn < op->csn)
		{
			entry->sv_attr.attr_state.delete_csn = op->csn;
			resolve_sv_attr_state (entry, NULL);			
		}
	}
	else  /* mv attr */
	{
		if (entry->mv_attr.values[op->value_index].delete_csn < op->csn)
		{
			entry->mv_attr.values[op->value_index].delete_csn = op->csn;
			resolve_mv_attr_state (entry, &(entry->mv_attr.values[op->value_index]));	
		}
	}
}

void apply_attr_delete_operation (Entry_State *entry, Operation *op)
{
	int i;

	if (op->sv_attr)
	{
		if (entry->sv_attr.attr_state.delete_csn < op->csn)
		{
			entry->sv_attr.attr_state.delete_csn = op->csn;
			resolve_sv_attr_state (entry, NULL);			
		}
	}
	else /* mv attr */
	{
		if (entry->mv_attr.attr_state.delete_csn < op->csn)
		{
			entry->mv_attr.attr_state.delete_csn = op->csn;

			for (i = 0; i < sim.value_count; i++)
			{
				resolve_mv_attr_state (entry, &(entry->mv_attr.values[i]));	
			}
		}
	}
}

void apply_rename_operation (Entry_State *entry, Operation *op)
{
	int index;
	Operation del_op;

	/* insert new dn into dn_csn_list */
	index = dn_csn_add (entry, op->sv_attr, op->value_index, op->csn);

	/* issue delete value operation for the old rdn */
	if (op->delete_old_rdn)
	{
		del_op.type			= OP_DELETE_VALUE;
		del_op.csn			= op->csn;
		del_op.sv_attr		= op->old_rdn_sv_attr;
		del_op.value_index	= op->old_rdn_value_index;

		apply_value_delete_operation (entry, &del_op);	
	}

	/* resolve state of the previous node in dn_csn_list */
	if (index > 0)
	{
		if (entry->dn_csns[index-1].sv_attr)
		{
			if (entry->dn_csns[index-1].value_index == 
				entry->sv_attr.current_value.value_index)
			{
				resolve_sv_attr_state (entry, &(entry->sv_attr.current_value));	
			}
			else if (entry->sv_attr.pending_value && 
                     entry->dn_csns[index-1].value_index == 
					 entry->sv_attr.pending_value->value_index)
			{
				resolve_sv_attr_state (entry, entry->sv_attr.pending_value);	
			}
		}
		else
		{
			int i = entry->dn_csns[index-1].value_index;
			resolve_mv_attr_state (entry, &(entry->mv_attr.values[i]));
		} 
	}

	/* resolve state of the new dn */
	if (op->sv_attr)
	{
		Value_State *value;
		Value_State temp_val;
		if (op->value_index == entry->sv_attr.current_value.value_index)
		{
			value = &entry->sv_attr.current_value;
		}
		else if (entry->sv_attr.pending_value && 
                 op->value_index == entry->sv_attr.pending_value->value_index)
		{
			value = entry->sv_attr.pending_value;	
		}
		else /* new value */
		{
			init_value_state (&temp_val, op->value_index);
			value = &temp_val;
		}

		if (value->presence_csn == NOT_PRESENT || value->presence_csn < op->csn)
			value->presence_csn = op->csn;			
		resolve_sv_attr_state (entry, value);
	}
	else
	{
		if (entry->mv_attr.values[op->value_index].presence_csn == NOT_PRESENT ||
			entry->mv_attr.values[op->value_index].presence_csn < op->csn)
			entry->mv_attr.values[op->value_index].presence_csn = op->csn;	

		resolve_mv_attr_state (entry, &(entry->mv_attr.values[op->value_index]));
	}
}

void purge_mv_attr_state (Entry_State *entry, Value_State *value)
{
	if (value->presence_csn > value->delete_csn)
		value->delete_csn = NOT_PRESENT;	
}

void purge_sv_attr_state (Entry_State *entry)
{
	if (entry->sv_attr.attr_state.delete_csn != NOT_PRESENT)
	{
		if (entry->sv_attr.pending_value)
		{
			if (entry->sv_attr.attr_state.delete_csn < 
                entry->sv_attr.pending_value->presence_csn)
			{
				entry->sv_attr.attr_state.delete_csn = NOT_PRESENT;
			}
		}	
		else
		{
			if (entry->sv_attr.attr_state.delete_csn < 
				entry->sv_attr.current_value.presence_csn)
				entry->sv_attr.attr_state.delete_csn = NOT_PRESENT;
		}
	}
}

void resolve_mv_attr_state (Entry_State *entry, Value_State *value)
{
	purge_mv_attr_state (entry, value);

	/* no deletes that effect the state */
	if (max_val (value->delete_csn, entry->mv_attr.attr_state.delete_csn) <
        value->presence_csn)
	{
		value->present = 1;
		return;
	}

	if (value->present)	/* check if it should be removed based on the current state */
	{
		if (!value_distinguished_at_csn (entry, 0, value, 
							max (value->delete_csn, entry->mv_attr.attr_state.delete_csn)))
		{
			value->present = 0;
		}			
	}
	else	/* not present - check if it should be restored */
	{
		if (value_distinguished_at_csn (entry, 0, value,
							max (value->delete_csn, entry->mv_attr.attr_state.delete_csn)))
		{
			value->present = 1;	
		}
	}

	if (entry->mv_attr.attr_state.delete_csn == NOT_PRESENT)
	{
		entry->mv_attr.attr_state.present = 1;
	}
	else
	{
		int i;
		int distinguished = 0;

		for (i = 0; i < entry->mv_attr.value_count; i ++)
		{
			distinguished |= value_distinguished_at_csn (entry, 0, 
                                                         &(entry->mv_attr.values[i]),
														 entry->mv_attr.attr_state.delete_csn);
		}

		entry->mv_attr.attr_state.present = distinguished;
	}
}

void resolve_sv_attr_state (Entry_State *entry, Value_State *value)
{
	purge_sv_attr_state (entry);
		 
	if (value)
	{
		/* existing value is modified */
		if (value == &(entry->sv_attr.current_value) ||
			value == entry->sv_attr.pending_value)
		{
			/* check if current value should be replaced with the pending value */
			if (entry->sv_attr.pending_value)
			{
				if (!value_distinguished_at_csn (entry, 1, &entry->sv_attr.current_value,
					entry->sv_attr.current_value.presence_csn))
				{
					/* replace current value with the pending value */
					memcpy (&entry->sv_attr.current_value, entry->sv_attr.pending_value,
							sizeof (Value_State));
					free (entry->sv_attr.pending_value);
					entry->sv_attr.pending_value = NULL;
				}
			} 
		}
		else	/* addition of a new value */
		{
			/* new value is before the current value; note that, for new value,
               presence_csn is the same as distinguished_csn */
			if (value->presence_csn < entry->sv_attr.current_value.presence_csn)
			{
				/* if new value is distinguished, it should become current and the
				   current can become pending */
				if (value_distinguished_at_csn (entry, 1, value,
					                            entry->sv_attr.current_value.presence_csn))
				{
					if (entry->sv_attr.pending_value == NULL)
					{
						entry->sv_attr.pending_value = (Value_State*)
														malloc (sizeof (Value_State));
						memcpy (entry->sv_attr.pending_value, &entry->sv_attr.current_value,
								sizeof (Value_State));
					}

					memcpy (&entry->sv_attr.current_value, value, sizeof (Value_State));
				}
			} 
			else /* new value is after the current value */
			{
				/* if current value is not distinguished, new value should 
                   become distinguished */
				if (!value_distinguished_at_csn (entry, 1, &entry->sv_attr.current_value, 
                     value->presence_csn))
				{
					memcpy (&entry->sv_attr.current_value, value, sizeof (Value_State));
				}
				else /* current value is distinguished - check if new value should replace
                        the pending value */
				{	if (entry->sv_attr.pending_value)
					{
						if (value->presence_csn > entry->sv_attr.pending_value->presence_csn)
						{
							memcpy (entry->sv_attr.pending_value, value, sizeof (Value_State));
						}
					}
					else
					{
						entry->sv_attr.pending_value = (Value_State*)malloc (sizeof (Value_State));	
						memcpy (entry->sv_attr.pending_value, value, sizeof (Value_State));
					}
				}
			}
		}
	}
	
	/* update the attribute state */
	purge_sv_attr_state (entry);

	/* set attribute state */
	if (entry->sv_attr.attr_state.delete_csn != NOT_PRESENT &&
		!value_distinguished_at_csn (entry, 1, &entry->sv_attr.current_value, 
									 entry->sv_attr.attr_state.delete_csn))
	{
		entry->sv_attr.attr_state.present = 0;
	}
	else
	{
		entry->sv_attr.attr_state.present = 1;
	}
}

int value_distinguished_at_csn (Entry_State *entry, int sv_attr, Value_State *value, int csn)
{
	int i;

	for (i = 0; i < entry->dn_csn_count; i++)
	{
		if (entry->dn_csns[i].csn > csn)
			break;
	}
	
	/* i is never equal to 0 because the csn of the first element is always
	   smaller than csn of any operation we can receive */
	return (entry->dn_csns[i-1].value_index == value->value_index &&
			entry->dn_csns[i-1].sv_attr == sv_attr);	
}

int compare_entry_state (Entry_State *entry1, Entry_State *entry2, int run)
{
	int i;
	int error = 0;

	error = compare_entry_state_quick (entry1, entry2, run);

	if (error)
		return 3;

	/* compare dnc_csn list */
	if (entry1->dn_csn_count != entry2->dn_csn_count)
	{
		fprintf (sim.fout, "dn_csn count is %d for run 1 and %d for run %d\n",
				entry1->dn_csn_count, entry2->dn_csn_count, run);
		error = 1;
	}

	for (i = 0; i < entry1->dn_csn_count; i++)
	{
		if (entry1->dn_csns [i].csn != entry2->dn_csns [i].csn || 
			entry1->dn_csns [i].sv_attr != entry2->dn_csns [i].sv_attr || 			
			entry1->dn_csns [i].value_index != entry2->dn_csns [i].value_index)
		{
			fprintf (sim.fout,"elements %d of dn csn list are different:\n"
					 "\tfirst run: csn - %d, attr - %s, value - %s\n"
					 "\t%d run: csn - %d, attr - %s value - %s\n", i, 
					 entry1->dn_csns [i].csn, 
					 entry1->dn_csns [i].sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME,
					 g_values[entry1->dn_csns [i].value_index],
					 run, entry2->dn_csns [i].csn, 
					 entry2->dn_csns [i].sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME,
					 g_values[entry2->dn_csns [i].value_index]);

			error = 1;
		}
	}

	error |= compare_sv_attr_state (&entry1->sv_attr, &entry2->sv_attr, run);

	error |= compare_mv_attr_state (&entry1->mv_attr, &entry2->mv_attr, run);
	
	if (error != 0)
	{
		return 1;
	}
	else
		return 0;
}

/* just compare if the same attributes and values are present */
int compare_entry_state_quick (Entry_State *entry1, Entry_State *entry2, int run)
{
	int error;

	error = compare_sv_attr_state_quick (&entry1->sv_attr, &entry2->sv_attr, run);
	
	error |= compare_mv_attr_state_quick (&entry1->mv_attr, &entry2->mv_attr, run);

	return error;
}

int compare_sv_attr_state_quick (SV_Attr_State *sv_attr1, SV_Attr_State *sv_attr2, int run)
{
	int error = 0;
	if (sv_attr1->attr_state.present !=	sv_attr2->attr_state.present)
	{
		fprintf (sim.fout, "singlevalued attribute is %s present in the first run "
				 "but is %s present in the %d run\n", 
				 sv_attr1->attr_state.present ? "" : "not", 
				 sv_attr2->attr_state.present ? "" : "not", run);
		return 1;	
	}

	if (sv_attr1->attr_state.present && 
        sv_attr1->current_value.value_index != sv_attr2->current_value.value_index)
	{
		fprintf (sim.fout, "different values for singlevalued attribute: %s for the \n"
                 "first run and %s for the %d run\n", 
				 g_values [sv_attr1->current_value.value_index],
				 g_values [sv_attr2->current_value.value_index], run);
		return 1;
	}

	return 0;
}

int compare_mv_attr_state_quick (MV_Attr_State *mv_attr1, MV_Attr_State *mv_attr2, int run)
{	
	int i;
	int error = 0;
 
	if (mv_attr1->attr_state.present !=	mv_attr2->attr_state.present)
	{
		fprintf (sim.fout, "multivalued attribute is %s present in the first run "
				 "but is %s present in the %d run\n", 
				 mv_attr1->attr_state.present ? "" : "not", 
				 mv_attr2->attr_state.present ? "" : "not", run);
		return 1;	
	}

	/* value count does not change during the iteration, so we don't have
       to check if the count is the same for both attributes */
	for (i = 0; i < mv_attr1->value_count; i++)
	{
		if (mv_attr1->values[i].present != mv_attr2->values[i].present)
		{
			fprintf (sim.fout, "value %s is %s present in the multivalued attribute\n"
                     "in the first run but %s present in the %d run\n",
					 g_values[i], mv_attr1->values[i].present ? "" : "not",	
					 mv_attr2->values[i].present ? "" : "not", run);
			error = 1;
		}					 
	}

	return error;
}

int compare_sv_attr_state (SV_Attr_State *sv_attr1, SV_Attr_State *sv_attr2, int run)
{
	int error = 0;

	if (sv_attr1->attr_state.delete_csn != sv_attr2->attr_state.delete_csn)
	{
		fprintf (sim.fout, "singlevalued attribute deletion csn is %d for run 1 "
				 "but is %d for run %d\n", sv_attr1->attr_state.delete_csn, 
				 sv_attr2->attr_state.delete_csn, run);
		error = 1;
	}

	error |= compare_value_state (&sv_attr1->current_value, &sv_attr2->current_value, run);

	if ((sv_attr1->pending_value && !sv_attr1->pending_value) ||
		(!sv_attr1->pending_value && sv_attr1->pending_value))
	{
		fprintf (sim.fout, "pending value is %s present in the singlevalued attribute\n"
				 " in the first run but is %s in the %d run\n",
				 sv_attr1->pending_value ? "" : "not",
				 sv_attr2->pending_value ? "" : "not", run);

		return 1;
	}	

	if (sv_attr1->pending_value)
		error |= compare_value_state (sv_attr1->pending_value, sv_attr2->pending_value, run);

	return 0; 
}

int compare_mv_attr_state (MV_Attr_State *mv_attr1, MV_Attr_State *mv_attr2, int run)
{
	int error = 0;
	int i;

	if (mv_attr1->attr_state.delete_csn != mv_attr2->attr_state.delete_csn)
	{
		fprintf (sim.fout, "multivalued attribute deletion csn is %d for run 1 "
				 "but is %d for run %d\n", mv_attr1->attr_state.delete_csn, 
				 mv_attr2->attr_state.delete_csn, run);
		error = 1;
	}
	
	for (i = 0; i < mv_attr1->value_count; i++)
	{
		error |= compare_value_state (&mv_attr1->values[i], &mv_attr2->values[i], run);
	}

	return error;
}

int compare_value_state (Value_State *value1, Value_State *value2, int run)
{
	int error = 0;

	if (value1->presence_csn != value2->presence_csn)
	{
		fprintf (sim.fout, "multivalued attribute: presence csn for value %s is %d "
				 "in run 1 but is %d in run %d\n", g_values[value1->value_index], 
				 value1->presence_csn, value2->presence_csn, run);
		error = 1;
	}

	if (value1->delete_csn != value2->delete_csn)
	{
		fprintf (sim.fout, "multivalued attribute: delete csn for value %s is %d in run 1 "
				 "but is %d in run %d\n", g_values[value1->value_index], 
				 value1->delete_csn, value2->delete_csn, run);
		error = 1;
	}

	return error;
}

int dn_csn_add (Entry_State *entry, int sv_attr, int value_index, int csn)
{
	int i;

	for (i = 0; i < entry->dn_csn_count; i++)
	{
		if (entry->dn_csns[i].csn > csn)
			break;
	}
	
	if (i < entry->dn_csn_count)
	{
		memcpy (&(entry->dn_csns[i+1]), &(entry->dn_csns[i]), 
				(entry->dn_csn_count - i) * sizeof (Dn_Csn));	
	}

	entry->dn_csns[i].csn = csn;
	entry->dn_csns[i].sv_attr = sv_attr;
	entry->dn_csns[i].value_index = value_index;
	entry->dn_csn_count ++;

	return i;				
}

void dump_operations (Operation *ops, int op_count, int *order)
{
	int index;
	int i;

	for (i = 0; i < op_count; i ++)
	{
		if (order == NULL)	/* current order */
			index = i;
		else
			index = order [i];

		dump_operation (&ops[index]);
	}

	fprintf (sim.fout, "\n");
}

void dump_operation (Operation *op)
{
	switch (op->type)
	{
		case OP_ADD_VALUE:		
				fprintf (sim.fout, "\t%d add value %s to %s\n", op->csn, 
						 g_values [op->value_index],
						 op->sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME);
				break; 
		case OP_DELETE_VALUE:	
				fprintf (sim.fout, "\t%d delete value %s from %s\n", op->csn, 
						 g_values [op->value_index],
						 op->sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME);
				break;
		case OP_DELETE_ATTR:
				fprintf (sim.fout, "\t%d delete %s attribute\n", op->csn,
						 op->sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME);
				break;
		case OP_RENAME_ENTRY:
				fprintf (sim.fout, "\t%d rename entry to %s=%s", op->csn, 
						 op->sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME,
						 g_values [op->value_index]);
				if (op->delete_old_rdn)
					fprintf (sim.fout, " delete old rdn %s=%s\n", 
						     op->old_rdn_sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME,
						     g_values [op->old_rdn_value_index]);
				else
					fprintf (sim.fout, "\n");	
				break;
	}			
}

void dump_perm_table (int **perm_table, int op_count)
{
	int i, j;
	int perm_count = get_perm_count (op_count);

	for (i = 0; i < op_count; i++)
	{
		for (j = 0; j < perm_count; j++)
		{
			fprintf (sim.fout, "%d  ", perm_table [j][i]);
		}

		fprintf (sim.fout, "\n");
	}
}

void dump_entry_state (Entry_State *entry)
{
	dump_dn_csn_list (entry);

	dump_sv_attr_state (&entry->sv_attr);
	dump_mv_attr_state (&entry->mv_attr);

	fprintf (sim.fout, "\n");
}

void dump_sv_attr_state (SV_Attr_State *sv_attr)
{
	fprintf (sim.fout, "\tattribute %s is %s present", SV_ATTR_NAME, 
			 sv_attr->attr_state.present ? "" : "not");
	if (sv_attr->attr_state.present)
	{
		fprintf (sim.fout, " and has the value of %s\n", 
				 g_values[sv_attr->current_value.value_index]);
	}
	else
	{ 
		fprintf (sim.fout, "\n");
	}

	if (sim.verbose)
	{
		fprintf (sim.fout, "\t\tdeletion csn: %d\n", sv_attr->attr_state.delete_csn);	
		fprintf (sim.fout, "\t\tcurrent value: ");
		dump_value_state (&sv_attr->current_value, 1/* for single valued attr */);
		if (sv_attr->pending_value)
		{
			fprintf (sim.fout, "\t\tpending value: ");
			dump_value_state (sv_attr->pending_value, 1/* for single valued attr */);
		}
	}
}

void dump_mv_attr_state (MV_Attr_State *mv_attr)
{
	int i;

	fprintf (sim.fout, "\tattribute %s is %s present\n", MV_ATTR_NAME, 
	         mv_attr->attr_state.present ? "" : "not");

	if (sim.verbose)
	{
		fprintf (sim.fout, "\t\tdeletion csn: %d\n", mv_attr->attr_state.delete_csn);
	}	

	for (i = 0; i < mv_attr->value_count; i++)
	{
		dump_value_state (&(mv_attr->values[i]), 0);
	}
}

void dump_value_state (Value_State *value, int sv_attr)
{
	if (!sv_attr)
	{
		fprintf (sim.fout, "\tvalue %s is %s present\n", g_values[value->value_index], 
				 value->present ? "" : "not");
	}
	else
	{
		fprintf (sim.fout, "%s\n", g_values[value->value_index]); 
	}

	if (sim.verbose)
	{	
		fprintf (sim.fout, "\t\t\tpresence csn: %d\n", value->presence_csn);
		fprintf (sim.fout, "\t\t\tdeletion value csn: %d\n", value->delete_csn);
	}
}

void dump_dn_csn_list (Entry_State *entry)
{
	int i;

	fprintf (sim.fout, "\tdn csn list: \n");	
	for (i = 0; i < entry->dn_csn_count; i++)
	{
		fprintf (sim.fout, "\t\t %s=%s, csn: %d\n", 
				 entry->dn_csns[i].sv_attr ? SV_ATTR_NAME : MV_ATTR_NAME,
				 g_values[entry->dn_csns[i].value_index], entry->dn_csns[i].csn);
	}
}

/* misc functions */
int max_val (int a, int b)
{
	if (a >= b)
		return a;
	else
		return b;
}