1
/* Copyright (C) 2001-2006 Artifex Software, Inc.
4
This software is provided AS-IS with no warranty, either express or
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.
14
/* $Id: iname.c 9179 2008-10-21 16:26:09Z leonardo $ */
15
/* Name lookup for Ghostscript interpreter */
20
#include "gxobj.h" /* for o_set_unmarked */
23
#include "imemory.h" /* for isave.h */
28
const uint name_max_string = max_name_string;
30
/* Define the permutation table for name hashing. */
31
static const byte hash_permutation[256] = {
32
NAME_HASH_PERMUTATION_DATA
35
/* Define the data for the 1-character names. */
36
static const byte nt_1char_names[NT_1CHAR_SIZE] = {
40
/* Structure descriptors */
41
gs_private_st_simple(st_name_sub_table, name_sub_table, "name_sub_table");
42
gs_private_st_composite(st_name_string_sub_table, name_string_sub_table_t,
43
"name_string_sub_table_t",
44
name_string_sub_enum_ptrs, name_string_sub_reloc_ptrs);
45
gs_private_st_composite(st_name_table, name_table, "name_table",
46
name_table_enum_ptrs, name_table_reloc_ptrs);
48
/* Forward references */
49
static int name_alloc_sub(name_table *);
50
static void name_free_sub(name_table *, uint);
51
static void name_scan_sub(name_table *, uint, bool);
53
/* Debugging printout */
56
name_print(const char *msg, const name_table *nt, uint nidx, const int *pflag)
58
const name_string_t *pnstr = names_index_string_inline(nt, nidx);
59
const name *pname = names_index_ptr_inline(nt, nidx);
60
const byte *str = pnstr->string_bytes;
62
dlprintf1("[n]%s", msg);
64
dprintf1("(%d)", *pflag);
65
dprintf2(" (0x%lx#%u)", (ulong)pname, nidx);
66
debug_print_string(str, pnstr->string_size);
67
dprintf2("(0x%lx,%u)\n", (ulong)str, pnstr->string_size);
69
# define if_debug_name(msg, nt, nidx, pflag)\
70
if ( gs_debug_c('n') ) name_print(msg, nt, nidx, pflag)
72
# define if_debug_name(msg, nt, nidx, pflag) DO_NOTHING
75
/* Initialize a name table */
77
names_init(ulong count, gs_ref_memory_t *imem)
79
gs_memory_t *mem = (gs_memory_t *)imem;
84
count = max_name_count + 1L;
85
else if (count - 1 > max_name_count)
87
nt = gs_alloc_struct(mem, name_table, &st_name_table, "name_init(nt)");
90
memset(nt, 0, sizeof(name_table));
92
((count - 1) | nt_sub_index_mask) >> nt_log2_sub_size;
93
nt->name_string_attrs = imemory_space(imem) | a_readonly;
95
/* Initialize the one-character names. */
96
/* Start by creating the necessary sub-tables. */
97
for (i = 0; i < NT_1CHAR_FIRST + NT_1CHAR_SIZE; i += nt_sub_size) {
98
int code = name_alloc_sub(nt);
101
while (nt->sub_next > 0)
102
name_free_sub(nt, --(nt->sub_next));
103
gs_free_object(mem, nt, "name_init(nt)");
107
for (i = -1; i < NT_1CHAR_SIZE; i++) {
108
uint ncnt = NT_1CHAR_FIRST + i;
109
uint nidx = name_count_to_index(ncnt);
110
name *pname = names_index_ptr_inline(nt, nidx);
111
name_string_t *pnstr = names_index_string_inline(nt, nidx);
114
pnstr->string_bytes = nt_1char_names,
115
pnstr->string_size = 0;
117
pnstr->string_bytes = nt_1char_names + i,
118
pnstr->string_size = 1;
119
pnstr->foreign_string = 1;
121
pname->pvalue = pv_no_defn;
123
nt->perm_count = NT_1CHAR_FIRST + NT_1CHAR_SIZE;
124
/* Reconstruct the free list. */
126
names_trace_finish(nt, NULL);
130
/* Get the allocator for the name table. */
132
names_memory(const name_table * nt)
137
/* Look up or enter a name in the table. */
138
/* Return 0 or an error code. */
139
/* The return may overlap the characters of the string! */
140
/* See iname.h for the meaning of enterflag. */
142
names_ref(name_table *nt, const byte *ptr, uint size, ref *pref, int enterflag)
145
name_string_t *pnstr;
149
/* Compute a hash for the string. */
150
/* Make a special check for 1-character names. */
153
nidx = name_count_to_index(1);
154
pname = names_index_ptr_inline(nt, nidx);
157
if (*ptr < NT_1CHAR_SIZE) {
158
uint hash = *ptr + NT_1CHAR_FIRST;
160
nidx = name_count_to_index(hash);
161
pname = names_index_ptr_inline(nt, nidx);
168
NAME_HASH(hash, hash_permutation, ptr, size);
169
phash = nt->hash + (hash & (NT_HASH_SIZE - 1));
173
for (nidx = *phash; nidx != 0;
174
nidx = name_next_index(nidx, pnstr)
176
pnstr = names_index_string_inline(nt, nidx);
177
if (pnstr->string_size == size &&
178
!memcmp_inline(ptr, pnstr->string_bytes, size)
180
pname = name_index_ptr_inline(nt, nidx);
184
/* Name was not in the table. Make a new entry. */
186
return_error(e_undefined);
187
if (size > max_name_string)
188
return_error(e_limitcheck);
191
int code = name_alloc_sub(nt);
197
pnstr = names_index_string_inline(nt, nidx);
198
if (enterflag == 1) {
199
byte *cptr = (byte *)gs_alloc_string(nt->memory, size,
200
"names_ref(string)");
203
return_error(e_VMerror);
204
memcpy(cptr, ptr, size);
205
pnstr->string_bytes = cptr;
206
pnstr->foreign_string = 0;
208
pnstr->string_bytes = ptr;
209
pnstr->foreign_string = (enterflag == 0 ? 1 : 0);
211
pnstr->string_size = size;
212
pname = name_index_ptr_inline(nt, nidx);
213
pname->pvalue = pv_no_defn;
214
nt->free = name_next_index(nidx, pnstr);
215
set_name_next_index(nidx, pnstr, *phash);
217
if_debug_name("new name", nt, nidx, &enterflag);
219
make_name(pref, nidx, pname);
223
/* Get the string for a name. */
225
names_string_ref(const name_table * nt, const ref * pnref /* t_name */ ,
226
ref * psref /* result, t_string */ )
228
const name_string_t *pnstr = names_string_inline(nt, pnref);
230
make_const_string(psref,
231
(pnstr->foreign_string ? avm_foreign | a_readonly :
232
nt->name_string_attrs),
234
(const byte *)pnstr->string_bytes);
237
/* Convert a t_string object to a name. */
238
/* Copy the executable attribute. */
240
names_from_string(name_table * nt, const ref * psref, ref * pnref)
242
int exec = r_has_attr(psref, a_executable);
243
int code = names_ref(nt, psref->value.bytes, r_size(psref), pnref, 1);
248
r_set_attrs(pnref, a_executable);
252
/* Enter a (permanently allocated) C string as a name. */
254
names_enter_string(name_table * nt, const char *str, ref * pref)
256
return names_ref(nt, (const byte *)str, strlen(str), pref, 0);
259
/* Invalidate the value cache for a name. */
261
names_invalidate_value_cache(name_table * nt, const ref * pnref)
263
pnref->value.pname->pvalue = pv_other;
266
/* Convert between names and indices. */
269
names_index(const name_table * nt, const ref * pnref)
271
return names_index_inline(nt, pnref);
274
names_index_ref(const name_table * nt, name_index_t index, ref * pnref)
276
names_index_ref_inline(nt, index, pnref);
279
names_index_ptr(const name_table * nt, name_index_t index)
281
return names_index_ptr_inline(nt, index);
284
/* Get the index of the next valid name. */
285
/* The argument is 0 or a valid index. */
286
/* Return 0 if there are no more. */
288
names_next_valid_index(name_table * nt, name_index_t nidx)
290
const name_string_sub_table_t *ssub =
291
nt->sub[nidx >> nt_log2_sub_size].strings;
292
const name_string_t *pnstr;
296
if ((nidx & nt_sub_index_mask) == 0)
297
for (;; nidx += nt_sub_size) {
298
if ((nidx >> nt_log2_sub_size) >= nt->sub_count)
300
ssub = nt->sub[nidx >> nt_log2_sub_size].strings;
304
pnstr = &ssub->strings[nidx & nt_sub_index_mask];
306
while (pnstr->string_bytes == 0);
310
/* ------ Garbage collection ------ */
312
/* Unmark all non-permanent names before a garbage collection. */
314
names_unmark_all(name_table * nt)
317
name_string_sub_table_t *ssub;
319
for (si = 0; si < nt->sub_count; ++si)
320
if ((ssub = nt->sub[si].strings) != 0) {
323
/* We can make the test much more efficient if we want.... */
324
for (i = 0; i < nt_sub_size; ++i)
325
if (name_index_to_count((si << nt_log2_sub_size) + i) >=
327
ssub->strings[i].mark = 0;
331
/* Mark a name. Return true if new mark. We export this so we can mark */
332
/* character names in the character cache. */
334
names_mark_index(name_table * nt, name_index_t nidx)
336
name_string_t *pnstr = names_index_string_inline(nt, nidx);
344
/* Get the object (sub-table) containing a name. */
345
/* The garbage collector needs this so it can relocate pointers to names. */
346
void /*obj_header_t */ *
347
names_ref_sub_table(name_table * nt, const ref * pnref)
349
/* When this procedure is called, the pointers from the name table */
350
/* to the sub-tables may or may not have been relocated already, */
351
/* so we can't use them. Instead, we have to work backwards from */
352
/* the name pointer itself. */
353
return pnref->value.pname - (r_size(pnref) & nt_sub_index_mask);
355
void /*obj_header_t */ *
356
names_index_sub_table(name_table * nt, name_index_t index)
358
return nt->sub[index >> nt_log2_sub_size].names;
360
void /*obj_header_t */ *
361
names_index_string_sub_table(name_table * nt, name_index_t index)
363
return nt->sub[index >> nt_log2_sub_size].strings;
367
* Clean up the name table after the trace/mark phase of a garbage
368
* collection, by removing names that aren't marked. gcst == NULL indicates
369
* we're doing this for initialization or restore rather than for a GC.
372
names_trace_finish(name_table * nt, gc_state_t * gcst)
374
uint *phash = &nt->hash[0];
377
for (i = 0; i < NT_HASH_SIZE; phash++, i++) {
378
name_index_t prev = 0;
380
* The following initialization is only to pacify compilers:
381
* pnprev is only referenced if prev has been set in the loop,
382
* in which case pnprev is also set.
384
name_string_t *pnprev = 0;
385
name_index_t nidx = *phash;
388
name_string_t *pnstr = names_index_string_inline(nt, nidx);
389
name_index_t next = name_next_index(nidx, pnstr);
395
if_debug_name("GC remove name", nt, nidx, NULL);
396
/* Zero out the string data for the GC. */
397
pnstr->string_bytes = 0;
398
pnstr->string_size = 0;
402
set_name_next_index(prev, pnprev, next);
407
/* Reconstruct the free list. */
409
for (i = nt->sub_count; --i >= 0;) {
410
name_sub_table *sub = nt->sub[i].names;
411
name_string_sub_table_t *ssub = nt->sub[i].strings;
414
int save_count = nt->sub_count;
416
name_scan_sub(nt, i, true);
417
if (save_count != nt->sub_count) {
418
/* name_scan_sub has released the i-th entry. */
421
if (nt->sub[i].names == 0 && gcst != 0) {
422
/* Mark the just-freed sub-table as unmarked. */
423
o_set_unmarked((obj_header_t *)sub - 1);
424
o_set_unmarked((obj_header_t *)ssub - 1);
431
/* ------ Save/restore ------ */
433
/* Clean up the name table before a restore. */
434
/* Currently, this is never called, because the name table is allocated */
435
/* in system VM. However, for a Level 1 system, we might choose to */
436
/* allocate the name table in global VM; in this case, this routine */
437
/* would be called before doing the global part of a top-level restore. */
438
/* Currently we don't make any attempt to optimize this. */
440
names_restore(name_table * nt, alloc_save_t * save)
442
/* We simply mark all names older than the save, */
443
/* and let names_trace_finish sort everything out. */
446
for (si = 0; si < nt->sub_count; ++si)
447
if (nt->sub[si].strings != 0) {
450
for (i = 0; i < nt_sub_size; ++i) {
451
name_string_t *pnstr =
452
names_index_string_inline(nt, (si << nt_log2_sub_size) + i);
454
if (pnstr->string_bytes == 0)
456
else if (pnstr->foreign_string) {
457
/* Avoid storing into a read-only name string. */
462
!alloc_is_since_save(pnstr->string_bytes, save);
465
names_trace_finish(nt, NULL);
468
/* ------ Internal procedures ------ */
470
/* Allocate the next sub-table. */
472
name_alloc_sub(name_table * nt)
474
gs_memory_t *mem = nt->memory;
475
uint sub_index = nt->sub_next;
477
name_string_sub_table_t *ssub;
479
for (;; ++sub_index) {
480
if (sub_index > nt->max_sub_count)
481
return_error(e_limitcheck);
482
if (nt->sub[sub_index].names == 0)
485
nt->sub_next = sub_index + 1;
486
if (nt->sub_next > nt->sub_count)
487
nt->sub_count = nt->sub_next;
488
sub = gs_alloc_struct(mem, name_sub_table, &st_name_sub_table,
489
"name_alloc_sub(sub-table)");
490
ssub = gs_alloc_struct(mem, name_string_sub_table_t,
491
&st_name_string_sub_table,
492
"name_alloc_sub(string sub-table)");
493
if (sub == 0 || ssub == 0) {
494
gs_free_object(mem, ssub, "name_alloc_sub(string sub-table)");
495
gs_free_object(mem, sub, "name_alloc_sub(sub-table)");
496
return_error(e_VMerror);
498
memset(sub, 0, sizeof(name_sub_table));
499
memset(ssub, 0, sizeof(name_string_sub_table_t));
500
/* The following code is only used if EXTEND_NAMES is non-zero. */
501
#if name_extension_bits > 0
502
sub->high_index = (sub_index >> (16 - nt_log2_sub_size)) << 16;
504
nt->sub[sub_index].names = sub;
505
nt->sub[sub_index].strings = ssub;
506
/* Add the newly allocated entries to the free list. */
507
/* Note that the free list will only be properly sorted if */
508
/* it was empty initially. */
509
name_scan_sub(nt, sub_index, false);
511
if (gs_debug_c('n')) { /* Print the lengths of the hash chains. */
514
for (i0 = 0; i0 < NT_HASH_SIZE; i0 += 16) {
517
dlprintf1("[n]chain %d:", i0);
518
for (i = i0; i < i0 + 16; i++) {
522
for (nidx = nt->hash[i]; nidx != 0;
523
nidx = name_next_index(nidx,
524
names_index_string_inline(nt, nidx))
536
/* Free a sub-table. */
538
name_free_sub(name_table * nt, uint sub_index)
540
gs_free_object(nt->memory, nt->sub[sub_index].strings,
541
"name_free_sub(string sub-table)");
542
gs_free_object(nt->memory, nt->sub[sub_index].names,
543
"name_free_sub(sub-table)");
544
nt->sub[sub_index].names = 0;
545
nt->sub[sub_index].strings = 0;
548
/* Scan a sub-table and add unmarked entries to the free list. */
549
/* We add the entries in decreasing count order, so the free list */
550
/* will stay sorted. If all entries are unmarked and free_empty is true, */
551
/* free the sub-table. */
553
name_scan_sub(name_table * nt, uint sub_index, bool free_empty)
555
name_string_sub_table_t *ssub = nt->sub[sub_index].strings;
556
uint free = nt->free;
557
uint nbase = sub_index << nt_log2_sub_size;
558
uint ncnt = nbase + (nt_sub_size - 1);
559
bool keep = !free_empty;
564
nbase = 1, keep = true; /* don't free name 0 */
566
uint nidx = name_count_to_index(ncnt);
567
name_string_t *pnstr = &ssub->strings[nidx & nt_sub_index_mask];
572
set_name_next_index(nidx, pnstr, free);
581
/* No marked entries, free the sub-table. */
582
name_free_sub(nt, sub_index);
583
if (sub_index == nt->sub_count - 1) {
584
/* Back up over a final run of deleted sub-tables. */
587
} while (nt->sub[sub_index].names == 0);
588
nt->sub_count = sub_index + 1;
589
if (nt->sub_next > sub_index)
590
nt->sub_next = sub_index;
591
} else if (nt->sub_next == sub_index)
596
/* Garbage collector enumeration and relocation procedures. */
598
ENUM_PTRS_BEGIN_PROC(name_table_enum_ptrs)
600
EV_CONST name_table *const nt = vptr;
603
if (i >= nt->sub_count)
606
ENUM_RETURN(nt->sub[i].strings);
608
ENUM_RETURN(nt->sub[i].names);
611
static RELOC_PTRS_WITH(name_table_reloc_ptrs, name_table *nt)
613
uint sub_count = nt->sub_count;
616
/* Now we can relocate the sub-table pointers. */
617
for (i = 0; i < sub_count; i++) {
618
RELOC_VAR(nt->sub[i].names);
619
RELOC_VAR(nt->sub[i].strings);
622
* We also need to relocate the cached value pointers.
623
* We don't do this here, but in a separate scan over the
624
* permanent dictionaries, at the very end of garbage collection.
629
static ENUM_PTRS_BEGIN_PROC(name_string_sub_enum_ptrs)
634
static RELOC_PTRS_BEGIN(name_string_sub_reloc_ptrs)
636
name_string_t *pnstr = ((name_string_sub_table_t *)vptr)->strings;
639
for (i = 0; i < nt_sub_size; ++pnstr, ++i) {
640
if (pnstr->string_bytes != 0 && !pnstr->foreign_string) {
641
gs_const_string nstr;
643
nstr.data = pnstr->string_bytes;
644
nstr.size = pnstr->string_size;
645
RELOC_CONST_STRING_VAR(nstr);
646
pnstr->string_bytes = nstr.data;
added
removed
psi/iname.c
