1/*
2 *
3 * tclXhandles.c --
4 *
5 * Tcl handles.  Provides a mechanism for managing expandable tables that are
6 * addressed by textual handles.
7 *-----------------------------------------------------------------------------
8 * Copyright 1991-1999 Karl Lehenbauer and Mark Diekhans.
9 *
10 * Permission to use, copy, modify, and distribute this software and its
11 * documentation for any purpose and without fee is hereby granted, provided
12 * that the above copyright notice appear in all copies.  Karl Lehenbauer and
13 * Mark Diekhans make no representations about the suitability of this
14 * software for any purpose.  It is provided "as is" without express or
15 * implied warranty.
16 *-----------------------------------------------------------------------------
17 * $Id: tclXhandles.c,v 1.1 2001/10/24 23:31:48 hobbs Exp $
18 *-----------------------------------------------------------------------------
19 */
20
21#include "tclExtdInt.h"
22
23/*
24 * Variable set to contain the alignment factor (in bytes) for this machine.
25 * It is set on the first table initialization.
26 */
27static int entryAlignment = 0;
28
29/*
30 * Rounded size of an entry header
31 */
32static int entryHeaderSize = 0;
33
34/*
35 * Marco to rounded up a size to be a multiple of (void *).  This is required
36 * for systems that have alignment restrictions on pointers and data.
37 */
38#define ROUND_ENTRY_SIZE(size) \
39    ((((size) + entryAlignment - 1) / entryAlignment) * entryAlignment)
40
41/*
42 * This is the table header.  It is separately allocated from the table body,
43 * since it must keep track of a table body that might move.  Each entry in the
44 * table is preceded with a header which has the free list link, which is a
45 * entry index of the next free entry.  Special values keep track of allocated
46 * entries.
47 */
48
49#define NULL_IDX      -1
50#define ALLOCATED_IDX -2
51
52typedef unsigned char ubyte_t;
53typedef ubyte_t *ubyte_pt;
54
55typedef struct {
56    int      useCount;          /* Keeps track of the number sharing       */
57    int      entrySize;         /* Entry size in bytes, including header   */
58    int      tableSize;         /* Current number of entries in the table  */
59    int      freeHeadIdx;       /* Index of first free entry in the table  */
60    ubyte_pt bodyPtr;           /* Pointer to table body                   */
61    int      baseLength;        /* Length of handleBase.                   */
62    char     handleBase [1];    /* Base handle name.  MUST BE LAST FIELD!  */
63    } tblHeader_t;
64typedef tblHeader_t *tblHeader_pt;
65
66typedef struct {
67    int freeLink;
68  } entryHeader_t;
69typedef entryHeader_t *entryHeader_pt;
70
71/*
72 * This macro is used to return a pointer to an entry, given its index.
73 */
74#define TBL_INDEX(hdrPtr, idx) \
75    ((entryHeader_pt) (hdrPtr->bodyPtr + (hdrPtr->entrySize * idx)))
76
77/*
78 * This macros to convert between pointers to the user and header area of
79 * an table entry.
80 */
81#define USER_AREA(entryHdrPtr) \
82    ((void_pt) (((ubyte_pt) entryHdrPtr) + entryHeaderSize))
83#define HEADER_AREA(entryPtr) \
84    ((entryHeader_pt) (((ubyte_pt) entryPtr) - entryHeaderSize))
85
86/*
87 * Prototypes of internal functions.
88 */
89static void
90LinkInNewEntries _ANSI_ARGS_((tblHeader_pt tblHdrPtr,
91                              int          newIdx,
92                              int          numEntries));
93
94static void
95ExpandTable _ANSI_ARGS_((tblHeader_pt tblHdrPtr,
96                         int          neededIdx));
97
98static entryHeader_pt
99AllocEntry _ANSI_ARGS_((tblHeader_pt  tblHdrPtr,
100                        int          *entryIdxPtr));
101
102static int
103HandleDecodeObj _ANSI_ARGS_((Tcl_Interp   *interp,
104                             tblHeader_pt  tblHdrPtr,
105                             CONST char   *handle));
106
107static int
108HandleDecode _ANSI_ARGS_((Tcl_Interp   *interp,
109                          tblHeader_pt  tblHdrPtr,
110                          CONST char   *handle));
111
112
113/*=============================================================================
114 * LinkInNewEntries --
115 *   Build free links through the newly allocated part of a table.
116 *
117 * Parameters:
118 *   o tblHdrPtr (I) - A pointer to the table header.
119 *   o newIdx (I) - Index of the first new entry.
120 *   o numEntries (I) - The number of new entries.
121 *-----------------------------------------------------------------------------
122 */
123static void
124LinkInNewEntries (tblHdrPtr, newIdx, numEntries)
125    tblHeader_pt tblHdrPtr;
126    int          newIdx;
127    int          numEntries;
128{
129    int            entIdx, lastIdx;
130    entryHeader_pt entryHdrPtr;
131
132    lastIdx = newIdx + numEntries - 1;
133
134    for (entIdx = newIdx; entIdx < lastIdx; entIdx++) {
135        entryHdrPtr = TBL_INDEX (tblHdrPtr, entIdx);
136        entryHdrPtr->freeLink = entIdx + 1;
137    }
138    entryHdrPtr = TBL_INDEX (tblHdrPtr, lastIdx);
139    entryHdrPtr->freeLink = tblHdrPtr->freeHeadIdx;
140    tblHdrPtr->freeHeadIdx = newIdx;
141
142}
143
144/*=============================================================================
145 * ExpandTable --
146 *   Expand a handle table, doubling its size.
147 * Parameters:
148 *   o tblHdrPtr (I) - A pointer to the table header.
149 *   o neededIdx (I) - If positive, then the table will be expanded so that
150 *     this entry is available.  If -1, then just expand by the number of
151 *     entries specified on table creation.  MUST be smaller than this size.
152 *-----------------------------------------------------------------------------
153 */
154static void
155ExpandTable (tblHdrPtr, neededIdx)
156    tblHeader_pt tblHdrPtr;
157    int          neededIdx;
158{
159    ubyte_pt oldbodyPtr = tblHdrPtr->bodyPtr;
160    int      numNewEntries;
161    int      newSize;
162
163    if (neededIdx < 0)
164        numNewEntries = tblHdrPtr->tableSize;
165    else
166        numNewEntries = (neededIdx - tblHdrPtr->tableSize) + 1;
167    newSize = (tblHdrPtr->tableSize + numNewEntries) * tblHdrPtr->entrySize;
168
169    tblHdrPtr->bodyPtr = (ubyte_pt) ckalloc (newSize);
170    memcpy (tblHdrPtr->bodyPtr, oldbodyPtr,
171            (tblHdrPtr->tableSize * tblHdrPtr->entrySize));
172    LinkInNewEntries (tblHdrPtr, tblHdrPtr->tableSize, numNewEntries);
173    tblHdrPtr->tableSize += numNewEntries;
174    ckfree ((char *) oldbodyPtr);
175
176}
177
178/*=============================================================================
179 * AllocEntry --
180 *   Allocate a table entry, expanding if necessary.
181 *
182 * Parameters:
183 *   o tblHdrPtr (I) - A pointer to the table header.
184 *   o entryIdxPtr (O) - The index of the table entry is returned here.
185 * Returns:
186 *    The a pointer to the entry.
187 *-----------------------------------------------------------------------------
188 */
189static entryHeader_pt
190AllocEntry (tblHdrPtr, entryIdxPtr)
191    tblHeader_pt  tblHdrPtr;
192    int          *entryIdxPtr;
193{
194    int            entryIdx;
195    entryHeader_pt entryHdrPtr;
196
197    if (tblHdrPtr->freeHeadIdx == NULL_IDX)
198        ExpandTable (tblHdrPtr, -1);
199
200    entryIdx = tblHdrPtr->freeHeadIdx;
201    entryHdrPtr = TBL_INDEX (tblHdrPtr, entryIdx);
202    tblHdrPtr->freeHeadIdx = entryHdrPtr->freeLink;
203    entryHdrPtr->freeLink = ALLOCATED_IDX;
204
205    *entryIdxPtr = entryIdx;
206    return entryHdrPtr;
207
208}
209
210/*=============================================================================
211 * HandleDecode --
212 *   Decode handle into an entry number.
213 *
214 *   Same as HandleDecode except it uses the object-based result
215 *   mechanism if an error occurs.
216 *
217 * Parameters:
218 *   o interp (I) - A error message may be returned in result.
219 *   o tblHdrPtr (I) - A pointer to the table header.
220 *   o handle (I) - Handle to decode.
221 * Returns:
222 *   The entry index decoded from the handle, or a negative number if an error
223 *   occured.
224 *-----------------------------------------------------------------------------
225 */
226static int
227HandleDecode (interp, tblHdrPtr, handle)
228    Tcl_Interp   *interp;
229    tblHeader_pt  tblHdrPtr;
230    CONST char   *handle;
231{
232    unsigned entryIdx;
233
234    if ((strncmp (tblHdrPtr->handleBase, (char *) handle,
235             tblHdrPtr->baseLength) != 0) ||
236             !TclX_StrToUnsigned (&handle [tblHdrPtr->baseLength], 10,
237                                 &entryIdx)) {
238        TclX_AppendObjResult (interp, "invalid ", tblHdrPtr->handleBase,
239                              " handle \"", handle, "\"", (char *) NULL);
240        return -1;
241    }
242    return entryIdx;
243}
244
245/*=============================================================================
246 * HandleDecodeObj --
247 *   Decode handle into an entry number.
248 *
249 *   Same as HandleDecode except it uses the object-based result
250 *   mechanism if an error occurs.
251 *
252 * Parameters:
253 *   o interp (I) - A error message may be returned in result.
254 *   o tblHdrPtr (I) - A pointer to the table header.
255 *   o handle (I) - Handle to decode.
256 * Returns:
257 *   The entry index decoded from the handle, or a negative number if an error
258 *   occured.
259 *-----------------------------------------------------------------------------
260 */
261static int
262HandleDecodeObj (interp, tblHdrPtr, handle)
263    Tcl_Interp   *interp;
264    tblHeader_pt  tblHdrPtr;
265    CONST char   *handle;
266{
267    unsigned entryIdx;
268
269    if ((strncmp (tblHdrPtr->handleBase, (char *) handle,
270                  tblHdrPtr->baseLength) != 0) ||
271        !TclX_StrToUnsigned (&handle [tblHdrPtr->baseLength], 10,
272                             &entryIdx)) {
273        TclX_AppendObjResult (interp, "invalid ", tblHdrPtr->handleBase,
274                              " handle \"", handle, "\"", (char *) NULL);
275        return -1;
276    }
277    return entryIdx;
278}
279
280/*=============================================================================
281 * TclX_HandleTblInit --
282 *   Create and initialize a Tcl dynamic handle table.  The use count on the
283 *   table is set to one.
284 * Parameters:
285 *   o handleBase(I) - The base name of the handle, the handle will be returned
286 *     in the form "baseNN", where NN is the table entry number.
287 *   o entrySize (I) - The size of an entry, in bytes.
288 *   o initEntries (I) - Initial size of the table, in entries.
289 * Returns:
290 *   A pointer to the table header.
291 *-----------------------------------------------------------------------------
292 */
293void_pt
294TclX_HandleTblInit (handleBase, entrySize, initEntries)
295    CONST char *handleBase;
296    int         entrySize;
297    int         initEntries;
298{
299    tblHeader_pt tblHdrPtr;
300    int          baseLength = strlen ((char *) handleBase);
301
302    /*
303     * It its not been calculated yet, determine the entry alignment required
304     * for this machine.
305     */
306    if (entryAlignment == 0) {
307        entryAlignment = sizeof (void *);
308        if (sizeof (long) > entryAlignment)
309            entryAlignment = sizeof (long);
310        if (sizeof (double) > entryAlignment)
311            entryAlignment = sizeof (double);
312        if (sizeof (off_t) > entryAlignment)
313            entryAlignment = sizeof (off_t);
314        entryHeaderSize = ROUND_ENTRY_SIZE (sizeof (entryHeader_t));
315    }
316
317    /*
318     * Set up the table entry.
319     */
320    tblHdrPtr = (tblHeader_pt) ckalloc (sizeof (tblHeader_t) + baseLength + 1);
321
322    tblHdrPtr->useCount = 1;
323    tblHdrPtr->baseLength = baseLength;
324    strcpy (tblHdrPtr->handleBase, (char *) handleBase);
325
326    /*
327     * Calculate entry size, including header, rounded up to sizeof (void *).
328     */
329    tblHdrPtr->entrySize = entryHeaderSize + ROUND_ENTRY_SIZE (entrySize);
330    tblHdrPtr->freeHeadIdx = NULL_IDX;
331    tblHdrPtr->tableSize = initEntries;
332    tblHdrPtr->bodyPtr =
333        (ubyte_pt) ckalloc (initEntries * tblHdrPtr->entrySize);
334    LinkInNewEntries (tblHdrPtr, 0, initEntries);
335
336    return (void_pt) tblHdrPtr;
337
338}
339
340/*=============================================================================
341 * TclX_HandleTblUseCount --
342 *   Alter the handle table use count by the specified amount, which can be
343 *   positive or negative.  Amount may be zero to retrieve the use count.
344 * Parameters:
345 *   o headerPtr (I) - Pointer to the table header.
346 *   o amount (I) - The amount to alter the use count by.
347 * Returns:
348 *   The resulting use count.
349 *-----------------------------------------------------------------------------
350 */
351int
352TclX_HandleTblUseCount (headerPtr, amount)
353    void_pt  headerPtr;
354    int      amount;
355{
356    tblHeader_pt   tblHdrPtr = (tblHeader_pt)headerPtr;
357
358    tblHdrPtr->useCount += amount;
359    return tblHdrPtr->useCount;
360}
361
362/*=============================================================================
363 * TclX_HandleTblRelease --
364 *   Decrement the use count on a Tcl dynamic handle table.  If the count
365 * goes to zero or negative, then release the table.
366 *
367 * Parameters:
368 *   o headerPtr (I) - Pointer to the table header.
369 *-----------------------------------------------------------------------------
370 */
371void
372TclX_HandleTblRelease (headerPtr)
373    void_pt headerPtr;
374{
375    tblHeader_pt  tblHdrPtr = (tblHeader_pt) headerPtr;
376
377    tblHdrPtr->useCount--;
378    if (tblHdrPtr->useCount <= 0) {
379        ckfree ((char *) tblHdrPtr->bodyPtr);
380        ckfree ((char *) tblHdrPtr);
381    }
382}
383
384/*=============================================================================
385 * TclX_HandleAlloc --
386 *   Allocate an entry and associate a handle with it.
387 *
388 * Parameters:
389 *   o headerPtr (I) - A pointer to the table header.
390 *   o handlePtr (O) - Buffer to return handle in. It must be big enough to
391 *     hold the name.
392 * Returns:
393 *   A pointer to the allocated entry (user part).
394 *-----------------------------------------------------------------------------
395 */
396void_pt
397TclX_HandleAlloc (headerPtr, handlePtr)
398    void_pt   headerPtr;
399    char     *handlePtr;
400{
401    tblHeader_pt   tblHdrPtr = (tblHeader_pt)headerPtr;
402    entryHeader_pt entryHdrPtr;
403    int            entryIdx;
404
405    entryHdrPtr = AllocEntry ((tblHeader_pt) headerPtr, &entryIdx);
406    sprintf (handlePtr, "%s%d", tblHdrPtr->handleBase, entryIdx);
407
408    return USER_AREA (entryHdrPtr);
409
410}
411
412/*=============================================================================
413 * TclX_HandleXlate --
414 *   Translate a handle to a entry pointer.
415 *
416 * Parameters:
417 *   o interp (I) - A error message may be returned in result.
418 *   o headerPtr (I) - A pointer to the table header.
419 *   o handle (I) - The handle assigned to the entry.
420 * Returns:
421 *   A pointer to the entry, or NULL if an error occured.
422 *-----------------------------------------------------------------------------
423 */
424void_pt
425TclX_HandleXlate (interp, headerPtr, handle)
426    Tcl_Interp *interp;
427    void_pt     headerPtr;
428    CONST char *handle;
429{
430    tblHeader_pt   tblHdrPtr = (tblHeader_pt)headerPtr;
431    entryHeader_pt entryHdrPtr;
432    int            entryIdx;
433
434    if ((entryIdx = HandleDecode (interp, tblHdrPtr, handle)) < 0)
435        return NULL;
436    entryHdrPtr = TBL_INDEX (tblHdrPtr, entryIdx);
437
438    if ((entryIdx >= tblHdrPtr->tableSize) ||
439            (entryHdrPtr->freeLink != ALLOCATED_IDX)) {
440        TclX_AppendObjResult (interp, tblHdrPtr->handleBase, " is not open",
441                              (char *) NULL);
442        return NULL;
443    }
444
445    return USER_AREA (entryHdrPtr);
446
447}
448
449/*=============================================================================
450 * TclX_HandleXlateObj --
451 *   Translate an object containing a handle name to a entry pointer.
452 *
453 * Parameters:
454 *   o interp (I) - A error message may be returned in result.
455 *   o headerPtr (I) - A pointer to the table header.
456 *   o handleObj (I) - The object containing the handle assigned to the entry.
457 * Returns:
458 *   A pointer to the entry, or NULL if an error occured.
459 *-----------------------------------------------------------------------------
460 */
461void_pt
462TclX_HandleXlateObj (interp, headerPtr, handleObj)
463    Tcl_Interp *interp;
464    void_pt     headerPtr;
465    Tcl_Obj *handleObj;
466{
467    tblHeader_pt   tblHdrPtr = (tblHeader_pt)headerPtr;
468    entryHeader_pt entryHdrPtr;
469    int            entryIdx;
470    char          *handle;
471
472    handle = Tcl_GetStringFromObj (handleObj, NULL);
473
474    if ((entryIdx = HandleDecodeObj (interp, tblHdrPtr, handle)) < 0)
475        return NULL;
476    entryHdrPtr = TBL_INDEX (tblHdrPtr, entryIdx);
477
478    if ((entryIdx >= tblHdrPtr->tableSize) ||
479            (entryHdrPtr->freeLink != ALLOCATED_IDX)) {
480        TclX_AppendObjResult (interp, tblHdrPtr->handleBase,
481                              " is not open", (char *) NULL);
482        return NULL;
483    }
484
485    return USER_AREA (entryHdrPtr);
486}
487
488/*=============================================================================
489 * TclX_HandleWalk --
490 *   Walk through and find every allocated entry in a table.  Entries may
491 *   be deallocated during a walk, but should not be allocated.
492 *
493 * Parameters:
494 *   o headerPtr (I) - A pointer to the table header.
495 *   o walkKeyPtr (I/O) - Pointer to a variable to use to keep track of the
496 *     place in the table.  The variable should be initialized to -1 before
497 *     the first call.
498 * Returns:
499 *   A pointer to the next allocated entry, or NULL if there are not more.
500 *-----------------------------------------------------------------------------
501 */
502void_pt
503TclX_HandleWalk (headerPtr, walkKeyPtr)
504    void_pt   headerPtr;
505    int      *walkKeyPtr;
506{
507    tblHeader_pt   tblHdrPtr = (tblHeader_pt)headerPtr;
508    int            entryIdx;
509    entryHeader_pt entryHdrPtr;
510
511    if (*walkKeyPtr == -1)
512        entryIdx = 0;
513    else
514        entryIdx = *walkKeyPtr + 1;
515
516    while (entryIdx < tblHdrPtr->tableSize) {
517        entryHdrPtr = TBL_INDEX (tblHdrPtr, entryIdx);
518        if (entryHdrPtr->freeLink == ALLOCATED_IDX) {
519            *walkKeyPtr = entryIdx;
520            return USER_AREA (entryHdrPtr);
521        }
522        entryIdx++;
523    }
524    return NULL;
525
526}
527
528/*=============================================================================
529 * TclX_WalkKeyToHandle --
530 *   Convert a walk key, as returned from a call to Tcl_HandleWalk into a
531 *   handle.  The Tcl_HandleWalk must have succeeded.
532 * Parameters:
533 *   o headerPtr (I) - A pointer to the table header.
534 *   o walkKey (I) - The walk key.
535 *   o handlePtr (O) - Buffer to return handle in. It must be big enough to
536 *     hold the name.
537 *-----------------------------------------------------------------------------
538 */
539void
540TclX_WalkKeyToHandle (headerPtr, walkKey, handlePtr)
541    void_pt   headerPtr;
542    int       walkKey;
543    char     *handlePtr;
544{
545    tblHeader_pt   tblHdrPtr = (tblHeader_pt)headerPtr;
546
547    sprintf (handlePtr, "%s%d", tblHdrPtr->handleBase, walkKey);
548
549}
550
551/*=============================================================================
552 * TclX_HandleFree --
553 *   Frees a handle table entry.
554 *
555 * Parameters:
556 *   o headerPtr (I) - A pointer to the table header.
557 *   o entryPtr (I) - Entry to free.
558 *-----------------------------------------------------------------------------
559 */
560void
561TclX_HandleFree (headerPtr, entryPtr)
562    void_pt headerPtr;
563    void_pt entryPtr;
564{
565    tblHeader_pt   tblHdrPtr = (tblHeader_pt)headerPtr;
566    entryHeader_pt entryHdrPtr;
567
568    entryHdrPtr = HEADER_AREA (entryPtr);
569    if (entryHdrPtr->freeLink != ALLOCATED_IDX)
570        panic ("Tcl_HandleFree: entry not allocated %x\n", entryHdrPtr);
571
572    entryHdrPtr->freeLink = tblHdrPtr->freeHeadIdx;
573    tblHdrPtr->freeHeadIdx =
574        (((ubyte_pt) entryHdrPtr) - tblHdrPtr->bodyPtr) / tblHdrPtr->entrySize;
575
576}
577
578
579
580