Home | History | Annotate | Line # | Download | only in linux
idr.h revision 1.5 
      1 /*	$NetBSD: idr.h,v 1.5 2018/08/27 06:55:01 riastradh Exp $	*/
      2 
      3 /*-
      4  * Copyright (c) 2013 The NetBSD Foundation, Inc.
      5  * All rights reserved.
      6  *
      7  * This code is derived from software contributed to The NetBSD Foundation
      8  * by Taylor R. Campbell.
      9  *
     10  * Redistribution and use in source and binary forms, with or without
     11  * modification, are permitted provided that the following conditions
     12  * are met:
     13  * 1. Redistributions of source code must retain the above copyright
     14  *    notice, this list of conditions and the following disclaimer.
     15  * 2. Redistributions in binary form must reproduce the above copyright
     16  *    notice, this list of conditions and the following disclaimer in the
     17  *    documentation and/or other materials provided with the distribution.
     18  *
     19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     29  * POSSIBILITY OF SUCH DAMAGE.
     30  */
     31 
     32 #ifndef _LINUX_IDR_H_
     33 #define _LINUX_IDR_H_
     34 
     35 #include <sys/types.h>
     36 #include <sys/rwlock.h>
     37 #include <sys/rbtree.h>
     38 #include <sys/queue.h>
     39 
     40 #include <linux/gfp.h>
     41 
     42 /* XXX Stupid expedient algorithm should be replaced by something better.  */
     43 
     44 struct idr {
     45 	kmutex_t	idr_lock;
     46 	rb_tree_t	idr_tree;
     47 };
     48 
     49 /* XXX Make the nm output a little more greppable...  */
     50 #define	idr_alloc		linux_idr_alloc
     51 #define	idr_destroy		linux_idr_destroy
     52 #define	idr_find		linux_idr_find
     53 #define	idr_for_each		linux_idr_for_each
     54 #define	idr_get_next		linux_idr_get_next
     55 #define	idr_init		linux_idr_init
     56 #define	idr_is_empty		linux_idr_is_empty
     57 #define	idr_preload		linux_idr_preload
     58 #define	idr_preload_end		linux_idr_preload_end
     59 #define	idr_remove		linux_idr_remove
     60 #define	idr_replace		linux_idr_replace
     61 
     62 int	linux_idr_module_init(void);
     63 void	linux_idr_module_fini(void);
     64 
     65 void	idr_init(struct idr *);
     66 void	idr_destroy(struct idr *);
     67 bool	idr_is_empty(struct idr *);
     68 void	*idr_find(struct idr *, int);
     69 void	*idr_get_next(struct idr *, int *);
     70 void	*idr_replace(struct idr *, void *, int);
     71 void	idr_remove(struct idr *, int);
     72 void	idr_preload(gfp_t);
     73 int	idr_alloc(struct idr *, void *, int, int, gfp_t);
     74 void	idr_preload_end(void);
     75 int	idr_for_each(struct idr *, int (*)(int, void *, void *), void *);
     76 
     77 #define	idr_for_each_entry(IDR, ENTRY, ID)				      \
     78 	for ((ID) = 0; ((ENTRY) = idr_get_next((IDR), &(ID))) != NULL; (ID)++)
     79 
     80 struct ida {
     81 	struct idr	ida_idr;
     82 };
     83 
     84 static inline void
     85 ida_init(struct ida *ida)
     86 {
     87 
     88 	idr_init(&ida->ida_idr);
     89 }
     90 
     91 static inline void
     92 ida_destroy(struct ida *ida)
     93 {
     94 
     95 	idr_destroy(&ida->ida_idr);
     96 }
     97 
     98 static inline void
     99 ida_remove(struct ida *ida, int id)
    100 {
    101 
    102 	idr_remove(&ida->ida_idr, id);
    103 }
    104 
    105 static inline int
    106 ida_simple_get(struct ida *ida, unsigned start, unsigned end, gfp_t gfp)
    107 {
    108 	int id;
    109 
    110 	KASSERT(start <= INT_MAX);
    111 	KASSERT(end <= INT_MAX);
    112 
    113 	idr_preload(gfp);
    114 	id = idr_alloc(&ida->ida_idr, NULL, start, end, gfp);
    115 	idr_preload_end();
    116 
    117 	return id;
    118 }
    119 
    120 #endif  /* _LINUX_IDR_H_ */
    121