4 extern unsigned hash() ;
6 /* An array A is a pointer to an array of struct array,
7 which is two hash tables in one. One for strings
10 each array is of size A_HASH_PRIME.
12 When an index is deleted via delete A[i], the
13 ANODE is not removed from the hash chain. A[i].cp
14 and A[i].sval are both freed and sval is set NULL.
15 This method of deletion simplifies for( i in A ) loops.
17 On the D_ANODE list, we use real deletion and move to the
20 Separate nodes (as opposed to one type of node on two lists)
22 (1) d1 != d2, but sprintf(A_FMT,d1) == sprintf(A_FMT,d1)
23 so two dnodes can point at the same anode.
24 (2) Save a little data space(64K PC mentality).
26 the cost is an extra level of indirection.
28 Some care is needed so that things like
29 A[1] = 2 ; delete A["1"] work .
32 #define _dhash(d) (((int)(d)&0x7fff)%A_HASH_PRIME)
33 #define DHASH(d) (last_dhash=_dhash(d))
34 static unsigned last_dhash ;
36 /* switch =======;;;;;;hhhh */
38 static ANODE *find_by_sval(A, sval, cflag)
41 int cflag ; /* create if on */
44 unsigned h = hash(s) % A_HASH_PRIME ;
45 register ANODE *p = A[h].link ;
46 ANODE *q = 0 ; /* holds first deleted ANODE */
51 { if ( strcmp(s,p->sval->str) == 0 ) return p ; }
52 else /* its deleted, mark with q */
61 if ( q ) p = q ; /* reuse the deleted node q */
63 { p = (ANODE *)zmalloc(sizeof(ANODE)) ;
64 p->link = A[h].link ; A[h].link = p ;
69 p->cp = (CELL *) zmalloc(sizeof(CELL)) ;
70 p->cp->type = C_NOINIT ;
76 /* on the D_ANODE list, when we find a node we move it
77 to the front of the hash chain */
79 static D_ANODE *find_by_dval(A, d, cflag)
84 unsigned h = DHASH(d) ;
85 register D_ANODE *p = A[h].dlink ;
86 D_ANODE *q = 0 ; /* trails p for move to front */
92 if ( ! p->ap->sval ) /* but it was deleted by string */
93 { if ( q ) q->dlink = p->dlink ;
94 else A[h].dlink = p->dlink ;
95 zfree(p, sizeof(D_ANODE)) ;
99 if ( !q ) return p ; /* already at front */
100 else /* delete to put at front */
101 { q->dlink = p->dlink ; goto found ; }
104 { q = p ; p = p->dlink ; }