⟦0d72ce27e⟧

TextFile

/*
 *	$Source: /u1/X/DECToolkit/src/RCS/Context.c,v $
 *	$Header: Context.c,v 1.1 86/12/17 09:01:00 swick Exp $
 */

#ifndef lint
static char *rcsid_Context_c = "$Header: Context.c,v 1.1 86/12/17 09:01:00 swick Exp $";
#endif	lint

#ifndef lint
static  char    *sccsid = "@(#)Context.c	1.4          12/11/86";
#endif lint
/*
 *			  COPYRIGHT 1986
 *		   DIGITAL EQUIPMENT CORPORATION
 *		       MAYNARD, MASSACHUSETTS
 *			ALL RIGHTS RESERVED.
 *
 * THE INFORMATION IN THIS SOFTWARE IS SUBJECT TO CHANGE WITHOUT NOTICE AND
 * SHOULD NOT BE CONSTRUED AS A COMMITMENT BY DIGITAL EQUIPMENT CORPORATION.
 * DIGITAL MAKES NO REPRESENTATIONS ABOUT THE SUITABILITY OF THIS SOFTWARE FOR
 * ANY PURPOSE.  IT IS SUPPLIED "AS IS" WITHOUT EXPRESS OR IMPLIED WARRANTY.
 *
 * IF THE SOFTWARE IS MODIFIED IN A MANNER CREATING DERIVATIVE COPYRIGHT RIGHTS,
 * APPROPRIATE LEGENDS MAY BE PLACED ON THE DERIVATIVE WORK IN ADDITION TO THAT
 * SET FORTH ABOVE.
 *
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted, provided
 * that the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting documentation,
 * and that the name of Digital Equipment Corporation not be used in advertising
 * or publicity pertaining to distribution of the software without specific, 
 * written prior permission.
 */


/* Created by weissman, Thu Jun 26 15:18:59 1986 */

/* This module implements a simple sparse array.

   SaveEntry(a,b,c) will store c in position (a,b) of the array.
   FindEntry(a,b,&c) will set c to be the value in position (a,b).
   DeleteEntry(a,b) will delete the entry in (a,b).
   b = UniqueEntry() allocates a unique type (b).

   These functions all return an error value which is one of:

	ERRNONE	   :  No error.
	ERRMEMORY  :  Out of memory.
	ERRNOTFOUND:  Entry not found.

   These values are all defined in the header file Toolkit.h.
*/

#include <stdio.h>
#include <X/Xlib.h>
#include "Toolkit.h"

#define INITHASHSIZE 1024 /* Number of entries originally in the hash table. */


typedef struct _TableEntry {	/* Stores one entry. */
    Window window;
    TEntryType type;
    caddr_t data;
    struct _TableEntry *next;
} TableEntry;

extern char *Tcalloc(), *Tmalloc();

static TableEntry **HashTable = NULL;

static int UniqueType = 0; /* next type to hand out */
static int HashSize = INITHASHSIZE/2; /* Current size of hash table */
static int NumEntries = 0;	/* How many entries are currently in table */
static int MaxEntries = -1; /* How many entries we can take before */
				      /* increasing table size.		     */


/* Given a Window and a type, returns a value between 0 and HashSize-1.
   Currently, this requires that HashSize be a power of 2.
*/

#define HashValue(window,type) \
    (((window << 3) + type) & (HashSize - 1))


static int ResizeTable(NewSize)
int NewSize;
{
    TableEntry **OldHashTable;
    TableEntry *CurEntry,*NextEntry;
    int i,OldHashSize,CurHash;
    OldHashTable = HashTable;
    OldHashSize = HashSize;
    HashTable = (TableEntry **)Tcalloc((unsigned)NewSize,sizeof(TableEntry *));
    if (HashTable == NULL) {
	HashTable = OldHashTable;
	return ERRMEMORY;
    }
    HashSize = NewSize;
    MaxEntries = HashSize; /* When to next resize the hash table. */
    if (OldHashTable != NULL) {
	for (i=0 ; i<OldHashSize ; i++) {
	    CurEntry = OldHashTable[i] ;
	    while (CurEntry != NULL) {
		DeleteEntry(CurEntry->window,CurEntry->type);
		NextEntry = CurEntry->next;
		CurHash = HashValue(CurEntry->window,CurEntry->type);
		CurEntry->next = HashTable[CurHash];
		HashTable[CurHash] = CurEntry;
		CurEntry = NextEntry;
	    }
	}
	free((char *) OldHashTable);
    }
    return ERRNONE;
}

/* Returns an Entry type which is guaranteed to be unique.
*/

TEntryType UniqueEntryType()
{
    return ((TEntryType) ++UniqueType);
}


/* Save the given value of data to correspond with the keys Window and type.
   If an entry with the given Window and type already exists, this one will 
   override it; however, such an override has costs in time and space.  It
   is better to call DeleteEntry first if you know the entry already exists.
   Returns nonzero error code if an error has occured, 0 otherwise.
   Possible errors are Out-of-memory.
*/   

SaveEntry(window,type,data)
Window window;
TEntryType type;
caddr_t data;
{
    int CurHash;
    TableEntry *CurEntry;
    if (++NumEntries > MaxEntries) 
	if (ResizeTable(HashSize * 2) == ERRMEMORY)
	    return ERRMEMORY;
    CurEntry = (TableEntry *)Tmalloc(sizeof(TableEntry));
    if (CurEntry == NULL) return ERRMEMORY;
    CurEntry->window = window;
    CurEntry->type = type;
    CurEntry->data = data;
    CurHash = HashValue(window,type);
    CurEntry->next = HashTable[CurHash];
    HashTable[CurHash] = CurEntry;
    return ERRNONE;
}



/* Given a window and type, returns the associated data.  Note that data here 
   is a pointer since it is a return value.  Returns nonzero error code
   if an error has occured, 0 otherwise.  Possible errors are Entry-not-found.
*/

FindEntry(window,type,data)
Window window;
TEntryType type;
caddr_t *data;    /* return value */
{
    TableEntry *CurEntry;
    for (CurEntry = HashTable[HashValue(window,type)];
	 CurEntry != NULL;
	 CurEntry = CurEntry->next)
    {
	if (CurEntry->window == window && CurEntry->type == type) {
	    *data = CurEntry->data;
	    return ERRNONE;
	}
    }
    return ERRNOTFOUND;
}



/* Deletes all entries for the given window and type from the datastructure.
   This returns the same thing that FindEntry would have returned if called
   with the same arguments.  If the given window and type isn't found, it
   returns -1; otherwise it returns the value stored as data for that entry.
*/

DeleteEntry(window,type)
Window window;
TEntryType type;
{
    int CurHash,Result;
    TableEntry *CurEntry,*PrevEntry,*NextEntry;
    Result = -1;
    CurHash = HashValue(window,type);
    PrevEntry = NULL;
    CurEntry = HashTable[CurHash];
    while (CurEntry != NULL) {
	if (CurEntry->window == window && CurEntry->type == type) {
	    NumEntries--;
	    if (Result == -1) Result = (int) CurEntry->data;
	    NextEntry = CurEntry->next;
	    if (PrevEntry == NULL) {
		HashTable[CurHash] = NextEntry;
	    } else {
		PrevEntry->next = NextEntry;
	    }
	    free((char *) CurEntry);
	    CurEntry = NextEntry;
	} else {
	    PrevEntry = CurEntry;
	    CurEntry = CurEntry->next;
	}
    }
    return Result;
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦0d72ce27e⟧ TextFile

Derivation

TextFile
