aliases.h

Go to the documentation of this file.

/*
 * Copyright (c) 2019 The University of Manchester
 *
 * 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
 *
 *     https://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.
 */
 
#ifndef __ALIASES_H__
#define __ALIASES_H__
 
#include <malloc_extras.h>
#include "../common/routing_table.h"
#include <debug.h>
 
/*****************************************************************************/
/* Vector-like object ********************************************************/
 
typedef struct _alias_element_t {  // Element of an alias list
    key_mask_t key_mask;
 
    uint32_t source;
} alias_element_t;
 
typedef struct _alias_list_t {
    unsigned int n_elements;
    unsigned int max_size;
    struct _alias_list_t *next;
    alias_element_t data;
} alias_list_t;
 
static alias_list_t* alias_list_new(unsigned int max_size) {
    // Compute how much memory to allocate
    unsigned int size =
            sizeof(alias_list_t) + (max_size - 1) * sizeof(alias_element_t);
 
    // Allocate and then fill in values
    alias_list_t *as = MALLOC(size);
    if (as == NULL){
        return NULL;
    }
 
    as->n_elements = 0;
    as->max_size = max_size;
    as->next = NULL;
    return as;
}
 
static bool alias_list_append(
        alias_list_t *as, key_mask_t val, uint32_t source) {
    if (as->n_elements < as->max_size) {
        (&as->data)[as->n_elements].key_mask = val;
        (&as->data)[as->n_elements].source = source;
        as->n_elements++;
        return true;
    }
    // Cannot append!
    return false;
}
 
static alias_element_t alias_list_get(alias_list_t *as, unsigned int i) {
    return (&as->data)[i];
}
 
static void alias_list_join(alias_list_t *a, alias_list_t *b) {
    // Traverse the list elements until we reach the end.
    while (a->next != NULL) {
        a = a->next;
    }
 
    // Store the next element
    a->next = b;
}
 
void alias_list_delete(alias_list_t *a) {
    if (a->next != NULL) {
        alias_list_delete(a->next);
        a->next = NULL;
    }
    FREE(a);
}
 
/*****************************************************************************/
 
 
/*****************************************************************************/
/* Map-like object ***********************************************************/
// Implemented as an AA tree
 
typedef union a_key_t {
    key_mask_t km;
 
    int64_t as_int;
} a_key_t;
 
typedef struct node_t {
    a_key_t key;
 
    alias_list_t *val;
 
    unsigned int level;
 
    struct node_t *left;
 
    struct node_t *right;
} node_t;
 
typedef struct aliases_t {
    node_t *root;
} aliases_t;
 
static aliases_t aliases_init(void) {
    aliases_t aliases = {NULL};
    return aliases;
}
 
static inline node_t *_aliases_find_node(node_t *node, a_key_t key) {
    while (node != NULL) {
        if (key.as_int == node->key.as_int) {
            // This is the requested item, return it
            return node;
        }
 
        if (key.as_int < node->key.as_int) {
            // Go left
            node = node->left;
        } else {
            // Go right
            node = node->right;
        }
    }
    return NULL;  // We didn't find the requested item
}
 
static inline alias_list_t *aliases_find(aliases_t *a, key_mask_t key) {
    // Search the tree
    node_t *node = _aliases_find_node(a->root, (a_key_t) key);
    if (node == NULL) {
        return NULL;
    }
    return node->val;
}
 
static inline bool aliases_contains(aliases_t *a, key_mask_t key) {
    return aliases_find(a, key) != NULL;
}
 
static inline node_t *_aliases_skew(node_t *n) {
    if (n == NULL) {
        return NULL;
    }
    if (n->left == NULL || n->level != n->left->level) {
        return n;
    }
 
    node_t *node_pointer = n->left;
    n->left = node_pointer->right;
    node_pointer->right = n;
    return node_pointer;
}
 
static inline node_t *_aliases_split(node_t *n) {
    if (n == NULL) {
        return NULL;
    }
    if (n->right == NULL || n->right->right == NULL
            || n->level != n->right->right->level) {
        return n;
    }
 
    node_t *r = n->right;
    n->right = r->left;
    r->left = n;
    r->level++;
    return r;
}
 
static bool _aliases_insert( // DO NOT INLINE; RECURSIVE!
        node_t *n, a_key_t key, alias_list_t *val) {
    if (n == NULL) {
        // If the node is NULL then create a new Node
        // Malloc room for the node
        n = MALLOC(sizeof(node_t));
        if (n == NULL) {
            log_error("failed to allocate memory for node");
            return false;
        }
 
        // Assign the values
        n->key = key;
        n->val = val;
        n->left = n->right = NULL;
        n->level = 1;
 
        return true;
    }
 
    if (key.as_int < n->key.as_int) {
        // Go left
        bool success = _aliases_insert(n->left, key, val);
        if (!success) {
            return false;
        }
    } else if (key.as_int > n->key.as_int) {
        // Go right
        bool success = _aliases_insert(n->right, key, val);
        if (!success) {
            return false;
        }
    } else {
        // Replace the value
        n->val = val;
    }
 
    // Rebalance the tree
    n = _aliases_skew(n);
    n = _aliases_split(n);
 
    return true;
}
 
 
static inline bool aliases_insert(
        aliases_t *a, key_mask_t key, alias_list_t *value) {
    // Insert into, and balance, the tree
 
   return _aliases_insert(a->root, (a_key_t) key, value);
}
 
 
static inline void aliases_remove(aliases_t *a, key_mask_t key) {
    // XXX This is a hack which removes the reference to the element in the
    // tree but doesn't remove the Node from the tree.
    node_t *n = _aliases_find_node(a->root, (a_key_t) key);
    if (n != NULL) {
        n->val = NULL;
    }
}
 
static void _aliases_clear(node_t *n) { // DO NOT INLINE; RECURSIVE!
    if (n == NULL) {
        return;
    }
 
    // Remove any children
    if (n->left != NULL) {
        _aliases_clear(n->left);
    }
    if (n->right != NULL) {
        _aliases_clear(n->right);
    }
 
    // Clear the value
    if (n->val != NULL) {
        alias_list_delete(n->val);
    }
 
    // Remove self
    FREE(n);
}
 
 
static inline void aliases_clear(aliases_t *a) {
    _aliases_clear(a->root);
}
 
/*****************************************************************************/
 
#endif  // __ALIASES_H__