123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651 |
- /* Copyright (C) 1989, 1995, 1997, 1998, 1999 Aladdin Enterprises. All rights reserved.
-
- This file is part of AFPL Ghostscript.
-
- AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND. No author or
- distributor accepts any responsibility for the consequences of using it, or
- for whether it serves any particular purpose or works at all, unless he or
- she says so in writing. Refer to the Aladdin Free Public License (the
- "License") for full details.
-
- Every copy of AFPL Ghostscript must include a copy of the License, normally
- in a plain ASCII text file named PUBLIC. The License grants you the right
- to copy, modify and redistribute AFPL Ghostscript, but only under certain
- conditions described in the License. Among other things, the License
- requires that the copyright notice and this notice be preserved on all
- copies.
- */
- /*$Id: iname.c,v 1.3 2000/09/19 19:00:45 lpd Exp $ */
- /* Name lookup for Ghostscript interpreter */
- #include "memory_.h"
- #include "string_.h"
- #include "ghost.h"
- #include "gsstruct.h"
- #include "gxobj.h" /* for o_set_unmarked */
- #include "errors.h"
- #include "inamedef.h"
- #include "imemory.h" /* for isave.h */
- #include "isave.h"
- #include "store.h"
- /* Public values */
- const uint name_max_string = max_name_string;
- /* Define the permutation table for name hashing. */
- private const byte hash_permutation[256] = {
- NAME_HASH_PERMUTATION_DATA
- };
- /* Define the data for the 1-character names. */
- private const byte nt_1char_names[NT_1CHAR_SIZE] = {
- NT_1CHAR_NAMES_DATA
- };
- /* Structure descriptors */
- gs_private_st_simple(st_name_sub_table, name_sub_table, "name_sub_table");
- gs_private_st_composite(st_name_string_sub_table, name_string_sub_table_t,
- "name_string_sub_table_t",
- name_string_sub_enum_ptrs, name_string_sub_reloc_ptrs);
- gs_private_st_composite(st_name_table, name_table, "name_table",
- name_table_enum_ptrs, name_table_reloc_ptrs);
- /* Forward references */
- private int name_alloc_sub(P1(name_table *));
- private void name_free_sub(P2(name_table *, uint));
- private void name_scan_sub(P3(name_table *, uint, bool));
- /* Debugging printout */
- #ifdef DEBUG
- private void
- name_print(const char *msg, const name_table *nt, uint nidx, const int *pflag)
- {
- const name_string_t *pnstr = names_index_string_inline(nt, nidx);
- const name *pname = names_index_ptr_inline(nt, nidx);
- const byte *str = pnstr->string_bytes;
- dlprintf1("[n]%s", msg);
- if (pflag)
- dprintf1("(%d)", *pflag);
- dprintf2(" (0x%lx#%u)", (ulong)pname, nidx);
- debug_print_string(str, pnstr->string_size);
- dprintf2("(0x%lx,%u)\n", (ulong)str, pnstr->string_size);
- }
- # define if_debug_name(msg, nt, nidx, pflag)\
- if ( gs_debug_c('n') ) name_print(msg, nt, nidx, pflag)
- #else
- # define if_debug_name(msg, nt, nidx, pflag) DO_NOTHING
- #endif
- /* Initialize a name table */
- name_table *
- names_init(ulong count, gs_ref_memory_t *imem)
- {
- gs_memory_t *mem = (gs_memory_t *)imem;
- name_table *nt;
- int i;
- if (count == 0)
- count = max_name_count + 1L;
- else if (count - 1 > max_name_count)
- return 0;
- nt = gs_alloc_struct(mem, name_table, &st_name_table, "name_init(nt)");
- if (nt == 0)
- return 0;
- memset(nt, 0, sizeof(name_table));
- nt->max_sub_count =
- ((count - 1) | nt_sub_index_mask) >> nt_log2_sub_size;
- nt->name_string_attrs = imemory_space(imem) | a_readonly;
- nt->memory = mem;
- /* Initialize the one-character names. */
- /* Start by creating the necessary sub-tables. */
- for (i = 0; i < NT_1CHAR_FIRST + NT_1CHAR_SIZE; i += nt_sub_size) {
- int code = name_alloc_sub(nt);
- if (code < 0) {
- while (nt->sub_next > 0)
- name_free_sub(nt, --(nt->sub_next));
- gs_free_object(mem, nt, "name_init(nt)");
- return 0;
- }
- }
- for (i = -1; i < NT_1CHAR_SIZE; i++) {
- uint ncnt = NT_1CHAR_FIRST + i;
- uint nidx = name_count_to_index(ncnt);
- name *pname = names_index_ptr_inline(nt, nidx);
- name_string_t *pnstr = names_index_string_inline(nt, nidx);
- if (i < 0)
- pnstr->string_bytes = nt_1char_names,
- pnstr->string_size = 0;
- else
- pnstr->string_bytes = nt_1char_names + i,
- pnstr->string_size = 1;
- pnstr->foreign_string = 1;
- pnstr->mark = 1;
- pname->pvalue = pv_no_defn;
- }
- nt->perm_count = NT_1CHAR_FIRST + NT_1CHAR_SIZE;
- /* Reconstruct the free list. */
- nt->free = 0;
- names_trace_finish(nt, NULL);
- return nt;
- }
- /* Get the allocator for the name table. */
- gs_memory_t *
- names_memory(const name_table * nt)
- {
- return nt->memory;
- }
- /* Look up or enter a name in the table. */
- /* Return 0 or an error code. */
- /* The return may overlap the characters of the string! */
- /* See iname.h for the meaning of enterflag. */
- int
- names_ref(name_table *nt, const byte *ptr, uint size, ref *pref, int enterflag)
- {
- name *pname;
- name_string_t *pnstr;
- uint nidx;
- uint *phash;
- /* Compute a hash for the string. */
- /* Make a special check for 1-character names. */
- switch (size) {
- case 0:
- nidx = name_count_to_index(1);
- pname = names_index_ptr_inline(nt, nidx);
- goto mkn;
- case 1:
- if (*ptr < NT_1CHAR_SIZE) {
- uint hash = *ptr + NT_1CHAR_FIRST;
- nidx = name_count_to_index(hash);
- pname = names_index_ptr_inline(nt, nidx);
- goto mkn;
- }
- /* falls through */
- default: {
- uint hash;
- NAME_HASH(hash, hash_permutation, ptr, size);
- phash = nt->hash + (hash & (NT_HASH_SIZE - 1));
- }
- }
- for (nidx = *phash; nidx != 0;
- nidx = name_next_index(nidx, pnstr)
- ) {
- pnstr = names_index_string_inline(nt, nidx);
- if (pnstr->string_size == size &&
- !memcmp_inline(ptr, pnstr->string_bytes, size)
- ) {
- pname = name_index_ptr_inline(nt, nidx);
- goto mkn;
- }
- }
- /* Name was not in the table. Make a new entry. */
- if (enterflag < 0)
- return_error(e_undefined);
- if (size > max_name_string)
- return_error(e_limitcheck);
- nidx = nt->free;
- if (nidx == 0) {
- int code = name_alloc_sub(nt);
- if (code < 0)
- return code;
- nidx = nt->free;
- }
- pnstr = names_index_string_inline(nt, nidx);
- if (enterflag == 1) {
- byte *cptr = (byte *)gs_alloc_string(nt->memory, size,
- "names_ref(string)");
- if (cptr == 0)
- return_error(e_VMerror);
- memcpy(cptr, ptr, size);
- pnstr->string_bytes = cptr;
- pnstr->foreign_string = 0;
- } else {
- pnstr->string_bytes = ptr;
- pnstr->foreign_string = (enterflag == 0 ? 1 : 0);
- }
- pnstr->string_size = size;
- pname = name_index_ptr_inline(nt, nidx);
- pname->pvalue = pv_no_defn;
- nt->free = name_next_index(nidx, pnstr);
- set_name_next_index(nidx, pnstr, *phash);
- *phash = nidx;
- if_debug_name("new name", nt, nidx, &enterflag);
- mkn:
- make_name(pref, nidx, pname);
- return 0;
- }
- /* Get the string for a name. */
- void
- names_string_ref(const name_table * nt, const ref * pnref /* t_name */ ,
- ref * psref /* result, t_string */ )
- {
- const name_string_t *pnstr = names_string_inline(nt, pnref);
- make_const_string(psref,
- (pnstr->foreign_string ? avm_foreign | a_readonly :
- nt->name_string_attrs),
- pnstr->string_size,
- (const byte *)pnstr->string_bytes);
- }
- /* Convert a t_string object to a name. */
- /* Copy the executable attribute. */
- int
- names_from_string(name_table * nt, const ref * psref, ref * pnref)
- {
- int exec = r_has_attr(psref, a_executable);
- int code = names_ref(nt, psref->value.bytes, r_size(psref), pnref, 1);
- if (code < 0)
- return code;
- if (exec)
- r_set_attrs(pnref, a_executable);
- return code;
- }
- /* Enter a (permanently allocated) C string as a name. */
- int
- names_enter_string(name_table * nt, const char *str, ref * pref)
- {
- return names_ref(nt, (const byte *)str, strlen(str), pref, 0);
- }
- /* Invalidate the value cache for a name. */
- void
- names_invalidate_value_cache(name_table * nt, const ref * pnref)
- {
- pnref->value.pname->pvalue = pv_other;
- }
- /* Convert between names and indices. */
- #undef names_index
- name_index_t
- names_index(const name_table * nt, const ref * pnref)
- {
- return names_index_inline(nt, pnref);
- }
- void
- names_index_ref(const name_table * nt, name_index_t index, ref * pnref)
- {
- names_index_ref_inline(nt, index, pnref);
- }
- name *
- names_index_ptr(const name_table * nt, name_index_t index)
- {
- return names_index_ptr_inline(nt, index);
- }
- /* Get the index of the next valid name. */
- /* The argument is 0 or a valid index. */
- /* Return 0 if there are no more. */
- name_index_t
- names_next_valid_index(name_table * nt, name_index_t nidx)
- {
- const name_string_sub_table_t *ssub =
- nt->sub[nidx >> nt_log2_sub_size].strings;
- const name_string_t *pnstr;
- do {
- ++nidx;
- if ((nidx & nt_sub_index_mask) == 0)
- for (;; nidx += nt_sub_size) {
- if ((nidx >> nt_log2_sub_size) >= nt->sub_count)
- return 0;
- ssub = nt->sub[nidx >> nt_log2_sub_size].strings;
- if (ssub != 0)
- break;
- }
- pnstr = &ssub->strings[nidx & nt_sub_index_mask];
- }
- while (pnstr->string_bytes == 0);
- return nidx;
- }
- /* ------ Garbage collection ------ */
- /* Unmark all non-permanent names before a garbage collection. */
- void
- names_unmark_all(name_table * nt)
- {
- uint si;
- name_string_sub_table_t *ssub;
- for (si = 0; si < nt->sub_count; ++si)
- if ((ssub = nt->sub[si].strings) != 0) {
- uint i;
- /* We can make the test much more efficient if we want.... */
- for (i = 0; i < nt_sub_size; ++i)
- if (name_index_to_count((si << nt_log2_sub_size) + i) >=
- nt->perm_count)
- ssub->strings[i].mark = 0;
- }
- }
- /* Mark a name. Return true if new mark. We export this so we can mark */
- /* character names in the character cache. */
- bool
- names_mark_index(name_table * nt, name_index_t nidx)
- {
- name_string_t *pnstr = names_index_string_inline(nt, nidx);
- if (pnstr->mark)
- return false;
- pnstr->mark = 1;
- return true;
- }
- /* Get the object (sub-table) containing a name. */
- /* The garbage collector needs this so it can relocate pointers to names. */
- void /*obj_header_t */ *
- names_ref_sub_table(name_table * nt, const ref * pnref)
- {
- /* When this procedure is called, the pointers from the name table */
- /* to the sub-tables may or may not have been relocated already, */
- /* so we can't use them. Instead, we have to work backwards from */
- /* the name pointer itself. */
- return pnref->value.pname - (r_size(pnref) & nt_sub_index_mask);
- }
- void /*obj_header_t */ *
- names_index_sub_table(name_table * nt, name_index_t index)
- {
- return nt->sub[index >> nt_log2_sub_size].names;
- }
- void /*obj_header_t */ *
- names_index_string_sub_table(name_table * nt, name_index_t index)
- {
- return nt->sub[index >> nt_log2_sub_size].strings;
- }
- /*
- * Clean up the name table after the trace/mark phase of a garbage
- * collection, by removing names that aren't marked. gcst == NULL indicates
- * we're doing this for initialization or restore rather than for a GC.
- */
- void
- names_trace_finish(name_table * nt, gc_state_t * gcst)
- {
- uint *phash = &nt->hash[0];
- uint i;
- for (i = 0; i < NT_HASH_SIZE; phash++, i++) {
- name_index_t prev = 0;
- /*
- * The following initialization is only to pacify compilers:
- * pnprev is only referenced if prev has been set in the loop,
- * in which case pnprev is also set.
- */
- name_string_t *pnprev = 0;
- name_index_t nidx = *phash;
- while (nidx != 0) {
- name_string_t *pnstr = names_index_string_inline(nt, nidx);
- name_index_t next = name_next_index(nidx, pnstr);
- if (pnstr->mark) {
- prev = nidx;
- pnprev = pnstr;
- } else {
- if_debug_name("GC remove name", nt, nidx, NULL);
- /* Zero out the string data for the GC. */
- pnstr->string_bytes = 0;
- pnstr->string_size = 0;
- if (prev == 0)
- *phash = next;
- else
- set_name_next_index(prev, pnprev, next);
- }
- nidx = next;
- }
- }
- /* Reconstruct the free list. */
- nt->free = 0;
- for (i = nt->sub_count; i--;) {
- name_sub_table *sub = nt->sub[i].names;
- name_string_sub_table_t *ssub = nt->sub[i].strings;
- if (sub != 0) {
- name_scan_sub(nt, i, true);
- if (nt->sub[i].names == 0 && gcst != 0) {
- /* Mark the just-freed sub-table as unmarked. */
- o_set_unmarked((obj_header_t *)sub - 1);
- o_set_unmarked((obj_header_t *)ssub - 1);
- }
- }
- if (i == 0)
- break;
- }
- nt->sub_next = 0;
- }
- /* ------ Save/restore ------ */
- /* Clean up the name table before a restore. */
- /* Currently, this is never called, because the name table is allocated */
- /* in system VM. However, for a Level 1 system, we might choose to */
- /* allocate the name table in global VM; in this case, this routine */
- /* would be called before doing the global part of a top-level restore. */
- /* Currently we don't make any attempt to optimize this. */
- void
- names_restore(name_table * nt, alloc_save_t * save)
- {
- /* We simply mark all names older than the save, */
- /* and let names_trace_finish sort everything out. */
- uint si;
- for (si = 0; si < nt->sub_count; ++si)
- if (nt->sub[si].strings != 0) {
- uint i;
- for (i = 0; i < nt_sub_size; ++i) {
- name_string_t *pnstr =
- names_index_string_inline(nt, (si << nt_log2_sub_size) + i);
- if (pnstr->string_bytes == 0)
- pnstr->mark = 0;
- else if (pnstr->foreign_string) {
- /* Avoid storing into a read-only name string. */
- if (!pnstr->mark)
- pnstr->mark = 1;
- } else
- pnstr->mark =
- !alloc_is_since_save(pnstr->string_bytes, save);
- }
- }
- names_trace_finish(nt, NULL);
- }
- /* ------ Internal procedures ------ */
- /* Allocate the next sub-table. */
- private int
- name_alloc_sub(name_table * nt)
- {
- gs_memory_t *mem = nt->memory;
- uint sub_index = nt->sub_next;
- name_sub_table *sub;
- name_string_sub_table_t *ssub;
- for (;; ++sub_index) {
- if (sub_index > nt->max_sub_count)
- return_error(e_limitcheck);
- if (nt->sub[sub_index].names == 0)
- break;
- }
- nt->sub_next = sub_index + 1;
- if (nt->sub_next > nt->sub_count)
- nt->sub_count = nt->sub_next;
- sub = gs_alloc_struct(mem, name_sub_table, &st_name_sub_table,
- "name_alloc_sub(sub-table)");
- ssub = gs_alloc_struct(mem, name_string_sub_table_t,
- &st_name_string_sub_table,
- "name_alloc_sub(string sub-table)");
- if (sub == 0 || ssub == 0) {
- gs_free_object(mem, ssub, "name_alloc_sub(string sub-table)");
- gs_free_object(mem, sub, "name_alloc_sub(sub-table)");
- return_error(e_VMerror);
- }
- memset(sub, 0, sizeof(name_sub_table));
- memset(ssub, 0, sizeof(name_string_sub_table_t));
- /* The following code is only used if EXTEND_NAMES is non-zero. */
- #if name_extension_bits > 0
- sub->high_index = (sub_index >> (16 - nt_log2_sub_size)) << 16;
- #endif
- nt->sub[sub_index].names = sub;
- nt->sub[sub_index].strings = ssub;
- /* Add the newly allocated entries to the free list. */
- /* Note that the free list will only be properly sorted if */
- /* it was empty initially. */
- name_scan_sub(nt, sub_index, false);
- #ifdef DEBUG
- if (gs_debug_c('n')) { /* Print the lengths of the hash chains. */
- int i0;
- for (i0 = 0; i0 < NT_HASH_SIZE; i0 += 16) {
- int i;
- dlprintf1("[n]chain %d:", i0);
- for (i = i0; i < i0 + 16; i++) {
- int n = 0;
- uint nidx;
- for (nidx = nt->hash[i]; nidx != 0;
- nidx = name_next_index(nidx,
- names_index_string_inline(nt, nidx))
- )
- n++;
- dprintf1(" %d", n);
- }
- dputc('\n');
- }
- }
- #endif
- return 0;
- }
- /* Free a sub-table. */
- private void
- name_free_sub(name_table * nt, uint sub_index)
- {
- gs_free_object(nt->memory, nt->sub[sub_index].strings,
- "name_free_sub(string sub-table)");
- gs_free_object(nt->memory, nt->sub[sub_index].names,
- "name_free_sub(sub-table)");
- nt->sub[sub_index].names = 0;
- nt->sub[sub_index].strings = 0;
- }
- /* Scan a sub-table and add unmarked entries to the free list. */
- /* We add the entries in decreasing count order, so the free list */
- /* will stay sorted. If all entries are unmarked and free_empty is true, */
- /* free the sub-table. */
- private void
- name_scan_sub(name_table * nt, uint sub_index, bool free_empty)
- {
- name_string_sub_table_t *ssub = nt->sub[sub_index].strings;
- uint free = nt->free;
- uint nbase = sub_index << nt_log2_sub_size;
- uint ncnt = nbase + (nt_sub_size - 1);
- bool keep = !free_empty;
- if (ssub == 0)
- return;
- if (nbase == 0)
- nbase = 1, keep = true; /* don't free name 0 */
- for (;; --ncnt) {
- uint nidx = name_count_to_index(ncnt);
- name_string_t *pnstr = &ssub->strings[nidx & nt_sub_index_mask];
- if (pnstr->mark)
- keep = true;
- else {
- set_name_next_index(nidx, pnstr, free);
- free = nidx;
- }
- if (ncnt == nbase)
- break;
- }
- if (keep)
- nt->free = free;
- else {
- /* No marked entries, free the sub-table. */
- name_free_sub(nt, sub_index);
- if (sub_index == nt->sub_count - 1) {
- /* Back up over a final run of deleted sub-tables. */
- do {
- --sub_index;
- } while (nt->sub[sub_index].names == 0);
- nt->sub_count = sub_index + 1;
- if (nt->sub_next > sub_index)
- nt->sub_next = sub_index;
- } else if (nt->sub_next == sub_index)
- nt->sub_next--;
- }
- }
- /* Garbage collector enumeration and relocation procedures. */
- private
- ENUM_PTRS_BEGIN_PROC(name_table_enum_ptrs)
- {
- EV_CONST name_table *const nt = vptr;
- uint i = index >> 1;
- if (i >= nt->sub_count)
- return 0;
- if (index & 1)
- ENUM_RETURN(nt->sub[i].strings);
- else
- ENUM_RETURN(nt->sub[i].names);
- }
- ENUM_PTRS_END_PROC
- private RELOC_PTRS_WITH(name_table_reloc_ptrs, name_table *nt)
- {
- uint sub_count = nt->sub_count;
- uint i;
- /* Now we can relocate the sub-table pointers. */
- for (i = 0; i < sub_count; i++) {
- RELOC_VAR(nt->sub[i].names);
- RELOC_VAR(nt->sub[i].strings);
- }
- /*
- * We also need to relocate the cached value pointers.
- * We don't do this here, but in a separate scan over the
- * permanent dictionaries, at the very end of garbage collection.
- */
- }
- RELOC_PTRS_END
- private ENUM_PTRS_BEGIN_PROC(name_string_sub_enum_ptrs)
- {
- return 0;
- }
- ENUM_PTRS_END_PROC
- private RELOC_PTRS_BEGIN(name_string_sub_reloc_ptrs)
- {
- name_string_t *pnstr = ((name_string_sub_table_t *)vptr)->strings;
- uint i;
- for (i = 0; i < nt_sub_size; ++pnstr, ++i) {
- if (pnstr->string_bytes != 0 && !pnstr->foreign_string) {
- gs_const_string nstr;
- nstr.data = pnstr->string_bytes;
- nstr.size = pnstr->string_size;
- RELOC_CONST_STRING_VAR(nstr);
- pnstr->string_bytes = nstr.data;
- }
- }
- }
- RELOC_PTRS_END
|