ziptree.h File Reference

#include <stddef.h>

Go to the source code of this file.

Macros
#define	ZIP_INLINE   inline
#define	ZIP_UNUSED
#define	ZIP_HEAD(name, type)
#define	ZIP_ENTRY(type)
#define	ZIP_INIT(head)   do { (head)->root = NULL; } while (0)
#define	ZIP_ROOT(head)   (head)->root
#define	ZIP_LEFT(elm, field)   (elm)->field.left
#define	ZIP_RIGHT(elm, field)   (elm)->field.right
#define	ZIP_RANK(elm, field)   (elm)->field.rank
#define	ZIP_INSERT(name, head, elm, rank)   name##_ZIP_INSERT(head, elm, rank)
#define	ZIP_REMOVE(name, head, elm)   name##_ZIP_REMOVE(head, elm)
#define	ZIP_FIND(name, head, key)   name##_ZIP_FIND(head, key)
#define	ZIP_MIN(name, head)   name##_ZIP_MIN(head)
#define	ZIP_MAX(name, head)   name##_ZIP_MAX(head)
#define	ZIP_ITER(name, head, cb, d)   name##_ZIP_ITER(head, cb, d)
#define	ZIP_FUNCTIONS(name, type, field, keytype, keyfield, cmp)

Typedefs
typedef enum ZIP_CMP(*	zip_cmp_cb) (const void *key1, const void *key2)
typedef void(*	__zip_iter_cb) (void *elm, void *context)

Enumerations
enum	ZIP_CMP

Functions
void *	__ZIP_INSERT (zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, void *root, void *elm)
void *	__ZIP_REMOVE (zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, void *root, void *elm)
void *	__ZIP_FIND (zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, void *root, const void *key)
void	__ZIP_ITER (unsigned short fieldoffset, __zip_iter_cb cb, void *context, void *elm)
void *	__ZIP_MIN (unsigned short fieldoffset, void *elm)
void *	__ZIP_MAX (unsigned short fieldoffset, void *elm)
unsigned char	__ZIP_FFS32 (unsigned int v)

Macro Definition Documentation

ZIP_INLINE

#define ZIP_INLINE   inline

This Source Code Form is subject to the terms of the Mozilla Public License, v.

2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

Copyright 2018, 2021 (c) Julius Pfrommer

Definition at line 16 of file ziptree.h.

ZIP_UNUSED

#define ZIP_UNUSED

Prevent warnings on unused static inline functions for some compilers.

Definition at line 23 of file ziptree.h.

ZIP_HEAD

#define ZIP_HEAD	(		name,
			type )

Value:

struct name {                                   \
    struct type *root;                          \
}

Reusable zip tree implementation.

The style is inspired by the BSD sys/queue.h linked list definition.

Zip trees were developed in: Tarjan, R. E., Levy, C. C., and Timmel, S. "Zip Trees." arXiv preprint arXiv:1806.06726 (2018). The original definition was modified so that several elements with the same key can be inserted. However, ZIP_FIND will only return the topmost of these elements in the tree.

The ZIP_ENTRY definitions are to be contained in the tree entries themselves. Use ZIP_FUNCTIONS to define the signature of the zip tree functions.

Definition at line 41 of file ziptree.h.

ZIP_ENTRY

#define ZIP_ENTRY

(

type

)

Value:

struct {                                        \
    struct type *left;                          \
    struct type *right;                         \
    unsigned char rank;                         \
}

Definition at line 46 of file ziptree.h.

ZIP_INIT

#define ZIP_INIT

(

head

)

do { (head)->root = NULL; } while (0)

Definition at line 61 of file ziptree.h.

ZIP_ROOT

#define ZIP_ROOT

(

head

)

(head)->root

Definition at line 62 of file ziptree.h.

ZIP_LEFT

#define ZIP_LEFT	(		elm,
			field )   (elm)->field.left

Definition at line 63 of file ziptree.h.

ZIP_RIGHT

#define ZIP_RIGHT	(		elm,
			field )   (elm)->field.right

Definition at line 64 of file ziptree.h.

ZIP_RANK

#define ZIP_RANK	(		elm,
			field )   (elm)->field.rank

Definition at line 65 of file ziptree.h.

ZIP_INSERT

#define ZIP_INSERT	(		name,
			head,
			elm,
			rank )   name##_ZIP_INSERT(head, elm, rank)

Generate zip tree method definitions with the ZIP_FUNCTIONS macro.

The comparison method "cmp" defined for every zip tree has the signature

enum ZIP_CMP cmpDateTime(const keytype *a, const keytype *b);

Definition at line 103 of file ziptree.h.

ZIP_REMOVE

#define ZIP_REMOVE	(		name,
			head,
			elm )   name##_ZIP_REMOVE(head, elm)

Definition at line 104 of file ziptree.h.

ZIP_FIND

#define ZIP_FIND	(		name,
			head,
			key )   name##_ZIP_FIND(head, key)

Definition at line 105 of file ziptree.h.

ZIP_MIN

#define ZIP_MIN	(		name,
			head )   name##_ZIP_MIN(head)

Definition at line 106 of file ziptree.h.

ZIP_MAX

#define ZIP_MAX	(		name,
			head )   name##_ZIP_MAX(head)

Definition at line 107 of file ziptree.h.

ZIP_ITER

#define ZIP_ITER	(		name,
			head,
			cb,
			d )   name##_ZIP_ITER(head, cb, d)

Definition at line 108 of file ziptree.h.

ZIP_FUNCTIONS

#define ZIP_FUNCTIONS	(		name,
			type,
			field,
			keytype,
			keyfield,
			cmp )

Definition at line 110 of file ziptree.h.

Typedef Documentation

zip_cmp_cb

typedef enum ZIP_CMP(* zip_cmp_cb) (const void *key1, const void *key2)

Definition at line 1 of file ziptree.h.

__zip_iter_cb

typedef void(* __zip_iter_cb) (void *elm, void *context)

Internal definitions.

Don't use directly.

Definition at line 69 of file ziptree.h.

Enumeration Type Documentation

ZIP_CMP

enum ZIP_CMP

Enumerator
ZIP_CMP_LESS
ZIP_CMP_EQ
ZIP_CMP_MORE

Definition at line 53 of file ziptree.h.

Function Documentation

__ZIP_INSERT()

void * __ZIP_INSERT	(	zip_cmp_cb	cmp,
		unsigned short	fieldoffset,
		unsigned short	keyoffset,
		void *	root,
		void *	elm )

__ZIP_REMOVE()

void * __ZIP_REMOVE	(	zip_cmp_cb	cmp,
		unsigned short	fieldoffset,
		unsigned short	keyoffset,
		void *	root,
		void *	elm )

__ZIP_FIND()

void * __ZIP_FIND	(	zip_cmp_cb	cmp,
		unsigned short	fieldoffset,
		unsigned short	keyoffset,
		void *	root,
		const void *	key )

__ZIP_ITER()

void __ZIP_ITER	(	unsigned short	fieldoffset,
		__zip_iter_cb	cb,
		void *	context,
		void *	elm )

__ZIP_MIN()

void * __ZIP_MIN	(	unsigned short	fieldoffset,
		void *	elm )

__ZIP_MAX()

void * __ZIP_MAX	(	unsigned short	fieldoffset,
		void *	elm )

__ZIP_FFS32()

unsigned char __ZIP_FFS32

(

unsigned int

v

)

Zip trees are a probabilistic data structure.

Entries are assigned a (non-negative) rank k with probability 1/2^{k+1}. A uniformly sampled random number has to be supplied with the insert method. __ZIP_FFS32 extracts from it least significant nonzero bit of a 32bit number. This then has the correct distribution.