linux-imx

/*

 * Copyright (C) 2001 Momchil Velikov

 * Portions Copyright (C) 2001 Christoph Hellwig

 * Copyright (C) 2005 SGI, Christoph Lameter

 * Copyright (C) 2006 Nick Piggin

 * Copyright (C) 2012 Konstantin Khlebnikov

 * Copyright (C) 2016 Intel, Matthew Wilcox

 * Copyright (C) 2016 Intel, Ross Zwisler

 *

 * This program is free software; you can redistribute it and/or

 * modify it under the terms of the GNU General Public License as

 * published by the Free Software Foundation; either version 2, or (at

 * your option) any later version.

 *

 * This program is distributed in the hope that it will be useful, but

 * WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

 */

​

#include <linux/bitmap.h>

#include <linux/bitops.h>

#include <linux/bug.h>

#include <linux/cpu.h>

#include <linux/errno.h>

#include <linux/export.h>

#include <linux/idr.h>

#include <linux/init.h>

#include <linux/kernel.h>

#include <linux/kmemleak.h>

#include <linux/percpu.h>

#include <linux/preempt.h>      /* in_interrupt() */

#include <linux/radix-tree.h>

#include <linux/rcupdate.h>

#include <linux/slab.h>

#include <linux/string.h>

#include <linux/xarray.h>

​

​

/*

 * Radix tree node cache.

 */

struct kmem_cache *radix_tree_node_cachep;

​

/*

 * The radix tree is variable-height, so an insert operation not only has

 * to build the branch to its corresponding item, it also has to build the

 * branch to existing items if the size has to be increased (by

 * radix_tree_extend).

 *

 * The worst case is a zero height tree with just a single item at index 0,

 * and then inserting an item at index ULONG_MAX. This requires 2 new branches

 * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.

 * Hence:

 */

#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)

​

/*

 * The IDR does not have to be as high as the radix tree since it uses