#include "tclInt.h"
#include "tclCompile.h"
#include "tclPort.h"
#define REBUILD_MULTIPLIER 3
static int AddLocalLiteralEntry _ANSI_ARGS_((
CompileEnv *envPtr, LiteralEntry *globalPtr,
int localHash));
static void ExpandLocalLiteralArray _ANSI_ARGS_((
CompileEnv *envPtr));
static unsigned int HashString _ANSI_ARGS_((CONST char *bytes,
int length));
static void RebuildLiteralTable _ANSI_ARGS_((
LiteralTable *tablePtr));
void
TclInitLiteralTable(tablePtr)
register LiteralTable *tablePtr;
{
#if (TCL_SMALL_HASH_TABLE != 4)
panic("TclInitLiteralTable: TCL_SMALL_HASH_TABLE is %d, not 4\n",
TCL_SMALL_HASH_TABLE);
#endif
tablePtr->buckets = tablePtr->staticBuckets;
tablePtr->staticBuckets[0] = tablePtr->staticBuckets[1] = 0;
tablePtr->staticBuckets[2] = tablePtr->staticBuckets[3] = 0;
tablePtr->numBuckets = TCL_SMALL_HASH_TABLE;
tablePtr->numEntries = 0;
tablePtr->rebuildSize = TCL_SMALL_HASH_TABLE*REBUILD_MULTIPLIER;
tablePtr->mask = 3;
}
void
TclDeleteLiteralTable(interp, tablePtr)
Tcl_Interp *interp;
LiteralTable *tablePtr;
{
LiteralEntry *entryPtr;
int i, start;
#ifdef TCL_COMPILE_DEBUG
TclVerifyGlobalLiteralTable((Interp *) interp);
#endif
start = 0;
while (tablePtr->numEntries > 0) {
for (i = start; i < tablePtr->numBuckets; i++) {
entryPtr = tablePtr->buckets[i];
if (entryPtr != NULL) {
TclReleaseLiteral(interp, entryPtr->objPtr);
start = i;
break;
}
}
}
if (tablePtr->buckets != tablePtr->staticBuckets) {
ckfree((char *) tablePtr->buckets);
}
}
int
TclRegisterLiteral(envPtr, bytes, length, onHeap)
CompileEnv *envPtr;
register char *bytes;
int length;
int onHeap;
{
Interp *iPtr = envPtr->iPtr;
LiteralTable *globalTablePtr = &(iPtr->literalTable);
LiteralTable *localTablePtr = &(envPtr->localLitTable);
register LiteralEntry *globalPtr, *localPtr;
register Tcl_Obj *objPtr;
unsigned int hash;
int localHash, globalHash, objIndex;
long n;
char buf[TCL_INTEGER_SPACE];
if (length < 0) {
length = (bytes? strlen(bytes) : 0);
}
hash = HashString(bytes, length);
localHash = (hash & localTablePtr->mask);
for (localPtr = localTablePtr->buckets[localHash];
localPtr != NULL; localPtr = localPtr->nextPtr) {
objPtr = localPtr->objPtr;
if ((objPtr->length == length) && ((length == 0)
|| ((objPtr->bytes[0] == bytes[0])
&& (memcmp(objPtr->bytes, bytes, (unsigned) length)
== 0)))) {
if (onHeap) {
ckfree(bytes);
}
objIndex = (localPtr - envPtr->literalArrayPtr);
#ifdef TCL_COMPILE_DEBUG
TclVerifyLocalLiteralTable(envPtr);
#endif
return objIndex;
}
}
globalHash = (hash & globalTablePtr->mask);
for (globalPtr = globalTablePtr->buckets[globalHash];
globalPtr != NULL; globalPtr = globalPtr->nextPtr) {
objPtr = globalPtr->objPtr;
if ((objPtr->length == length) && ((length == 0)
|| ((objPtr->bytes[0] == bytes[0])
&& (memcmp(objPtr->bytes, bytes, (unsigned) length)
== 0)))) {
if (onHeap) {
ckfree(bytes);
}
objIndex = AddLocalLiteralEntry(envPtr, globalPtr, localHash);
#ifdef TCL_COMPILE_DEBUG
if (globalPtr->refCount < 1) {
panic("TclRegisterLiteral: global literal \"%.*s\" had bad refCount %d",
(length>60? 60 : length), bytes,
globalPtr->refCount);
}
TclVerifyLocalLiteralTable(envPtr);
#endif
return objIndex;
}
}
TclNewObj(objPtr);
Tcl_IncrRefCount(objPtr);
if (onHeap) {
objPtr->bytes = bytes;
objPtr->length = length;
} else {
TclInitStringRep(objPtr, bytes, length);
}
if (TclLooksLikeInt(bytes, length)) {
if (TclGetLong((Tcl_Interp *) NULL, objPtr->bytes, &n) == TCL_OK) {
TclFormatInt(buf, n);
if (strcmp(objPtr->bytes, buf) == 0) {
objPtr->internalRep.longValue = n;
objPtr->typePtr = &tclIntType;
}
}
}
#ifdef TCL_COMPILE_DEBUG
if (TclLookupLiteralEntry((Tcl_Interp *) iPtr, objPtr) != NULL) {
panic("TclRegisterLiteral: literal \"%.*s\" found globally but shouldn't be",
(length>60? 60 : length), bytes);
}
#endif
globalPtr = (LiteralEntry *) ckalloc((unsigned) sizeof(LiteralEntry));
globalPtr->objPtr = objPtr;
globalPtr->refCount = 0;
globalPtr->nextPtr = globalTablePtr->buckets[globalHash];
globalTablePtr->buckets[globalHash] = globalPtr;
globalTablePtr->numEntries++;
if (globalTablePtr->numEntries >= globalTablePtr->rebuildSize) {
RebuildLiteralTable(globalTablePtr);
}
objIndex = AddLocalLiteralEntry(envPtr, globalPtr, localHash);
#ifdef TCL_COMPILE_DEBUG
TclVerifyGlobalLiteralTable(iPtr);
TclVerifyLocalLiteralTable(envPtr);
{
LiteralEntry *entryPtr;
int found, i;
found = 0;
for (i = 0; i < globalTablePtr->numBuckets; i++) {
for (entryPtr = globalTablePtr->buckets[i];
entryPtr != NULL; entryPtr = entryPtr->nextPtr) {
if ((entryPtr == globalPtr)
&& (entryPtr->objPtr == objPtr)) {
found = 1;
}
}
}
if (!found) {
panic("TclRegisterLiteral: literal \"%.*s\" wasn't global",
(length>60? 60 : length), bytes);
}
}
#endif
#ifdef TCL_COMPILE_STATS
iPtr->stats.numLiteralsCreated++;
iPtr->stats.totalLitStringBytes += (double) (length + 1);
iPtr->stats.currentLitStringBytes += (double) (length + 1);
iPtr->stats.literalCount[TclLog2(length)]++;
#endif
return objIndex;
}
LiteralEntry *
TclLookupLiteralEntry(interp, objPtr)
Tcl_Interp *interp;
register Tcl_Obj *objPtr;
{
Interp *iPtr = (Interp *) interp;
LiteralTable *globalTablePtr = &(iPtr->literalTable);
register LiteralEntry *entryPtr;
char *bytes;
int length, globalHash;
bytes = Tcl_GetStringFromObj(objPtr, &length);
globalHash = (HashString(bytes, length) & globalTablePtr->mask);
for (entryPtr = globalTablePtr->buckets[globalHash];
entryPtr != NULL; entryPtr = entryPtr->nextPtr) {
if (entryPtr->objPtr == objPtr) {
return entryPtr;
}
}
return NULL;
}
void
TclHideLiteral(interp, envPtr, index)
Tcl_Interp *interp;
register CompileEnv *envPtr;
int index;
{
LiteralEntry **nextPtrPtr, *entryPtr, *lPtr;
LiteralTable *localTablePtr = &(envPtr->localLitTable);
int localHash, length;
char *bytes;
Tcl_Obj *newObjPtr;
lPtr = &(envPtr->literalArrayPtr[index]);
newObjPtr = Tcl_DuplicateObj(lPtr->objPtr);
Tcl_IncrRefCount(newObjPtr);
TclReleaseLiteral(interp, lPtr->objPtr);
lPtr->objPtr = newObjPtr;
bytes = Tcl_GetStringFromObj(newObjPtr, &length);
localHash = (HashString(bytes, length) & localTablePtr->mask);
nextPtrPtr = &localTablePtr->buckets[localHash];
for (entryPtr = *nextPtrPtr; entryPtr != NULL; entryPtr = *nextPtrPtr) {
if (entryPtr == lPtr) {
*nextPtrPtr = lPtr->nextPtr;
lPtr->nextPtr = NULL;
localTablePtr->numEntries--;
break;
}
nextPtrPtr = &entryPtr->nextPtr;
}
}
int
TclAddLiteralObj(envPtr, objPtr, litPtrPtr)
register CompileEnv *envPtr;
Tcl_Obj *objPtr;
LiteralEntry **litPtrPtr;
{
register LiteralEntry *lPtr;
int objIndex;
if (envPtr->literalArrayNext >= envPtr->literalArrayEnd) {
ExpandLocalLiteralArray(envPtr);
}
objIndex = envPtr->literalArrayNext;
envPtr->literalArrayNext++;
lPtr = &(envPtr->literalArrayPtr[objIndex]);
lPtr->objPtr = objPtr;
Tcl_IncrRefCount(objPtr);
lPtr->refCount = -1;
lPtr->nextPtr = NULL;
if (litPtrPtr) {
*litPtrPtr = lPtr;
}
return objIndex;
}
static int
AddLocalLiteralEntry(envPtr, globalPtr, localHash)
register CompileEnv *envPtr;
LiteralEntry *globalPtr;
int localHash;
{
register LiteralTable *localTablePtr = &(envPtr->localLitTable);
LiteralEntry *localPtr;
int objIndex;
objIndex = TclAddLiteralObj(envPtr, globalPtr->objPtr, &localPtr);
localPtr->nextPtr = localTablePtr->buckets[localHash];
localTablePtr->buckets[localHash] = localPtr;
localTablePtr->numEntries++;
globalPtr->refCount++;
if (localTablePtr->numEntries >= localTablePtr->rebuildSize) {
RebuildLiteralTable(localTablePtr);
}
#ifdef TCL_COMPILE_DEBUG
TclVerifyLocalLiteralTable(envPtr);
{
char *bytes;
int length, found, i;
found = 0;
for (i = 0; i < localTablePtr->numBuckets; i++) {
for (localPtr = localTablePtr->buckets[i];
localPtr != NULL; localPtr = localPtr->nextPtr) {
if (localPtr->objPtr == globalPtr->objPtr) {
found = 1;
}
}
}
if (!found) {
bytes = Tcl_GetStringFromObj(globalPtr->objPtr, &length);
panic("AddLocalLiteralEntry: literal \"%.*s\" wasn't found locally",
(length>60? 60 : length), bytes);
}
}
#endif
return objIndex;
}
static void
ExpandLocalLiteralArray(envPtr)
register CompileEnv *envPtr;
{
LiteralTable *localTablePtr = &(envPtr->localLitTable);
int currElems = envPtr->literalArrayNext;
size_t currBytes = (currElems * sizeof(LiteralEntry));
register LiteralEntry *currArrayPtr = envPtr->literalArrayPtr;
register LiteralEntry *newArrayPtr =
(LiteralEntry *) ckalloc((unsigned) (2 * currBytes));
int i;
memcpy((VOID *) newArrayPtr, (VOID *) currArrayPtr, currBytes);
for (i = 0; i < currElems; i++) {
if (currArrayPtr[i].nextPtr == NULL) {
newArrayPtr[i].nextPtr = NULL;
} else {
newArrayPtr[i].nextPtr = newArrayPtr
+ (currArrayPtr[i].nextPtr - currArrayPtr);
}
}
for (i = 0; i < localTablePtr->numBuckets; i++) {
if (localTablePtr->buckets[i] != NULL) {
localTablePtr->buckets[i] = newArrayPtr
+ (localTablePtr->buckets[i] - currArrayPtr);
}
}
if (envPtr->mallocedLiteralArray) {
ckfree((char *) currArrayPtr);
}
envPtr->literalArrayPtr = newArrayPtr;
envPtr->literalArrayEnd = (2 * currElems);
envPtr->mallocedLiteralArray = 1;
}
void
TclReleaseLiteral(interp, objPtr)
Tcl_Interp *interp;
register Tcl_Obj *objPtr;
{
Interp *iPtr = (Interp *) interp;
LiteralTable *globalTablePtr = &(iPtr->literalTable);
register LiteralEntry *entryPtr, *prevPtr;
ByteCode* codePtr;
char *bytes;
int length, index;
bytes = Tcl_GetStringFromObj(objPtr, &length);
index = (HashString(bytes, length) & globalTablePtr->mask);
for (prevPtr = NULL, entryPtr = globalTablePtr->buckets[index];
entryPtr != NULL;
prevPtr = entryPtr, entryPtr = entryPtr->nextPtr) {
if (entryPtr->objPtr == objPtr) {
entryPtr->refCount--;
if (entryPtr->refCount == 0) {
if (prevPtr == NULL) {
globalTablePtr->buckets[index] = entryPtr->nextPtr;
} else {
prevPtr->nextPtr = entryPtr->nextPtr;
}
ckfree((char *) entryPtr);
globalTablePtr->numEntries--;
TclDecrRefCount(objPtr);
if (objPtr->typePtr == &tclByteCodeType) {
codePtr = (ByteCode *) objPtr->internalRep.otherValuePtr;
if ((codePtr->numLitObjects == 1)
&& (codePtr->objArrayPtr[0] == objPtr)) {
codePtr->objArrayPtr[0] = NULL;
}
}
#ifdef TCL_COMPILE_STATS
iPtr->stats.currentLitStringBytes -= (double) (length + 1);
#endif
}
break;
}
}
Tcl_DecrRefCount(objPtr);
}
static unsigned int
HashString(bytes, length)
register CONST char *bytes;
int length;
{
register unsigned int result;
register int i;
result = 0;
for (i = 0; i < length; i++) {
result += (result<<3) + *bytes++;
}
return result;
}
static void
RebuildLiteralTable(tablePtr)
register LiteralTable *tablePtr;
{
LiteralEntry **oldBuckets;
register LiteralEntry **oldChainPtr, **newChainPtr;
register LiteralEntry *entryPtr;
LiteralEntry **bucketPtr;
char *bytes;
int oldSize, count, index, length;
oldSize = tablePtr->numBuckets;
oldBuckets = tablePtr->buckets;
tablePtr->numBuckets *= 4;
tablePtr->buckets = (LiteralEntry **) ckalloc((unsigned)
(tablePtr->numBuckets * sizeof(LiteralEntry *)));
for (count = tablePtr->numBuckets, newChainPtr = tablePtr->buckets;
count > 0;
count--, newChainPtr++) {
*newChainPtr = NULL;
}
tablePtr->rebuildSize *= 4;
tablePtr->mask = (tablePtr->mask << 2) + 3;
for (oldChainPtr = oldBuckets;
oldSize > 0;
oldSize--, oldChainPtr++) {
for (entryPtr = *oldChainPtr; entryPtr != NULL;
entryPtr = *oldChainPtr) {
bytes = Tcl_GetStringFromObj(entryPtr->objPtr, &length);
index = (HashString(bytes, length) & tablePtr->mask);
*oldChainPtr = entryPtr->nextPtr;
bucketPtr = &(tablePtr->buckets[index]);
entryPtr->nextPtr = *bucketPtr;
*bucketPtr = entryPtr;
}
}
if (oldBuckets != tablePtr->staticBuckets) {
ckfree((char *) oldBuckets);
}
}
#ifdef TCL_COMPILE_STATS
char *
TclLiteralStats(tablePtr)
LiteralTable *tablePtr;
{
#define NUM_COUNTERS 10
int count[NUM_COUNTERS], overflow, i, j;
double average, tmp;
register LiteralEntry *entryPtr;
char *result, *p;
for (i = 0; i < NUM_COUNTERS; i++) {
count[i] = 0;
}
overflow = 0;
average = 0.0;
for (i = 0; i < tablePtr->numBuckets; i++) {
j = 0;
for (entryPtr = tablePtr->buckets[i]; entryPtr != NULL;
entryPtr = entryPtr->nextPtr) {
j++;
}
if (j < NUM_COUNTERS) {
count[j]++;
} else {
overflow++;
}
tmp = j;
average += (tmp+1.0)*(tmp/tablePtr->numEntries)/2.0;
}
result = (char *) ckalloc((unsigned) ((NUM_COUNTERS*60) + 300));
sprintf(result, "%d entries in table, %d buckets\n",
tablePtr->numEntries, tablePtr->numBuckets);
p = result + strlen(result);
for (i = 0; i < NUM_COUNTERS; i++) {
sprintf(p, "number of buckets with %d entries: %d\n",
i, count[i]);
p += strlen(p);
}
sprintf(p, "number of buckets with %d or more entries: %d\n",
NUM_COUNTERS, overflow);
p += strlen(p);
sprintf(p, "average search distance for entry: %.1f", average);
return result;
}
#endif
#ifdef TCL_COMPILE_DEBUG
void
TclVerifyLocalLiteralTable(envPtr)
CompileEnv *envPtr;
{
register LiteralTable *localTablePtr = &(envPtr->localLitTable);
register LiteralEntry *localPtr;
char *bytes;
register int i;
int length, count;
count = 0;
for (i = 0; i < localTablePtr->numBuckets; i++) {
for (localPtr = localTablePtr->buckets[i];
localPtr != NULL; localPtr = localPtr->nextPtr) {
count++;
if (localPtr->refCount != -1) {
bytes = Tcl_GetStringFromObj(localPtr->objPtr, &length);
panic("TclVerifyLocalLiteralTable: local literal \"%.*s\" had bad refCount %d",
(length>60? 60 : length), bytes,
localPtr->refCount);
}
if (TclLookupLiteralEntry((Tcl_Interp *) envPtr->iPtr,
localPtr->objPtr) == NULL) {
bytes = Tcl_GetStringFromObj(localPtr->objPtr, &length);
panic("TclVerifyLocalLiteralTable: local literal \"%.*s\" is not global",
(length>60? 60 : length), bytes);
}
if (localPtr->objPtr->bytes == NULL) {
panic("TclVerifyLocalLiteralTable: literal has NULL string rep");
}
}
}
if (count != localTablePtr->numEntries) {
panic("TclVerifyLocalLiteralTable: local literal table had %d entries, should be %d",
count, localTablePtr->numEntries);
}
}
void
TclVerifyGlobalLiteralTable(iPtr)
Interp *iPtr;
{
register LiteralTable *globalTablePtr = &(iPtr->literalTable);
register LiteralEntry *globalPtr;
char *bytes;
register int i;
int length, count;
count = 0;
for (i = 0; i < globalTablePtr->numBuckets; i++) {
for (globalPtr = globalTablePtr->buckets[i];
globalPtr != NULL; globalPtr = globalPtr->nextPtr) {
count++;
if (globalPtr->refCount < 1) {
bytes = Tcl_GetStringFromObj(globalPtr->objPtr, &length);
panic("TclVerifyGlobalLiteralTable: global literal \"%.*s\" had bad refCount %d",
(length>60? 60 : length), bytes,
globalPtr->refCount);
}
if (globalPtr->objPtr->bytes == NULL) {
panic("TclVerifyGlobalLiteralTable: literal has NULL string rep");
}
}
}
if (count != globalTablePtr->numEntries) {
panic("TclVerifyGlobalLiteralTable: global literal table had %d entries, should be %d",
count, globalTablePtr->numEntries);
}
}
#endif