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