lib/util/idtree_random.c

   1 /*
   2    Unix SMB/CIFS implementation.
   3
   4    very efficient functions to manage mapping a id (such as a fnum) to
   5    a pointer. This is used for fnum and search id allocation.
   6
   7    Copyright (C) Andrew Tridgell 2004
   8
   9    This code is derived from lib/idr.c in the 2.6 Linux kernel, which was
  10    written by Jim Houston jim.houston@ccur.com, and is
  11    Copyright (C) 2002 by Concurrent Computer Corporation
  12
  13    This program is free software; you can redistribute it and/or modify
  14    it under the terms of the GNU General Public License as published by
  15    the Free Software Foundation; either version 2 of the License, or
  16    (at your option) any later version.
  17
  18    This program is distributed in the hope that it will be useful,
  19    but WITHOUT ANY WARRANTY; without even the implied warranty of
  20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21    GNU General Public License for more details.
  22
  23    You should have received a copy of the GNU General Public License
  24    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  25 */
  26
  27 /*
  28   see the section marked "public interface" below for documentation
  29 */
  30
  31 /**
  32  * @file
  33  */
  34
  35 #include "replace.h"
  36 #include "samba_util.h" /* generate_random() */
  37 #include "idtree.h"
  38 #include "idtree_random.h"
  39
  40 /**
  41   allocate a new id randomly in the given range
  42 */
  43 _PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
  44 {
  45         int id;
  46
  47         /* first try a random starting point in the whole range, and if that fails,
  48            then start randomly in the bottom half of the range. This can only
  49            fail if the range is over half full, and finally fallback to any
  50            free id */
  51         id = idr_get_new_above(idp, ptr, 1+(generate_random() % limit), limit);
  52         if (id == -1) {
  53                 id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit);
  54         }
  55         if (id == -1) {
  56                 id = idr_get_new_above(idp, ptr, 1, limit);
  57         }
  58
  59         return id;
  60 }