Home | History | Annotate | Line # | Download | only in linux 
      1 /*	$NetBSD: idr.h,v 1.11 2023/07/11 10:42:36 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/mutex.h>
     37 #include <sys/rbtree.h>
     38 
     39 #include <linux/gfp.h>
     40 
     41 /* XXX Stupid expedient algorithm should be replaced by something better.  */
     42 
     43 struct idr {
     44 	kmutex_t	idr_lock;
     45 	rb_tree_t	idr_tree;
     46 	int		idr_base;
     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_init_base		linux_idr_init_base
     57 #define	idr_is_empty		linux_idr_is_empty
     58 #define	idr_preload		linux_idr_preload
     59 #define	idr_preload_end		linux_idr_preload_end
     60 #define	idr_remove		linux_idr_remove
     61 #define	idr_replace		linux_idr_replace
     62 
     63 int	linux_idr_module_init(void);
     64 void	linux_idr_module_fini(void);
     65 
     66 void	idr_init(struct idr *);
     67 void	idr_init_base(struct idr *, int);
     68 void	idr_destroy(struct idr *);
     69 bool	idr_is_empty(struct idr *);
     70 void	*idr_find(struct idr *, int);
     71 void	*idr_get_next(struct idr *, int *);
     72 void	*idr_replace(struct idr *, void *, int);
     73 void	*idr_remove(struct idr *, int);
     74 void	idr_preload(gfp_t);
     75 int	idr_alloc(struct idr *, void *, int, int, gfp_t);
     76 void	idr_preload_end(void);
     77 int	idr_for_each(struct idr *, int (*)(int, void *, void *), void *);
     78 
     79 #define	idr_for_each_entry(IDR, ENTRY, ID)				      \
     80 	for ((ID) = 0; ((ENTRY) = idr_get_next((IDR), &(ID))) != NULL; (ID)++)
     81 
     82 struct ida {
     83 	struct idr	ida_idr;
     84 };
     85 
     86 static inline void
     87 ida_init(struct ida *ida)
     88 {
     89 
     90 	idr_init(&ida->ida_idr);
     91 }
     92 
     93 static inline void
     94 ida_destroy(struct ida *ida)
     95 {
     96 
     97 	idr_destroy(&ida->ida_idr);
     98 }
     99 
    100 static inline void
    101 ida_free(struct ida *ida, int id)
    102 {
    103 
    104 	idr_remove(&ida->ida_idr, id);
    105 }
    106 
    107 static inline int
    108 ida_simple_get(struct ida *ida, unsigned start, unsigned end, gfp_t gfp)
    109 {
    110 	int id;
    111 
    112 	KASSERT(start <= INT_MAX);
    113 	KASSERT(end <= INT_MAX);
    114 
    115 	idr_preload(gfp);
    116 	id = idr_alloc(&ida->ida_idr, NULL, start, end, gfp);
    117 	idr_preload_end();
    118 
    119 	return id;
    120 }
    121 
    122 static inline int
    123 ida_alloc_max(struct ida *ida, unsigned max, gfp_t gfp)
    124 {
    125 
    126 	return ida_simple_get(ida, 0, max + 1, gfp);
    127 }
    128 
    129 static inline void
    130 ida_simple_remove(struct ida *ida, unsigned int id)
    131 {
    132 
    133 	KASSERT((int)id >= 0);
    134 	ida_free(ida, id);
    135 }
    136 
    137 #endif  /* _LINUX_IDR_H_ */
    138