home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 February / PCWK0296.iso / sharewar / dos / program / gs300sr1 / gs300sr1.exe / INAME.C < prev    next >
C/C++ Source or Header  |  1994-07-27  |  14KB  |  436 lines
  1. /* Copyright (C) 1989, 1992, 1993, 1994 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* iname.c */
  20. /* Name lookup for Ghostscript interpreter */
  21. #include "memory_.h"
  22. #include "ghost.h"
  23. #include "gsstruct.h"
  24. #include "errors.h"
  25. #include "iname.h"
  26. #include "store.h"
  27.  
  28. /* In the code below, we use the hashing method described in */
  29. /* "Fast Hashing of Variable-Length Text Strings" by Peter K. Pearson, */
  30. /* pp. 677-680, CACM 33(6), June 1990. */
  31.  
  32. /* Define a pseudo-random permutation of the integers 0..255. */
  33. /* Pearson's article claims this permutation gave good results. */
  34. private const far_data byte hash_permutation[256] = {
  35.   1,  87,  49,  12, 176, 178, 102, 166, 121, 193,   6,  84, 249, 230,  44, 163,
  36.  14, 197, 213, 181, 161,  85, 218,  80,  64, 239,  24, 226, 236, 142,  38, 200,
  37. 110, 177, 104, 103, 141, 253, 255,  50,  77, 101,  81,  18,  45,  96,  31, 222,
  38.  25, 107, 190,  70,  86, 237, 240,  34,  72, 242,  20, 214, 244, 227, 149, 235,
  39.  97, 234,  57,  22,  60, 250,  82, 175, 208,   5, 127, 199, 111,  62, 135, 248,
  40. 174, 169, 211,  58,  66, 154, 106, 195, 245, 171,  17, 187, 182, 179,   0, 243,
  41. 132,  56, 148,  75, 128, 133, 158, 100, 130, 126,  91,  13, 153, 246, 216, 219,
  42. 119,  68, 223,  78,  83,  88, 201,  99, 122,  11,  92,  32, 136, 114,  52,  10,
  43. 138,  30,  48, 183, 156,  35,  61,  26, 143,  74, 251,  94, 129, 162,  63, 152,
  44. 170,   7, 115, 167, 241, 206,   3, 150,  55,  59, 151, 220,  90,  53,  23, 131,
  45. 125, 173,  15, 238,  79,  95,  89,  16, 105, 137, 225, 224, 217, 160,  37, 123,
  46. 118,  73,   2, 157,  46, 116,   9, 145, 134, 228, 207, 212, 202, 215,  69, 229,
  47.  27, 188,  67, 124, 168, 252,  42,   4,  29, 108,  21, 247,  19, 205,  39, 203,
  48. 233,  40, 186, 147, 198, 192, 155,  33, 164, 191,  98, 204, 165, 180, 117,  76,
  49. 140,  36, 210, 172,  41,  54, 159,   8, 185, 232, 113, 196, 231,  47, 146, 120,
  50.  51,  65,  28, 144, 254, 221,  93, 189, 194, 139, 112,  43,  71, 109, 184, 209
  51. };
  52.  
  53. /*
  54.  * Definitions and structure for the name table.
  55.  * The very first entry is left unused.
  56.  * 1-character names are the next nt_1char_size entries.
  57.  */
  58. #define nt_hash_size 512        /* must be a power of 2 */
  59. #define nt_1char_size 128
  60.  
  61. typedef name name_sub_table[nt_sub_size];
  62. gs_private_st_simple(st_name_sub_table, name_sub_table, "name_sub_table");
  63.  
  64. struct name_table_s {
  65.     ushort hash[nt_hash_size];
  66.     name *table[nt_sub_count];    /* name_sub_table */
  67.     uint count;
  68. #define nt_count(nt) ((nt)->count)
  69. #define set_nt_count(nt,cnt) ((nt)->count = (cnt))
  70.     gs_memory_t *memory;
  71. };
  72. /*typedef struct name_table_s name_table;*/    /* in iname.h */
  73. gs_private_st_composite(st_name_table, name_table,
  74.   "name_table", name_table_enum_ptrs, name_table_reloc_ptrs);
  75. #define nt_index_ptr(nt, index)\
  76.   ((nt)->table[(index) >> nt_log2_sub_size] + ((index) & nt_sub_index_mask))
  77.  
  78. /* The one and only name table (for now). */
  79. private name_table *the_nt;
  80. private gs_gc_root_t the_nt_root;
  81.  
  82. /* Forward references */
  83. private int name_alloc_sub(P1(name_table *));
  84.  
  85. /* Make a t_name ref out of a name * */
  86. #define make_name(pref, idx, pnm)\
  87.   make_tasv(pref, t_name, 0, idx, pname, pnm)
  88.  
  89. /* Debugging printout */
  90. #ifdef DEBUG
  91. private void
  92. name_print(const char *msg, name *pname, uint nidx, uint ncnt, int *pflag)
  93. {    const byte *ptr = pname->string_bytes;
  94.     uint ci;
  95.     dprintf1("[n]%s", msg);
  96.     if ( pflag )
  97.       dprintf1("(%d)", *pflag);
  98.     dprintf2(" (0x%lx#%u)", (ulong)pname, nidx);
  99.     for ( ci = 0; ci < pname->string_size; ci++ )
  100.       dputc(ptr[ci]);
  101.     dprintf3("(0x%lx,%u), count=%u\n",
  102.          (ulong)ptr, pname->string_size, ncnt);
  103. }
  104. #  define if_debug_name(msg, pname, nidx, ncnt, pflag)\
  105.      if ( gs_debug_c('n') ) name_print(msg, pname, nidx, ncnt, pflag)
  106. #else
  107. #  define if_debug_name(msg, pname, nidx, ncnt, pflag) DO_NOTHING
  108. #endif
  109.  
  110. /* Initialize the name table */
  111. name_table *
  112. name_init(gs_memory_t *mem)
  113. {    register uint i;
  114.     name_table *nt =
  115.       gs_alloc_struct(mem, name_table, &st_name_table, "name_init(nt)");
  116.     byte *one_char_names =
  117.       gs_alloc_string(mem, nt_1char_size, "name_init(one_char_names)");
  118.     the_nt = nt;
  119.     memset(nt, 0, sizeof(name_table));
  120.     set_nt_count(nt, 1);
  121.     nt->memory = mem;
  122.     /* Initialize the one-character names. */
  123.     for ( i = 0; i < nt_1char_size; i++ )
  124.     {    uint ncnt = i + 1;
  125.         uint nidx = name_count_to_index(ncnt);
  126.         register name *pname;
  127.         if ( nt->table[nidx >> nt_log2_sub_size] == 0 )
  128.             name_alloc_sub(nt);
  129.         pname = nt_index_ptr(nt, nidx);
  130.         set_nt_count(nt, ncnt + 1);
  131.         one_char_names[i] = i;
  132.         pname->string_size = 1;
  133.         pname->foreign_string = 0;
  134.         pname->string_bytes = one_char_names + i;
  135.         pname->pvalue = pv_no_defn;
  136.     }
  137.     /* Register the name table root. */
  138.     gs_register_struct_root(mem, &the_nt_root, (void **)&the_nt,
  139.                 "name table");
  140.     return nt;
  141. }
  142.  
  143. /* Look up or enter a name in the table. */
  144. /* Return 0 or an error code. */
  145. /* The return may overlap the characters of the string! */
  146. /* See iname.h for the meaning of enterflag. */
  147. int
  148. name_ref(const byte *ptr, uint size, ref *pref, int enterflag)
  149. {    name_table *nt = the_nt;
  150.     register name *pname;
  151.     const byte *cptr;
  152.     uint nidx, ncnt;
  153.     ushort *phash;
  154.     /* Compute a hash for the string. */
  155.     {    uint hash;
  156.         const byte *p = ptr;
  157.         uint n = size;
  158.         /* Make a special check for 1-character names. */
  159.         switch ( size )
  160.           {
  161.           case 0:
  162.             hash = 0;
  163.             break;
  164.           case 1:
  165.             if ( *p < nt_1char_size )
  166.               {    hash = *p + 1;
  167.                 nidx = name_count_to_index(hash);
  168.                 pname = nt_index_ptr(nt, nidx);
  169.                 make_name(pref, nidx, pname);
  170.                 return 0;
  171.               }
  172.           default:
  173.             hash = hash_permutation[*p++];
  174.             while ( --n > 0 )
  175.               hash = (hash << 8) |
  176.                 hash_permutation[(byte)hash ^ *p++];
  177.           }
  178.         phash = nt->hash + (hash & (nt_hash_size - 1));
  179.     }
  180.  
  181.     for ( nidx = *phash; nidx != 0; nidx = pname->next_index )
  182.     {    pname = nt_index_ptr(nt, nidx);
  183.         if ( pname->string_size == size &&
  184.              !memcmp_inline(ptr, pname->string_bytes, size)
  185.            )
  186.         {    make_name(pref, nidx, pname);
  187.             return 0;
  188.         }
  189.     }
  190.     /* Name was not in the table.  Make a new entry. */
  191.     if ( enterflag < 0 )
  192.         return_error(e_undefined);
  193.     ncnt = nt_count(nt);
  194.     if ( !(ncnt & (nt_sub_size - 1)) )
  195.        {    int code = name_alloc_sub(nt);
  196.         if ( code < 0 ) return code;
  197.        }
  198.     nidx = name_count_to_index(ncnt);
  199.     pname = nt_index_ptr(nt, nidx);
  200.     if ( enterflag == 1 )
  201.     {    cptr = (const byte *)gs_alloc_string(nt->memory, size,
  202.                              "name_ref(string)");
  203.         if ( cptr == 0 )
  204.           {    /* If we just allocated a sub-table, deallocate it */
  205.             /* before bailing out. */
  206.             if ( !(ncnt & (nt_sub_size - 1)) )
  207.               gs_free_object(nt->memory,
  208.                      nt->table[ncnt >> nt_log2_sub_size],
  209.                      "name_ref(sub_table)");
  210.             return_error(e_VMerror);
  211.           }
  212.         memcpy((byte *)cptr, ptr, size);
  213.         pname->foreign_string = 0;
  214.     }
  215.     else
  216.     {    cptr = ptr;
  217.         pname->foreign_string = (enterflag == 0 ? 1 : 0);
  218.     }
  219.     pname->string_size = size;
  220.     pname->string_bytes = cptr;
  221.     pname->pvalue = pv_no_defn;
  222.     pname->next_index = *phash;
  223.     *phash = nidx;
  224.     set_nt_count(nt, ncnt + 1);
  225.     make_name(pref, nidx, pname);
  226.     if_debug_name("new name", pname, nidx, name_index_to_count(nidx),
  227.               &enterflag);
  228.     return 0;
  229. }
  230.  
  231. /* Get the string for a name. */
  232. void
  233. name_string_ref(const ref *pnref /* t_name */,
  234.   ref *psref /* result, t_string */)
  235. {    name *pname = pnref->value.pname;
  236.     make_const_string(psref,
  237.               (pname->foreign_string ?
  238.                a_readonly | a_foreign : a_readonly),
  239.               pname->string_size,
  240.               (const byte *)pname->string_bytes);
  241. }
  242.  
  243. /* Convert a t_string object to a name. */
  244. /* Copy the executable attribute. */
  245. int
  246. name_from_string(const ref *psref, ref *pnref)
  247. {    int exec = r_has_attr(psref, a_executable);
  248.     int code = name_ref(psref->value.bytes, r_size(psref), pnref, 1);
  249.     if ( code < 0 )
  250.       return code;
  251.     if ( exec )
  252.       r_set_attrs(pnref, a_executable);
  253.     return code;
  254. }
  255.  
  256. /* Enter a (permanently allocated) C string as a name. */
  257. int
  258. name_enter_string(const char *str, ref *pref)
  259. {    return name_ref((const byte *)str, strlen(str), pref, 0);
  260. }
  261.  
  262. /* Get the name with a given index. */
  263. void
  264. name_index_ref(uint index, ref *pnref)
  265. {    make_name(pnref, index, nt_index_ptr(the_nt, index));
  266. }
  267. name *
  268. name_index_ptr(uint index)
  269. {    return nt_index_ptr(the_nt, index);
  270. }
  271.  
  272. /* Get the current name count. */
  273. uint
  274. name_count(void)
  275. {    return nt_count(the_nt);
  276. }
  277.  
  278. /* Get the allocator for names. */
  279. gs_memory_t *
  280. name_memory(void)
  281. {    return the_nt->memory;
  282. }
  283.  
  284. /* Mark a name.  Return true if new mark.  We export this so we can mark */
  285. /* character names in the character cache. */
  286. bool
  287. name_mark_index(uint nidx)
  288. {    name *pname = name_index_ptr(nidx);
  289.     if ( pname->mark )
  290.       return false;
  291.     pname->mark = 1;
  292.     return true;
  293. }
  294.  
  295. /* Get the object (sub-table) containing a name. */
  296. /* The garbage collector needs this so it can relocate pointers to names. */
  297. void/*obj_header_t*/ *
  298. name_ref_sub_table(ref *pnref)
  299. {    /* When this procedure is called, the pointers from the name table */
  300.     /* to the sub-tables may or may not have been relocated already, */
  301.     /* so we can't use them.  Instead, we have to work backwards from */
  302.     /* the name pointer itself. */
  303.     return pnref->value.pname - (name_index(pnref) & nt_sub_index_mask);
  304. }
  305. void/*obj_header_t*/ *
  306. name_index_ptr_sub_table(uint index, name *pname)
  307. {    return pname - (index & nt_sub_index_mask);
  308. }
  309.  
  310. /* Clean up the name table before a restore. */
  311. /* The count will be reset, and added subtables will be freed. */
  312. /* All we have to do is remove initial entries from the hash chains, */
  313. /* since we know they are linked in decreasing index order */
  314. /* (by sub-table, but not within each sub-table.) */
  315. /* Some spurious non-zero entries may remain in the subtable table, */
  316. /* but this doesn't matter since they will never be accessed. */
  317. void
  318. name_restore(uint old_count)
  319. {    name_table *nt = the_nt;
  320.     ushort *phash = &nt->hash[0];
  321.     uint old_sub = old_count & -nt_sub_size;
  322.     register uint i;
  323.     /* Often no new names will have been created since the save. */
  324.     /* This is worth checking for. */
  325.     if ( old_count >= nt_count(nt) )
  326.         return;
  327.     for ( i = 0; i < nt_hash_size; phash++, i++ )
  328.        {    register ushort *pnh = phash;
  329.         while ( *pnh >= old_sub )
  330.            {    if ( name_index_to_count(*pnh) < old_count )
  331.               pnh = &nt_index_ptr(nt, *pnh)->next_index;
  332.             else
  333.                {
  334. #ifdef DEBUG
  335.                 if ( gs_debug_c('n') | gs_debug_c('U') )
  336.                   name_print("restore remove name",
  337.                          nt_index_ptr(nt, *pnh), *pnh,
  338.                          name_index_to_count(*pnh),
  339.                          NULL);
  340. #endif
  341.                 *pnh = nt_index_ptr(nt, *pnh)->next_index;
  342.                }
  343.            }
  344.        }
  345.     set_nt_count(nt, old_count);
  346. }
  347.  
  348. /* Clean up the name table after a garbage collection, by removing */
  349. /* names that aren't marked, and relocating name string pointers. */
  350. /* Currently we don't reuse the deleted name slots, */
  351. /* so some space is permanently lost. */
  352. void
  353. name_gc_cleanup(gc_state_t *gcst)
  354. {    name_table *nt = the_nt;
  355.     ushort *phash = &nt->hash[0];
  356.     register uint i;
  357.     for ( i = 0; i < nt_hash_size; phash++, i++ )
  358.     {    register ushort *pnh = phash;
  359.         while ( *pnh != 0 )
  360.         {    name *pname = nt_index_ptr(nt, *pnh);
  361.             if ( pname->mark )
  362.             {    if ( !pname->foreign_string )
  363.                   pname->string_bytes =
  364.                     gs_reloc_const_string_ptr(pname->string_bytes, gcst);
  365.                 pnh = &pname->next_index;
  366.             }
  367.             else
  368.             {    if_debug_name("GC remove name", pname, *pnh,
  369.                           name_index_to_count(*pnh),
  370.                           NULL);
  371.                 *pnh = pname->next_index;
  372.             }
  373.         }
  374.     }
  375. }
  376.  
  377.  
  378. /* ------ Internal procedures ------ */
  379.  
  380. /* Allocate the next sub-table. */
  381. private int
  382. name_alloc_sub(name_table *nt)
  383. {    name *sub = gs_alloc_struct(nt->memory, name, &st_name_sub_table,
  384.                     "name_alloc_sub");
  385.     if ( sub == 0 )
  386.         return_error(e_VMerror);
  387.     memset(sub, 0, sizeof(name_sub_table));
  388.     nt->table[nt_count(nt) >> nt_log2_sub_size] = sub;
  389. #ifdef DEBUG
  390.     if ( gs_debug_c('n') )
  391.       {    /* Print the lengths of the hash chains. */
  392.         int i0;
  393.         for ( i0 = 0; i0 < nt_hash_size; i0 += 16 )
  394.           {    int i;
  395.             dprintf1("[n]chain %d:", i0);
  396.             for ( i = i0; i < i0 + 16; i++ )
  397.               {    int n = 0;
  398.                 uint nidx;
  399.                 for ( nidx = nt->hash[i]; nidx != 0;
  400.                       nidx = nt_index_ptr(nt, nidx)->next_index
  401.                     )
  402.                   n++;
  403.                 dprintf1(" %d", n);
  404.               }
  405.             dputc('\n');
  406.           }
  407.       }
  408. #endif
  409.     return 0;
  410. }
  411.  
  412. /* Garbage collector enumeration and relocation procedures. */
  413. #define ntptr ((name_table *)vptr)
  414. private ENUM_PTRS_BEGIN_PROC(name_table_enum_ptrs) {
  415.     if ( index > (nt_count(ntptr)  - 1) >> nt_log2_sub_size )
  416.         return 0;
  417.     *pep = ntptr->table[index];
  418.     return ptr_struct_type;
  419. } ENUM_PTRS_END_PROC
  420. private RELOC_PTRS_BEGIN(name_table_reloc_ptrs) {
  421.     name_sub_table **sub = (name_sub_table **)ntptr->table;
  422.     uint i;
  423.     uint sub_count = (nt_count(ntptr) - 1) >> nt_log2_sub_size;
  424.     /* For now, we just clear the cache pointers in names. */
  425.     /* We should relocate them instead! */
  426.     for ( i = 0; i < nt_count(ntptr); i++ )
  427.     {    uint nidx = name_count_to_index(i);
  428.         name *pname = nt_index_ptr(ntptr, nidx);
  429.         if ( pv_valid(pname->pvalue) )
  430.             pname->pvalue = pv_other;
  431.     }
  432.     /* Now we can relocate the sub-table pointers. */
  433.     for ( i = 0; i <= sub_count; i++, sub++ )
  434.         *sub = gs_reloc_struct_ptr(*sub, gcst);
  435. } RELOC_PTRS_END
  436.