1 /* Copyright (C) 2001-2006 Artifex Software, Inc.
2    All Rights Reserved.
3 
4    This software is provided AS-IS with no warranty, either express or
5    implied.
6 
7    This software is distributed under license and may not be copied, modified
8    or distributed except as expressly authorized under the terms of that
9    license.  Refer to licensing information at http://www.artifex.com/
10    or contact Artifex Software, Inc.,  7 Mt. Lassen Drive - Suite A-134,
11    San Rafael, CA  94903, U.S.A., +1(415)492-9861, for further information.
12 */
13 
14 /* $Id: idicttpl.h 9043 2008-08-28 22:48:19Z giles $ */
15 /* A template for packed dictionary search method */
16 
17 /*
18  * Define template for searching a packed dictionary.
19  *
20  * Free variables:
21  *      ref_packed kpack - holds the packed key.
22  *      uint hash - holds the hash of the name.
23  *      dict *pdict - points to the dictionary.
24  *      uint size - holds npairs(pdict).
25  *
26  * Template parameters are :
27  *	found   - the found key action.
28  *	deleted - the deleted key action.
29  *	missing - the missed key action.
30  *
31  * Note that the template is *not* enclosed in {}, so that we can access
32  * the values of kbot and kp after leaving the template.
33  */
34 
35     const ref_packed *kbot = pdict->keys.value.packed;
36     const int start = dict_hash_mod(hash, size) + 1;
37     register const ref_packed *kp = kbot + start;
38     int wrap = 0;
39 
40     again:
41     for (; ; kp-- ) {
42 	if_debug2('D', "[D]probe 0x%lx: 0x%x\n", (ulong)kp, *kp);
43 	if ( *kp == kpack ) {
44 	    found;
45 	} else if ( !r_packed_is_name(kp) ) {
46 	    /* Empty, deleted, or wraparound. Figure out which. */
47 	    if ( *kp == packed_key_empty )
48 		missing;
49 	    if ( kp == kbot ) {
50 		if (wrap)
51 		    break;
52 		else {
53 		    wrap++;
54 		    kp += size; /* wrap */
55 		    goto again; /* skip "kp--". */
56 		}
57 	    } else {
58 		deleted;
59 	    }
60 	}
61    }
62