open62541 1.4.15
Open source implementation of OPC UA
Loading...
Searching...
No Matches
Macros | Typedefs | Enumerations | Functions
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_INSERT(name, head, elm)   name##_ZIP_INSERT(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_REMOVE(name, head, elm)   name##_ZIP_REMOVE(head, elm)
 
#define ZIP_ZIP(name, left, right)   name##_ZIP_ZIP(left, right)
 
#define ZIP_UNZIP(name, head, key, left, right)    name##_ZIP_UNZIP(head, key, left, right)
 
#define ZIP_ITER(name, head, cb, ctx)   name##_ZIP_ITER(head, cb, ctx)
 
#define ZIP_ITER_KEY(name, head, key, cb, ctx)   name##_ZIP_ITER_KEY(head, key, cb, ctx)
 
#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 *context, void *elm)
 

Enumerations

enum  ZIP_CMP
 

Functions

void __ZIP_INSERT (void *h, zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, void *elm)
 
void * __ZIP_REMOVE (void *h, zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, void *elm)
 
void * __ZIP_ITER (unsigned short fieldoffset, zip_iter_cb cb, void *context, void *elm)
 
void * __ZIP_ITER_KEY (zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, const void *key, zip_iter_cb cb, void *context, void *elm)
 
void * __ZIP_ZIP (unsigned short fieldoffset, void *left, void *right)
 
void __ZIP_UNZIP (zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, const void *key, void *h, void *l, void *r)
 

Macro Definition Documentation

◆ ZIP_ENTRY

#define ZIP_ENTRY (   type)
Value:
struct { \
struct type *left; \
struct type *right; \
}
type
const UA_DataType * type
Definition types.h:626

Definition at line 49 of file ziptree.h.

◆ ZIP_FIND

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

Definition at line 73 of file ziptree.h.

◆ ZIP_FUNCTIONS

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

Macro to generate typed ziptree methods.

Definition at line 100 of file ziptree.h.

◆ ZIP_HEAD

#define ZIP_HEAD (   name,
  type 
)
Value:
struct name { \
struct type *root; \
}
name
qn name
Definition types.h:517

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 in two ways:

  • Multiple elements with the same key can be inserted. These appear adjacent in the tree. ZIP_FIND will return the topmost of these elements.
  • The pointer-value of the elements are used as the rank. This simplifies the code and is (empirically) faster.

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 44 of file ziptree.h.

◆ ZIP_INIT

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

Definition at line 68 of file ziptree.h.

◆ 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-2022 (c) Julius Pfrommer

Definition at line 16 of file ziptree.h.

◆ ZIP_INSERT

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

Definition at line 72 of file ziptree.h.

◆ ZIP_ITER

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

Definition at line 94 of file ziptree.h.

◆ ZIP_ITER_KEY

#define ZIP_ITER_KEY (   name,
  head,
  key,
  cb,
  ctx 
)    name##_ZIP_ITER_KEY(head, key, cb, ctx)

Same as _ITER, but only visits elements with the given key.

Definition at line 97 of file ziptree.h.

◆ ZIP_LEFT

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

Definition at line 70 of file ziptree.h.

◆ ZIP_MAX

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

Definition at line 75 of file ziptree.h.

◆ ZIP_MIN

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

Definition at line 74 of file ziptree.h.

◆ ZIP_REMOVE

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

Returns the element if it was found in the tree.

Returns NULL otherwise.

Definition at line 78 of file ziptree.h.

◆ ZIP_RIGHT

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

Definition at line 71 of file ziptree.h.

◆ ZIP_ROOT

#define ZIP_ROOT (   head)    (head)->root

Definition at line 69 of file ziptree.h.

◆ ZIP_UNUSED

#define ZIP_UNUSED

Definition at line 22 of file ziptree.h.

◆ ZIP_UNZIP

#define ZIP_UNZIP (   name,
  head,
  key,
  left,
  right 
)     name##_ZIP_UNZIP(head, key, left, right)

Definition at line 83 of file ziptree.h.

◆ ZIP_ZIP

#define ZIP_ZIP (   name,
  left,
  right 
)    name##_ZIP_ZIP(left, right)

Split (_UNZIP) and merge (_ZIP) trees.

_UNZIP splits at the key and moves elements <= into the left output (right otherwise).

Definition at line 82 of file ziptree.h.

Typedef Documentation

◆ zip_cmp_cb

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

The comparison method "cmp" for a zip tree has the signature.

Provide this to the ZIP_FUNCTIONS macro.

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

Definition at line 1 of file ziptree.h.

◆ zip_iter_cb

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

ZIP_ITER uses in-order traversal of the tree (in the order of the keys).

The memory if a node is not accessed by ZIP_ITER after the callback has been executed for it. So a tree can be cleaned by calling free on each node from within the iteration callback.

ZIP_ITER returns a void pointer. The first callback to return non-NULL aborts the iteration. This pointer is then returned.

Definition at line 93 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 55 of file ziptree.h.

Function Documentation

◆ __ZIP_INSERT()

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

Internal definitions.

Don't use directly.

◆ __ZIP_ITER()

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

◆ __ZIP_ITER_KEY()

void * __ZIP_ITER_KEY ( zip_cmp_cb  cmp,
unsigned short  fieldoffset,
unsigned short  keyoffset,
const void *  key,
zip_iter_cb  cb,
void *  context,
void *  elm 
)

◆ __ZIP_REMOVE()

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

◆ __ZIP_UNZIP()

void __ZIP_UNZIP ( zip_cmp_cb  cmp,
unsigned short  fieldoffset,
unsigned short  keyoffset,
const void *  key,
void *  h,
void *  l,
void *  r 
)

◆ __ZIP_ZIP()

void * __ZIP_ZIP ( unsigned short  fieldoffset,
void *  left,
void *  right 
)
Generated by doxygen 1.9.8