src/mesa/program/symbol_table.c - platform/external/mesa3d - Git at Google

 /*
  * Copyright © 2008 Intel Corporation
  *
  * Permission is hereby granted, free of charge, to any person obtaining a
  * copy of this software and associated documentation files (the "Software"),
  * to deal in the Software without restriction, including without limitation
  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  * and/or sell copies of the Software, and to permit persons to whom the
  * Software is furnished to do so, subject to the following conditions:
  *
  * The above copyright notice and this permission notice (including the next
  * paragraph) shall be included in all copies or substantial portions of the
  * Software.
  *
  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  * DEALINGS IN THE SOFTWARE.
  */

 #include "main/imports.h"
 #include "symbol_table.h"
 #include "hash_table.h"

 struct symbol {
     /**
      * Link to the next symbol in the table with the same name
      *
      * The linked list of symbols with the same name is ordered by scope
      * from inner-most to outer-most.
      */
     struct symbol *next_with_same_name;


     /**
      * Link to the next symbol in the table with the same scope
      *
      * The linked list of symbols with the same scope is unordered.  Symbols
      * in this list my have unique names.
      */
     struct symbol *next_with_same_scope;


     /**
      * Header information for the list of symbols with the same name.
      */
     struct symbol_header *hdr;


     /**
      * Name space of the symbol
      *
      * Name space are arbitrary user assigned integers.  No two symbols can
      * exist in the same name space at the same scope level.
      */
     int name_space;

     /** Scope depth where this symbol was defined. */
     unsigned depth;

     /**
      * Arbitrary user supplied data.
      */
     void *data;
 };


 /**
  */
 struct symbol_header {
     /** Linkage in list of all headers in a given symbol table. */
     struct symbol_header *next;

     /** Symbol name. */
     char *name;

     /** Linked list of symbols with the same name. */
     struct symbol *symbols;
 };


 /**
  * Element of the scope stack.
  */
 struct scope_level {
     /** Link to next (inner) scope level. */
     struct scope_level *next;

     /** Linked list of symbols with the same scope. */
     struct symbol *symbols;
 };


 /**
  *
  */
 struct _mesa_symbol_table {
     /** Hash table containing all symbols in the symbol table. */
     struct hash_table *ht;

     /** Top of scope stack. */
     struct scope_level *current_scope;

     /** List of all symbol headers in the table. */
     struct symbol_header *hdr;

     /** Current scope depth. */
     unsigned depth;
 };


 struct _mesa_symbol_table_iterator {
     /**
      * Name space of symbols returned by this iterator.
      */
     int name_space;


     /**
      * Currently iterated symbol
      *
      * The next call to \c _mesa_symbol_table_iterator_get will return this
      * value.  It will also update this value to the value that should be
      * returned by the next call.
      */
     struct symbol *curr;
 };


 static void
 check_symbol_table(struct _mesa_symbol_table *table)
 {
 #if 1
     struct scope_level *scope;

     for (scope = table->current_scope; scope != NULL; scope = scope->next) {
         struct symbol *sym;

         for (sym = scope->symbols
              ; sym != NULL
              ; sym = sym->next_with_same_name) {
             const struct symbol_header *const hdr = sym->hdr;
             struct symbol *sym2;

             for (sym2 = hdr->symbols
                  ; sym2 != NULL
                  ; sym2 = sym2->next_with_same_name) {
                 assert(sym2->hdr == hdr);
             }
         }
     }
 #endif
 }

 void
 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
 {
     struct scope_level *const scope = table->current_scope;
     struct symbol *sym = scope->symbols;

     table->current_scope = scope->next;
     table->depth--;

     free(scope);

     while (sym != NULL) {
         struct symbol *const next = sym->next_with_same_scope;
         struct symbol_header *const hdr = sym->hdr;

         assert(hdr->symbols == sym);

         hdr->symbols = sym->next_with_same_name;

         free(sym);

         sym = next;
     }

     check_symbol_table(table);
 }


 void
 _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
 {
     struct scope_level *const scope = calloc(1, sizeof(*scope));

     scope->next = table->current_scope;
     table->current_scope = scope;
     table->depth++;
 }


 static struct symbol_header *
 find_symbol(struct _mesa_symbol_table *table, const char *name)
 {
     return (struct symbol_header *) hash_table_find(table->ht, name);
 }


 struct _mesa_symbol_table_iterator *
 _mesa_symbol_table_iterator_ctor(struct _mesa_symbol_table *table,
                                  int name_space, const char *name)
 {
     struct _mesa_symbol_table_iterator *iter = calloc(1, sizeof(*iter));
     struct symbol_header *const hdr = find_symbol(table, name);

     iter->name_space = name_space;

     if (hdr != NULL) {
         struct symbol *sym;

         for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
             assert(sym->hdr == hdr);

             if ((name_space == -1) || (sym->name_space == name_space)) {
                 iter->curr = sym;
                 break;
             }
         }
     }

     return iter;
 }


 void
 _mesa_symbol_table_iterator_dtor(struct _mesa_symbol_table_iterator *iter)
 {
     free(iter);
 }


 void *
 _mesa_symbol_table_iterator_get(struct _mesa_symbol_table_iterator *iter)
 {
     return (iter->curr == NULL) ? NULL : iter->curr->data;
 }


 int
 _mesa_symbol_table_iterator_next(struct _mesa_symbol_table_iterator *iter)
 {
     struct symbol_header *hdr;

     if (iter->curr == NULL) {
         return 0;
     }

     hdr = iter->curr->hdr;
     iter->curr = iter->curr->next_with_same_name;

     while (iter->curr != NULL) {
         assert(iter->curr->hdr == hdr);

         if ((iter->name_space == -1)
             || (iter->curr->name_space == iter->name_space)) {
             return 1;
         }

         iter->curr = iter->curr->next_with_same_name;
     }

     return 0;
 }


 /**
  * Determine the scope "distance" of a symbol from the current scope
  *
  * \return
  * A non-negative number for the number of scopes between the current scope
  * and the scope where a symbol was defined.  A value of zero means the current
  * scope.  A negative number if the symbol does not exist.
  */
 int
 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
 				int name_space, const char *name)
 {
     struct symbol_header *const hdr = find_symbol(table, name);
     struct symbol *sym;

     if (hdr != NULL) {
        for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
 	  assert(sym->hdr == hdr);

 	  if ((name_space == -1) || (sym->name_space == name_space)) {
 	     assert(sym->depth <= table->depth);
 	     return sym->depth - table->depth;
 	  }
        }
     }

     return -1;
 }


 void *
 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table,
                                int name_space, const char *name)
 {
     struct symbol_header *const hdr = find_symbol(table, name);

     if (hdr != NULL) {
         struct symbol *sym;


         for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
             assert(sym->hdr == hdr);

             if ((name_space == -1) || (sym->name_space == name_space)) {
                 return sym->data;
             }
         }
     }

     return NULL;
 }


 int
 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
                               int name_space, const char *name,
                               void *declaration)
 {
     struct symbol_header *hdr;
     struct symbol *sym;

     check_symbol_table(table);

     hdr = find_symbol(table, name);

     check_symbol_table(table);

     if (hdr == NULL) {
        hdr = calloc(1, sizeof(*hdr));
        hdr->name = strdup(name);

        hash_table_insert(table->ht, hdr, hdr->name);
        hdr->next = table->hdr;
        table->hdr = hdr;
     }

     check_symbol_table(table);

     /* If the symbol already exists in this namespace at this scope, it cannot
      * be added to the table.
      */
     for (sym = hdr->symbols
 	 ; (sym != NULL) && (sym->name_space != name_space)
 	 ; sym = sym->next_with_same_name) {
        /* empty */
     }

     if (sym && (sym->depth == table->depth))
        return -1;

     sym = calloc(1, sizeof(*sym));
     sym->next_with_same_name = hdr->symbols;
     sym->next_with_same_scope = table->current_scope->symbols;
     sym->hdr = hdr;
     sym->name_space = name_space;
     sym->data = declaration;
     sym->depth = table->depth;

     assert(sym->hdr == hdr);

     hdr->symbols = sym;
     table->current_scope->symbols = sym;

     check_symbol_table(table);
     return 0;
 }


 int
 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table,
 				     int name_space, const char *name,
 				     void *declaration)
 {
     struct symbol_header *hdr;
     struct symbol *sym;
     struct symbol *curr;
     struct scope_level *top_scope;

     check_symbol_table(table);

     hdr = find_symbol(table, name);

     check_symbol_table(table);

     if (hdr == NULL) {
         hdr = calloc(1, sizeof(*hdr));
         hdr->name = strdup(name);

         hash_table_insert(table->ht, hdr, hdr->name);
         hdr->next = table->hdr;
         table->hdr = hdr;
     }

     check_symbol_table(table);

     /* If the symbol already exists in this namespace at this scope, it cannot
      * be added to the table.
      */
     for (sym = hdr->symbols
 	 ; (sym != NULL) && (sym->name_space != name_space)
 	 ; sym = sym->next_with_same_name) {
        /* empty */
     }

     if (sym && sym->depth == 0)
        return -1;

     /* Find the top-level scope */
     for (top_scope = table->current_scope
 	 ; top_scope->next != NULL
 	 ; top_scope = top_scope->next) {
        /* empty */
     }

     sym = calloc(1, sizeof(*sym));
     sym->next_with_same_scope = top_scope->symbols;
     sym->hdr = hdr;
     sym->name_space = name_space;
     sym->data = declaration;

     assert(sym->hdr == hdr);

     /* Since next_with_same_name is ordered by scope, we need to append the
      * new symbol to the _end_ of the list.
      */
     if (hdr->symbols == NULL) {
        hdr->symbols = sym;
     } else {
        for (curr = hdr->symbols
 	    ; curr->next_with_same_name != NULL
 	    ; curr = curr->next_with_same_name) {
 	  /* empty */
        }
        curr->next_with_same_name = sym;
     }
     top_scope->symbols = sym;

     check_symbol_table(table);
     return 0;
 }


 struct _mesa_symbol_table *
 _mesa_symbol_table_ctor(void)
 {
     struct _mesa_symbol_table *table = calloc(1, sizeof(*table));

     if (table != NULL) {
        table->ht = hash_table_ctor(32, hash_table_string_hash,
 				   hash_table_string_compare);

        _mesa_symbol_table_push_scope(table);
     }

     return table;
 }


 void
 _mesa_symbol_table_dtor(struct _mesa_symbol_table *table)
 {
    struct symbol_header *hdr;
    struct symbol_header *next;

    while (table->current_scope != NULL) {
       _mesa_symbol_table_pop_scope(table);
    }

    for (hdr = table->hdr; hdr != NULL; hdr = next) {
        next = hdr->next;
        free(hdr->name);
        free(hdr);
    }

    hash_table_dtor(table->ht);
    free(table);
 }
	/*
	* Copyright © 2008 Intel Corporation
	*
	* Permission is hereby granted, free of charge, to any person obtaining a
	* copy of this software and associated documentation files (the "Software"),
	* to deal in the Software without restriction, including without limitation
	* the rights to use, copy, modify, merge, publish, distribute, sublicense,
	* and/or sell copies of the Software, and to permit persons to whom the
	* Software is furnished to do so, subject to the following conditions:
	*
	* The above copyright notice and this permission notice (including the next
	* paragraph) shall be included in all copies or substantial portions of the
	* Software.
	*
	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
	* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
	* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
	* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
	* DEALINGS IN THE SOFTWARE.
	*/

	#include "main/imports.h"
	#include "symbol_table.h"
	#include "hash_table.h"

	struct symbol {
	/**
	* Link to the next symbol in the table with the same name
	*
	* The linked list of symbols with the same name is ordered by scope
	* from inner-most to outer-most.
	*/
	struct symbol *next_with_same_name;


	/**
	* Link to the next symbol in the table with the same scope
	*
	* The linked list of symbols with the same scope is unordered. Symbols
	* in this list my have unique names.
	*/
	struct symbol *next_with_same_scope;


	/**
	* Header information for the list of symbols with the same name.
	*/
	struct symbol_header *hdr;


	/**
	* Name space of the symbol
	*
	* Name space are arbitrary user assigned integers. No two symbols can
	* exist in the same name space at the same scope level.
	*/
	int name_space;

	/** Scope depth where this symbol was defined. */
	unsigned depth;

	/**
	* Arbitrary user supplied data.
	*/
	void *data;
	};


	/**
	*/
	struct symbol_header {
	/** Linkage in list of all headers in a given symbol table. */
	struct symbol_header *next;

	/** Symbol name. */
	char *name;

	/** Linked list of symbols with the same name. */
	struct symbol *symbols;
	};


	/**
	* Element of the scope stack.
	*/
	struct scope_level {
	/** Link to next (inner) scope level. */
	struct scope_level *next;

	/** Linked list of symbols with the same scope. */
	struct symbol *symbols;
	};


	/**
	*
	*/
	struct _mesa_symbol_table {
	/** Hash table containing all symbols in the symbol table. */
	struct hash_table *ht;

	/** Top of scope stack. */
	struct scope_level *current_scope;

	/** List of all symbol headers in the table. */
	struct symbol_header *hdr;

	/** Current scope depth. */
	unsigned depth;
	};


	struct _mesa_symbol_table_iterator {
	/**
	* Name space of symbols returned by this iterator.
	*/
	int name_space;


	/**
	* Currently iterated symbol
	*
	* The next call to \c _mesa_symbol_table_iterator_get will return this
	* value. It will also update this value to the value that should be
	* returned by the next call.
	*/
	struct symbol *curr;
	};


	static void
	check_symbol_table(struct _mesa_symbol_table *table)
	{
	#if 1
	struct scope_level *scope;

	for (scope = table->current_scope; scope != NULL; scope = scope->next) {
	struct symbol *sym;

	for (sym = scope->symbols
	; sym != NULL
	; sym = sym->next_with_same_name) {
	const struct symbol_header *const hdr = sym->hdr;
	struct symbol *sym2;

	for (sym2 = hdr->symbols
	; sym2 != NULL
	; sym2 = sym2->next_with_same_name) {
	assert(sym2->hdr == hdr);
	}
	}
	}
	#endif
	}

	void
	_mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
	{
	struct scope_level *const scope = table->current_scope;
	struct symbol *sym = scope->symbols;

	table->current_scope = scope->next;
	table->depth--;

	free(scope);

	while (sym != NULL) {
	struct symbol *const next = sym->next_with_same_scope;
	struct symbol_header *const hdr = sym->hdr;

	assert(hdr->symbols == sym);

	hdr->symbols = sym->next_with_same_name;

	free(sym);

	sym = next;
	}

	check_symbol_table(table);
	}


	void
	_mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
	{
	struct scope_level const scope = calloc(1, sizeof(scope));

	scope->next = table->current_scope;
	table->current_scope = scope;
	table->depth++;
	}


	static struct symbol_header *
	find_symbol(struct _mesa_symbol_table table, const char name)
	{
	return (struct symbol_header *) hash_table_find(table->ht, name);
	}


	struct _mesa_symbol_table_iterator *
	_mesa_symbol_table_iterator_ctor(struct _mesa_symbol_table *table,
	int name_space, const char *name)
	{
	struct _mesa_symbol_table_iterator iter = calloc(1, sizeof(iter));
	struct symbol_header *const hdr = find_symbol(table, name);

	iter->name_space = name_space;

	if (hdr != NULL) {
	struct symbol *sym;

	for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
	assert(sym->hdr == hdr);

	if ((name_space == -1) \|\| (sym->name_space == name_space)) {
	iter->curr = sym;
	break;
	}
	}
	}

	return iter;
	}


	void
	_mesa_symbol_table_iterator_dtor(struct _mesa_symbol_table_iterator *iter)
	{
	free(iter);
	}


	void *
	_mesa_symbol_table_iterator_get(struct _mesa_symbol_table_iterator *iter)
	{
	return (iter->curr == NULL) ? NULL : iter->curr->data;
	}


	int
	_mesa_symbol_table_iterator_next(struct _mesa_symbol_table_iterator *iter)
	{
	struct symbol_header *hdr;

	if (iter->curr == NULL) {
	return 0;
	}

	hdr = iter->curr->hdr;
	iter->curr = iter->curr->next_with_same_name;

	while (iter->curr != NULL) {
	assert(iter->curr->hdr == hdr);

	if ((iter->name_space == -1)
	\|\| (iter->curr->name_space == iter->name_space)) {
	return 1;
	}

	iter->curr = iter->curr->next_with_same_name;
	}

	return 0;
	}


	/**
	* Determine the scope "distance" of a symbol from the current scope
	*
	* \return
	* A non-negative number for the number of scopes between the current scope
	* and the scope where a symbol was defined. A value of zero means the current
	* scope. A negative number if the symbol does not exist.
	*/
	int
	_mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
	int name_space, const char *name)
	{
	struct symbol_header *const hdr = find_symbol(table, name);
	struct symbol *sym;

	if (hdr != NULL) {
	for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
	assert(sym->hdr == hdr);

	if ((name_space == -1) \|\| (sym->name_space == name_space)) {
	assert(sym->depth <= table->depth);
	return sym->depth - table->depth;
	}
	}
	}

	return -1;
	}


	void *
	_mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table,
	int name_space, const char *name)
	{
	struct symbol_header *const hdr = find_symbol(table, name);

	if (hdr != NULL) {
	struct symbol *sym;


	for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
	assert(sym->hdr == hdr);

	if ((name_space == -1) \|\| (sym->name_space == name_space)) {
	return sym->data;
	}
	}
	}

	return NULL;
	}


	int
	_mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
	int name_space, const char *name,
	void *declaration)
	{
	struct symbol_header *hdr;
	struct symbol *sym;

	check_symbol_table(table);

	hdr = find_symbol(table, name);

	check_symbol_table(table);

	if (hdr == NULL) {
	hdr = calloc(1, sizeof(*hdr));
	hdr->name = strdup(name);

	hash_table_insert(table->ht, hdr, hdr->name);
	hdr->next = table->hdr;
	table->hdr = hdr;
	}

	check_symbol_table(table);

	/* If the symbol already exists in this namespace at this scope, it cannot
	* be added to the table.
	*/
	for (sym = hdr->symbols
	; (sym != NULL) && (sym->name_space != name_space)
	; sym = sym->next_with_same_name) {
	/* empty */
	}

	if (sym && (sym->depth == table->depth))
	return -1;

	sym = calloc(1, sizeof(*sym));
	sym->next_with_same_name = hdr->symbols;
	sym->next_with_same_scope = table->current_scope->symbols;
	sym->hdr = hdr;
	sym->name_space = name_space;
	sym->data = declaration;
	sym->depth = table->depth;

	assert(sym->hdr == hdr);

	hdr->symbols = sym;
	table->current_scope->symbols = sym;

	check_symbol_table(table);
	return 0;
	}


	int
	_mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table,
	int name_space, const char *name,
	void *declaration)
	{
	struct symbol_header *hdr;
	struct symbol *sym;
	struct symbol *curr;
	struct scope_level *top_scope;

	check_symbol_table(table);

	hdr = find_symbol(table, name);

	check_symbol_table(table);

	if (hdr == NULL) {
	hdr = calloc(1, sizeof(*hdr));
	hdr->name = strdup(name);

	hash_table_insert(table->ht, hdr, hdr->name);
	hdr->next = table->hdr;
	table->hdr = hdr;
	}

	check_symbol_table(table);

	/* If the symbol already exists in this namespace at this scope, it cannot
	* be added to the table.
	*/
	for (sym = hdr->symbols
	; (sym != NULL) && (sym->name_space != name_space)
	; sym = sym->next_with_same_name) {
	/* empty */
	}

	if (sym && sym->depth == 0)
	return -1;

	/* Find the top-level scope */
	for (top_scope = table->current_scope
	; top_scope->next != NULL
	; top_scope = top_scope->next) {
	/* empty */
	}

	sym = calloc(1, sizeof(*sym));
	sym->next_with_same_scope = top_scope->symbols;
	sym->hdr = hdr;
	sym->name_space = name_space;
	sym->data = declaration;

	assert(sym->hdr == hdr);

	/* Since next_with_same_name is ordered by scope, we need to append the
	* new symbol to the _end_ of the list.
	*/
	if (hdr->symbols == NULL) {
	hdr->symbols = sym;
	} else {
	for (curr = hdr->symbols
	; curr->next_with_same_name != NULL
	; curr = curr->next_with_same_name) {
	/* empty */
	}
	curr->next_with_same_name = sym;
	}
	top_scope->symbols = sym;

	check_symbol_table(table);
	return 0;
	}



	struct _mesa_symbol_table *
	_mesa_symbol_table_ctor(void)
	{
	struct _mesa_symbol_table table = calloc(1, sizeof(table));

	if (table != NULL) {
	table->ht = hash_table_ctor(32, hash_table_string_hash,
	hash_table_string_compare);

	_mesa_symbol_table_push_scope(table);
	}

	return table;
	}


	void
	_mesa_symbol_table_dtor(struct _mesa_symbol_table *table)
	{
	struct symbol_header *hdr;
	struct symbol_header *next;

	while (table->current_scope != NULL) {
	_mesa_symbol_table_pop_scope(table);
	}

	for (hdr = table->hdr; hdr != NULL; hdr = next) {
	next = hdr->next;
	free(hdr->name);
	free(hdr);
	}

	hash_table_dtor(table->ht);
	free(table);
	}