ordered_covering.h File Reference

An ordered covering of routing table entries. More...

#include <malloc_extras.h>
#include <debug.h>
#include "aliases.h"
#include "bit_set.h"
#include "merge.h"
#include "../common/routing_table.h"

Go to the source code of this file.

Functions
static unsigned int	oc_get_insertion_point (const unsigned int generality)
	Get the index where the routing table entry resulting from a merge should be inserted.
static bool	oc_up_check (merge_t *merge, int min_goodness, volatile bool *stop_compressing, bool *changed)
	Remove from a merge any entries which would be covered by being existing entries if they were included in the given merge.
static bool	oc_down_check (merge_t *merge, int min_goodness, aliases_t *aliases, bool *failed_by_malloc, volatile bool *stop_compressing)
	Remove entries from a merge such that the merge would not cover existing entries positioned below the merge.
static bool	oc_get_best_merge (aliases_t *aliases, merge_t *best, bool *failed_by_malloc, volatile bool *stop_compressing)
	Get the best merge which can be applied to a routing table.
static bool	oc_merge_apply (merge_t *merge, aliases_t *aliases, bool *failed_by_malloc)
	Apply a merge to the table against which it is defined.
bool	minimise_run (int target_length, bool *failed_by_malloc, volatile bool *stop_compressing)
	Apply the ordered covering algorithm to a routing table.

Detailed Description

An ordered covering of routing table entries.

Definition in file ordered_covering.h.

Function Documentation

oc_get_insertion_point()

static unsigned int oc_get_insertion_point ( const unsigned int  generality )

static

Get the index where the routing table entry resulting from a merge should be inserted.

Parameters

[in]

generality

The number of least-significant bits masked out

Returns

The insertion point for this generality factor

Definition at line 39 of file ordered_covering.h.

oc_up_check()

static bool oc_up_check ( merge_t *  merge, int  min_goodness, volatile bool *  stop_compressing, bool *  changed  )

inlinestatic

Remove from a merge any entries which would be covered by being existing entries if they were included in the given merge.

Parameters

[in]	merge	The merge to consider
[in]	min_goodness	Minimum goodness factor for a merge to be performed
[in]	stop_compressing	Whether the compressor should stop; points to a variable set by interrupt
[out]	changed	Whether the merge drops below goodness level

Returns

Whether the method was successful in completing or not

Definition at line 94 of file ordered_covering.h.

oc_down_check()

static bool oc_down_check ( merge_t *  merge, int  min_goodness, aliases_t *  aliases, bool *  failed_by_malloc, volatile bool *  stop_compressing  )

static

Remove entries from a merge such that the merge would not cover existing entries positioned below the merge.

Parameters

[in]	merge	The merge to eventually apply
[in]	min_goodness	The minimum number of bits to mask out for removal to be considered
[in]	aliases	Describes what entries alias what other entries
[out]	failed_by_malloc	Flag saying if it failed due to running out of memory
[in]	stop_compressing	Variable saying whether the compressor should stop, set by interrupt

Returns

Whether it was successful or not

Definition at line 255 of file ordered_covering.h.

oc_get_best_merge()

static bool oc_get_best_merge ( aliases_t *  aliases, merge_t *  best, bool *  failed_by_malloc, volatile bool *  stop_compressing  )

inlinestatic

Get the best merge which can be applied to a routing table.

Parameters

[in]	aliases	Describes what entries alias what other entries
[in,out]	best	The best merge found
[out]	failed_by_malloc	Flag saying failed by memory exhaustion
[in]	stop_compressing	Variable saying if compression should stop; set by interrupt

Returns

Whether successful or not.

Definition at line 451 of file ordered_covering.h.

oc_merge_apply()

static bool oc_merge_apply ( merge_t *  merge, aliases_t *  aliases, bool *  failed_by_malloc  )

inlinestatic

Apply a merge to the table against which it is defined.

Parameters

[in]	merge	The merge to apply to the routing tables
[in]	aliases	Describes what entries alias what other entries
[out]	failed_by_malloc	Flag saying failed by memory exhaustion

Returns

Whether successful or not

Definition at line 630 of file ordered_covering.h.

minimise_run()

bool minimise_run	(	int	target_length,
		bool *	failed_by_malloc,
		volatile bool *	stop_compressing
	)

Apply the ordered covering algorithm to a routing table.

Minimise the table until either the table is shorter than the target length or no more merges are possible.

Parameters

[in]	target_length	The length to reach
[out]	failed_by_malloc	Flag stating that it failed due to malloc
[out]	stop_compressing	Variable saying if the compressor should stop and return false; set by interrupt DURING the run of this method!

Returns

Whether successful or not.

Definition at line 773 of file ordered_covering.h.