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