mal_namespace.mx

一个内存数据库的源代码这是服务器端还有客户端

@' The contents of this file are subject to the MonetDB Public License
@' Version 1.1 (the "License"); you may not use this file except in
@' compliance with the License. You may obtain a copy of the License at
@' http://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
@'
@' Software distributed under the License is distributed on an "AS IS"
@' basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
@' License for the specific language governing rights and limitations
@' under the License.
@'
@' The Original Code is the MonetDB Database System.
@'
@' The Initial Developer of the Original Code is CWI.
@' Portions created by CWI are Copyright (C) 1997-2007 CWI.
@' All Rights Reserved.

@a M.L. Kersten
@+ Name Space Management.
Significant speed improvement at type resolution and during the 
optimization phases can be gained when each module or function identifier is 
replaced by a fixed length internal identifier. This translation is
done once during parsing.
Variables are always stored local to the MAL block in which they
are used.

The number of module and function names is expected to be limited. 
Therefore, the namespace manager is organized as a shared table. The alternative
is a namespace per client. However, this would force
passing around the client identity or an expensive operation to deduce
this from the process id. The price paid is that updates to the namespace
should be protected against concurrent access.

The space can, however, also become polluted with identifiers generated on the fly.
Compilers are adviced to be conservative in their naming, or explicitly manage
the name space by deletion of non-used names once in a while.
@{
@h
#ifndef _MAL_NAMESPACE_H
#define _MAL_NAMESPACE_H

mal_export void initNamespace(void);
mal_export void finishNamespace(void);
mal_export str putName(str nme,int len);
mal_export str getName(str nme,int len);
mal_export void delName(str nme,int len);
mal_export void dumpNamespaceStatistics(stream *f, int details);

#endif /* _MAL_NAMESPACE_H */
@+ Code bodies
The Namespace block is organized using a simple hashstructure over the first
character. Better structures can be introduced when searching becomes
too expensive. An alternative would be to use a BAT to handle the collection.
@c
#include "mal_config.h"
#include "mal_type.h"
#include "mal_namespace.h"
#define MAXIDENTIFIERS 2048

typedef struct NAMESPACE{
	int  size;  /* amount of space available */
	int  nmetop;
	str  *nme;
	int  *link;
	int  *hit;
	int	 *length;
	int	 totalhit;
} Namespace;

static Namespace namespace;
#ifdef _BACKUP_
/* code to aid hunting for illegal frees on the namespace */
static Namespace backup;
#endif

static void expandNamespace(int incr){
	str *nme;
	int *length, *link, *hit, newsize;

	if(incr < 0){
		GDKwarning("expandNamespace:illegal increment\n");
		return;
	}
	if(namespace.size+incr > 32000)
		GDKwarning("Namespace becomes too large\n");

	newsize= namespace.size+incr;
	nme= (str *) GDKmalloc(sizeof(str *) * newsize);
	link= (int *) GDKmalloc(sizeof(int) * newsize);
	hit = (int *) GDKmalloc(sizeof(int) * newsize);
	length = (int *) GDKmalloc(sizeof(int) * newsize);
	memcpy(nme, namespace.nme, sizeof(str *) * namespace.nmetop);
	memcpy(link, namespace.link, sizeof(int) * namespace.nmetop);
	memcpy(hit, namespace.hit, sizeof(int) * namespace.nmetop);
	memcpy(length, namespace.length, sizeof(int) * namespace.nmetop);

	namespace.size += incr;
	namespace.totalhit= 0;
	GDKfree(namespace.nme); namespace.nme= nme;
	GDKfree(namespace.link); namespace.link= link;
	GDKfree(namespace.hit); namespace.hit= hit;
	GDKfree(namespace.length); namespace.length= length;

#ifdef _BACKUP_
	nme= (str *) GDKmalloc(sizeof(str *) * (backup.nmetop+incr));
	link= (int *) GDKmalloc(sizeof(int) * (backup.nmetop+incr));
	hit = (int *) GDKmalloc(sizeof(int) * (backup.nmetop+incr));
	length = (int *) GDKmalloc(sizeof(int) * (backup.nmetop+incr));
	memcpy(nme, backup.nme, sizeof(str *) * backup.nmetop);
	memcpy(link, backup.link, sizeof(int) * backup.nmetop);
	memcpy(hit, backup.hit, sizeof(int) * backup.nmetop);
	memcpy(length, backup.hit, sizeof(int) * backup.nmetop);

	backup.size += incr;
	backup.totalhit= 0;
	GDKfree(backup.nme); backup.nme= nme;
	GDKfree(backup.link); backup.link= link;
	GDKfree(backup.hit); backup.hit= hit;
	GDKfree(backup.length); backup.length= length;
#endif

}
void initNamespace() {
	namespace.nme= (str *) GDKzalloc(sizeof(str *) * MAXIDENTIFIERS);
	namespace.link= (int *) GDKzalloc(sizeof(int) * MAXIDENTIFIERS);
	namespace.hit= (int *) GDKzalloc(sizeof(int) * MAXIDENTIFIERS);
	namespace.length= (int *) GDKzalloc(sizeof(int) * MAXIDENTIFIERS);
	namespace.size = MAXIDENTIFIERS;
	namespace.nmetop= 256; /* hash overflow */

#ifdef _BACKUP_
	backup.nme= (str *) GDKzalloc(sizeof(str *) * MAXIDENTIFIERS);
	backup.link= (int *) GDKzalloc(sizeof(int) * MAXIDENTIFIERS);
	backup.hit= (int *) GDKzalloc(sizeof(int) * MAXIDENTIFIERS);
	backup.size = MAXIDENTIFIERS;
	backup.nmetop= 256; /* hash overflow */
#endif
}
void finishNamespace() {
	int i;
	for(i=0;i<namespace.nmetop; i++) {
		if( namespace.nme[i]) 
			GDKfree(namespace.nme[i]);
		namespace.nme[i]= 0;
	}
	GDKfree(namespace.nme); namespace.nme= 0;
	GDKfree(namespace.link); namespace.link= 0;
	GDKfree(namespace.hit); namespace.hit= 0;
	GDKfree(namespace.length); namespace.length= 0;
#ifdef _BACKUP_
	GDKfree(backup.nme);	backup.nme=0;
	GDKfree(backup.link);	backup.link=0;
	GDKfree(backup.hit);	backup.hit=0;
	GDKfree(backup.length);	backup.length=0;
#endif
}

#ifdef _BACKUP_
void chkName(int l){
	int i;
	if( namespace.nme[l] && strcmp(namespace.nme[l],backup.nme[l])!=0){
		printf("error in namespace %d\n",l);
		printf("backup %s\n",backup.nme[l]);
		for( i=0; i< strlen(backup.nme[l]); i++)
		printf("[%d] %d '%c'\n",i, namespace.nme[l][i], namespace.nme[l][i]);

	}
}
#endif
@-
Before a name is being stored we should check for its occurrence first.
The administration is initialized incrementally.
@c
str getName(str nme, int len)
{
	int l;
	if(len == 0 || nme== NULL || *nme==0) return 0;
	
	for(l= nme[0]; l && namespace.nme[l]; l= namespace.link[l]){
#ifdef _BACKUP_
		chkName(l);
#endif
	    if( namespace.length[l] == len  &&
			strncmp(nme,namespace.nme[l],len)==0) {
	        namespace.hit[l]++;
			namespace.totalhit++;
			return namespace.nme[l];
	    }
	}
	return 0;
}
@-
Name deletion from the namespace is tricky, because there may
be multiple threads active on the structure. Moreover, the
symbol may be picked up by a concurrent thread and stored
somewhere.
To avoid all these problems, the namespace should become
private to each Client, but this would mean expensive look ups
deep into the kernel to access the context.
@c
void delName(str nme, int len){
	str n;
	n= getName(nme,len);
	if( nme[0]==0 || n == 0) return ;
	
	mal_set_lock(mal_contextLock,"putName");
	GDKwarning("Namespace garbage collection not available");
	mal_unset_lock(mal_contextLock,"putName");
}
str putName(str nme, int len)
{
	int i,k=0,l,top;
	char buf[1024];
	str s;

	if( nme == NULL)
		return NULL;
	for(l= nme[0]; l && namespace.nme[l]; l= namespace.link[l]){
#ifdef _BACKUP_
		chkName(l);
#endif
	    if( namespace.length[l] == len  &&
			strncmp(nme,namespace.nme[l],len) == 0 ) {
	        namespace.hit[l]++;
			namespace.totalhit++;
			/* aggressive test for reorganization needs */
			if( k && 2*namespace.hit[k] < namespace.hit[l]){
				mal_set_lock(mal_contextLock,"putName");
				s= namespace.nme[l]; namespace.nme[l]= namespace.nme[k];
				namespace.nme[k]=s;
				i= namespace.hit[l]; namespace.hit[l]=namespace.hit[k];
				namespace.hit[k]= i;
				i= namespace.length[l]; namespace.length[l]=namespace.length[k];
				namespace.length[k]= i;

#ifdef _BACKUP_
				s= backup.nme[l]; backup.nme[l]= backup.nme[k];
				backup.nme[k]=s;
				i= backup.hit[l]; backup.hit[l]=backup.hit[k];
				backup.hit[k]= i;
				i= backup.length[l]; backup.length[l]=backup.length[k];
				backup.length[k]= i;
#endif
				mal_unset_lock(mal_contextLock,"putName");
				l=k;
			}
			return namespace.nme[l];
	    }
		k=l;
	}

	if(len>=1024) GDKfatal("Identifier too long");
	memcpy(buf, nme, (size_t) len); 
	buf[len]=0;

	mal_set_lock(mal_contextLock,"putName");
	if( namespace.nmetop+1== namespace.size)
	    expandNamespace(MAXIDENTIFIERS);
	l= nme[0];
	top= namespace.nme[l]== 0? l: namespace.nmetop;
	namespace.nme[top]= GDKstrdup(buf);
	namespace.link[top]= namespace.link[l];
	if( top == namespace.nmetop)
		namespace.link[l]= top;
	namespace.hit[top]= 0;
	namespace.length[top]= len;
	namespace.nmetop++;

#ifdef _BACKUP_
	top= backup.nme[l]== 0? l: backup.nmetop;
	backup.nme[top]= GDKstrdup(buf);
	backup.link[top]= backup.link[l];
	if( top == backup.nmetop)
		backup.link[l]= top;
	backup.nmetop++;
#endif
	mal_unset_lock(mal_contextLock,"putName");
	nme= namespace.nme[top];
	return namespace.nme[top];
}
@-
The namespace may become a bottleneck when the chain of identifiers grows.
This issue can be tackled from two angles. Either we change the hash function
using multiple characters of the identifier or we sort the identifiers list
using the actual hits reported so far. The field hit keeps track of this
crucial information. The choice on the way to move forward is postponed.

The re-organization scheme can be triggered by the calls made
to the namespace.
@c
void dumpNamespaceStatistics(stream *f, int details)
{
	int i,l,cnt,hits,steps;

	stream_printf(f,"Namespace statistics\n");
	stream_printf(f,"nmetop = %d size= %d\n",
	    namespace.nmetop, namespace.size);
	for(i=0;i<256; i++)
	if(namespace.nme[i]){
	    hits= steps= cnt =0;
	    stream_printf(f,"list %d ",i);
	    for(l= i; l && namespace.nme[l]; l= namespace.link[l]){
	        cnt++;
	        if(details) {
	            stream_printf(f,"(%s %d) ",
	            namespace.nme[l], namespace.hit[l]);
	            if( i+1 % 5 == 0) stream_printf(f,"\n");
				hits+= namespace.hit[l];
				steps += namespace.hit[l]*cnt;
	        }
	    }
	    if(cnt)  stream_printf(f," has %d elements, %d hits, %d steps",cnt,hits,steps/(hits+1));
		stream_printf(f,"\n");
	}
}
@}