[gs-cvs] rev 8062 - in trunk/gs: doc src
leonardo at ghostscript.com
leonardo at ghostscript.com
Mon Jun 18 22:45:59 PDT 2007
Author: leonardo
Date: 2007-06-18 22:45:58 -0700 (Mon, 18 Jun 2007)
New Revision: 8062
Added:
trunk/gs/src/idicttpl.h
Modified:
trunk/gs/doc/Develop.htm
trunk/gs/src/idict.c
trunk/gs/src/idictdef.h
trunk/gs/src/idstack.c
trunk/gs/src/int.mak
Log:
Fix (PS interpreter) : Replace packed_search_* macros with a template.
DETAILS :
This change is algorithmically equivalent.
The purpose is to improve the debugging technology.
It allows to trace through the packed search code
with Microsoft Developer Studio.
We define a new variable 'wrap'
for reducing 3 macros to a single template.
We believe it shouldn't cause a sensible slowdown.
An alternative is 2 (nested) templates and no new variables.
We noticed that the missing key case is not optimized well.
When the key is missing, the algorithm scans the
left part of the array 2 times. One time should be enough.
It should be optimized in a separate patch.
EXPECTED DIFFERENCES :
None.
Modified: trunk/gs/doc/Develop.htm
===================================================================
--- trunk/gs/doc/Develop.htm 2007-06-19 02:39:15 UTC (rev 8061)
+++ trunk/gs/doc/Develop.htm 2007-06-19 05:45:58 UTC (rev 8062)
@@ -2211,7 +2211,8 @@
<a href="../src/iddict.h">src/iddict.h</a>,
<a href="../src/idict.h">src/idict.h</a>,
<a href="../src/idict.c">src/idict.c</a>,
-<a href="../src/idictdef.h">src/idictdef.h</a>.
+<a href="../src/idictdef.h">src/idictdef.h</a>,
+<a href="../src/idicttpl.h">src/idicttpl.h</a>.
<dt>
Names:
Modified: trunk/gs/src/idict.c
===================================================================
--- trunk/gs/src/idict.c 2007-06-19 02:39:15 UTC (rev 8061)
+++ trunk/gs/src/idict.c 2007-06-19 05:45:58 UTC (rev 8062)
@@ -29,6 +29,10 @@
#include "idictdef.h"
#include "iutil.h"
#include "ivmspace.h" /* for store check */
+/*
+#include "idicttpl.h" - Do not remove this comment.
+ "idicttpl.h" is included below.
+*/
/*
* Dictionaries per se aren't supposed to know anything about the
@@ -339,12 +343,13 @@
if (dict_is_packed(pdict)) {
const ref_packed *pslot = 0;
- packed_search_1(*ppvalue = packed_search_value_pointer,
- return 1,
- if (pslot == 0) pslot = kp, goto miss);
- packed_search_2(*ppvalue = packed_search_value_pointer,
- return 1,
- if (pslot == 0) pslot = kp, goto miss);
+# define found *ppvalue = packed_search_value_pointer; return 1
+# define deleted if (pslot == 0) pslot = kp
+# define missing goto miss
+# include "idicttpl.h"
+# undef missing
+# undef deleted
+# undef found
/*
* Double wraparound, dict is full.
* Note that even if there was an empty slot (pslot != 0),
Modified: trunk/gs/src/idictdef.h
===================================================================
--- trunk/gs/src/idictdef.h 2007-06-19 02:39:15 UTC (rev 8061)
+++ trunk/gs/src/idictdef.h 2007-06-19 05:45:58 UTC (rev 8062)
@@ -79,39 +79,8 @@
#define npairs(dct) (nslots(dct) - 1)
#define d_length(dct) ((uint)((dct)->count.value.intval))
-/*
- * Define macros for searching a packed dictionary. Free variables:
- * ref_packed kpack - holds the packed key.
- * uint hash - holds the hash of the name.
- * dict *pdict - points to the dictionary.
- * uint size - holds npairs(pdict).
- * Note that the macro is *not* enclosed in {}, so that we can access
- * the values of kbot and kp after leaving the loop.
- *
- * We break the macro into two to avoid overflowing some preprocessors.
- */
-/* packed_search_body also uses kp and kbot as free variables. */
+/* packed_search_value_pointer simplifies the access to
+ packed dictionary search template data - see idicttpl.h . */
#define packed_search_value_pointer (pdict->values.value.refs + (kp - kbot))
-#define packed_search_body(found1,found2,del,miss)\
- { if_debug2('D', "[D]probe 0x%lx: 0x%x\n", (ulong)kp, *kp);\
- if ( *kp == kpack )\
- { found1;\
- found2;\
- }\
- else if ( !r_packed_is_name(kp) )\
- { /* Empty, deleted, or wraparound. Figure out which. */\
- if ( *kp == packed_key_empty ) miss;\
- if ( kp == kbot ) break; /* wrap */\
- else { del; }\
- }\
- }
-#define packed_search_1(found1,found2,del,miss)\
- const ref_packed *kbot = pdict->keys.value.packed;\
- register const ref_packed *kp;\
- for ( kp = kbot + dict_hash_mod(hash, size) + 1; ; kp-- )\
- packed_search_body(found1,found2,del,miss)
-#define packed_search_2(found1,found2,del,miss)\
- for ( kp += size; ; kp-- )\
- packed_search_body(found1,found2,del,miss)
#endif /* idictdef_INCLUDED */
Added: trunk/gs/src/idicttpl.h
===================================================================
--- trunk/gs/src/idicttpl.h 2007-06-19 02:39:15 UTC (rev 8061)
+++ trunk/gs/src/idicttpl.h 2007-06-19 05:45:58 UTC (rev 8062)
@@ -0,0 +1,61 @@
+/* Copyright (C) 2001-2006 Artifex Software, Inc.
+ All Rights Reserved.
+
+ This software is provided AS-IS with no warranty, either express or
+ implied.
+
+ This software is distributed under license and may not be copied, modified
+ or distributed except as expressly authorized under the terms of that
+ license. Refer to licensing information at http://www.artifex.com/
+ or contact Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134,
+ San Rafael, CA 94903, U.S.A., +1(415)492-9861, for further information.
+*/
+
+/* $Id: idicttpl.h 8022 2007-06-05 22:23:38Z giles $ */
+/* A template for packed dictionary search method */
+
+/*
+ * Define template for searching a packed dictionary.
+ *
+ * Free variables:
+ * ref_packed kpack - holds the packed key.
+ * uint hash - holds the hash of the name.
+ * dict *pdict - points to the dictionary.
+ * uint size - holds npairs(pdict).
+ *
+ * Template parameters are :
+ * found - the found key action.
+ * deleted - the deleted key action.
+ * missing - the missed key action.
+ *
+ * Note that the template is *not* enclosed in {}, so that we can access
+ * the values of kbot and kp after leaving the template.
+ */
+
+ const ref_packed *kbot = pdict->keys.value.packed;
+ register const ref_packed *kp = kbot + dict_hash_mod(hash, size) + 1;
+
+ int wrap = 0;
+
+ again:
+ for (; ; kp-- ) {
+ if_debug2('D', "[D]probe 0x%lx: 0x%x\n", (ulong)kp, *kp);
+ if ( *kp == kpack ) {
+ found;
+ } else if ( !r_packed_is_name(kp) ) {
+ /* Empty, deleted, or wraparound. Figure out which. */
+ if ( *kp == packed_key_empty )
+ missing;
+ if ( kp == kbot ) {
+ if (wrap)
+ break;
+ else {
+ wrap++;
+ kp += size; /* wrap */
+ goto again; /* skip "kp--". */
+ }
+ } else {
+ deleted;
+ }
+ }
+ }
Modified: trunk/gs/src/idstack.c
===================================================================
--- trunk/gs/src/idstack.c 2007-06-19 02:39:15 UTC (rev 8061)
+++ trunk/gs/src/idstack.c 2007-06-19 05:45:58 UTC (rev 8062)
@@ -22,6 +22,10 @@
#include "ipacked.h"
#include "iutil.h"
#include "ivmspace.h"
+/*
+#include "idicttpl.h" - Do not remove this comment.
+ "idicttpl.h" is included below.
+*/
/* Debugging statistics */
#ifdef DEBUG
@@ -123,13 +127,13 @@
#define INCR_DEPTH(pdref)\
INCR(depth[min(MAX_STATS_DEPTH, pds->stack.p - pdref)])
if (dict_is_packed(pdict)) {
- packed_search_1(INCR_DEPTH(pdref),
- return packed_search_value_pointer,
- DO_NOTHING, goto miss);
- packed_search_2(INCR_DEPTH(pdref),
- return packed_search_value_pointer,
- DO_NOTHING, break);
- miss:;
+# define found INCR_DEPTH(pdref); return packed_search_value_pointer
+# define deleted
+# define missing break;
+# include "idicttpl.h"
+# undef missing
+# undef deleted
+# undef found
} else {
/*
* The name_index macro takes mem as its first argument, but
Modified: trunk/gs/src/int.mak
===================================================================
--- trunk/gs/src/int.mak 2007-06-19 02:39:15 UTC (rev 8061)
+++ trunk/gs/src/int.mak 2007-06-19 05:45:58 UTC (rev 8062)
@@ -52,6 +52,7 @@
iddstack_h=$(PSSRC)iddstack.h
idict_h=$(PSSRC)idict.h $(iddstack_h)
idictdef_h=$(PSSRC)idictdef.h
+idicttpl_h=$(PSSRC)idicttpl.h
idosave_h=$(PSSRC)idosave.h
igcstr_h=$(PSSRC)igcstr.h
inames_h=$(PSSRC)inames.h
@@ -168,7 +169,7 @@
$(PSOBJ)idict.$(OBJ) : $(PSSRC)idict.c $(GH) $(math__h) $(string__h)\
$(ierrors_h)\
$(gxalloc_h)\
- $(iddstack_h) $(idebug_h) $(idict_h) $(idictdef_h)\
+ $(iddstack_h) $(idebug_h) $(idict_h) $(idictdef_h) $(idicttpl_h)\
$(imemory_h) $(iname_h) $(inamedef_h) $(ipacked_h) $(isave_h)\
$(iutil_h) $(ivmspace_h) $(store_h)
$(PSCC) $(PSO_)idict.$(OBJ) $(C_) $(PSSRC)idict.c
@@ -180,7 +181,7 @@
$(PSCC) $(PSO_)idparam.$(OBJ) $(C_) $(PSSRC)idparam.c
$(PSOBJ)idstack.$(OBJ) : $(PSSRC)idstack.c $(GH)\
- $(idebug_h) $(idict_h) $(idictdef_h) $(idstack_h) $(iname_h) $(inamedef_h)\
+ $(idebug_h) $(idict_h) $(idictdef_h) $(idicttpl_h) $(idstack_h) $(iname_h) $(inamedef_h)\
$(ipacked_h) $(iutil_h) $(ivmspace_h)
$(PSCC) $(PSO_)idstack.$(OBJ) $(C_) $(PSSRC)idstack.c
More information about the gs-cvs
mailing list