skiplist.c File Reference

#include "general/skiplist.h"
#include <assert.h>
#include <math.h>
#include <postgres.h>
#include <gsl/gsl_rng.h>
#include <meos.h>
#include <meos_internal.h>
#include "general/pg_types.h"
#include "general/span.h"
#include "general/temporal_aggfuncs.h"
#include "general/time_aggfuncs.h"
#include "general/type_util.h"

Include dependency graph for skiplist.c:

Macros
#define	MaxAllocSize   ((Size) 0x3fffffff) /* 1 gigabyte - 1 */
	Functions manipulating skiplists. More...
#define	SKIPLIST_GROW   1
	double the capacity to expand the skiplist More...
#define	SKIPLIST_INITIAL_CAPACITY   1024
#define	SKIPLIST_INITIAL_FREELIST   32

Enumerations
enum	RelativeTimePos { BEFORE , DURING , AFTER }
	Enumeration for the relative position of a given element into a skiplist. More...

Functions
void	aggstate_set_extra (SkipList *state, void *data, size_t size)
	Output the skiplist in graphviz dot format for visualisation and debugging purposes. More...
static long int	gsl_random48 ()
static RelativeTimePos	pos_period_period (const Span *p1, const Span *p2)
	Determine the relative position of two periods. More...
static RelativeTimePos	pos_period_timestamp (const Span *p, TimestampTz t)
	Determine the relative position of a period and a timestamp. More...
static int	random_level ()
	This simulates up to SKIPLIST_MAXLEVEL repeated coin flips without spinning the RNG every time (courtesy of the internet) More...
static int	skiplist_alloc (SkipList *list)
	Return the position to store an additional element in the skiplist. More...
static void	skiplist_delete (SkipList *list, int cur)
	Delete an element from the skiplist. More...
static RelativeTimePos	skiplist_elempos (const SkipList *list, Span *p, int cur)
	Comparison function used for skiplists. More...
void	skiplist_free (SkipList *list)
	Free the skiplist. More...
void *	skiplist_headval (SkipList *list)
	Return the value at the head of the skiplist. More...
SkipList *	skiplist_make (void **values, int count, SkipListElemType elemtype)
	Constructs a skiplist from the array of values values. More...
Span **	skiplist_period_values (SkipList *list)
	Return a copy of the period values contained in the skiplist. More...
void	skiplist_splice (SkipList *list, void **values, int count, datum_func2 func, bool crossings)
	Splice the skiplist with the array of values using the aggregation function. More...
Temporal **	skiplist_temporal_values (SkipList *list)
	Return a copy of the temporal values contained in the skiplist. More...
void **	skiplist_values (SkipList *list)
	Return the values contained in the skiplist. More...

Variables
gsl_rng *	_aggregation_rng = NULL