skiplist.c File Reference

Functions manipulating skiplists. More...

#include "temporal/skiplist.h"
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <postgres.h>
#include <utils/timestamp.h>
#include <meos.h>
#include <meos_internal.h>
#include "temporal/temporal_aggfuncs.h"
#include "temporal/type_util.h"

Macros
#define	MaxAllocSize   ((Size) 0x3fffffff) /* 1 gigabyte - 1 */
#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...
bool	ensure_same_skiplist_subtype (SkipList *state, uint8 subtype)
static long int	gsl_random48 ()
static RelativeTimePos	pos_span_span (const Span *s1, const Span *s2)
	Determine the relative position of two periods. More...
static RelativeTimePos	pos_span_timestamptz (const Span *s, TimestampTz t)
	Determine the relative position of a span and a timestamptz. 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 *s, int cur)
	Comparison function used for skiplists. More...
void	skiplist_free (SkipList *list)
	Delete the skiplist and free its allocated memory. More...
void *	skiplist_headval (SkipList *list)
	Return the value at the head of the skiplist. More...
SkipList *	skiplist_make (void **values, int count)
	Constructs a skiplist from the array of values values. 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...

Detailed Description

Functions manipulating skiplists.

Note

See the description of skip lists in Wikipedia https://en.wikipedia.org/wiki/Skip_list Note also that according to https://github.com/postgres/postgres/blob/master/src/backend/utils/mmgr/README#L99 pfree/repalloc Do Not Depend On CurrentMemoryContext