<commit_before>/* Copyright (c) 2015, ENEA Software AB
 * Copyright (c) 2015, Nokia
 * All rights reserved.
 *
 * SPDX-License-Identifier:	BSD-3-Clause
 */

/** \file
 * \anchor rt_lookup
 *
 * Radix tree contains all the routing data for the simple executive.
 * Data has two types:
 * - MAC addresses
 * - Gateway addresses
 *
 * For a given address the first hit may be a gateway address, whose
 * MAC address is looked up using a second lookup.
 *
 */

#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include "ofpi_util.h"
#include "ofpi.h"
#include "odp.h"
#include "ofpi_rt_lookup.h"
#include "ofpi_log.h"

#define SHM_NAME_RT_LOOKUP	"OfpRtlookupShMem"

#define NUM_NODES		ROUTE4_NODES
#define NUM_NODES_6		ROUTE6_NODES

/*
 * Shared data
 */
struct ofp_rt_lookup_mem {
	struct ofp_rtl_node *global_stack[65];
	struct ofp_rtl_node node_list[NUM_NODES];
	struct ofp_rtl_tailq free_nodes;
	int nodes_allocated, max_nodes_allocated;

	struct ofp_rtl6_node *global_stack6[129];
	struct ofp_rtl6_node node_list6[NUM_NODES_6];
	struct ofp_rtl6_node *free_nodes6;
	int nodes_allocated6, max_nodes_allocated6;
};

/*
 * Data per core
 */
static __thread struct ofp_rt_lookup_mem *shm;

static void NODEFREE(struct ofp_rtl_node *node)
{
	node->left = shm->free_nodes.last;
	node->right = NULL;
	if (shm->free_nodes.last)
		shm->free_nodes.last->right = node;
	else
		shm->free_nodes.first = node;
	shm->free_nodes.last = node;
	shm->nodes_allocated--;
}

static struct ofp_rtl_node *NODEALLOC(void)
{
	struct ofp_rtl_node *p = shm->free_nodes.first;
	if (shm->free_nodes.first) {
		shm->free_nodes.first = shm->free_nodes.first->right;
		if (shm->free_nodes.first)
			shm->free_nodes.first->left = NULL;
		else
			shm->free_nodes.last = NULL;
		shm->nodes_allocated++;
		if (shm->nodes_allocated > shm->max_nodes_allocated)
			shm->max_nodes_allocated = shm->nodes_allocated;
	}
	return p;
}

static void NODEFREE6(struct ofp_rtl6_node *node)
{
	node->left = NULL;
	node->right = shm->free_nodes6;
	if (shm->free_nodes6) shm->free_nodes6->left = node;
	shm->free_nodes6 = node;
	shm->nodes_allocated6--;
}

static struct ofp_rtl6_node *NODEALLOC6(void)
{
	struct ofp_rtl6_node *p = shm->free_nodes6;
	if (shm->free_nodes6) {
		shm->free_nodes6->left = NULL;
		shm->free_nodes6 = shm->free_nodes6->right;
		shm->nodes_allocated6++;
		if (shm->nodes_allocated6 > shm->max_nodes_allocated6)
			shm->max_nodes_allocated6 = shm->nodes_allocated6;
	}
	return p;
}

int ofp_rtl_init(struct ofp_rtl_tree *tree)
{
	return ofp_rtl_root_init(tree, 0);
}

int ofp_rtl6_init(struct ofp_rtl6_tree *tree)
{
	tree->root = NODEALLOC6();
	if (!tree->root) {
		OFP_ERR("NODEALLOC6 failed");
		return -1;
	}

	tree->root->flags = 0;
	tree->root->left = NULL;
	tree->root->right = NULL;

	return 0;
}

int ofp_rtl_root_init(struct ofp_rtl_tree *tree, uint16_t vrf)
{
	tree->root = NODEALLOC();
	if (!tree->root) {
		OFP_ERR("NODEALLOC failed");
		return -1;
	}

	tree->root->flags = 0;
	tree->root->left = NULL;
	tree->root->right = NULL;
	tree->vrf = vrf;

	return 0;
}


/* __attribute__((optimize("O0"))) */
struct ofp_nh_entry *
ofp_rtl_insert(struct ofp_rtl_tree *tree, uint32_t addr_be,
			   uint32_t masklen, struct ofp_nh_entry *data)
{
	struct ofp_rtl_node  *node;
	struct ofp_rtl_node  *last = NULL;
	uint32_t              depth;
	uint32_t              mask = 0x80000000;
	uint32_t              addr = (odp_be_to_cpu_32(addr_be)) & ((~0)<<(32-masklen));

	depth = 0;
	node = tree->root;
	while (depth < masklen && node) {
		last = node;
		if (addr & mask) {
			node = node->right;
		} else {
			node = node->left;
		}
		depth++;
		mask >>= 1;
	}

	if (node) {
		node->data[0] = *data;
		node->flags = OFP_RTL_FLAGS_VALID_DATA;
		return NULL;
	}

	node = NODEALLOC();
	if (!node) {
		OFP_ERR("NODEALLOC failed");
		return data;
	}

	memset(node, 0, sizeof(*node));<commit_msg>Fix "left shift of negative value" warning.<commit_after>/* Copyright (c) 2015, ENEA Software AB
 * Copyright (c) 2015, Nokia
 * All rights reserved.
 *
 * SPDX-License-Identifier:	BSD-3-Clause
 */

/** \file
 * \anchor rt_lookup
 *
 * Radix tree contains all the routing data for the simple executive.
 * Data has two types:
 * - MAC addresses
 * - Gateway addresses
 *
 * For a given address the first hit may be a gateway address, whose
 * MAC address is looked up using a second lookup.
 *
 */

#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include "ofpi_util.h"
#include "ofpi.h"
#include "odp.h"
#include "ofpi_rt_lookup.h"
#include "ofpi_log.h"

#define SHM_NAME_RT_LOOKUP	"OfpRtlookupShMem"

#define NUM_NODES		ROUTE4_NODES
#define NUM_NODES_6		ROUTE6_NODES

/*
 * Shared data
 */
struct ofp_rt_lookup_mem {
	struct ofp_rtl_node *global_stack[65];
	struct ofp_rtl_node node_list[NUM_NODES];
	struct ofp_rtl_tailq free_nodes;
	int nodes_allocated, max_nodes_allocated;

	struct ofp_rtl6_node *global_stack6[129];
	struct ofp_rtl6_node node_list6[NUM_NODES_6];
	struct ofp_rtl6_node *free_nodes6;
	int nodes_allocated6, max_nodes_allocated6;
};

/*
 * Data per core
 */
static __thread struct ofp_rt_lookup_mem *shm;

static void NODEFREE(struct ofp_rtl_node *node)
{
	node->left = shm->free_nodes.last;
	node->right = NULL;
	if (shm->free_nodes.last)
		shm->free_nodes.last->right = node;
	else
		shm->free_nodes.first = node;
	shm->free_nodes.last = node;
	shm->nodes_allocated--;
}

static struct ofp_rtl_node *NODEALLOC(void)
{
	struct ofp_rtl_node *p = shm->free_nodes.first;
	if (shm->free_nodes.first) {
		shm->free_nodes.first = shm->free_nodes.first->right;
		if (shm->free_nodes.first)
			shm->free_nodes.first->left = NULL;
		else
			shm->free_nodes.last = NULL;
		shm->nodes_allocated++;
		if (shm->nodes_allocated > shm->max_nodes_allocated)
			shm->max_nodes_allocated = shm->nodes_allocated;
	}
	return p;
}

static void NODEFREE6(struct ofp_rtl6_node *node)
{
	node->left = NULL;
	node->right = shm->free_nodes6;
	if (shm->free_nodes6) shm->free_nodes6->left = node;
	shm->free_nodes6 = node;
	shm->nodes_allocated6--;
}

static struct ofp_rtl6_node *NODEALLOC6(void)
{
	struct ofp_rtl6_node *p = shm->free_nodes6;
	if (shm->free_nodes6) {
		shm->free_nodes6->left = NULL;
		shm->free_nodes6 = shm->free_nodes6->right;
		shm->nodes_allocated6++;
		if (shm->nodes_allocated6 > shm->max_nodes_allocated6)
			shm->max_nodes_allocated6 = shm->nodes_allocated6;
	}
	return p;
}

int ofp_rtl_init(struct ofp_rtl_tree *tree)
{
	return ofp_rtl_root_init(tree, 0);
}

int ofp_rtl6_init(struct ofp_rtl6_tree *tree)
{
	tree->root = NODEALLOC6();
	if (!tree->root) {
		OFP_ERR("NODEALLOC6 failed");
		return -1;
	}

	tree->root->flags = 0;
	tree->root->left = NULL;
	tree->root->right = NULL;

	return 0;
}

int ofp_rtl_root_init(struct ofp_rtl_tree *tree, uint16_t vrf)
{
	tree->root = NODEALLOC();
	if (!tree->root) {
		OFP_ERR("NODEALLOC failed");
		return -1;
	}

	tree->root->flags = 0;
	tree->root->left = NULL;
	tree->root->right = NULL;
	tree->vrf = vrf;

	return 0;
}


/* __attribute__((optimize("O0"))) */
struct ofp_nh_entry *
ofp_rtl_insert(struct ofp_rtl_tree *tree, uint32_t addr_be,
			   uint32_t masklen, struct ofp_nh_entry *data)
{
	struct ofp_rtl_node  *node;
	struct ofp_rtl_node  *last = NULL;
	uint32_t              depth;
	uint32_t              mask = 0x80000000;
	uint32_t              addr = (odp_be_to_cpu_32(addr_be)) & ((~0U)<<(32-masklen));

	depth = 0;
	node = tree->root;
	while (depth < masklen && node) {
		last = node;
		if (addr & mask) {
			node = node->right;
		} else {
			node = node->left;
		}
		depth++;
		mask >>= 1;
	}

	if (node) {
		node->data[0] = *data;
		node->flags = OFP_RTL_FLAGS_VALID_DATA;
		return NULL;
	}

	node = NODEALLOC();
	if (!node) {
		OFP_ERR("NODEALLOC failed");
		return data;
	}

	memset(node, 0, sizeof(*node));
{'fraction_non_alphanumeric': 0.13742126237305566, 'fraction_numerical': 0.022625016068903457, 'mean_word_length': 4.0519480519480515, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 147, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4470065', 'n_tokens_mistral': 3414, 'n_tokens_neox': 3197, 'n_words': 655}