Home | History | Annotate | Line # | Download | only in linux
idr.h revision 1.7 
      1 /*	$NetBSD: idr.h,v 1.7 2018/08/27 14:14:42 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/rbtree.h>
     37 
     38 #include <linux/gfp.h>
     39 
     40 /* XXX Stupid expedient algorithm should be replaced by something better.  */
     41 
     42 struct idr {
     43 	kmutex_t	idr_lock;
     44 	rb_tree_t	idr_tree;
     45 };
     46 
     47 /* XXX Make the nm output a little more greppable...  */
     48 #define	idr_alloc		linux_idr_alloc
     49 #define	idr_destroy		linux_idr_destroy
     50 #define	idr_find		linux_idr_find
     51 #define	idr_for_each		linux_idr_for_each
     52 #define	idr_get_next		linux_idr_get_next
     53 #define	idr_init		linux_idr_init
     54 #define	idr_is_empty		linux_idr_is_empty
     55 #define	idr_preload		linux_idr_preload
     56 #define	idr_preload_end		linux_idr_preload_end
     57 #define	idr_remove		linux_idr_remove
     58 #define	idr_replace		linux_idr_replace
     59 
     60 int	linux_idr_module_init(void);
     61 void	linux_idr_module_fini(void);
     62 
     63 void	idr_init(struct idr *);
     64 void	idr_destroy(struct idr *);
     65 bool	idr_is_empty(struct idr *);
     66 void	*idr_find(struct idr *, int);
     67 void	*idr_get_next(struct idr *, int *);
     68 void	*idr_replace(struct idr *, void *, int);
     69 void	idr_remove(struct idr *, int);
     70 void	idr_preload(gfp_t);
     71 int	idr_alloc(struct idr *, void *, int, int, gfp_t);
     72 void	idr_preload_end(void);
     73 int	idr_for_each(struct idr *, int (*)(int, void *, void *), void *);
     74 
     75 #define	idr_for_each_entry(IDR, ENTRY, ID)				      \
     76 	for ((ID) = 0; ((ENTRY) = idr_get_next((IDR), &(ID))) != NULL; (ID)++)
     77 
     78 struct ida {
     79 	struct idr	ida_idr;
     80 };
     81 
     82 static inline void
     83 ida_init(struct ida *ida)
     84 {
     85 
     86 	idr_init(&ida->ida_idr);
     87 }
     88 
     89 static inline void
     90 ida_destroy(struct ida *ida)
     91 {
     92 
     93 	idr_destroy(&ida->ida_idr);
     94 }
     95 
     96 static inline void
     97 ida_remove(struct ida *ida, int id)
     98 {
     99 
    100 	idr_remove(&ida->ida_idr, id);
    101 }
    102 
    103 static inline int
    104 ida_simple_get(struct ida *ida, unsigned start, unsigned end, gfp_t gfp)
    105 {
    106 	int id;
    107 
    108 	KASSERT(start <= INT_MAX);
    109 	KASSERT(end <= INT_MAX);
    110 
    111 	idr_preload(gfp);
    112 	id = idr_alloc(&ida->ida_idr, NULL, start, end, gfp);
    113 	idr_preload_end();
    114 
    115 	return id;
    116 }
    117 
    118 static inline void
    119 ida_simple_remove(struct ida *ida, unsigned int id)
    120 {
    121 
    122 	KASSERT((int)id >= 0);
    123 	ida_remove(ida, id);
    124 }
    125 
    126 #endif  /* _LINUX_IDR_H_ */
    127