A table of IdSet values. More...

#include "idsetset.h"
#include "idset.h"
#include "error.h"
#include "binary.h"
#include "misc.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/errno.h>

Data Structures
struct	El
	A single key-value pair, with a pointer to the next one. More...
struct	IdSetSet
	The hash table. More...

Macros
#define	SETS_PER_BUCKET 0.7

Functions
static int	resize (IdSetSet *self, int dim)
	Change the size of the hash map and rehash.
static El *	El_new (IdSet *idset)
	Construct a new element with given key and value.
static El *	El_free_shallow (El *e)
	Destroy a linked list of El objects, but do not free IdSet pointers.
static El *	El_free_deep (El *e)
	Destroy a linked list of El objects, including IdSet pointers.
static El *	El_add (El self, IdSet idset, int *status)
	Add an new IdSet into the linked list.
static void	El_sanityCheck (El el, const char file, int line)
IdSetSet *	IdSetSet_new (int n)
	Constructor reserves space for n elements.
void	IdSetSet_free_shallow (IdSetSet *self)
	Shallow destructor does not free IdSet objects.
void	IdSetSet_free_deep (IdSetSet *self)
	Deep destructor frees IdSet objects.
void	IdSetSet_empty_shallow (IdSetSet *self)
	Empty IdSetSet. Does not free the IdSet pointers.
void	IdSetSet_empty_deep (IdSetSet *self)
	Empty IdSetSet, including IdSet pointers.
int	IdSetSet_add (IdSetSet self, IdSet idset)
	Add a value to the table, resizing if necessary.
int	IdSetSet_size (IdSetSet *self)
	Return the number of elements.
int	IdSetSet_toArray (IdSetSet self, unsigned size, IdSet v[size])
	Put idset pointers into array "v".
int	IdSetSet_rewind (IdSetSet *self)
	Move curr to first filled bucket in hash table.
IdSet *	IdSetSet_next (IdSetSet *self)
	Return the next IdSet pointer, or NULL if there are no more.
int	IdSetSet_reserve (IdSetSet *self, int m)
	Make sure hash table is large enough to hold m additional elements.
void	IdSetSet_sanityCheck (IdSetSet self, const char file, int line)

Variables
static const double	sets_per_bucket = SETS_PER_BUCKET
static const double	buckets_per_set = 1.0/SETS_PER_BUCKET

Detailed Description

A table of IdSet values.

Author: Alan R. Rogers

The IdSetSet_add function merges entries that have identical tipId_t values and also identical migration histories. In that case, the probabilities of duplicate IdSet values add. If the IdSet objects are not identical, the IdSetSet_add function as separate copies.

To iterate across an IdSetSet named x:

IdSet *idset; IdSetSet_rewind(x); while( (idset = IdSetSet_next(x)) != NULL ) { <operate on idset> }

Copyright: Copyright (c) 2020, Alan R. Rogers roger.nosp@m.s@an.nosp@m.thro..nosp@m.utah.nosp@m..edu. This file is released under the Internet Systems Consortium License, which can be found in file "LICENSE".

Function Documentation

◆ El_add()

El * El_add	(	El *	self,
		IdSet *	idset,
		int *	status )

static

Add an new IdSet into the linked list.

Usage:

El *list=NULL;
int status;
list = El_add(list, idset, &status);
switch(status) {
case 0:
    printf("Added to probability of existing IdSet.\n");
    break;
case 1:
    printf("Added new IdSet to list\n");
    break;
default:
    printf("This should not happen.\n");
}

Parameters

	self	current element of list
[in]	idset,a	pointer
[out]	status	pointer to int, which will be set to 1 if the new IdSet did not previously exist in the list or to 0 if it was already there.

Returns: pointer to self or to a newly-allocated El.

References El_add(), El_new(), and El::next.

Referenced by El_add(), IdSetSet_add(), and resize().

◆ IdSetSet_add()

int IdSetSet_add	(	IdSetSet *	self,
		IdSet *	idset )

Add a value to the table, resizing if necessary.

Returns: 0 on success; ENOMEM if the function attempts unsuccessfully to resize the hash table.

References El_add(), and resize().

Referenced by get_descendants1(), and mv_to_waiting_room().

◆ IdSetSet_next()

IdSet * IdSetSet_next ( IdSetSet * self )

Return the next IdSet pointer, or NULL if there are no more.

Then move to next entry in the hash table.

References El::next.

Referenced by get_descendants1(), Segment_sanityCheck(), visitComb(), and visitSetPart().

◆ IdSetSet_rewind()

int IdSetSet_rewind ( IdSetSet * self )

Move curr to first filled bucket in hash table.

Return 0 on success or 1 if the hash table is empty;

Referenced by get_descendants1(), Segment_sanityCheck(), visitComb(), and visitSetPart().

◆ IdSetSet_toArray()

int IdSetSet_toArray	(	IdSetSet *	self,
		unsigned	size,
		IdSet *	v[size] )

Put idset pointers into array "v".

If the array isn't large enough, return BUFFER_OVERFLOW. Otherwise return 0.

References El::next.

Data Structures

Macros

Functions