1
2/***********************************************************
3Copyright 1987, 1988, 1990 by Digital Equipment Corporation, Maynard,
4
5                        All Rights Reserved
6
7Permission to use, copy, modify, and distribute this software and its
8documentation for any purpose and without fee is hereby granted,
9provided that the above copyright notice appear in all copies and that
10both that copyright notice and this permission notice appear in
11supporting documentation, and that the name Digital not be
12used in advertising or publicity pertaining to distribution of the
13software without specific, written prior permission.
14
15DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
16ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
17DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
18ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
19WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
20ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
21SOFTWARE.
22
23******************************************************************/
24
25/*
26
27Copyright 1987, 1988, 1990, 1994, 1998  The Open Group
28
29Permission to use, copy, modify, distribute, and sell this software and its
30documentation for any purpose is hereby granted without fee, provided that
31the above copyright notice appear in all copies and that both that
32copyright notice and this permission notice appear in supporting
33documentation.
34
35The above copyright notice and this permission notice shall be included
36in all copies or substantial portions of the Software.
37
38THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
39OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
40MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
41IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
42OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
43ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
44OTHER DEALINGS IN THE SOFTWARE.
45
46Except as contained in this notice, the name of The Open Group shall
47not be used in advertising or otherwise to promote the sale, use or
48other dealings in this Software without prior written authorization
49from The Open Group.
50
51*/
52
53/* This module implements a simple sparse array.
54
55   XSaveContext(a,b,c,d) will store d in position (a,b,c) of the array.
56   XFindContext(a,b,c,&d) will set d to be the value in position (a,b,c).
57   XDeleteContext(a,b,c) will delete the entry in (a,b,c).
58
59   a is a display id, b is a resource id, and c is a Context.  d is just an
60   XPointer.  This code will work with any range of parameters, but is geared
61   to be most efficient with very few (one or two) different a's.
62
63*/
64
65#ifdef HAVE_CONFIG_H
66#include <config.h>
67#endif
68#include "Xlibint.h"
69#include "Xutil.h"
70#ifdef XTHREADS
71#include "locking.h"
72#endif
73
74#define INITHASHMASK 63 /* Number of entries originally in the hash table. */
75
76typedef struct _TableEntryRec {	/* Stores one entry. */
77    XID 			rid;
78    XContext			context;
79    XPointer			data;
80    struct _TableEntryRec	*next;
81} TableEntryRec, *TableEntry;
82
83typedef struct _XContextDB {	/* Stores hash table for one display. */
84    TableEntry *table;		/* Pointer to array of hash entries. */
85    int mask;			/* Current size of hash table minus 1. */
86    int numentries;		/* Number of entries currently in table. */
87#ifdef XTHREADS
88    LockInfoRec linfo;
89#endif
90} DBRec, *DB;
91
92#ifdef MOTIFBC
93static DB NullDB = (DB)0;
94#endif
95
96/* Given an XID and a context, returns a value between 0 and HashSize-1.
97   Currently, this requires that HashSize be a power of 2.
98*/
99
100#define Hash(db,rid,context) \
101    (db)->table[(((rid) << 1) + context) & (db)->mask]
102
103/* Resize the given db */
104
105static void ResizeTable(DB db)
106{
107    TableEntry *otable;
108    register TableEntry entry, next, *pold, *head;
109    register int i, j;
110
111    otable = db->table;
112    for (i = INITHASHMASK+1; (i + i) < db->numentries; )
113	i += i;
114    db->table = Xcalloc(i, sizeof(TableEntry));
115    if (!db->table) {
116	db->table = otable;
117	return;
118    }
119    j = db->mask + 1;
120    db->mask = i - 1;
121    for (pold = otable ; --j >= 0; pold++) {
122	for (entry = *pold; entry; entry = next) {
123	    next = entry->next;
124	    head = &Hash(db, entry->rid, entry->context);
125	    entry->next = *head;
126	    *head = entry;
127	}
128    }
129    Xfree(otable);
130}
131
132static void _XFreeContextDB(Display *display)
133{
134    register DB db;
135    register int i;
136    register TableEntry *pentry, entry, next;
137
138    db = display->context_db;
139    if (db) {
140	for (i = db->mask + 1, pentry = db->table ; --i >= 0; pentry++) {
141	    for (entry = *pentry; entry; entry = next) {
142		next = entry->next;
143		Xfree(entry);
144	    }
145	}
146	Xfree(db->table);
147	_XFreeMutex(&db->linfo);
148	Xfree(db);
149	display->context_db = NULL;
150    }
151}
152
153/* Public routines. */
154
155/* Save the given value of data to correspond with the keys XID and context.
156   Returns nonzero error code if an error has occurred, 0 otherwise.
157   Possible errors are Out-of-memory.
158*/
159
160int XSaveContext(
161    Display *display,
162    register XID rid,
163    register XContext context,
164    _Xconst char* data)
165{
166    DB *pdb;
167    register DB db;
168    TableEntry *head;
169    register TableEntry entry;
170
171#ifdef MOTIFBC
172    if (!display) {
173	pdb = &NullDB;
174	db = *pdb;
175    } else
176#endif
177    {
178	LockDisplay(display);
179	pdb = &display->context_db;
180	db = *pdb;
181	UnlockDisplay(display);
182    }
183    if (!db) {
184	db = Xmalloc(sizeof(DBRec));
185	if (!db)
186	    return XCNOMEM;
187	db->mask = INITHASHMASK;
188	db->table = Xcalloc(db->mask + 1, sizeof(TableEntry));
189	if (!db->table) {
190	    Xfree(db);
191	    return XCNOMEM;
192	}
193	db->numentries = 0;
194	_XCreateMutex(&db->linfo);
195#ifdef MOTIFBC
196	if (!display) *pdb = db; else
197#endif
198	{
199	    LockDisplay(display);
200	    *pdb = db;
201	    display->free_funcs->context_db = _XFreeContextDB;
202	    UnlockDisplay(display);
203	}
204    }
205    _XLockMutex(&db->linfo);
206    head = &Hash(db, rid, context);
207    _XUnlockMutex(&db->linfo);
208    for (entry = *head; entry; entry = entry->next) {
209	if (entry->rid == rid && entry->context == context) {
210	    entry->data = (XPointer)data;
211	    return 0;
212	}
213    }
214    entry = Xmalloc(sizeof(TableEntryRec));
215    if (!entry)
216	return XCNOMEM;
217    entry->rid = rid;
218    entry->context = context;
219    entry->data = (XPointer)data;
220    entry->next = *head;
221    *head = entry;
222    _XLockMutex(&db->linfo);
223    db->numentries++;
224    if (db->numentries > (db->mask << 2))
225	ResizeTable(db);
226    _XUnlockMutex(&db->linfo);
227    return 0;
228}
229
230
231
232/* Given an XID and context, returns the associated data.  Note that data
233   here is a pointer since it is a return value.  Returns nonzero error code
234   if an error has occurred, 0 otherwise.  Possible errors are Entry-not-found.
235*/
236
237int XFindContext(Display *display, XID rid, XContext context, XPointer *data)
238{
239    register DB db;
240    register TableEntry entry;
241
242#ifdef MOTIFBC
243    if (!display) db = NullDB; else
244#endif
245    {
246	LockDisplay(display);
247	db = display->context_db;
248	UnlockDisplay(display);
249    }
250    if (!db)
251	return XCNOENT;
252    _XLockMutex(&db->linfo);
253    for (entry = Hash(db, rid, context); entry; entry = entry->next)
254    {
255	if (entry->rid == rid && entry->context == context) {
256	    *data = (XPointer)entry->data;
257	    _XUnlockMutex(&db->linfo);
258	    return 0;
259	}
260    }
261    _XUnlockMutex(&db->linfo);
262    return XCNOENT;
263}
264
265
266
267/* Deletes the entry for the given XID and context from the datastructure.
268   This returns the same thing that FindContext would have returned if called
269   with the same arguments.
270*/
271
272int XDeleteContext(Display *display, XID rid, XContext context)
273{
274    register DB db;
275    register TableEntry entry, *prev;
276
277#ifdef MOTIFBC
278    if (!display) db = NullDB; else
279#endif
280    {
281	LockDisplay(display);
282	db = display->context_db;
283	UnlockDisplay(display);
284    }
285    if (!db)
286	return XCNOENT;
287    _XLockMutex(&db->linfo);
288    for (prev = &Hash(db, rid, context);
289	 (entry = *prev);
290	 prev = &entry->next) {
291	if (entry->rid == rid && entry->context == context) {
292	    *prev = entry->next;
293	    Xfree(entry);
294	    db->numentries--;
295	    if (db->numentries < db->mask && db->mask > INITHASHMASK)
296		ResizeTable(db);
297	    _XUnlockMutex(&db->linfo);
298	    return 0;
299	}
300    }
301    _XUnlockMutex(&db->linfo);
302    return XCNOENT;
303}
304