nodehvs.h File Reference

Node Hash Value Service. More...

#include "node.h"

Include dependency graph for nodehvs.h:

Go to the source code of this file.

Data Structures
struct	_nhvs_seq_list
	NHVS Sequece List. More...
struct	_nhvs_tree_node
	NHVS Tree node. More...
Defines
#define	NHASH_HASH(n)   ((n) & NHASH_HASH_MASK)
	Get the hash value from the nhash_t.
#define	NHASH_HASH_MASK   0x00FFFFFFFFFFFFFFLL
#define	NHASH_SEQ(n)   (((n) >> 56 ) & 0xFFLL)
	Get the sequential number from the nhash_t.
#define	NHASH_SEQ_MASK   0xFF00000000000000LL
#define	SET_NHASH_HASH(n, h)   (((n) & NHASH_SEQ_MASK) | ((h) & NHASH_HASH_MASK))
	Set the hash value.
#define	SET_NHASH_SEQ(n, s)   (((n) & NHASH_HASH_MASK) | (((s) & 0xFFLL) << 56 ))
	Set the seq value.
Typedefs
typedef uword64	nhash_t
	Node hash value type.
typedef _nhvs_seq_list	NHVSSeqList
	NHVS Sequece List.
typedef _nhvs_tree_node	NHVSTreeNode
	NHVS Tree node.
Functions
nhash_t	nhash_hash_func (Node *node)
	Hashing function.
STORAGE_TYPE int	nhvs_dict_lookup (Node *node, const char *string)
	Set dictionary item.
STORAGE_TYPE int	nhvs_free ()
	Free NHVS static data.
int	nhvs_gen_set (Node *node, const char *string)
	Set generic item.
nhash_t	nhvs_get_hash (Node *node)
	Returns the hash-value of the node.
STORAGE_TYPE Node *	nhvs_get_node (nhash_t hash)
	Tries to obtain a node value from the given hash.
STORAGE_TYPE int	nhvs_new ()
	Create NHVS static data.
void	nhvs_parsed_set (Node *node, const char *string)
	Set parsed item.
int	nhvs_put_local (nhash_t hash, Node *node)
STORAGE_TYPE void	nhvs_update_hash (nhash_t *hash, Node *node)
	Updates the hash-value of the node.

---

Detailed Description

Node Hash Value Service.

This module is a set of functions that make the Node Hash Value Service.

The hash value aims to help to keep the statement base more compact by storing real values that may be long enough outside of statement base (stmtbase.h). The statement base should keep only hash-values of the real node values.

Also, the hash-values should be transferred by the protocol between the server and clients until one of them needs to resolve unknown value. Resolve is the request to the hash-sending side which is supposed to know the real value of the hash-value it sends.

You know, that because of the hash-value is limited in size it is not guaranteed the two different real values have the different hash-values. So some distinguishing mechanism is needed to assign numbers to the same hash-value of different real-values to set the strict correspondence.

The Node Hash Value Service is implemented as a binary-search tree that stores the real-values by the key that is the hash-value of the real-value. Each time the new node is created it must be checked against the Node Hash Value Service by calling nhvs_update_hash().

---

Define Documentation

#define NHASH_HASH (  n   )     ((n) & NHASH_HASH_MASK)

Get the hash value from the nhash_t.

#define NHASH_HASH_MASK   0x00FFFFFFFFFFFFFFLL

#define NHASH_SEQ (  n   )     (((n) >> 56 ) & 0xFFLL)

Get the sequential number from the nhash_t.

#define NHASH_SEQ_MASK   0xFF00000000000000LL

#define SET_NHASH_HASH (  n, h   )     (((n) & NHASH_SEQ_MASK) | ((h) & NHASH_HASH_MASK))

Set the hash value.

#define SET_NHASH_SEQ (  n, s   )     (((n) & NHASH_HASH_MASK) | (((s) & 0xFFLL) << 56 ))

Set the seq value.

---

Typedef Documentation

typedef uword64 nhash_t

Node hash value type. The standard size of nhash_t is 64 bit. The nhash_t is devided into two fields of 8 and 56 bits of size respectively. The first (lowest) 56 bits are for hash value (the nearest 56-bit prime is 0xfffffffffffb) The other (high) 8 bits represent the sequential number of the node value with the same hash-value.

typedef struct _nhvs_seq_list NHVSSeqList

NHVS Sequece List. if the current service has no super-server set then the sequence number (a field of nhash_t type) must be equal to the real position of the corresponded node in the list.

typedef struct _nhvs_tree_node NHVSTreeNode

NHVS Tree node. NHVS Tree is a simple binary search tree that handles fast search of the given hash_value

---

Function Documentation

nhash_t nhash_hash_func (  Node *  node  )

Hashing function.

STORAGE_TYPE int nhvs_dict_lookup (  Node *  node, const char *  string )

Set dictionary item. Associates the id and string alias as a dictionary item. modifies passed node structure. If id is already associated with different string, then overrides it. If string is already associated with different id,

STORAGE_TYPE int nhvs_free (   )

Free NHVS static data.

int nhvs_gen_set (  Node *  node, const char *  string )

Set generic item. Looks through the tree for the literal supplied

nhash_t nhvs_get_hash (  Node *  node  )

Returns the hash-value of the node.

STORAGE_TYPE Node* nhvs_get_node (  nhash_t  hash  )

Tries to obtain a node value from the given hash. Returns: null if there is no value correspondent to the hash.

STORAGE_TYPE int nhvs_new (   )

Create NHVS static data.

void nhvs_parsed_set (  Node *  node, const char *  string )

Set parsed item. Associates parsed value, coming with node and the literal

int nhvs_put_local (  nhash_t  hash, Node *  node )

STORAGE_TYPE void nhvs_update_hash (  nhash_t *  hash, Node *  node )

Updates the hash-value of the node. First, it looks the hash-value (given by hash argument) in the tree. If the value is present in the tree, it searches for the concrete value in the list associated with this node of the tree. If the real value exists and there is a number given for this value, the hash is updated with this hash-value and the number. If there is no number given for the value the service tries to ask the server (or other super-nhvs) for the number, associates it with the value and returns updated hash-value. If there is no super-server or there is no responce from it, the nhvs_update() generates a next number greater then all the numbers for the values with the same hash, associates it with the value and returns updated hash-value.

---