From f3a6e4fa5b40f2ae09e43b4fe0d46244e96f6505 Mon Sep 17 00:00:00 2001 From: Ian Romanick Date: Sat, 26 Feb 2005 01:09:35 +0000 Subject: Fairly significant changes to enums.c and the way it is generated. enums.c now contains 3 static tables. The first table is a single, large string of all the enum names. The second table is an array, sorted by enum name, of indexes to the string table and the matching enum value. The extra string table is used to eliminate relocs (and save space) in the compiled file. The third table is an array, sorted by enum value, of indexes into the second table. The [name, enum] table contains all of the enums, but the table sorted by enum-value does not. This table contains one entry per enum value. For enum values that have multiple names (e.g., 0x84C0 has GL_TEXTURE0_ARB and GL_TEXTURE0), only an index to the "best" name will appear in the table. gl_enums.py gives precedence to "core" GL versions of names, followed by ARB versions, followed by EXT versions, followed, finally, by vendor versions (i.e., anything that doesn't fall into one of the previous categories). By filtering the unneeded elements from this table, not only can we guarantee determinism in the generated tables, but we save 364 elements in the table. The optimizations outlined above reduced the size of the stripped enums.o (on x86) from ~80KB to ~53KB. The internal organization of gl_enums.py was also heavily modified. Previously enums were stored in an unsorted list as [value, name] tuples (basically). This list was then sorted, using a user-specified compare function (i.e., VERY slow in most Python implementations) to generate a table sorted by enum value. It was then sorted again, using another user-specified compare function, to generate a table sorted by name. Enums are now stored in a dictionary, called enum_table, with the enum value as the key. Each dictionary element is a list of [name, priority] pairs. The priority is determined as described above. The table sorted by enum value is generated by sorting the keys of enum_table (i.e., very fast). The tables sorted by name are generated by creating a list, called name_table, of [name, enum value] pairs. This table can then be sorted by doing name_table.sort() (i.e., very fast). The result is a fair amount more Python code, but execution time was reduced from ~14 seconds to ~2 seconds. --- src/mesa/glapi/gl_XML.py | 3 - src/mesa/glapi/gl_enums.py | 164 ++++++++++++++++++++++++++++++++++----------- 2 files changed, 124 insertions(+), 43 deletions(-) (limited to 'src/mesa/glapi') diff --git a/src/mesa/glapi/gl_XML.py b/src/mesa/glapi/gl_XML.py index f096d3d953..b2e3cd4325 100644 --- a/src/mesa/glapi/gl_XML.py +++ b/src/mesa/glapi/gl_XML.py @@ -503,7 +503,6 @@ class FilterGLAPISpecBase(saxutils.XMLFilterBase): self.factory = glItemFactory() self.header_tag = None self.undef_list = [] - self.enums = [] def find_type(self,type_name): @@ -588,8 +587,6 @@ class FilterGLAPISpecBase(saxutils.XMLFilterBase): self.xref[obj.name] = index elif object_type == "type": self.types[obj.name] = obj - elif object_type == "enum": - self.enums.append(obj) return diff --git a/src/mesa/glapi/gl_enums.py b/src/mesa/glapi/gl_enums.py index 776f814b5b..2237b7d148 100644 --- a/src/mesa/glapi/gl_enums.py +++ b/src/mesa/glapi/gl_enums.py @@ -41,6 +41,7 @@ class PrintGlEnums(gl_XML.FilterGLAPISpecBase): gl_XML.FilterGLAPISpecBase.__init__(self) self.license = license.bsd_license_template % ( \ """Copyright (C) 1999-2005 Brian Paul All Rights Reserved.""", "BRIAN PAUL") + self.enum_table = {} def printRealHeader(self): @@ -49,32 +50,46 @@ class PrintGlEnums(gl_XML.FilterGLAPISpecBase): print '#include "imports.h"' print '' print 'typedef struct {' - print ' const char *c;' + print ' size_t offset;' print ' int n;' print '} enum_elt;' print '' - print 'static const enum_elt all_enums[] =' - print '{' return def printBody(self): print """ -}; - #define Elements(x) sizeof(x)/sizeof(*x) typedef int (*cfunc)(const void *, const void *); -/* note the extra level of indirection +/** + * Compare a key name to an element in the \c all_enums array. + * + * \c bsearch always passes the key as the first parameter and the pointer + * to the array element as the second parameter. We can elimiate some + * extra work by taking advantage of that fact. + * + * \param a Pointer to the desired enum name. + * \param b Pointer to an element of the \c all_enums array. */ -static int compar_name( const enum_elt **a, const enum_elt **b ) +static int compar_name( const char *a, const enum_elt *b ) { - return _mesa_strcmp((*a)->c, (*b)->c); + return _mesa_strcmp( a, & enum_string_table[ b->offset ] ); } -static int compar_nr( const enum_elt *a, const enum_elt *b ) +/** + * Compare a key enum value to an element in the \c all_enums array. + * + * \c bsearch always passes the key as the first parameter and the pointer + * to the array element as the second parameter. We can elimiate some + * extra work by taking advantage of that fact. + * + * \param a Pointer to the desired enum name. + * \param b Pointer to an index into the \c all_enums array. + */ +static int compar_nr( const int *a, const unsigned *b ) { - return a->n - b->n; + return a[0] - all_enums[*b].n; } @@ -82,18 +97,16 @@ static char token_tmp[20]; const char *_mesa_lookup_enum_by_nr( int nr ) { - enum_elt tmp, *e; + unsigned * i; - tmp.n = nr; + i = (unsigned *)bsearch( & nr, reduced_enums, Elements(reduced_enums), + sizeof(reduced_enums[0]), (cfunc) compar_nr ); - e = (enum_elt *)bsearch( &tmp, all_enums, Elements(all_enums), - sizeof(*all_enums), (cfunc) compar_nr ); - - if (e) { - return e->c; + if ( i != NULL ) { + return & enum_string_table[ all_enums[ *i ].offset ]; } else { - /* this isn't re-entrant safe, no big deal here */ + /* this is not re-entrant safe, no big deal here */ _mesa_sprintf(token_tmp, "0x%x", nr); return token_tmp; } @@ -101,46 +114,117 @@ const char *_mesa_lookup_enum_by_nr( int nr ) int _mesa_lookup_enum_by_name( const char *symbol ) { - enum_elt tmp, *e, **f; - static const enum_elt * const index1[] = {""" - - def printRealFooter(self): - print """ }; + enum_elt * f = NULL; - if (!symbol) - return 0; - - tmp.c = symbol; - e = &tmp; - - f = (enum_elt **)bsearch( &e, index1, Elements(all_enums), - sizeof(*index1), (cfunc) compar_name ); + if ( symbol != NULL ) { + f = (enum_elt *)bsearch( symbol, all_enums, Elements(all_enums), + sizeof( enum_elt ), (cfunc) compar_name ); + } - return f ? (*f)->n : -1; + return (f != NULL) ? f->n : -1; } """ return def printFunctions(self): - self.enums.sort(lambda x,y: x.value - y.value) - for enum in self.enums: - print ' { "%s", 0x%X },' % (enum.name, enum.value) - nameEnums = self.enums[:] + keys = self.enum_table.keys() + keys.sort() + + name_table = [] + enum_table = {} + + for enum in keys: + low_pri = 9 + for [name, pri] in self.enum_table[ enum ]: + name_table.append( [name, enum] ) + + if pri < low_pri: + low_pri = pri + enum_table[enum] = name + + + name_table.sort() + + string_offsets = {} + i = 0; + print 'static const char enum_string_table[] = ' + for [name, enum] in name_table: + print ' "%s\\0"' % (name) + string_offsets[ name ] = i + i += len(name) + 1 + + print ' ;' + print '' + + + print 'static const enum_elt all_enums[%u] =' % (len(name_table)) + print '{' + for [name, enum] in name_table: + print ' { % 5u, 0x%08X }, /* %s */' % (string_offsets[name], enum, name) + print '};' + print '' + + print 'static const unsigned reduced_enums[%u] =' % (len(keys)) + print '{' + for enum in keys: + name = enum_table[ enum ] + if [name, enum] not in name_table: + print ' /* Error! %s, 0x%04x */ 0,' % (name, enum) + else: + i = name_table.index( [name, enum] ) + + print ' % 4u, /* %s */' % (i, name) + print '};' + + self.printBody(); - self.enums.sort(lambda x,y: cmp(x.name, y.name)) - for enum in self.enums: - print ' &all_enums[%d], ' % (nameEnums.index(enum)) return + def append(self, object_type, obj): + if object_type == "enum": + if obj.value not in self.enum_table: + self.enum_table[ obj.value ] = [] + + + # Prevent duplicate names in the enum table. + + if obj.name not in self.enum_table[ obj.value ]: + + # Calculate a "priority" for this enum name. + # When we lookup an enum by number, there may + # be many possible names, but only one can be + # returned. The priority is used by this + # script to select which name is the "best". + # + # Highest precedence is given to "core" name. + # ARB extension names have the next highest, + # followed by EXT extension names. Vendor + # extension names are the lowest. + + if obj.category.startswith( "GL_VERSION_" ): + priority = 0 + elif obj.category.startswith( "GL_ARB_" ): + priority = 1 + elif obj.category.startswith( "GL_EXT_" ): + priority = 2 + else: + priority = 3 + + self.enum_table[ obj.value ].append( [obj.name, priority] ) + + else: + gl_XML.FilterGLAPISpecBase.append(self, object_type, obj) + + def show_usage(): print "Usage: %s [-f input_file_name]" % sys.argv[0] sys.exit(1) if __name__ == '__main__': file_name = "gl_API.xml" - + try: (args, trail) = getopt.getopt(sys.argv[1:], "f:") except Exception,e: -- cgit v1.2.3