unofficial mirror of guile-devel@gnu.org 
 help / color / mirror / Atom feed
* [PATCH] Universally-unique gensyms
@ 2012-01-17 13:27 Mark H Weaver
  2012-01-17 13:57 ` Andy Wingo
  0 siblings, 1 reply; 17+ messages in thread
From: Mark H Weaver @ 2012-01-17 13:27 UTC (permalink / raw)
  To: guile-devel

[-- Attachment #1: Type: text/plain, Size: 80 bytes --]

This patch makes our gensyms universally-unique.  Comments welcome.

    Mark



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: [PATCH] Universally-unique gensyms --]
[-- Type: text/x-patch, Size: 3611 bytes --]

From 18616afc6a3d5aca48da2e0819d08d7ff98de214 Mon Sep 17 00:00:00 2001
From: Mark H Weaver <mhw@netris.org>
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


^ permalink raw reply related	[flat|nested] 17+ messages in thread

end of thread, other threads:[~2012-01-20  0:50 UTC | newest]

Thread overview: 17+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2012-01-17 13:27 [PATCH] Universally-unique gensyms Mark H Weaver
2012-01-17 13:57 ` Andy Wingo
2012-01-17 14:06   ` Andy Wingo
2012-01-18  8:04   ` Mark H Weaver
2012-01-18  9:35     ` Mark H Weaver
2012-01-18 21:41     ` Ludovic Courtès
2012-01-18 22:23       ` Andy Wingo
2012-01-18 22:43         ` Ludovic Courtès
2012-01-18 23:30         ` Mark H Weaver
2012-01-19  1:21           ` David Kastrup
2012-01-19  4:50             ` Mark H Weaver
2012-01-19  6:25               ` David Kastrup
2012-01-19 10:23                 ` Mark H Weaver
2012-01-20  0:50                   ` Mark H Weaver
2012-01-19  0:58       ` Mark H Weaver
2012-01-19 23:26         ` Ludovic Courtès
2012-01-18 21:42     ` Ludovic Courtès

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).