lib/util: Move idr_get_new_random() to new source file idtree_random.c

This function depends on genrand.c, which depends on lib/crypto.  This
way the other IDR tree code can be used without lib/crypto.

While doing this, create idtree.h and idtree_random.h and clean up the
includes.

Signed-off-by: Martin Schwenke <martin@meltin.net>
Reviewed-by: Volker Lendecke <vl@samba.org>

6 files changed, 176 insertions, 63 deletions

diff --git a/lib/util/idtree.c b/lib/util/idtree.c
index 4dde69413fb..6f1a4ac9dd0 100644
--- a/lib/util/idtree.c
+++ b/lib/util/idtree.c
@@ -32,7 +32,10 @@
  * @file
  */
 
-#include "includes.h"
+#include <talloc.h>
+#include "replace.h"
+#include "debug.h"
+#include "idtree.h"
 
 #define IDR_BITS 5
 #define IDR_FULL 0xfffffffful
@@ -366,28 +369,6 @@ _PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_
 }
 
 /**
-  allocate a new id randomly in the given range
-*/
-_PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
-{
-	int id;
-
-	/* first try a random starting point in the whole range, and if that fails,
-	   then start randomly in the bottom half of the range. This can only
-	   fail if the range is over half full, and finally fallback to any
-	   free id */
-	id = idr_get_new_above(idp, ptr, 1+(generate_random() % limit), limit);
-	if (id == -1) {
-		id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit);
-	}
-	if (id == -1) {
-		id = idr_get_new_above(idp, ptr, 1, limit);
-	}
-
-	return id;
-}
-
-/**
   find a pointer value previously set with idr_get_new given an id
 */
 _PUBLIC_ void *idr_find(struct idr_context *idp, int id)
diff --git a/lib/util/idtree.h b/lib/util/idtree.h
new file mode 100644
index 00000000000..e7864a86968
--- /dev/null
+++ b/lib/util/idtree.h
@@ -0,0 +1,68 @@
+/*
+   Unix SMB/CIFS implementation.
+
+   very efficient functions to manage mapping a id (such as a fnum) to
+   a pointer. This is used for fnum and search id allocation.
+
+   Copyright (C) Andrew Tridgell 2004
+
+   This code is derived from lib/idr.c in the 2.6 Linux kernel, which was
+   written by Jim Houston jim.houston@ccur.com, and is
+   Copyright (C) 2002 by Concurrent Computer Corporation
+
+   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 of the License, 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, see <http://www.gnu.org/licenses/>.
+*/
+
+#ifndef _SAMBA_IDTREE_H_
+#define _SAMBA_IDTREE_H_
+
+#include <talloc.h>
+
+struct idr_context;
+
+/**
+  initialise a idr tree. The context return value must be passed to
+  all subsequent idr calls. To destroy the idr tree use talloc_free()
+  on this context
+ */
+struct idr_context *idr_init(TALLOC_CTX *mem_ctx);
+
+/**
+  allocate the next available id, and assign 'ptr' into its slot.
+  you can retrieve later this pointer using idr_find()
+*/
+int idr_get_new(struct idr_context *idp, void *ptr, int limit);
+
+/**
+   allocate a new id, giving the first available value greater than or
+   equal to the given starting id
+*/
+int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit);
+
+/**
+  allocate a new id randomly in the given range
+*/
+int idr_get_new_random(struct idr_context *idp, void *ptr, int limit);
+
+/**
+  find a pointer value previously set with idr_get_new given an id
+*/
+void *idr_find(struct idr_context *idp, int id);
+
+/**
+  remove an id from the idr tree
+*/
+int idr_remove(struct idr_context *idp, int id);
+
+#endif /* _SAMBA_IDTREE_H_ */
diff --git a/lib/util/idtree_random.c b/lib/util/idtree_random.c
new file mode 100644
index 00000000000..80758e74d6d
--- /dev/null
+++ b/lib/util/idtree_random.c
@@ -0,0 +1,60 @@
+/*
+   Unix SMB/CIFS implementation.
+
+   very efficient functions to manage mapping a id (such as a fnum) to
+   a pointer. This is used for fnum and search id allocation.
+
+   Copyright (C) Andrew Tridgell 2004
+
+   This code is derived from lib/idr.c in the 2.6 Linux kernel, which was
+   written by Jim Houston jim.houston@ccur.com, and is
+   Copyright (C) 2002 by Concurrent Computer Corporation
+
+   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 of the License, 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, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+  see the section marked "public interface" below for documentation
+*/
+
+/**
+ * @file
+ */
+
+#include "replace.h"
+#include "samba_util.h" /* generate_random() */
+#include "idtree.h"
+#include "idtree_random.h"
+
+/**
+  allocate a new id randomly in the given range
+*/
+_PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit)
+{
+	int id;
+
+	/* first try a random starting point in the whole range, and if that fails,
+	   then start randomly in the bottom half of the range. This can only
+	   fail if the range is over half full, and finally fallback to any
+	   free id */
+	id = idr_get_new_above(idp, ptr, 1+(generate_random() % limit), limit);
+	if (id == -1) {
+		id = idr_get_new_above(idp, ptr, 1+(generate_random()%(limit/2)), limit);
+	}
+	if (id == -1) {
+		id = idr_get_new_above(idp, ptr, 1, limit);
+	}
+
+	return id;
+}
diff --git a/lib/util/idtree_random.h b/lib/util/idtree_random.h
new file mode 100644
index 00000000000..4d3b61c33d5
--- /dev/null
+++ b/lib/util/idtree_random.h
@@ -0,0 +1,38 @@
+/*
+   Unix SMB/CIFS implementation.
+
+   very efficient functions to manage mapping a id (such as a fnum) to
+   a pointer. This is used for fnum and search id allocation.
+
+   Copyright (C) Andrew Tridgell 2004
+
+   This code is derived from lib/idr.c in the 2.6 Linux kernel, which was
+   written by Jim Houston jim.houston@ccur.com, and is
+   Copyright (C) 2002 by Concurrent Computer Corporation
+
+   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 of the License, 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, see <http://www.gnu.org/licenses/>.
+*/
+
+#ifndef _SAMBA_IDTREE_RANDOM_H_
+#define _SAMBA_IDTREE_RANDOM_H_
+
+#include <talloc.h>
+#include "idtree.h"
+
+/**
+  allocate a new id randomly in the given range
+*/
+int idr_get_new_random(struct idr_context *idp, void *ptr, int limit);
+
+#endif /* _SAMBA_IDTREE_RANDOM_H_ */
diff --git a/lib/util/samba_util.h b/lib/util/samba_util.h
index ec939cc4753..9da61fa4379 100644
--- a/lib/util/samba_util.h
+++ b/lib/util/samba_util.h
@@ -793,42 +793,8 @@ int ms_fnmatch_protocol(const char *pattern, const char *string, int protocol);
 /** a generic fnmatch function - uses for non-CIFS pattern matching */
 int gen_fnmatch(const char *pattern, const char *string);
 
-/* The following definitions come from lib/util/idtree.c  */
-
-
-/**
-  initialise a idr tree. The context return value must be passed to
-  all subsequent idr calls. To destroy the idr tree use talloc_free()
-  on this context
- */
-_PUBLIC_ struct idr_context *idr_init(TALLOC_CTX *mem_ctx);
-
-/**
-  allocate the next available id, and assign 'ptr' into its slot.
-  you can retrieve later this pointer using idr_find()
-*/
-_PUBLIC_ int idr_get_new(struct idr_context *idp, void *ptr, int limit);
-
-/**
-   allocate a new id, giving the first available value greater than or
-   equal to the given starting id
-*/
-_PUBLIC_ int idr_get_new_above(struct idr_context *idp, void *ptr, int starting_id, int limit);
-
-/**
-  allocate a new id randomly in the given range
-*/
-_PUBLIC_ int idr_get_new_random(struct idr_context *idp, void *ptr, int limit);
-
-/**
-  find a pointer value previously set with idr_get_new given an id
-*/
-_PUBLIC_ void *idr_find(struct idr_context *idp, int id);
-
-/**
-  remove an id from the idr tree
-*/
-_PUBLIC_ int idr_remove(struct idr_context *idp, int id);
+#include "idtree.h"
+#include "idtree_random.h"
 
 /**
  Close the low 3 fd's and open dev/null in their place
diff --git a/lib/util/wscript_build b/lib/util/wscript_build
index c14851455a4..d7e5b03e62c 100755
--- a/lib/util/wscript_build
+++ b/lib/util/wscript_build
@@ -34,15 +34,15 @@ bld.SAMBA_LIBRARY('socket-blocking',
 bld.SAMBA_LIBRARY('samba-util',
                   source='''talloc_stack.c smb_threads.c xfile.c data_blob.c
                     util_file.c time.c rbtree.c rfc1738.c select.c getpass.c
-                    genrand.c fsusage.c become_daemon.c
-                    signal.c system.c params.c util.c util_id.c util_net.c
-                    util_strlist.c util_paths.c idtree.c fault.c base64.c
+                    genrand.c fsusage.c become_daemon.c signal.c system.c
+                    params.c util.c util_id.c util_net.c util_strlist.c
+                    util_paths.c idtree.c idtree_random.c fault.c base64.c
                     util_str.c util_str_common.c substitute.c ms_fnmatch.c
                     server_id.c dprintf.c parmlist.c bitmap.c pidfile.c
                     tevent_debug.c util_process.c memcache.c''',
                   deps='DYNCONFIG time-basic close-low-fd samba-debug tini tiniparser socket-blocking',
                   public_deps='talloc tevent execinfo pthread LIBCRYPTO charset util_setid systemd-daemon',
-                  public_headers='debug.h attr.h byteorder.h data_blob.h memory.h safe_string.h time.h talloc_stack.h xfile.h dlinklist.h samba_util.h string_wrappers.h',
+                  public_headers='debug.h attr.h byteorder.h data_blob.h memory.h safe_string.h time.h talloc_stack.h xfile.h dlinklist.h samba_util.h string_wrappers.h idtree.h idtree_random.h',
                   header_path= [ ('dlinklist.h samba_util.h', '.'), ('*', 'util') ],
                   local_include=False,
                   vnum='0.0.1',