path: root/lib/symtab.h

/* Symbol Table data structure -- header
 * Copyright (C) 2009 Chris Hall (GMCH), Highwayman
 *
 * This file is part of GNU Zebra.
 *
 * GNU Zebra is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published
 * by the Free Software Foundation; either version 2, or (at your
 * option) any later version.
 *
 * GNU Zebra is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with GNU Zebra; see the file COPYING.  If not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#ifndef _ZEBRA_SYMTAB_H
#define _ZEBRA_SYMTAB_H

#include "misc.h"
#include "vector.h"

/*==============================================================================
 * Symbol table definitions
 *
 * Note that count things in uint -- which is expected to be at least 32 bits.
 *
 * Expect to run out of memory before really challenge that assumption !  (At
 * 8 bytes to a pointer, 4G of pointers is already 32G.)
 */
enum
{
  /* Minimum and maximum number of symbol table bases.
   *
   * Something has gone tragically wrong if we hit the maximum !  We assume can
   * multiply the maximum by 2 and get valid uint result.
   */
  SYMBOL_TABLE_BASES_MIN = 50,
  SYMBOL_TABLE_BASES_MAX = UINT_MAX / 2,

  /* Point at which stops doubling the symbol table size (bases)
   */
  SYMBOL_TABLE_BASES_DOUBLE_MAX  = 4000,

  /* Default density
   */
  SYMBOL_TABLE_DEFAULT_DENSITY   = 200,         /* 2.00 entries/base    */

#if 0
  /* LS bit of the reference count is used as symbol is set bit.
   */
  symbol_is_set_bit    = 1,
  symbol_ref_increment = 2,     /* so we count in 2's !                 */
#endif
} ;

/*------------------------------------------------------------------------------
 * Structures defined below.
 */
struct symbol_table ;
struct symbol ;
struct symbol_nref ;

typedef uint32_t symbol_hash_t ;
typedef uint symbol_ref_count_t ;

typedef struct symbol_table*   symbol_table ;
typedef struct symbol_table    symbol_table_t ;

typedef struct symbol*         symbol ;
typedef struct symbol          symbol_t ;

typedef struct symbol_nref*    symbol_nref ;
typedef struct symbol_nref     symbol_nref_t ;

typedef struct symbol_funcs* symbol_funcs ;
typedef struct symbol_funcs  symbol_funcs_t ;
typedef const struct symbol_funcs* symbol_funcs_c ;

typedef struct symbol_walker*    symbol_walker ;
typedef struct symbol_walker     symbol_walker_t ;

/*------------------------------------------------------------------------------
 * Set of functions for a Symbol Table
 */
typedef symbol_hash_t symbol_hash_func(const void* name) ;
typedef int           symbol_cmp_func(const void* body, const void* name) ;
typedef void          symbol_free_func(void* body) ;

struct symbol_funcs
{
  symbol_hash_func* hash ;      /* function to hash given name          */
  symbol_cmp_func*  cmp ;       /* function to compare symbol and name  */
  symbol_free_func* free ;      /* called when symbol is destroyed      */
} ;

/*------------------------------------------------------------------------------
 * Symbol Table.
 *
 * Don't fiddle with this directly... see access functions below.
 */
struct symbol_table
{
  void*    parent ;             /* to identify the table.               */

  symbol*  bases ;              /* ref:array of chain bases             */
  uint	   base_count ;         /* number of chain bases                */

  uint	   entry_count ;        /* number of entries in the table       */
  uint     max_index ;          /* maximum index in the table           */
  uint	   extend_thresh ;      /* when to extend the hash table        */

  float    density ;            /* entries per chain base               */

  symbol_funcs_t func ;         /* the functions, as above              */
} ;

/*------------------------------------------------------------------------------
 * Symbol Table Entry.
 *
 * Don't fiddle with this directly... see access functions below.
 */
struct symbol
{
  symbol_table table ;    /* so can go from symbol to enclosing table
                           * NULL => orphan symbol                      */

  void*    body ;         /* see: symbol_get_body(sym) etc.             */

  symbol   next ;         /* assume chains are short and seldom remove
                           * symbols -- so single pointer will do.      */

  symbol_nref nref_list ; /* list of notify references (if any)         */
  symbol_ref_count_t ref_count ;
                          /* count of references (incl. nref)           */

  symbol_hash_t  hash ;   /* used in lookup and when extending bases.   */
} ;

/* The ref_count actually counts in 2's.  The LS bit is the "symbol_set" bit.
 * While the "symbol_set" bit is set, the reference count is not zero !
 */
enum
{
  symbol_ref_count_increment   = 2,
  symbol_ref_count_symbol_set  = 1
} ;

/*------------------------------------------------------------------------------
 * Symbol Notify Reference (or "bookmark").
 *
 * Don't fiddle with this directly...  see access functions below
 */
struct symbol_nref
{
  symbol      sym ;         /* Address of symbol referred to (if any).
                             * (In "bookmark" this points to self.)     */

  void*	      parent ;      /* In "bookmark" points to symbol           */
  uintptr_t   tag ;

  symbol_nref next ;         /* fellow references to the symbol ...     */
  symbol_nref prev ;         /* ... ignore if sym is NULL.              */
} ;

/* Symbol Walk Iterator
 */
struct symbol_walker
{
  symbol    next ;        /* next symbol to return (if any)         */
  symbol*   base ;        /* next chain base to process (if any)    */
  uint      base_count ;  /* number of chain bases left to process  */
} ;

/*==============================================================================
 * Symbol Table Operations.
 */
extern symbol_table symbol_table_new(void* parent, uint base_count,
                                           uint density, symbol_funcs_c funcs) ;

extern void  symbol_table_set_parent(symbol_table table, void* parent) ;
extern void* symbol_table_get_parent(symbol_table table) ;

extern symbol symbol_table_ream(symbol_table table, symbol sym,
                                                        free_keep_b free_body) ;
extern symbol_table symbol_table_free(symbol_table table,
                                                        free_keep_b free_body) ;
extern void symbol_table_reset(symbol_table table, uint base_count) ;

extern symbol symbol_lookup(symbol_table table, const void* name, add_b add) ;

extern void symbol_set_body(symbol sym, void* body, bool set,
                                                         free_keep_b free_old) ;
Inline void symbol_set(symbol sym) ;
Inline symbol symbol_unset(symbol sym, free_keep_b free_body) ;
extern symbol symbol_delete(symbol sym, free_keep_b free_body) ;

Inline bool symbol_is_set(const symbol sym) ;
Inline bool symbol_has_references(const symbol sym) ;

extern symbol_hash_t symbol_hash_string(const void* string) ;
extern symbol_hash_t symbol_hash_bytes(const void* bytes, size_t len) ;
Inline symbol_hash_t symbol_hash_word(symbol_hash_t h) ;

Inline void* symbol_get_body(const symbol sym) ;
Inline symbol_table symbol_get_table(const symbol sym) ;

Inline symbol symbol_inc_ref(symbol sym) ;
Inline symbol symbol_dec_ref(symbol sym) ;

Private symbol symbol_zero_ref(symbol sym, free_keep_b free_body) ;

extern symbol_nref symbol_nref_init(symbol_nref nref) ;
extern symbol_nref symbol_nref_set(symbol_nref nref, symbol sym) ;
extern symbol_nref symbol_nref_unset(symbol_nref nref, free_keep_b free_it) ;

Inline void* symbol_nref_get_symbol(symbol_nref nref) ;
Inline void* symbol_nref_get_body(symbol_nref nref) ;
Inline void* symbol_nref_get_parent(symbol_nref nref) ;
Inline uintptr_t symbol_nref_get_tag(symbol_nref nref) ;
Inline void symbol_nref_set_parent(symbol_nref nref, void* pa) ;
Inline void symbol_nref_set_tag(symbol_nref nref, uintptr_t tag) ;

extern void symbol_nref_walk_start(symbol sym, symbol_nref walk) ;
extern symbol_nref symbol_nref_walk_step(symbol_nref walk) ;
extern void symbol_nref_walk_end(symbol_nref walk) ;

extern void symbol_walk_start(symbol_table table, symbol_walker walk);
extern symbol symbol_walk_next(symbol_walker walk) ;

typedef int symbol_select_cmp(const symbol sym, const void* name) ;
typedef int symbol_sort_cmp(const symbol* a, const symbol* b) ;
extern vector symbol_table_extract(symbol_table table,
	                           symbol_select_cmp* select,
	                           const void* p_value,
			           bool most,
			           symbol_sort_cmp* sort) ;

extern int symbol_mixed_name_cmp(const char* a, const char* b) ;

/*==============================================================================
 * The Inline stuff.
 */

/*------------------------------------------------------------------------------
 * Access functions -- argument is address of symbol (may be NULL).
 */
Inline void*
symbol_get_body(const symbol sym)
{
  return (sym != NULL) ? sym->body : NULL ;
} ;

Inline symbol_table
symbol_get_table(const symbol sym)
{
  return (sym != NULL) ? sym->table : NULL ;
} ;

/*------------------------------------------------------------------------------
 * Reference count functions.
 */
Inline symbol
symbol_inc_ref(symbol sym)
{
  sym->ref_count += symbol_ref_count_increment ;
  return sym ;
} ;

Inline symbol
symbol_dec_ref(symbol sym)
{
  if (sym->ref_count > symbol_ref_count_increment)
    {
      sym->ref_count -= symbol_ref_count_increment ;
      return NULL ;
    } ;

  qassert(sym->ref_count == symbol_ref_count_increment) ;

  return symbol_zero_ref(sym, free_it) ;        /* returns NULL */
} ;

/*------------------------------------------------------------------------------
 * Set the "symbol_set" state
 */
Inline void
symbol_set(symbol sym)
{
  sym->ref_count |= symbol_ref_count_symbol_set ;
} ;

/*------------------------------------------------------------------------------
 * Clear the "symbol_set" state (if is set)
 *
 * If result is a zero reference count, free the symbol and, if required, the
 * symbol body.
 */
Inline symbol
symbol_unset(symbol sym, free_keep_b free_body)
{
  sym->ref_count &= ~symbol_ref_count_symbol_set ;

  if (sym->ref_count != 0)
    return sym ;

  return symbol_zero_ref(sym, free_body) ;      /* returns NULL */
} ;

/*------------------------------------------------------------------------------
 * Test whether there are any references -- NULL symbol has none (!)
 *
 * Note that for this purpose, the "value_set" state does not count
 */
Inline bool
symbol_has_references(const symbol sym)
{
  return (sym != NULL) ? (sym->ref_count >= symbol_ref_count_increment)
                       : false ;
} ;

/*------------------------------------------------------------------------------
 * Test the "value_set" state -- NULL symbol is not set (!)
 */
Inline bool
symbol_is_set(const symbol sym)
{
  return (sym != NULL) ? (sym->ref_count & symbol_ref_count_symbol_set)
                       : false ;
} ;

/*------------------------------------------------------------------------------
 * Symbol Reference access functions -- argument is address of symbol_ref.
 *
 * These cope if address of symbol_ref is null, or reference is undefined.
 *
 * Note that can cast a uintptr_t to a void* if required.
 */
Inline void*
symbol_nref_get_symbol(symbol_nref nref)
{
  return (nref != NULL) ? nref->sym : NULL ;
} ;

Inline void*
symbol_nref_get_body(symbol_nref nref)
{
  return symbol_get_body(symbol_nref_get_symbol(nref)) ;
} ;

Inline void*
symbol_nref_get_parent(symbol_nref nref)
{
  return (nref != NULL) ? nref->parent : NULL ;
} ;

Inline uintptr_t
symbol_nref_get_tag(symbol_nref nref)
{
  return (nref != NULL) ? nref->tag : 0 ;
} ;

/*------------------------------------------------------------------------------
 * Set properties of reference -- argument is address of symbol_ref, which is
 * assumed to NOT be NULL.
 *
 * Note that can cast a void* to a uintptr_t if required.
 */

Inline void
symbol_nref_set_parent(symbol_nref nref, void* pa)
{
  nref->parent = pa ;
} ;

Inline void
symbol_nref_set_tag(symbol_nref nref, uintptr_t tag)
{
  nref->tag = tag ;
} ;

/*------------------------------------------------------------------------------
 * Standard symbol integer hash function.
 *
 * Simple approach -- treat as seed for random number !
 */
Inline symbol_hash_t
symbol_hash_word(symbol_hash_t h)
{
  return (h * 2650845021u) + 5 ;        /* See Knuth 3.3.4      */
} ;

#endif /* _ZEBRA_SYMTAB_H */