summaryrefslogtreecommitdiffstats
path: root/src/vnet
diff options
context:
space:
mode:
authorMarco Varlese <marco.varlese@suse.com>2017-11-09 15:16:20 +0100
committerDamjan Marion <dmarion.lists@gmail.com>2017-11-10 20:24:00 +0000
commitf616d10d04d5c444e20e617841a54cfb2c58d07d (patch)
tree5af3062476065673d67009bbf5fd76ba28eb99ac /src/vnet
parent6a6f4f7fe777dc77f8496fae1fc1075372ad16b6 (diff)
Allow Openssl 1.1.0
This patch addresses all the code changes required to VPP to support openssl 1.1.0 API. All the changes have been done so that VPP can still be built against current openssl API whilst forward-looking to version 1.1.0. Change-Id: I65e22c53c5decde7a15c7eb78a62951ee246b8dc Signed-off-by: Marco Varlese <marco.varlese@suse.com>
Diffstat (limited to 'src/vnet')
-rw-r--r--src/vnet/ipsec/esp.h24
-rw-r--r--src/vnet/ipsec/esp_decrypt.c4
-rw-r--r--src/vnet/ipsec/esp_encrypt.c4
-rw-r--r--src/vnet/ipsec/ikev2.c4
-rw-r--r--src/vnet/ipsec/ikev2_crypto.c135
5 files changed, 159 insertions, 12 deletions
diff --git a/src/vnet/ipsec/esp.h b/src/vnet/ipsec/esp.h
index bc67f9d0783..d9ab1d855a8 100644
--- a/src/vnet/ipsec/esp.h
+++ b/src/vnet/ipsec/esp.h
@@ -63,11 +63,23 @@ typedef struct
typedef struct
{
CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ EVP_CIPHER_CTX *encrypt_ctx;
+#else
EVP_CIPHER_CTX encrypt_ctx;
+#endif
CLIB_CACHE_LINE_ALIGN_MARK (cacheline1);
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ EVP_CIPHER_CTX *decrypt_ctx;
+#else
EVP_CIPHER_CTX decrypt_ctx;
+#endif
CLIB_CACHE_LINE_ALIGN_MARK (cacheline2);
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ HMAC_CTX *hmac_ctx;
+#else
HMAC_CTX hmac_ctx;
+#endif
ipsec_crypto_alg_t last_encrypt_alg;
ipsec_crypto_alg_t last_decrypt_alg;
ipsec_integ_alg_t last_integ_alg;
@@ -273,9 +285,15 @@ esp_init ()
for (thread_id = 0; thread_id < tm->n_vlib_mains - 1; thread_id++)
{
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ em->per_thread_data[thread_id].encrypt_ctx = EVP_CIPHER_CTX_new ();
+ em->per_thread_data[thread_id].decrypt_ctx = EVP_CIPHER_CTX_new ();
+ em->per_thread_data[thread_id].hmac_ctx = HMAC_CTX_new ();
+#else
EVP_CIPHER_CTX_init (&(em->per_thread_data[thread_id].encrypt_ctx));
EVP_CIPHER_CTX_init (&(em->per_thread_data[thread_id].decrypt_ctx));
HMAC_CTX_init (&(em->per_thread_data[thread_id].hmac_ctx));
+#endif
}
}
@@ -287,7 +305,11 @@ hmac_calc (ipsec_integ_alg_t alg,
{
esp_main_t *em = &esp_main;
u32 thread_index = vlib_get_thread_index ();
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ HMAC_CTX *ctx = em->per_thread_data[thread_index].hmac_ctx;
+#else
HMAC_CTX *ctx = &(em->per_thread_data[thread_index].hmac_ctx);
+#endif
const EVP_MD *md = NULL;
unsigned int len;
@@ -302,7 +324,7 @@ hmac_calc (ipsec_integ_alg_t alg,
em->per_thread_data[thread_index].last_integ_alg = alg;
}
- HMAC_Init (ctx, key, key_len, md);
+ HMAC_Init_ex (ctx, key, key_len, md, NULL);
HMAC_Update (ctx, data, data_len);
diff --git a/src/vnet/ipsec/esp_decrypt.c b/src/vnet/ipsec/esp_decrypt.c
index de4cc6dd4dd..81ebbe55301 100644
--- a/src/vnet/ipsec/esp_decrypt.c
+++ b/src/vnet/ipsec/esp_decrypt.c
@@ -86,7 +86,11 @@ esp_decrypt_aes_cbc (ipsec_crypto_alg_t alg,
{
esp_main_t *em = &esp_main;
u32 thread_index = vlib_get_thread_index ();
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ EVP_CIPHER_CTX *ctx = em->per_thread_data[thread_index].decrypt_ctx;
+#else
EVP_CIPHER_CTX *ctx = &(em->per_thread_data[thread_index].decrypt_ctx);
+#endif
const EVP_CIPHER *cipher = NULL;
int out_len;
diff --git a/src/vnet/ipsec/esp_encrypt.c b/src/vnet/ipsec/esp_encrypt.c
index b6ee25808b6..7bf1256acca 100644
--- a/src/vnet/ipsec/esp_encrypt.c
+++ b/src/vnet/ipsec/esp_encrypt.c
@@ -90,7 +90,11 @@ esp_encrypt_aes_cbc (ipsec_crypto_alg_t alg,
{
esp_main_t *em = &esp_main;
u32 thread_index = vlib_get_thread_index ();
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ EVP_CIPHER_CTX *ctx = em->per_thread_data[thread_index].encrypt_ctx;
+#else
EVP_CIPHER_CTX *ctx = &(em->per_thread_data[thread_index].encrypt_ctx);
+#endif
const EVP_CIPHER *cipher = NULL;
int out_len;
diff --git a/src/vnet/ipsec/ikev2.c b/src/vnet/ipsec/ikev2.c
index 49bae17f730..34ab87c3e56 100644
--- a/src/vnet/ipsec/ikev2.c
+++ b/src/vnet/ipsec/ikev2.c
@@ -3030,7 +3030,11 @@ ikev2_initiate_sa_init (vlib_main_t * vm, u8 * name)
sa.i_auth.method = p->auth.method;
sa.i_auth.hex = p->auth.hex;
sa.i_auth.data = vec_dup (p->auth.data);
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ clib_memcpy (sa.i_auth.key, p->auth.key, EVP_PKEY_size (p->auth.key));
+#else
sa.i_auth.key = vec_dup (p->auth.key);
+#endif
vec_add (sa.childs[0].tsi, &p->loc_ts, 1);
vec_add (sa.childs[0].tsr, &p->rem_ts, 1);
diff --git a/src/vnet/ipsec/ikev2_crypto.c b/src/vnet/ipsec/ikev2_crypto.c
index ca56158f898..32e687e37c0 100644
--- a/src/vnet/ipsec/ikev2_crypto.c
+++ b/src/vnet/ipsec/ikev2_crypto.c
@@ -25,6 +25,7 @@
#include <openssl/x509.h>
#include <openssl/pem.h>
#include <openssl/bn.h>
+#include <openssl/dh.h>
/* from RFC7296 */
static const char modp_dh_768_prime[] =
@@ -255,17 +256,27 @@ static const char modp_dh_2048_256_generator[] =
v8 *
ikev2_calc_prf (ikev2_sa_transform_t * tr, v8 * key, v8 * data)
{
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ HMAC_CTX *ctx;
+#else
HMAC_CTX ctx;
+#endif
v8 *prf;
unsigned int len = 0;
prf = vec_new (u8, tr->key_trunc);
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ ctx = HMAC_CTX_new ();
+ HMAC_Init_ex (ctx, key, vec_len (key), tr->md, NULL);
+ HMAC_Update (ctx, data, vec_len (data));
+ HMAC_Final (ctx, prf, &len);
+#else
HMAC_CTX_init (&ctx);
HMAC_Init_ex (&ctx, key, vec_len (key), tr->md, NULL);
HMAC_Update (&ctx, data, vec_len (data));
HMAC_Final (&ctx, prf, &len);
HMAC_CTX_cleanup (&ctx);
-
+#endif
ASSERT (len == tr->key_trunc);
return prf;
@@ -317,7 +328,11 @@ v8 *
ikev2_calc_integr (ikev2_sa_transform_t * tr, v8 * key, u8 * data, int len)
{
v8 *r;
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ HMAC_CTX *hctx;
+#else
HMAC_CTX hctx;
+#endif
unsigned int l;
ASSERT (tr->type == IKEV2_TRANSFORM_TYPE_INTEG);
@@ -325,11 +340,18 @@ ikev2_calc_integr (ikev2_sa_transform_t * tr, v8 * key, u8 * data, int len)
r = vec_new (u8, tr->key_len);
/* verify integrity of data */
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ hctx = HMAC_CTX_new ();
+ HMAC_Init_ex (hctx, key, vec_len (key), tr->md, NULL);
+ HMAC_Update (hctx, (const u8 *) data, len);
+ HMAC_Final (hctx, r, &l);
+#else
HMAC_CTX_init (&hctx);
- HMAC_Init (&hctx, key, vec_len (key), tr->md);
+ HMAC_Init_ex (&hctx, key, vec_len (key), tr->md, NULL);
HMAC_Update (&hctx, (const u8 *) data, len);
HMAC_Final (&hctx, r, &l);
HMAC_CTX_cleanup (&hctx);
+#endif
ASSERT (l == tr->key_len);
@@ -339,7 +361,11 @@ ikev2_calc_integr (ikev2_sa_transform_t * tr, v8 * key, u8 * data, int len)
v8 *
ikev2_decrypt_data (ikev2_sa_t * sa, u8 * data, int len)
{
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ EVP_CIPHER_CTX *ctx;
+#else
EVP_CIPHER_CTX ctx;
+#endif
v8 *r;
int out_len = 0, block_size;
ikev2_sa_transform_t *tr_encr;
@@ -356,23 +382,40 @@ ikev2_decrypt_data (ikev2_sa_t * sa, u8 * data, int len)
return 0;
}
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ ctx = EVP_CIPHER_CTX_new ();
+#else
EVP_CIPHER_CTX_init (&ctx);
+#endif
+
r = vec_new (u8, len - block_size);
+
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ EVP_DecryptInit_ex (ctx, tr_encr->cipher, NULL, key, data);
+ EVP_DecryptUpdate (ctx, r, &out_len, data + block_size, len - block_size);
+ EVP_DecryptFinal_ex (ctx, r + out_len, &out_len);
+#else
EVP_DecryptInit_ex (&ctx, tr_encr->cipher, NULL, key, data);
EVP_DecryptUpdate (&ctx, r, &out_len, data + block_size, len - block_size);
EVP_DecryptFinal_ex (&ctx, r + out_len, &out_len);
-
+#endif
/* remove padding */
_vec_len (r) -= r[vec_len (r) - 1] + 1;
+#if OPENSSL_VERSION_NUMBER < 0x10100000L
EVP_CIPHER_CTX_cleanup (&ctx);
+#endif
return r;
}
int
ikev2_encrypt_data (ikev2_sa_t * sa, v8 * src, u8 * dst)
{
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ EVP_CIPHER_CTX *ctx;
+#else
EVP_CIPHER_CTX ctx;
+#endif
int out_len;
int bs;
ikev2_sa_transform_t *tr_encr;
@@ -385,12 +428,16 @@ ikev2_encrypt_data (ikev2_sa_t * sa, v8 * src, u8 * dst)
/* generate IV */
RAND_bytes (dst, bs);
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ ctx = EVP_CIPHER_CTX_new ();
+ EVP_EncryptInit_ex (ctx, tr_encr->cipher, NULL, key, dst /* dst */ );
+ EVP_EncryptUpdate (ctx, dst + bs, &out_len, src, vec_len (src));
+#else
EVP_CIPHER_CTX_init (&ctx);
-
EVP_EncryptInit_ex (&ctx, tr_encr->cipher, NULL, key, dst /* dst */ );
EVP_EncryptUpdate (&ctx, dst + bs, &out_len, src, vec_len (src));
-
EVP_CIPHER_CTX_cleanup (&ctx);
+#endif
ASSERT (vec_len (src) == out_len);
@@ -401,30 +448,54 @@ void
ikev2_generate_dh (ikev2_sa_t * sa, ikev2_sa_transform_t * t)
{
int r;
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ BIGNUM *p = BN_new ();
+ BIGNUM *q = BN_new ();
+ BIGNUM *g = BN_new ();
+ BIGNUM *pub_key = BN_new ();
+ BIGNUM *priv_key = BN_new ();
+#endif
if (t->dh_group == IKEV2_DH_GROUP_MODP)
{
DH *dh = DH_new ();
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ BN_hex2bn (&p, t->dh_p);
+ BN_hex2bn (&g, t->dh_g);
+ DH_set0_pqg (dh, p, q, g);
+#else
BN_hex2bn (&dh->p, t->dh_p);
BN_hex2bn (&dh->g, t->dh_g);
+#endif
DH_generate_key (dh);
if (sa->is_initiator)
{
sa->i_dh_data = vec_new (u8, t->key_len);
+ sa->dh_private_key = vec_new (u8, t->key_len);
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ r = BN_bn2bin (pub_key, sa->i_dh_data);
+ ASSERT (r == t->key_len);
+ r = BN_bn2bin (priv_key, sa->dh_private_key);
+ DH_set0_key (dh, pub_key, priv_key);
+#else
r = BN_bn2bin (dh->pub_key, sa->i_dh_data);
ASSERT (r == t->key_len);
-
- sa->dh_private_key = vec_new (u8, t->key_len);
r = BN_bn2bin (dh->priv_key, sa->dh_private_key);
ASSERT (r == t->key_len);
-
+#endif
}
else
{
sa->r_dh_data = vec_new (u8, t->key_len);
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ r = BN_bn2bin (pub_key, sa->i_dh_data);
+ ASSERT (r == t->key_len);
+ DH_set0_key (dh, pub_key, NULL);
+#else
r = BN_bn2bin (dh->pub_key, sa->r_dh_data);
ASSERT (r == t->key_len);
+#endif
BIGNUM *ex;
sa->dh_shared_key = vec_new (u8, t->key_len);
ex = BN_bin2bn (sa->i_dh_data, vec_len (sa->i_dh_data), NULL);
@@ -509,15 +580,31 @@ void
ikev2_complete_dh (ikev2_sa_t * sa, ikev2_sa_transform_t * t)
{
int r;
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ BIGNUM *p = BN_new ();
+ BIGNUM *q = BN_new ();
+ BIGNUM *g = BN_new ();
+ BIGNUM *priv_key = BN_new ();
+#endif
if (t->dh_group == IKEV2_DH_GROUP_MODP)
{
DH *dh = DH_new ();
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ BN_hex2bn (&p, t->dh_p);
+ BN_hex2bn (&g, t->dh_g);
+ DH_set0_pqg (dh, p, q, g);
+
+ priv_key =
+ BN_bin2bn (sa->dh_private_key, vec_len (sa->dh_private_key), NULL);
+ DH_set0_key (dh, NULL, priv_key);
+#else
BN_hex2bn (&dh->p, t->dh_p);
BN_hex2bn (&dh->g, t->dh_g);
+
dh->priv_key =
BN_bin2bn (sa->dh_private_key, vec_len (sa->dh_private_key), NULL);
-
+#endif
BIGNUM *ex;
sa->dh_shared_key = vec_new (u8, t->key_len);
ex = BN_bin2bn (sa->r_dh_data, vec_len (sa->r_dh_data), NULL);
@@ -582,21 +669,47 @@ ikev2_complete_dh (ikev2_sa_t * sa, ikev2_sa_transform_t * t)
int
ikev2_verify_sign (EVP_PKEY * pkey, u8 * sigbuf, u8 * data)
{
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ EVP_MD_CTX *md_ctx = EVP_MD_CTX_new ();
+#else
EVP_MD_CTX md_ctx;
+#endif
- EVP_VerifyInit (&md_ctx, EVP_sha1 ());
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ EVP_VerifyInit (md_ctx, EVP_sha1 ());
+ EVP_VerifyUpdate (md_ctx, data, vec_len (data));
+#else
+ EVP_VerifyInit_ex (&md_ctx, EVP_sha1 (), NULL);
EVP_VerifyUpdate (&md_ctx, data, vec_len (data));
+#endif
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ return EVP_VerifyFinal (md_ctx, sigbuf, vec_len (sigbuf), pkey);
+#else
return EVP_VerifyFinal (&md_ctx, sigbuf, vec_len (sigbuf), pkey);
+#endif
}
u8 *
ikev2_calc_sign (EVP_PKEY * pkey, u8 * data)
{
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ EVP_MD_CTX *md_ctx = EVP_MD_CTX_new ();
+#else
EVP_MD_CTX md_ctx;
+#endif
unsigned int sig_len = 0;
u8 *sign;
+#if OPENSSL_VERSION_NUMBER >= 0x10100000L
+ EVP_SignInit (md_ctx, EVP_sha1 ());
+ EVP_SignUpdate (md_ctx, data, vec_len (data));
+ /* get sign len */
+ EVP_SignFinal (md_ctx, NULL, &sig_len, pkey);
+ sign = vec_new (u8, sig_len);
+ /* calc sign */
+ EVP_SignFinal (md_ctx, sign, &sig_len, pkey);
+#else
EVP_SignInit (&md_ctx, EVP_sha1 ());
EVP_SignUpdate (&md_ctx, data, vec_len (data));
/* get sign len */
@@ -604,7 +717,7 @@ ikev2_calc_sign (EVP_PKEY * pkey, u8 * data)
sign = vec_new (u8, sig_len);
/* calc sign */
EVP_SignFinal (&md_ctx, sign, &sig_len, pkey);
-
+#endif
return sign;
}
, f->min_root); ASSERT (n->key >= m->key); /* Min root must have no parent. */ if (ni == f->min_root) ASSERT (n->parent == ~0); /* Check sibling linkages. */ if (n->next_sibling == ~0) ASSERT (n->prev_sibling == ~0); else if (n->prev_sibling == ~0) ASSERT (n->next_sibling == ~0); else { fheap_node_t *prev, *next; u32 si = n->next_sibling, si_start = si; do { m = vec_elt_at_index (f->nodes, si); prev = vec_elt_at_index (f->nodes, m->prev_sibling); next = vec_elt_at_index (f->nodes, m->next_sibling); ASSERT (prev->next_sibling == si); ASSERT (next->prev_sibling == si); si = m->next_sibling; } while (si != si_start); } /* Loop through all siblings. */ { u32 n_siblings = 0; foreach_fheap_node_sibling (f, si, n->next_sibling, ( { m = vec_elt_at_index (f->nodes, si); /* All siblings must have same parent. */ ASSERT (m->parent == n-> parent); n_siblings += 1;} )); /* Either parent is non-empty or there are siblings present. */ if (n->parent == ~0 && ni != f->min_root) ASSERT (n_siblings > 0); } /* Loop through all children. */ { u32 found_first_child = n->first_child == ~0; u32 n_children = 0; foreach_fheap_node_sibling (f, si, n->first_child, ( { m = vec_elt_at_index (f->nodes, si); /* Children must have larger keys than their parent. */ ASSERT (m->key >= n->key); if (!found_first_child) found_first_child = si == n->first_child; n_children += 1;} )); /* Check that first child is present on list. */ ASSERT (found_first_child); /* Make sure rank is correct. */ ASSERT (n->rank == n_children); } } /* Increment serial number for each successful validate. Failure can be used as condition for gdb breakpoints. */ f->validate_serial++; } always_inline void fheap_node_add_sibling (fheap_t * f, u32 ni, u32 ni_to_add) { fheap_node_t *n = vec_elt_at_index (f->nodes, ni); fheap_node_t *n_to_add = vec_elt_at_index (f->nodes, ni_to_add); fheap_node_t *n_next = fheap_get_node (f, n->next_sibling); fheap_node_t *parent; /* Empty list? */ if (n->next_sibling == ~0) { ASSERT (n->prev_sibling == ~0); n->next_sibling = n->prev_sibling = ni_to_add; n_to_add->next_sibling = n_to_add->prev_sibling = ni; } else { /* Add node after existing node. */ n_to_add->prev_sibling = ni; n_to_add->next_sibling = n->next_sibling; n->next_sibling = ni_to_add; n_next->prev_sibling = ni_to_add; } n_to_add->parent = n->parent; parent = fheap_get_node (f, n->parent); if (parent) parent->rank += 1; } void fheap_add (fheap_t * f, u32 ni, u32 key) { fheap_node_t *r, *n; u32 ri; n = vec_elt_at_index (f->nodes, ni); clib_memset (n, 0, sizeof (n[0])); n->parent = n->first_child = n->next_sibling = n->prev_sibling = ~0; n->key = key; r = fheap_get_root (f); ri = f->min_root; if (!r) { /* No root? Add node as new root. */ f->min_root = ni; } else { /* Add node as sibling of current root. */ fheap_node_add_sibling (f, ri, ni); /* New node may become new root. */ if (r->key > n->key) f->min_root = ni; } fheap_validate (f); } always_inline u32 fheap_node_remove_internal (fheap_t * f, u32 ni, u32 invalidate) { fheap_node_t *n = vec_elt_at_index (f->nodes, ni); u32 prev_ni = n->prev_sibling; u32 next_ni = n->next_sibling; u32 list_has_single_element = prev_ni == ni; fheap_node_t *prev = fheap_get_node (f, prev_ni); fheap_node_t *next = fheap_get_node (f, next_ni); fheap_node_t *p = fheap_get_node (f, n->parent); if (p) { ASSERT (p->rank > 0); p->rank -= 1; p->first_child = list_has_single_element ? ~0 : next_ni; } if (prev) { ASSERT (prev->next_sibling == ni); prev->next_sibling = next_ni; } if (next) { ASSERT (next->prev_sibling == ni); next->prev_sibling = prev_ni; } n->prev_sibling = n->next_sibling = ni; n->parent = ~0; n->is_valid = invalidate == 0; return list_has_single_element ? ~0 : next_ni; } always_inline u32 fheap_node_remove (fheap_t * f, u32 ni) { return fheap_node_remove_internal (f, ni, /* invalidate */ 0); } always_inline u32 fheap_node_remove_and_invalidate (fheap_t * f, u32 ni) { return fheap_node_remove_internal (f, ni, /* invalidate */ 1); } static void fheap_link_root (fheap_t * f, u32 ni) { fheap_node_t *n = vec_elt_at_index (f->nodes, ni); fheap_node_t *r, *lo, *hi; u32 ri, lo_i, hi_i, k; while (1) { k = n->rank; vec_validate_init_empty (f->root_list_by_rank, k, ~0); ri = f->root_list_by_rank[k]; r = fheap_get_node (f, ri); if (!r) { f->root_list_by_rank[k] = ni; return; } f->root_list_by_rank[k] = ~0; /* Sort n/r into lo/hi by their keys. */ lo = r, lo_i = ri; hi = n, hi_i = ni; if (hi->key < lo->key) { u32 ti; fheap_node_t *tn; ti = lo_i, tn = lo; lo = hi, lo_i = hi_i; hi = tn, hi_i = ti; } /* Remove larger key. */ fheap_node_remove (f, hi_i); /* Add larger key as child of smaller one. */ if (lo->first_child == ~0) { hi->parent = lo_i; lo->first_child = hi_i; lo->rank = 1; } else fheap_node_add_sibling (f, lo->first_child, hi_i); /* Following Fredman & Trajan: "When making a root node X a child of another node in a linking step, we unmark X". */ hi->is_marked = 0; ni = lo_i; n = lo; } } u32 fheap_del_min (fheap_t * f, u32 * min_key) { fheap_node_t *r = fheap_get_root (f); u32 to_delete_min_ri = f->min_root; u32 ri, ni; /* Empty heap? */ if (!r) return ~0; /* Root's children become siblings. Call this step a; see below. */ if (r->first_child != ~0) { u32 ci, cni, rni; fheap_node_t *c, *cn, *rn; /* Splice child & root circular lists together. */ ci = r->first_child; c = vec_elt_at_index (f->nodes, ci); cni = c->next_sibling; rni = r->next_sibling; cn = vec_elt_at_index (f->nodes, cni); rn = vec_elt_at_index (f->nodes, rni); r->next_sibling = cni; c->next_sibling = rni; cn->prev_sibling = to_delete_min_ri; rn->prev_sibling = ci; } /* Remove min root. */ ri = fheap_node_remove_and_invalidate (f, to_delete_min_ri); /* Find new min root from among siblings including the ones we've just added. */ f->min_root = ~0; if (ri != ~0) { u32 ri_last, ri_next, i, min_ds; r = fheap_get_node (f, ri); ri_last = r->prev_sibling; while (1) { /* Step a above can put children (with r->parent != ~0) on root list. */ r->parent = ~0; ri_next = r->next_sibling; fheap_link_root (f, ri); if (ri == ri_last) break; ri = ri_next; r = fheap_get_node (f, ri); } min_ds = ~0; vec_foreach_index (i, f->root_list_by_rank) { ni = f->root_list_by_rank[i]; if (ni == ~0) continue; f->root_list_by_rank[i] = ~0; r = fheap_get_node (f, ni); if (r->key < min_ds) { f->min_root = ni; min_ds = r->key; ASSERT (r->parent == ~0); } } } /* Return deleted min root. */ r = vec_elt_at_index (f->nodes, to_delete_min_ri); if (min_key) *min_key = r->key; fheap_validate (f); return to_delete_min_ri; } static void fheap_mark_parent (fheap_t * f, u32 pi) { fheap_node_t *p = vec_elt_at_index (f->nodes, pi); /* Parent is a root: do nothing. */ if (p->parent == ~0) return; /* If not marked, mark it. */ if (!p->is_marked) { p->is_marked = 1; return; } /* Its a previously marked, non-root parent. Cut edge to its parent and add to root list. */ fheap_node_remove (f, pi); fheap_node_add_sibling (f, f->min_root, pi); /* Unmark it since its now a root node. */ p->is_marked = 0; /* "Cascading cuts": check parent. */ if (p->parent != ~0) fheap_mark_parent (f, p->parent); } /* Set key to new smaller value. */ void fheap_decrease_key (fheap_t * f, u32 ni, u32 new_key) { fheap_node_t *n = vec_elt_at_index (f->nodes, ni); fheap_node_t *r = fheap_get_root (f); n->key = new_key; if (n->parent != ~0) { fheap_mark_parent (f, n->parent); /* Remove node and add to root list. */ fheap_node_remove (f, ni); fheap_node_add_sibling (f, f->min_root, ni); } if (n->key < r->key) f->min_root = ni; fheap_validate (f); } void fheap_del (fheap_t * f, u32 ni) { fheap_node_t *n; n = vec_elt_at_index (f->nodes, ni); if (n->parent == ~0) { ASSERT (ni == f->min_root); fheap_del_min (f, 0); } else { u32 ci; fheap_mark_parent (f, n->parent); /* Add children to root list. */ foreach_fheap_node_sibling (f, ci, n->first_child, ( { fheap_node_remove (f, ci); fheap_node_add_sibling (f, f->min_root, ci);} )); fheap_node_remove_and_invalidate (f, ni); } fheap_validate (f); } /* * fd.io coding-style-patch-verification: ON * * Local Variables: * eval: (c-set-style "gnu") * End: */