Fix : Replace packed_search_* macros with a template.
"Igor V. Melichev" <[email protected]> Tue, 19 Jun 2007 01:11:12 +0400
| Newsgroups | gmane.comp.printing.ghostscript.patches |
|---|---|
| Message-ID | <[email protected]> |
This is a multi-part message in MIME format.
------=_NextPart_000_0015_01C7B20E.BA26F4F0
Content-Type: text/plain; format=flowed; charset="koi8-r"; reply-type=original
Content-Transfer-Encoding: 7bit
[Log message beg]
Fix : Replace packed_search_* macros with a template.
DETAILS :
This change is algorithmically equivalent.
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.
A possible optimization should be a separate patch,
rather it appears difficult in a single template with no code duplication.
EXPECTED DIFFERENCES :
None.
[Log message end]
------=_NextPart_000_0015_01C7B20E.BA26F4F0
Content-Type: text/plain; format=flowed; name="patch1.txt"; reply-type=original
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
filename="patch1.txt"
*** F:\SVN-GS\HEAD\gs\src\idict.c Thu Jun 7 23:31:37 2007
--- files\gs\src\idict.c Tue Jun 19 00:53:32 2007
***************
*** 30,33 ****
--- 30,37 ----
#include "iutil.h"
#include "ivmspace.h" /* for store check */
+ /*
+ #include "idicttpl.h" - Do not remove this comment.
+ "idicttpl.h" is included below.
+ */
=20
/*
***************
*** 340,349 ****
const ref_packed *pslot =3D 0;
=20
! packed_search_1(*ppvalue =3D packed_search_value_pointer,
! return 1,
! if (pslot =3D=3D 0) pslot =3D kp, goto miss);
! packed_search_2(*ppvalue =3D packed_search_value_pointer,
! return 1,
! if (pslot =3D=3D 0) pslot =3D kp, goto miss);
/*
* Double wraparound, dict is full.
--- 344,354 ----
const ref_packed *pslot =3D 0;
=20
! # define found *ppvalue =3D packed_search_value_pointer; return 1
! # define deleted if (pslot =3D=3D 0) pslot =3D kp
! # define missing goto miss
! # include "idicttpl.h"
! # undef missing
! # undef deleted
! # undef found
/*
* Double wraparound, dict is full.
=20
=20
=20
*** F:\SVN-GS\HEAD\gs\src\idictdef.h Thu Jun 7 23:31:53 2007
--- files\gs\src\idictdef.h Tue Jun 19 00:47:15 2007
***************
*** 80,117 ****
#define d_length(dct) ((uint)((dct)->count.value.intval))
=20
! /*
! * 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. */
#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 =3D=3D kpack )\
- { found1;\
- found2;\
- }\
- else if ( !r_packed_is_name(kp) )\
- { /* Empty, deleted, or wraparound. Figure out which. */\
- if ( *kp =3D=3D packed_key_empty ) miss;\
- if ( kp =3D=3D kbot ) break; /* wrap */\
- else { del; }\
- }\
- }
- #define packed_search_1(found1,found2,del,miss)\
- const ref_packed *kbot =3D pdict->keys.value.packed;\
- register const ref_packed *kp;\
- for ( kp =3D 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 +=3D size; ; kp-- )\
- packed_search_body(found1,found2,del,miss)
=20
#endif /* idictdef_INCLUDED */
--- 80,86 ----
#define d_length(dct) ((uint)((dct)->count.value.intval))
=20
! /* packed_search_value_pointer simplifies the access to=20
! packed dictionary search template data - see idicttpl.h . */
#define packed_search_value_pointer (pdict->values.value.refs + (kp - =
kbot))
=20
#endif /* idictdef_INCLUDED */
=20
=20
=20
=20
=20
=20
*** F:\SVN-GS\HEAD\gs\src\idstack.c Thu Jun 7 23:31:40 2007
--- files\gs\src\idstack.c Tue Jun 19 01:06:47 2007
***************
*** 23,26 ****
--- 23,30 ----
#include "iutil.h"
#include "ivmspace.h"
+ /*
+ #include "idicttpl.h" - Do not remove this comment.
+ "idicttpl.h" is included below.
+ */
=20
/* Debugging statistics */
***************
*** 124,134 ****
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:;
} else {
/*
--- 128,138 ----
INCR(depth[min(MAX_STATS_DEPTH, pds->stack.p - pdref)])
if (dict_is_packed(pdict)) {
! # define found INCR_DEPTH(pdref); return =
packed_search_value_pointer
! # define deleted=20
! # define missing break;
! # include "idicttpl.h"
! # undef missing
! # undef deleted
! # undef found
} else {
/*
=20
=20
=20
*** F:\SVN-GS\HEAD\gs\src\int.mak Thu Jun 7 23:31:18 2007
--- files\gs\src\int.mak Tue Jun 19 00:54:36 2007
***************
*** 53,56 ****
--- 53,57 ----
idict_h=3D$(PSSRC)idict.h $(iddstack_h)
idictdef_h=3D$(PSSRC)idictdef.h
+ idicttpl_h=3D$(PSSRC)idicttpl.h
idosave_h=3D$(PSSRC)idosave.h
igcstr_h=3D$(PSSRC)igcstr.h
***************
*** 169,173 ****
$(ierrors_h)\
$(gxalloc_h)\
! $(iddstack_h) $(idebug_h) $(idict_h) $(idictdef_h)\
$(imemory_h) $(iname_h) $(inamedef_h) $(ipacked_h) $(isave_h)\
$(iutil_h) $(ivmspace_h) $(store_h)
--- 170,174 ----
$(ierrors_h)\
$(gxalloc_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)
***************
*** 181,185 ****
=20
$(PSOBJ)idstack.$(OBJ) : $(PSSRC)idstack.c $(GH)\
! $(idebug_h) $(idict_h) $(idictdef_h) $(idstack_h) $(iname_h) =
$(inamedef_h)\
$(ipacked_h) $(iutil_h) $(ivmspace_h)
$(PSCC) $(PSO_)idstack.$(OBJ) $(C_) $(PSSRC)idstack.c
--- 182,186 ----
=20
$(PSOBJ)idstack.$(OBJ) : $(PSSRC)idstack.c $(GH)\
! $(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
=20
------=_NextPart_000_0015_01C7B20E.BA26F4F0
Content-Type: text/plain; format=flowed; name="idicttpl.h"; reply-type=original
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment;
filename="idicttpl.h"
/* Copyright (C) 2001-2006 Artifex Software, Inc.
All Rights Reserved.
=20
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. =20
*
* 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 =3D pdict->keys.value.packed;
register const ref_packed *kp =3D kbot + dict_hash_mod(hash, size) + =
1;
int wrap =3D 0;
again:
for (; ; kp-- ) {
if_debug2('D', "[D]probe 0x%lx: 0x%x\n", (ulong)kp, *kp);
if ( *kp =3D=3D kpack ) {
found;
} else if ( !r_packed_is_name(kp) ) {
/* Empty, deleted, or wraparound. Figure out which. */
if ( *kp =3D=3D packed_key_empty )=20
missing;
if ( kp =3D=3D kbot ) {
if (wrap)
break;
else {
wrap++;
kp +=3D size; /* wrap */
goto again; /* skip "kp--". */
}
} else {=20
deleted;=20
}
}
}
------=_NextPart_000_0015_01C7B20E.BA26F4F0
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
gs-code-review mailing list
[email protected]
http://www.ghostscript.com/mailman/listinfo/gs-code-review
------=_NextPart_000_0015_01C7B20E.BA26F4F0--