2 * dynamic hashed associative table for commands and variables
7 #define INIT_TBLS 8 /* initial table size (power of 2) */
9 static void texpand(struct table
*, int);
10 static int tnamecmp(void *, void *);
20 return h
* 32821; /* scatter bits */
24 ktinit(struct table
*tp
, Area
*ap
, int tsize
)
28 tp
->size
= tp
->nfree
= 0;
34 texpand(struct table
*tp
, int nsize
)
37 struct tbl
*tblp
, **p
;
38 struct tbl
**ntblp
, **otblp
= tp
->tbls
;
41 ntblp
= (struct tbl
**) alloc(sizeofN(struct tbl
*, nsize
), tp
->areap
);
42 for (i
= 0; i
< nsize
; i
++)
45 tp
->nfree
= 8*nsize
/10; /* table can get 80% full */
49 for (i
= 0; i
< osize
; i
++)
50 if ((tblp
= otblp
[i
]) != NULL
) {
51 if ((tblp
->flag
&DEFINED
)) {
52 for (p
= &ntblp
[hash(tblp
->name
)
55 if (p
== ntblp
) /* wrap */
59 } else if (!(tblp
->flag
& FINUSE
)) {
60 afree((void*)tblp
, tp
->areap
);
63 afree((void*)otblp
, tp
->areap
);
67 ktsearch(struct table
*tp
, const char *n
, unsigned int h
)
74 /* search for name in hashed table */
75 for (pp
= &tp
->tbls
[h
& (tp
->size
-1)]; (p
= *pp
) != NULL
; pp
--) {
76 if (*p
->name
== *n
&& strcmp(p
->name
, n
) == 0
79 if (pp
== tp
->tbls
) /* wrap */
87 ktenter(struct table
*tp
, const char *n
, unsigned int h
)
93 texpand(tp
, INIT_TBLS
);
95 /* search for name in hashed table */
96 for (pp
= &tp
->tbls
[h
& (tp
->size
-1)]; (p
= *pp
) != NULL
; pp
--) {
97 if (*p
->name
== *n
&& strcmp(p
->name
, n
) == 0)
99 if (pp
== tp
->tbls
) /* wrap */
103 if (tp
->nfree
<= 0) { /* too full */
104 texpand(tp
, 2*tp
->size
);
108 /* create new tbl entry */
110 p
= (struct tbl
*) alloc(offsetof(struct tbl
, name
[0]) + len
,
114 p
->areap
= tp
->areap
;
116 p
->u
.array
= (struct tbl
*)0;
117 memcpy(p
->name
, n
, len
);
119 /* enter in tp->tbls */
126 ktdelete(struct tbl
*p
)
132 ktwalk(struct tstate
*ts
, struct table
*tp
)
139 ktnext(struct tstate
*ts
)
141 while (--ts
->left
>= 0) {
142 struct tbl
*p
= *ts
->next
++;
143 if (p
!= NULL
&& (p
->flag
&DEFINED
))
150 tnamecmp(void *p1
, void *p2
)
152 return strcmp(((struct tbl
*)p1
)->name
, ((struct tbl
*)p2
)->name
);
156 ktsort(struct table
*tp
)
159 struct tbl
**p
, **sp
, **dp
;
161 p
= (struct tbl
**)alloc(sizeofN(struct tbl
*, tp
->size
+1), ATEMP
);
162 sp
= tp
->tbls
; /* source */
164 for (i
= 0; i
< tp
->size
; i
++)
165 if ((*dp
= *sp
++) != NULL
&& (((*dp
)->flag
&DEFINED
) ||
166 ((*dp
)->flag
&ARRAY
)))
169 qsortp((void**)p
, (size_t)i
, tnamecmp
);
174 #ifdef PERF_DEBUG /* performance debugging */
176 void tprintinfo(struct table
*tp
);
179 tprintinfo(struct table
*tp
)
185 int totncmp
= 0, maxncmp
= 0;
189 shellf("table size %d, nfree %d\n", tp
->size
, tp
->nfree
);
190 shellf(" Ncmp name\n");
192 while ((te
= ktnext(&ts
))) {
195 h
= hash(n
= te
->name
);
198 /* taken from ktsearch() and added counter */
199 for (pp
= &tp
->tbls
[h
& (tp
->size
-1)]; (p
= *pp
); pp
--) {
201 if (*p
->name
== *n
&& strcmp(p
->name
, n
) == 0
202 && (p
->flag
&DEFINED
))
203 break; /* return p; */
204 if (pp
== tp
->tbls
) /* wrap */
207 shellf(" %4d %s\n", ncmp
, n
);
214 shellf(" %d entries, worst ncmp %d, avg ncmp %d.%02d\n",
217 (totncmp
% nentries
) * 100 / nentries
);
219 #endif /* PERF_DEBUG */