Lely core libraries 2.3.4
bimap.h File Reference

This header file is part of the utilities library; it contains the bidirectional map declarations. More...

#include <lely/util/cmp.h>
#include <lely/util/rbtree.h>
#include <assert.h>
Include dependency graph for bimap.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  binode
 A node in a bidirectional map. More...
 
struct  bimap
 A bidirectional map. More...
 

Macros

#define binode_foreach_by_key(first, node)    _binode_foreach_by_key(first, node, __LINE__)
 Iterates over each node in a bidirectional map in ascending order by key. More...
 
#define binode_foreach_by_value(first, node)    _binode_foreach_by_value(first, node, __LINE__)
 Iterates over each node in a bidirectional map in ascending order by value. More...
 
#define bimap_foreach_by_key(map, node)    binode_foreach_by_key (bimap_first_by_key(map), node)
 Iterates over each node in a bidirectional map in ascending order by key. More...
 
#define bimap_foreach_by_value(map, node)    binode_foreach_by_value (bimap_first_by_value(map), node)
 Iterates over each node in a bidirectional map in ascending order by value. More...
 

Functions

void binode_init (struct binode *node, const void *key, const void *value)
 Initializes a node in a bidirectional map. More...
 
struct binodebinode_prev_by_key (const struct binode *node)
 Returns a pointer to the previous (in-order) node by key in a bidirectional map with respect to node. More...
 
struct binodebinode_next_by_key (const struct binode *node)
 Returns a pointer to the next (in-order) node by key in a bidirectional map with respect to node. More...
 
struct binodebinode_prev_by_value (const struct binode *node)
 Returns a pointer to the previous (in-order) node by value in a bidirectional map with respect to node. More...
 
struct binodebinode_next_by_value (const struct binode *node)
 Returns a pointer to the next (in-order) node by value in a bidirectional map with respect to node. More...
 
void bimap_init (struct bimap *map, cmp_t *key_cmp, cmp_t *value_cmp)
 Initializes a bidirectional map. More...
 
int bimap_empty (const struct bimap *map)
 Returns 1 if the bidirectional map is empty, and 0 if not.
 
size_t bimap_size (const struct bimap *map)
 Returns the size (in number of nodes) of a bidirectional map. More...
 
void bimap_insert (struct bimap *map, struct binode *node)
 Inserts a node into a bidirectional map. More...
 
void bimap_remove (struct bimap *map, struct binode *node)
 Removes a node from a bidirectional map. More...
 
struct binodebimap_find_by_key (const struct bimap *map, const void *key)
 Finds a node by key in a bidirectional map. More...
 
struct binodebimap_find_by_value (const struct bimap *map, const void *value)
 Finds a node by value in a bidirectional map. More...
 
struct binodebimap_first_by_key (const struct bimap *map)
 Returns a pointer to the first (leftmost) node by key in a bidirectional map. More...
 
struct binodebimap_last_by_key (const struct bimap *map)
 Returns a pointer to the last (rightmost) node by key in a bidirectional map. More...
 
struct binodebimap_first_by_value (const struct bimap *map)
 Returns a pointer to the first (leftmost) node by value in a bidirectional map. More...
 
struct binodebimap_last_by_value (const struct bimap *map)
 Returns a pointer to the last (rightmost) node by value in a bidirectional map. More...
 

Detailed Description

This header file is part of the utilities library; it contains the bidirectional map declarations.

The bidirectional map is implemented as a pair of red-black trees, one for lookups by key, the other for lookups by value. The implementation is generic and can be used for any kind of key-value pair. Only (void) pointers to keys and values are stored. Upon initialization of the map, the user is responsible for providing suitable comparison functions (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 bimap.h.

Macro Definition Documentation

◆ binode_foreach_by_key

#define binode_foreach_by_key (   first,
  node 
)     _binode_foreach_by_key(first, node, __LINE__)

Iterates over each node in a bidirectional map in ascending order by key.

It is safe to remove the current node during the iteration.

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
binode_next_by_key()

Definition at line 133 of file bimap.h.

◆ binode_foreach_by_value

#define binode_foreach_by_value (   first,
  node 
)     _binode_foreach_by_value(first, node, __LINE__)

Iterates over each node in a bidirectional map in ascending order by value.

It is safe to remove the current node during the iteration.

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
binode_next_by_value()

Definition at line 162 of file bimap.h.

◆ bimap_foreach_by_key

#define bimap_foreach_by_key (   map,
  node 
)     binode_foreach_by_key (bimap_first_by_key(map), node)

Iterates over each node in a bidirectional map in ascending order by key.

See also
binode_foreach_by_key(), bimap_first_by_key()

Definition at line 275 of file bimap.h.

◆ bimap_foreach_by_value

#define bimap_foreach_by_value (   map,
  node 
)     binode_foreach_by_value (bimap_first_by_value(map), node)

Iterates over each node in a bidirectional map in ascending order by value.

See also
binode_foreach_by_value(), bimap_first_by_value()

Definition at line 283 of file bimap.h.

Function Documentation

◆ binode_init()

void binode_init ( struct binode node,
const void *  key,
const void *  value 
)
inline

Initializes a node in a bidirectional map.

Parameters
nodea pointer to the node to be initialized.
keya pointer to the key of the node. The key MUST NOT be modified while the node is part of a map.
valuea pointer to the value of the node. The value MUST NOT be modified while the node is part of a map.

Definition at line 287 of file bimap.h.

◆ binode_prev_by_key()

struct binode * binode_prev_by_key ( const struct binode node)
inline

Returns a pointer to the previous (in-order) node by key in a bidirectional map with respect to node.

This is, at worst, an O(log(n)) operation.

See also
binode_next_by_key(), binode_prev_by_value()

Definition at line 296 of file bimap.h.

◆ binode_next_by_key()

struct binode * binode_next_by_key ( const struct binode node)
inline

Returns a pointer to the next (in-order) node by key in a bidirectional map with respect to node.

This is, at worst, an O(log(n)) operation. However, visiting all nodes in order is an O(n) operation, and therefore, on average, O(1) for each node.

See also
binode_prev_by_key(), binode_next_by_value()

Definition at line 305 of file bimap.h.

◆ binode_prev_by_value()

struct binode * binode_prev_by_value ( const struct binode node)
inline

Returns a pointer to the previous (in-order) node by value in a bidirectional map with respect to node.

This is, at worst, an O(log(n)) operation.

See also
binode_next_by_value(), binode_prev_by_key()

Definition at line 314 of file bimap.h.

◆ binode_next_by_value()

struct binode * binode_next_by_value ( const struct binode node)
inline

Returns a pointer to the next (in-order) node by value in a bidirectional map with respect to node.

This is, at worst, an O(log(n)) operation. However, visiting all nodes in order is an O(n) operation, and therefore, on average, O(1) for each node.

See also
binode_prev_by_value(), binode_next_by_key()

Definition at line 323 of file bimap.h.

◆ bimap_init()

void bimap_init ( struct bimap map,
cmp_t key_cmp,
cmp_t value_cmp 
)
inline

Initializes a bidirectional map.

Parameters
mapa pointer to the map to be initialized.
key_cmpa pointer to the function used to compare two keys.
value_cmpa pointer to the function used to compare two values.

Definition at line 332 of file bimap.h.

◆ bimap_size()

size_t bimap_size ( const struct bimap map)
inline

Returns the size (in number of nodes) of a bidirectional map.

This is an O(1) operation.

Definition at line 349 of file bimap.h.

◆ bimap_insert()

void bimap_insert ( struct bimap map,
struct binode node 
)
inline

Inserts a node into a bidirectional map.

This is an O(log(n)) operation. This function does not check whether a node with the same key or value already exists, or whether the node is already part of another map.

See also
bimap_remove(), bimap_find_by_key(), bimap_find_by_value()

Definition at line 357 of file bimap.h.

◆ bimap_remove()

void bimap_remove ( struct bimap map,
struct binode node 
)
inline

Removes a node from a bidirectional map.

This is an O(log(n)) operation.

See also
bimap_insert()

Definition at line 367 of file bimap.h.

◆ bimap_find_by_key()

struct binode * bimap_find_by_key ( const struct bimap map,
const void *  key 
)
inline

Finds a node by key in a bidirectional map.

This is an O(log(n)) operation.

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

Definition at line 377 of file bimap.h.

◆ bimap_find_by_value()

struct binode * bimap_find_by_value ( const struct bimap map,
const void *  value 
)
inline

Finds a node by value in a bidirectional map.

This is an O(log(n)) operation.

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

Definition at line 387 of file bimap.h.

◆ bimap_first_by_key()

struct binode * bimap_first_by_key ( const struct bimap map)
inline

Returns a pointer to the first (leftmost) node by key in a bidirectional map.

This is an O(log(n)) operation.

See also
bimap_last_by_key(), bimap_first_by_value()

Definition at line 397 of file bimap.h.

◆ bimap_last_by_key()

struct binode * bimap_last_by_key ( const struct bimap map)
inline

Returns a pointer to the last (rightmost) node by key in a bidirectional map.

This is an O(log(n)) operation.

See also
bimap_first_by_key(), bimap_last_by_value()

Definition at line 406 of file bimap.h.

◆ bimap_first_by_value()

struct binode * bimap_first_by_value ( const struct bimap map)
inline

Returns a pointer to the first (leftmost) node by value in a bidirectional map.

This is an O(log(n)) operation.

See also
bimap_last_by_value(), bimap_first_by_key()

Definition at line 415 of file bimap.h.

◆ bimap_last_by_value()

struct binode * bimap_last_by_value ( const struct bimap map)
inline

Returns a pointer to the last (rightmost) node by value in a bidirectional map.

This is an O(log(n)) operation.

See also
bimap_first_by_value(), bimap_last_by_key()

Definition at line 424 of file bimap.h.