Lely core libraries 2.3.4
pheap.h File Reference

This header file is part of the utilities library; it contains the pairing heap declarations. More...

#include <lely/features.h>
#include <assert.h>
#include <stddef.h>
Include dependency graph for pheap.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  pnode
 A node in a pairing heap. More...
 
struct  pheap
 A pairing heap. More...
 

Macros

#define PNODE_INIT
 The static initializer for pnode.
 
#define PHEAP_INIT
 The static initializer for pheap.
 
#define pnode_foreach(first, node)   pnode_foreach_(__LINE__, first, node)
 Iterates over each node in a pairing heap in unspecified order. More...
 
#define pheap_foreach(heap, node)   pnode_foreach (pheap_first(heap), node)
 Iterates over each node in a pairing heap in unspecified order. More...
 

Typedefs

typedef int pheap_cmp_t(const void *p1, const void *p2)
 The type of a comparison function suitable for use in a paring heap. More...
 

Functions

void pnode_init (struct pnode *node, const void *key)
 Initializes a node in a paring heap. More...
 
struct pnodepnode_next (const struct pnode *node)
 Returns a pointer to the next node (in unspecified order) in a pairing heap.
 
void pheap_init (struct pheap *heap, pheap_cmp_t *cmp)
 Initializes a pairing heap. More...
 
int pheap_empty (const struct pheap *heap)
 Returns 1 if the pairing heap is empty, and 0 if not.
 
size_t pheap_size (const struct pheap *heap)
 Returns the size (in number of nodes) of a pairing heap. More...
 
void pheap_insert (struct pheap *heap, struct pnode *node)
 Inserts a node into a pairing heap. More...
 
void pheap_remove (struct pheap *heap, struct pnode *node)
 Removes a node from a pairing heap. More...
 
struct pnodepheap_find (const struct pheap *heap, const void *key)
 Finds a node in a pairing heap. More...
 
int pheap_contains (const struct pheap *heap, const struct pnode *node)
 Checks if a node is part of a pairing heap. More...
 
struct pnodepheap_first (const struct pheap *heap)
 Returns a pointer to the first (minimum) node in a pairing heap. More...
 

Detailed Description

This header file is part of the utilities library; it contains the pairing heap declarations.

A pairing heap is a half-sorted tree structure suitable for a priority queue. Compared to a self-balancing binary tree, insertion and retrieval of the first (minimum) element is faster (O(1) vs. O(log(n))), while finding an arbitrary element is slower (O(n) vs. O(log(n))).

The pairing heap implemented here is generic and can be used for any kind of key-value pair; only (void) pointers to keys are stored. Upon initialization of the heap, the user is responsible for providing a suitable comparison function (pheap_cmp_t).

Author
J. S. Seldenthuis jseld.nosp@m.enth.nosp@m.uis@l.nosp@m.ely..nosp@m.com

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Definition in file pheap.h.

Macro Definition Documentation

◆ pnode_foreach

#define pnode_foreach (   first,
  node 
)    pnode_foreach_(__LINE__, first, node)

Iterates over each node in a pairing heap in unspecified order.

It is safe to remove the current node during the iteration. However, since pheap_remove() may change the order of the nodes, it is not guaranteed that all nodes will be visited.

Parameters
firsta pointer to the first node.
nodethe name of the pointer to the nodes. This variable is declared in the scope of the loop.
See also
pnode_next()

Definition at line 129 of file pheap.h.

◆ pheap_foreach

#define pheap_foreach (   heap,
  node 
)    pnode_foreach (pheap_first(heap), node)

Iterates over each node in a pairing heap in unspecified order.

See also
pnode_foreach(), pheap_first()

Definition at line 204 of file pheap.h.

Typedef Documentation

◆ pheap_cmp_t

typedef int pheap_cmp_t(const void *p1, const void *p2)

The type of a comparison function suitable for use in a paring heap.

p1 and p2 MUST be NULL or point to objects of the same type.

Returns
an integer greater than, equal to, or less than 0 if the object at p1 is greater than, equal to, or less than the object at p2.

Definition at line 84 of file pheap.h.

Function Documentation

◆ pnode_init()

void pnode_init ( struct pnode node,
const void *  key 
)
inline

Initializes a node in a paring heap.

Parameters
nodea pointer to the node to be initialized.
keya pointer to the key for this node. The key MUST NOT be modified while the node is part of a heap.

Definition at line 207 of file pheap.h.

◆ pheap_init()

void pheap_init ( struct pheap heap,
pheap_cmp_t cmp 
)
inline

Initializes a pairing heap.

Parameters
heapa pointer to the heap to be initialized.
cmpa pointer to the function used to compare two keys.

Definition at line 229 of file pheap.h.

◆ pheap_size()

size_t pheap_size ( const struct pheap heap)
inline

Returns the size (in number of nodes) of a pairing heap.

This is an O(1) operation.

Definition at line 246 of file pheap.h.

◆ pheap_insert()

void pheap_insert ( struct pheap heap,
struct pnode node 
)

Inserts a node into a pairing heap.

This is an O(1) operation. This function does not check whether a node with the same key already exists, or whether the node is already part of another heap. It is the responsibility of the user to ensure that the node is not part of the heap before calling this function.

See also
pheap_remove(), pheap_find()

Definition at line 35 of file pheap.c.

◆ pheap_remove()

void pheap_remove ( struct pheap heap,
struct pnode node 
)

Removes a node from a pairing heap.

This is an (amortized) O(log(n)) operation. It is the responsibility of the user to ensure that the node is part of the heap before calling this function.

See also
pheap_insert(), pheap_contains()

Definition at line 63 of file pheap.c.

◆ pheap_find()

struct pnode * pheap_find ( const struct pheap heap,
const void *  key 
)

Finds a node in a pairing heap.

This is an O(n) operation.

Returns
a pointer to the node if found, or NULL if not.
See also
pheap_insert()

Definition at line 96 of file pheap.c.

◆ pheap_contains()

int pheap_contains ( const struct pheap heap,
const struct pnode node 
)

Checks if a node is part of a pairing heap.

Returns
1 if the node was found in the heap, and 0 if not.

Definition at line 122 of file pheap.c.

◆ pheap_first()

struct pnode * pheap_first ( const struct pheap heap)
inline

Returns a pointer to the first (minimum) node in a pairing heap.

This is an O(1) operation.

Definition at line 254 of file pheap.h.