Quelle interval_tree.c Sprache: C

// SPDX-License-Identifier: GPL-2.0-only
/*
* mm/interval_tree.c - interval tree for mapping->i_mmap
*
* Copyright (C) 2012, Michel Lespinasse <walken@google.com>
*/

#include <linux/mm.h>
#include <linux/fs.h>
#include <linux/rmap.h>
#include <linux/interval_tree_generic.h>

static inline unsigned long vma_start_pgoff(struct vm_area_struct *v)
{
return v->vm_pgoff;
}

static inline unsigned long vma_last_pgoff(struct vm_area_struct *v)
{
return v->vm_pgoff + vma_pages(v) - 1;
}

INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.rb,
       unsigned long, shared.rb_subtree_last,
       vma_start_pgoff, vma_last_pgoff, /* empty */, vma_interval_tree)

/* Insert node immediately after prev in the interval tree */
void vma_interval_tree_insert_after(struct vm_area_struct *node,
        struct vm_area_struct *prev,
        struct rb_root_cached *root)
{
struct rb_node **link;
struct vm_area_struct *parent;
unsigned long last = vma_last_pgoff(node);

VM_BUG_ON_VMA(vma_start_pgoff(node) != vma_start_pgoff(prev), node);

if (!prev->shared.rb.rb_right) {
  parent = prev;
  link = &prev->shared.rb.rb_right;
} else {
  parent = rb_entry(prev->shared.rb.rb_right,
      struct vm_area_struct, shared.rb);
  if (parent->shared.rb_subtree_last < last)
   parent->shared.rb_subtree_last = last;
  while (parent->shared.rb.rb_left) {
   parent = rb_entry(parent->shared.rb.rb_left,
    struct vm_area_struct, shared.rb);
   if (parent->shared.rb_subtree_last < last)
    parent->shared.rb_subtree_last = last;
  }
  link = &parent->shared.rb.rb_left;
}

node->shared.rb_subtree_last = last;
rb_link_node(&node->shared.rb, &parent->shared.rb, link);
rb_insert_augmented(&node->shared.rb, &root->rb_root,
       &vma_interval_tree_augment);
}

static inline unsigned long avc_start_pgoff(struct anon_vma_chain *avc)
{
return vma_start_pgoff(avc->vma);
}

static inline unsigned long avc_last_pgoff(struct anon_vma_chain *avc)
{
return vma_last_pgoff(avc->vma);
}

INTERVAL_TREE_DEFINE(struct anon_vma_chain, rb, unsigned long, rb_subtree_last,
       avc_start_pgoff, avc_last_pgoff,
       static inline, __anon_vma_interval_tree)

void anon_vma_interval_tree_insert(struct anon_vma_chain *node,
       struct rb_root_cached *root)
{
#ifdef CONFIG_DEBUG_VM_RB
node->cached_vma_start = avc_start_pgoff(node);
node->cached_vma_last = avc_last_pgoff(node);
#endif
__anon_vma_interval_tree_insert(node, root);
}

void anon_vma_interval_tree_remove(struct anon_vma_chain *node,
       struct rb_root_cached *root)
{
__anon_vma_interval_tree_remove(node, root);
}

struct anon_vma_chain *
anon_vma_interval_tree_iter_first(struct rb_root_cached *root,
      unsigned long first, unsigned long last)
{
return __anon_vma_interval_tree_iter_first(root, first, last);
}

struct anon_vma_chain *
anon_vma_interval_tree_iter_next(struct anon_vma_chain *node,
     unsigned long first, unsigned long last)
{
return __anon_vma_interval_tree_iter_next(node, first, last);
}

#ifdef CONFIG_DEBUG_VM_RB
void anon_vma_interval_tree_verify(struct anon_vma_chain *node)
{
WARN_ON_ONCE(node->cached_vma_start != avc_start_pgoff(node));
WARN_ON_ONCE(node->cached_vma_last != avc_last_pgoff(node));
}
#endif

quality98%

¤ Dauer der Verarbeitung: 0.16 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.