open62541 1.3.12
Open source implementation of OPC UA
Loading...
Searching...
No Matches
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.