cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

rblist.c (2710B)

      1// SPDX-License-Identifier: GPL-2.0-only
      2/*
      3 * Based on strlist.c by:
      4 * (c) 2009 Arnaldo Carvalho de Melo <acme@redhat.com>
      5 */
      6
      7#include <errno.h>
      8#include <stdio.h>
      9#include <stdlib.h>
     10
     11#include "rblist.h"
     12
     13int rblist__add_node(struct rblist *rblist, const void *new_entry)
     14{
     15	struct rb_node **p = &rblist->entries.rb_root.rb_node;
     16	struct rb_node *parent = NULL, *new_node;
     17	bool leftmost = true;
     18
     19	while (*p != NULL) {
     20		int rc;
     21
     22		parent = *p;
     23
     24		rc = rblist->node_cmp(parent, new_entry);
     25		if (rc > 0)
     26			p = &(*p)->rb_left;
     27		else if (rc < 0) {
     28			p = &(*p)->rb_right;
     29			leftmost = false;
     30		}
     31		else
     32			return -EEXIST;
     33	}
     34
     35	new_node = rblist->node_new(rblist, new_entry);
     36	if (new_node == NULL)
     37		return -ENOMEM;
     38
     39	rb_link_node(new_node, parent, p);
     40	rb_insert_color_cached(new_node, &rblist->entries, leftmost);
     41	++rblist->nr_entries;
     42
     43	return 0;
     44}
     45
     46void rblist__remove_node(struct rblist *rblist, struct rb_node *rb_node)
     47{
     48	rb_erase_cached(rb_node, &rblist->entries);
     49	--rblist->nr_entries;
     50	rblist->node_delete(rblist, rb_node);
     51}
     52
     53static struct rb_node *__rblist__findnew(struct rblist *rblist,
     54					 const void *entry,
     55					 bool create)
     56{
     57	struct rb_node **p = &rblist->entries.rb_root.rb_node;
     58	struct rb_node *parent = NULL, *new_node = NULL;
     59	bool leftmost = true;
     60
     61	while (*p != NULL) {
     62		int rc;
     63
     64		parent = *p;
     65
     66		rc = rblist->node_cmp(parent, entry);
     67		if (rc > 0)
     68			p = &(*p)->rb_left;
     69		else if (rc < 0) {
     70			p = &(*p)->rb_right;
     71			leftmost = false;
     72		}
     73		else
     74			return parent;
     75	}
     76
     77	if (create) {
     78		new_node = rblist->node_new(rblist, entry);
     79		if (new_node) {
     80			rb_link_node(new_node, parent, p);
     81			rb_insert_color_cached(new_node,
     82					       &rblist->entries, leftmost);
     83			++rblist->nr_entries;
     84		}
     85	}
     86
     87	return new_node;
     88}
     89
     90struct rb_node *rblist__find(struct rblist *rblist, const void *entry)
     91{
     92	return __rblist__findnew(rblist, entry, false);
     93}
     94
     95struct rb_node *rblist__findnew(struct rblist *rblist, const void *entry)
     96{
     97	return __rblist__findnew(rblist, entry, true);
     98}
     99
    100void rblist__init(struct rblist *rblist)
    101{
    102	if (rblist != NULL) {
    103		rblist->entries	 = RB_ROOT_CACHED;
    104		rblist->nr_entries = 0;
    105	}
    106
    107	return;
    108}
    109
    110void rblist__exit(struct rblist *rblist)
    111{
    112	struct rb_node *pos, *next = rb_first_cached(&rblist->entries);
    113
    114	while (next) {
    115		pos = next;
    116		next = rb_next(pos);
    117		rblist__remove_node(rblist, pos);
    118	}
    119}
    120
    121void rblist__delete(struct rblist *rblist)
    122{
    123	if (rblist != NULL) {
    124		rblist__exit(rblist);
    125		free(rblist);
    126	}
    127}
    128
    129struct rb_node *rblist__entry(const struct rblist *rblist, unsigned int idx)
    130{
    131	struct rb_node *node;
    132
    133	for (node = rb_first_cached(&rblist->entries); node;
    134	     node = rb_next(node)) {
    135		if (!idx--)
    136			return node;
    137	}
    138
    139	return NULL;
    140}