[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH] Universally-unique gensyms
From: |
Mark H Weaver |
Subject: |
[PATCH] Universally-unique gensyms |
Date: |
Tue, 17 Jan 2012 08:27:58 -0500 |
This patch makes our gensyms universally-unique. Comments welcome.
Mark
>From 18616afc6a3d5aca48da2e0819d08d7ff98de214 Mon Sep 17 00:00:00 2001
From: Mark H Weaver <address@hidden>
Date: Tue, 17 Jan 2012 08:15:10 -0500
Subject: [PATCH] Universally-unique gensyms
* libguile/symbols.c (scm_gensym): The gensym counter is now 128 bits,
initialized to a random number at the beginning of each session. This
counter is rendered as a 22 byte suffix of mostly base64 digits.
---
libguile/symbols.c | 69 +++++++++++++++++++++++++++++++++++++++++++++-------
1 files changed, 60 insertions(+), 9 deletions(-)
diff --git a/libguile/symbols.c b/libguile/symbols.c
index 59aca00..cf82518 100644
--- a/libguile/symbols.c
+++ b/libguile/symbols.c
@@ -340,7 +340,9 @@ SCM_DEFINE (scm_string_ci_to_symbol, "string-ci->symbol",
1, 0, 0,
/* The default prefix for `gensym'd symbols. */
static SCM default_gensym_prefix;
-#define MAX_PREFIX_LENGTH 30
+#define GENSYM_LENGTH 22 /* bytes */
+#define GENSYM_RADIX_BITS 6
+#define GENSYM_RADIX (1 << (GENSYM_RADIX_BITS))
SCM_DEFINE (scm_gensym, "gensym", 0, 1, 0,
(SCM prefix),
@@ -351,22 +353,71 @@ SCM_DEFINE (scm_gensym, "gensym", 0, 1, 0,
"resetting the counter.")
#define FUNC_NAME s_scm_gensym
{
- static int gensym_counter = 0;
-
+ static int initialized = 0;
+ static unsigned char digit_buf[GENSYM_LENGTH];
+ static char base64[GENSYM_RADIX] =
+ "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789$@";
+ static char base4[4] = "_.-~";
+
+ char char_buf[GENSYM_LENGTH];
SCM suffix, name;
- int n, n_digits;
- char buf[SCM_INTBUFLEN];
+ int i;
+
+ if (SCM_UNLIKELY (!initialized))
+ {
+ int res = 0;
+ FILE *f = fopen ("/dev/urandom", "r");
+ if (f)
+ {
+ res = fread(digit_buf, 1, GENSYM_LENGTH, f);
+ fclose (f);
+ }
+ if (res == GENSYM_LENGTH)
+ {
+ for (i = (GENSYM_LENGTH - 1); i >= 0; --i)
+ digit_buf[i] &= (GENSYM_RADIX - 1);
+ }
+ else
+ {
+ /* This is a fallback in case /dev/urandom fails */
+ SCM tm = scm_gettimeofday ();
+ SCM seed = scm_sum (scm_product (scm_car (tm),
+ scm_from_int (1000000)),
+ scm_cdr (tm));
+ SCM random_state = scm_seed_to_random_state (seed);
+ SCM radix = scm_from_int (GENSYM_RADIX);
+ for (i = (GENSYM_LENGTH - 1); i >= 0; --i)
+ digit_buf[i] = scm_to_int (scm_random (radix, random_state));
+ }
+ initialized = 1;
+ }
if (SCM_UNBNDP (prefix))
prefix = default_gensym_prefix;
- /* mutex in case another thread looks and incs at the exact same moment */
+ /* ENHANCE-ME: make digit_buf thread-local to avoid the mutex */
+
+ /* lock the mutex */
scm_i_scm_pthread_mutex_lock (&scm_i_misc_mutex);
- n = gensym_counter++;
+
+ /* increment digit_buf */
+ for (i = (GENSYM_LENGTH - 1); i >= 0; --i)
+ {
+ if (SCM_LIKELY (++(digit_buf[i]) < GENSYM_RADIX))
+ break;
+ else
+ digit_buf[i] = 0;
+ }
+
+ /* convert digit_buf to the base64 char_buf */
+ for (i = (GENSYM_LENGTH - 1); i > 0; --i)
+ char_buf[i] = base64[digit_buf[i]];
+ char_buf[0] = base4[digit_buf[0] & 3];
+
+ /* unlock the mutex */
scm_i_pthread_mutex_unlock (&scm_i_misc_mutex);
- n_digits = scm_iint2str (n, 10, buf);
- suffix = scm_from_latin1_stringn (buf, n_digits);
+ suffix = scm_from_latin1_stringn (char_buf, GENSYM_LENGTH);
name = scm_string_append (scm_list_2 (prefix, suffix));
return scm_string_to_symbol (name);
}
--
1.7.5.4
- [PATCH] Universally-unique gensyms,
Mark H Weaver <=
- Re: [PATCH] Universally-unique gensyms, Andy Wingo, 2012/01/17
- Re: [PATCH] Universally-unique gensyms, Andy Wingo, 2012/01/17
- Re: [PATCH] Universally-unique gensyms, Mark H Weaver, 2012/01/18
- Re: [PATCH] Universally-unique gensyms, Mark H Weaver, 2012/01/18
- Re: [PATCH] Universally-unique gensyms, Ludovic Courtès, 2012/01/18
- Re: [PATCH] Universally-unique gensyms, Ludovic Courtès, 2012/01/18
- Re: [PATCH] Universally-unique gensyms, Andy Wingo, 2012/01/18
- Re: [PATCH] Universally-unique gensyms, Ludovic Courtès, 2012/01/18
- Re: [PATCH] Universally-unique gensyms, Mark H Weaver, 2012/01/18
- Re: [PATCH] Universally-unique gensyms, David Kastrup, 2012/01/18