You can subscribe to this list here.
2000 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
(19) |
Jul
(96) |
Aug
(144) |
Sep
(222) |
Oct
(496) |
Nov
(171) |
Dec
(6) |
---|---|---|---|---|---|---|---|---|---|---|---|---|
2001 |
Jan
(4) |
Feb
(4) |
Mar
(9) |
Apr
(4) |
May
(12) |
Jun
(6) |
Jul
|
Aug
|
Sep
(1) |
Oct
(2) |
Nov
|
Dec
|
2002 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
(1) |
Jul
(52) |
Aug
(47) |
Sep
(47) |
Oct
(95) |
Nov
(56) |
Dec
(34) |
2003 |
Jan
(99) |
Feb
(116) |
Mar
(125) |
Apr
(99) |
May
(123) |
Jun
(69) |
Jul
(110) |
Aug
(130) |
Sep
(289) |
Oct
(211) |
Nov
(98) |
Dec
(140) |
2004 |
Jan
(85) |
Feb
(87) |
Mar
(342) |
Apr
(125) |
May
(101) |
Jun
(60) |
Jul
(151) |
Aug
(118) |
Sep
(162) |
Oct
(117) |
Nov
(125) |
Dec
(95) |
2005 |
Jan
(141) |
Feb
(54) |
Mar
(79) |
Apr
(83) |
May
(74) |
Jun
(125) |
Jul
(63) |
Aug
(89) |
Sep
(130) |
Oct
(89) |
Nov
(34) |
Dec
(39) |
2006 |
Jan
(98) |
Feb
(62) |
Mar
(56) |
Apr
(94) |
May
(169) |
Jun
(41) |
Jul
(34) |
Aug
(35) |
Sep
(132) |
Oct
(722) |
Nov
(381) |
Dec
(36) |
2007 |
Jan
(34) |
Feb
(174) |
Mar
(15) |
Apr
(35) |
May
(74) |
Jun
(15) |
Jul
(8) |
Aug
(18) |
Sep
(39) |
Oct
(125) |
Nov
(89) |
Dec
(129) |
2008 |
Jan
(176) |
Feb
(91) |
Mar
(69) |
Apr
(178) |
May
(310) |
Jun
(434) |
Jul
(171) |
Aug
(73) |
Sep
(187) |
Oct
(132) |
Nov
(259) |
Dec
(292) |
2009 |
Jan
(27) |
Feb
(54) |
Mar
(35) |
Apr
(54) |
May
(93) |
Jun
(10) |
Jul
(36) |
Aug
(36) |
Sep
(93) |
Oct
(52) |
Nov
(45) |
Dec
(74) |
2010 |
Jan
(20) |
Feb
(120) |
Mar
(165) |
Apr
(101) |
May
(56) |
Jun
(12) |
Jul
(73) |
Aug
(306) |
Sep
(154) |
Oct
(82) |
Nov
(63) |
Dec
(42) |
2011 |
Jan
(176) |
Feb
(86) |
Mar
(199) |
Apr
(86) |
May
(237) |
Jun
(50) |
Jul
(26) |
Aug
(56) |
Sep
(42) |
Oct
(62) |
Nov
(62) |
Dec
(52) |
2012 |
Jan
(35) |
Feb
(33) |
Mar
(128) |
Apr
(152) |
May
(133) |
Jun
(21) |
Jul
(74) |
Aug
(423) |
Sep
(165) |
Oct
(129) |
Nov
(387) |
Dec
(276) |
2013 |
Jan
(105) |
Feb
(30) |
Mar
(130) |
Apr
(42) |
May
(60) |
Jun
(79) |
Jul
(101) |
Aug
(46) |
Sep
(81) |
Oct
(14) |
Nov
(43) |
Dec
(4) |
2014 |
Jan
(25) |
Feb
(32) |
Mar
(30) |
Apr
(80) |
May
(42) |
Jun
(23) |
Jul
(68) |
Aug
(127) |
Sep
(112) |
Oct
(72) |
Nov
(29) |
Dec
(69) |
2015 |
Jan
(35) |
Feb
(49) |
Mar
(95) |
Apr
(10) |
May
(70) |
Jun
(64) |
Jul
(93) |
Aug
(85) |
Sep
(43) |
Oct
(38) |
Nov
(124) |
Dec
(29) |
2016 |
Jan
(253) |
Feb
(181) |
Mar
(132) |
Apr
(419) |
May
(68) |
Jun
(90) |
Jul
(52) |
Aug
(142) |
Sep
(131) |
Oct
(80) |
Nov
(84) |
Dec
(192) |
2017 |
Jan
(329) |
Feb
(842) |
Mar
(248) |
Apr
(85) |
May
(247) |
Jun
(186) |
Jul
(37) |
Aug
(73) |
Sep
(98) |
Oct
(108) |
Nov
(143) |
Dec
(143) |
2018 |
Jan
(155) |
Feb
(139) |
Mar
(72) |
Apr
(112) |
May
(82) |
Jun
(119) |
Jul
(24) |
Aug
(33) |
Sep
(179) |
Oct
(295) |
Nov
(111) |
Dec
(34) |
2019 |
Jan
(20) |
Feb
(29) |
Mar
(49) |
Apr
(89) |
May
(185) |
Jun
(131) |
Jul
(9) |
Aug
(59) |
Sep
(30) |
Oct
(44) |
Nov
(118) |
Dec
(53) |
2020 |
Jan
(70) |
Feb
(108) |
Mar
(50) |
Apr
(9) |
May
(70) |
Jun
(24) |
Jul
(103) |
Aug
(82) |
Sep
(132) |
Oct
(119) |
Nov
(174) |
Dec
(169) |
2021 |
Jan
(75) |
Feb
(51) |
Mar
(76) |
Apr
(73) |
May
(53) |
Jun
(120) |
Jul
(114) |
Aug
(73) |
Sep
(70) |
Oct
(18) |
Nov
(26) |
Dec
|
2022 |
Jan
(26) |
Feb
(63) |
Mar
(64) |
Apr
(64) |
May
(48) |
Jun
(74) |
Jul
(129) |
Aug
(106) |
Sep
(238) |
Oct
(169) |
Nov
(149) |
Dec
(111) |
2023 |
Jan
(110) |
Feb
(47) |
Mar
(82) |
Apr
(106) |
May
(168) |
Jun
(101) |
Jul
(155) |
Aug
(35) |
Sep
(51) |
Oct
(55) |
Nov
(134) |
Dec
(202) |
2024 |
Jan
(103) |
Feb
(129) |
Mar
(154) |
Apr
(89) |
May
(60) |
Jun
(162) |
Jul
(201) |
Aug
(61) |
Sep
(167) |
Oct
(111) |
Nov
(133) |
Dec
(141) |
2025 |
Jan
(122) |
Feb
(88) |
Mar
(106) |
Apr
(113) |
May
(203) |
Jun
(185) |
Jul
(124) |
Aug
(202) |
Sep
(176) |
Oct
(42) |
Nov
|
Dec
|
From: Joe E. <jen...@fl...> - 2010-02-01 20:01:14
|
Donal K. Fellows wrote: > On 01/02/2010 13:35, Alexandre Ferrieux wrote: > > No, specifically, NULL is not invalid in that context. It is just > > flagging VarIsUndefined, which is a special, but legal, state for > > array entries as you very well know. > > > > Generalizing, the idea is that 0xDEADBEEF is both certainly invalid > > for all pointer types that are not union members, and easy to spot by > > naked eye in gdb traces. > > There's no guarantee that it's distinct from the set of pointers. The > only value that's guaranteed to not point to anything is NULL. Right, there's no guarantee that this does anything useful. Setting 'ptr = (void*)0xDEADBEEF;' yields Undefined Behavior, so anything can happen, including that the program magically works correctly. In practice, however, it's a pretty reliable way to get a SIGBUS. Which is the desired effect in this case. > That > said, if you turn on Tcl's memory debugging then a block is filled with > 0x61 bytes when it is ckfree()d. That should be quite sufficiently > distinctive for finding problems where memory is accessed after it has > been disposed. Yep. Tcl_Obj records aren't passed to ckfree(), though [*], they're stored on a linked list. Alexandre is proposing a similar stomping scheme for them as is done for ckfree()d memory. I don't think it's a bad idea. --Joe English [*] Except when the core is compiled with a certain set of -D flags the #ifdeffery of which I'm not fully able to disentangle. |
From: Donald G P. <don...@ni...> - 2010-02-01 18:32:18
|
Alexandre Ferrieux wrote: > (3) What about obj->typePtr itself ? The reform you are talking about does not apply to objPtr->typePtr. That field must either hold a valid pointer to the Tcl_ObjType struct that governs the current intrep, or NULL to indicate there is no current intrep. No other state is valid. Unless you talking exclusively about those Tcl_Obj structs that have been returned to the free list. For those I don't think I care. -- | Don Porter Mathematical and Computational Sciences Division | | don...@ni... Information Technology Laboratory | | http://math.nist.gov/~DPorter/ NIST | |______________________________________________________________________| |
From: Alexandre F. <ale...@gm...> - 2010-02-01 15:19:11
|
On 2/1/10, Donal K. Fellows <don...@ma...> wrote: > On 01/02/2010 13:35, Alexandre Ferrieux wrote: > > > No, specifically, NULL is not invalid in that context. It is just > > flagging VarIsUndefined, which is a special, but legal, state for > > array entries as you very well know. > > > > Generalizing, the idea is that 0xDEADBEEF is both certainly invalid > > for all pointer types that are not union members, and easy to spot by > > naked eye in gdb traces. > > > > There's no guarantee that it's distinct from the set of pointers. The > only value that's guaranteed to not point to anything is NULL. Ah of course, I was focusing on aligned memory access, so any odd value would do. If we want to also catch unaligned (char *), then maybe (void *)(-1) is a better idea. So my proposal becomes: + varPtr->value.objPtr=(void *)(-1); And again, NULL doesn't fulfill the contract, since it most often is not really invalid. > That > said, if you turn on Tcl's memory debugging then a block is filled with > 0x61 bytes when it is ckfree()d. That should be quite sufficiently > distinctive for finding problems where memory is accessed after it has > been disposed. So, to summarize: - you're vetoing my proposal - you're proposing two "alternatives": (a) stick to NULL, which misses the point in not triggering any runtime fault in many areas of the core (b) use mem debug to isolate those bugs, which misses the point in two ways: - many code paths are different under mem debug, so some bugs are not catchable. Also some bugs manifest themselves in production only, where memedebug (or any custom rebuilt Tcl for that matter) is not an potion. - the resulting pointer is 0x61616161 or 0x6161616161616161, which has exactly the same profile as 0xDEADBEEF or (-1) regarding bus errors and segmentation faults. No, actually, (-1) is likely better, since no realistic heap or stack area would land there. (c) be content with remarks like this one, in the test suite: test trace-0.0 {memory corruption in trace (Tcl Bug 484339)} { # You may need Purify or Electric Fence to reliably # see this one fail. Am I summarizing accurately ? -Alex |
From: Donal K. F. <don...@ma...> - 2010-02-01 14:42:15
|
On 01/02/2010 13:35, Alexandre Ferrieux wrote: > No, specifically, NULL is not invalid in that context. It is just > flagging VarIsUndefined, which is a special, but legal, state for > array entries as you very well know. > > Generalizing, the idea is that 0xDEADBEEF is both certainly invalid > for all pointer types that are not union members, and easy to spot by > naked eye in gdb traces. There's no guarantee that it's distinct from the set of pointers. The only value that's guaranteed to not point to anything is NULL. That said, if you turn on Tcl's memory debugging then a block is filled with 0x61 bytes when it is ckfree()d. That should be quite sufficiently distinctive for finding problems where memory is accessed after it has been disposed. Donal. |
From: Alexandre F. <ale...@gm...> - 2010-02-01 13:58:03
|
On 2/1/10, Kevin Kenny <kev...@gm...> wrote: > Donal K. Fellows wrote: > > On 01/02/2010 13:06, Alexandre Ferrieux wrote: > >> (1) Am I allowed to commit the following 1-line addition to tclVar.c: > >> > >> @@ -5610,6 +5624,7 @@ FreeVarEntry( > >> > >> if (TclIsVarUndefined(varPtr)&& !TclIsVarTraced(varPtr) > >> && (VarHashRefCount(varPtr) == 1)) { > >> + varPtr->value.objPtr=(void *)0xdeadbeef; > >> ckfree((char *) varPtr); > >> } else { > >> VarHashInvalidateEntry(varPtr); > >> > >> Rationale: it makes more reliable any time-bomb-like crash related to > >> nasty reentrant trace issues like 2939073. Allows my fix for this bug > >> to contain a test case. > > > > I'd be more inclined to put a NULL in there so that we're making the > > clear statement that this memory cell isn't pointing to anything. YMMV. > > > Let me make sure we're on the same page. Pointers in unused/freed > objects should be set to NULL - the only constant that we know doesn't > point to anything. Yes, but more often than not, instead of blindly trying an indirection, the code uses the special value NULL as a flag (like an undefined array entry pending true eradication), so the value doesn't generate immediate SIGBUS as it should. In addition to VarInHash (or Var), this is also notably true of Tcl_Obj, where "typePtr==NULL" means pure string. -Alex |
From: Alexandre F. <ale...@gm...> - 2010-02-01 13:41:22
|
On 2/1/10, Donal K. Fellows <don...@ma...> wrote: > On 01/02/2010 13:06, Alexandre Ferrieux wrote: > > > (1) Am I allowed to commit the following 1-line addition to tclVar.c: > > > > @@ -5610,6 +5624,7 @@ FreeVarEntry( > > > > if (TclIsVarUndefined(varPtr)&& !TclIsVarTraced(varPtr) > > && (VarHashRefCount(varPtr) == 1)) { > > + varPtr->value.objPtr=(void *)0xdeadbeef; > > ckfree((char *) varPtr); > > } else { > > VarHashInvalidateEntry(varPtr); > > > > Rationale: it makes more reliable any time-bomb-like crash related to > > nasty reentrant trace issues like 2939073. Allows my fix for this bug > > to contain a test case. > > > > I'd be more inclined to put a NULL in there so that we're making the > clear statement that this memory cell isn't pointing to anything. YMMV. No, specifically, NULL is not invalid in that context. It is just flagging VarIsUndefined, which is a special, but legal, state for array entries as you very well know. Generalizing, the idea is that 0xDEADBEEF is both certainly invalid for all pointer types that are not union members, and easy to spot by naked eye in gdb traces. -Alex |
From: Kevin K. <kev...@gm...> - 2010-02-01 13:40:39
|
Donal K. Fellows wrote: > On 01/02/2010 13:06, Alexandre Ferrieux wrote: >> (1) Am I allowed to commit the following 1-line addition to tclVar.c: >> >> @@ -5610,6 +5624,7 @@ FreeVarEntry( >> >> if (TclIsVarUndefined(varPtr)&& !TclIsVarTraced(varPtr) >> && (VarHashRefCount(varPtr) == 1)) { >> + varPtr->value.objPtr=(void *)0xdeadbeef; >> ckfree((char *) varPtr); >> } else { >> VarHashInvalidateEntry(varPtr); >> >> Rationale: it makes more reliable any time-bomb-like crash related to >> nasty reentrant trace issues like 2939073. Allows my fix for this bug >> to contain a test case. > > I'd be more inclined to put a NULL in there so that we're making the > clear statement that this memory cell isn't pointing to anything. YMMV. Let me make sure we're on the same page. Pointers in unused/freed objects should be set to NULL - the only constant that we know doesn't point to anything. Other data can be set to some arbitrary constant like 0xa1C0ffee or 0xBadDecaf. For speed, the intentional spoliation of freed data should perhaps be conditioned on being in a debug build. And it's a very good idea, go for it! Donal, do you agree? -- 73 de ke9tv/2, Kevin |
From: Donal K. F. <don...@ma...> - 2010-02-01 13:12:19
|
On 01/02/2010 13:06, Alexandre Ferrieux wrote: > (1) Am I allowed to commit the following 1-line addition to tclVar.c: > > @@ -5610,6 +5624,7 @@ FreeVarEntry( > > if (TclIsVarUndefined(varPtr)&& !TclIsVarTraced(varPtr) > && (VarHashRefCount(varPtr) == 1)) { > + varPtr->value.objPtr=(void *)0xdeadbeef; > ckfree((char *) varPtr); > } else { > VarHashInvalidateEntry(varPtr); > > Rationale: it makes more reliable any time-bomb-like crash related to > nasty reentrant trace issues like 2939073. Allows my fix for this bug > to contain a test case. I'd be more inclined to put a NULL in there so that we're making the clear statement that this memory cell isn't pointing to anything. YMMV. > (2) What about reusing the same idea in other areas as well ? > (3) What about obj->typePtr itself ? Again, I'd be inclined to go with using NULL. But there's nothing wrong at all with doing this stuff. Well, so long as we make sure all the problems associated with it go away afterwards, but it's for finding those things that we'd consider doing this in the first place. :-) Donal. |
From: Alexandre F. <ale...@gm...> - 2010-02-01 13:06:06
|
Hello, One particularly time consuming source of bugs is that of reuse of a freed structure. When "reuse" means rewrite, the heap can get corrupted pretty fast, and when it means only re-read, the effect can be felt *much* later and much more randomly.... A recent sweeping change (by Don IIRC) in that area was resetting the typePtr of freed Tcl-Objs. That's one step in the good direction. However, as bug 2939073 shows: https://sourceforge.net/tracker/?func=detail&atid=110894&aid=2939073&group_id=10894 there are numerous other things whose refcount can be botched, and hence lending themselves to reuse-after-free (here, VarInHash structures). While solving that bug, I found it annoying that the effect was so random and so hard to keep in an atomic case. One efficient solution consists of poking "visibly" invalid values in key fields of the structure, just before freeing it: var->objPtr = (Tcl_Obj *) 0xDEADBEEF ; What's nice with the method is that it is much more efficient and readable than sprinkling the code with explicit validity checks (like refcount>0): indeed, the memory access itself will do the test, the result being a SIGBUS or SIGSEGV at the point of illegal reuse. Of course this works only for structures holding fields which are frequently used as pointers. Better this than nothing.... Questions: (1) Am I allowed to commit the following 1-line addition to tclVar.c: @@ -5610,6 +5624,7 @@ FreeVarEntry( if (TclIsVarUndefined(varPtr) && !TclIsVarTraced(varPtr) && (VarHashRefCount(varPtr) == 1)) { + varPtr->value.objPtr=(void *)0xdeadbeef; ckfree((char *) varPtr); } else { VarHashInvalidateEntry(varPtr); Rationale: it makes more reliable any time-bomb-like crash related to nasty reentrant trace issues like 2939073. Allows my fix for this bug to contain a test case. (2) What about reusing the same idea in other areas as well ? (3) What about obj->typePtr itself ? -Alex |
From: Alexandre F. <ale...@gm...> - 2010-02-01 08:58:14
|
Hello Andy, On 2/1/10, Andy Goth <unu...@ai...> wrote: > (Is this the right forum for this type of discussion?) If it's not, we're doomed :} > I believe it is possible to merge the list and dict Tcl_Obj types such that a dict is simply a list whose intrep contains some extra indexing information; dict extends list without replacing it, like a subclass. This change can be made without affecting script-level, API-level, or even binary-level compatibility. The only observable difference should be a performance improvement in some circumstances from reduced shimmering. I sympathetize with the idea of inheritance among obj types, but given Donal's reaction to the suggestion I have more or less given it up: http://groups.google.com/group/comp.lang.tcl/tree/browse_frm/thread/a5214ae93e0294ac/0c62a476064031b1?rnum=11&q=polymorphism&_done=%2Fgroup%2Fcomp.lang.tcl%2Fbrowse_frm%2Fthread%2Fa5214ae93e0294ac%2Fe929b181c5aac543%3Flnk%3Dgst%26q%3Dpolymorphism%26safe%3Dimages%26#doc_2fe1f8c2cf7e339a I must say that the lack of a "compelling need" plays an important role though... > The idea came about while working on processing HTTP headers in Wibble. Headers can repeat, so I create a key/value list using [lappend] instead of [dict set]. Most of the time header repetition can be neglected, so the resulting list is conveniently accessed using [dict get], which returns the last (usually only) matching entry. However, this incurs a significant shimmering penalty for every lookup. If [dict get] were to access a persistent index over the list, rather than insisting on storing the values themselves in the index, this shimmering would not take place. (The Wibble version I describe hasn't been posted to the Wiki yet.) Uh, maybe I'm missing something, but doing this you'll wreck repeated headers, right ? The standard idiom for {HTTP,SMTP,SIP} headers is rather (with array, translate to dict if you want): lappend values($header) value so that for non-repeated headers you need an extra [lindex 0], but in exchange you have absolutely no shimmering. Given this compromise, is there a "compelling need" for a new bump in code complexity ? -Alex |
From: Andy G. <unu...@ai...> - 2010-02-01 06:24:24
|
(Is this the right forum for this type of discussion?) I believe it is possible to merge the list and dict Tcl_Obj types such that a dict is simply a list whose intrep contains some extra indexing information; dict extends list without replacing it, like a subclass. This change can be made without affecting script-level, API-level, or even binary-level compatibility. The only observable difference should be a performance improvement in some circumstances from reduced shimmering. The idea came about while working on processing HTTP headers in Wibble. Headers can repeat, so I create a key/value list using [lappend] instead of [dict set]. Most of the time header repetition can be neglected, so the resulting list is conveniently accessed using [dict get], which returns the last (usually only) matching entry. However, this incurs a significant shimmering penalty for every lookup. If [dict get] were to access a persistent index over the list, rather than insisting on storing the values themselves in the index, this shimmering would not take place. (The Wibble version I describe hasn't been posted to the Wiki yet.) I have decided against using the Tcl hash table implementation for this project, primary because there is no good way to pass "client data" to the custom hash procs. Such client data is necessary to tie the hash table back to the intrep. I considered and rejected global variables, thread-local storage, and putting magic keys in the table. I suppose I could have a global hash table mapping from hash tables back to intreps, but that is too incestuous for my liking. Freed from using a generic hash table, I have integrated an optimized hash table directly into the data structure. I have mostly been using the BLT hash table implementation as reference. In my "sandbox copy" of Tcl I have added a *dict field to the definition of List in tclInt.h. (As far as I know, changing data structure definitions tclInt.h doesn't automatically break binary compatibility with extensions.) typedef struct List { int refCount; int maxElemCount; /* Total number of element array slots. */ int elemCount; /* Current number of list elements. */ int canonicalFlag; /* Set if the string representation was * derived from the list representation. May * be ignored if there is no string rep at * all.*/ Tcl_Obj *elements; /* First list element; the struct is grown to * accomodate all elements. */ Dict *dict; /* Dict index over the list, or NULL if this * list doesn't have a dict representation. */ } List; I have modified the list functions to recognize when to invalidate the dict index. That's the only responsibility added to the list functions. I define Dict thusly: #define ENTRIES_PER_BUCKET 3 #define STATIC_BUCKETS 4 #define STATIC_ENTRIES (STATIC_BUCKETS * ENTRIES_PER_BUCKET) struct Dict { int *buckets; /* Pointer to bucket array. Each element is the * bucket head entry's index into the entries * array, or -1 if the bucket is empty. */ DictEntry *entries; /* Pointer to entry array. */ int *allocation; /* Partitioned list tracking the allocation of * entries, containing indexes into entries. The * first numEntries values are the indexes of * allocated entries, in the order they were * created. The remaining values are the indexes * of unused entries, in arbitrary order. */ int maxBuckets; /* Size of the buckets array. */ int numEntries; /* Number of entries present in table. Equal to * elemCount/2 plus the number of duplicate keys * in the elements array. */ int maxEntries; /* Size of the entries and allocation arrays. The * table grows when numEntries exceeds this. */ unsigned long mask; /* Mask value used in hashing function. */ unsigned int downShift; /* Shift count used in hashing function. Designed * to use high-order bits of randomized keys. */ int staticBuckets[STATIC_BUCKETS]; /* Bucket array used for small dicts to avoid * malloc. When the dict is small, buckets points * to this array. */ DictEntry staticEntries[STATIC_ENTRIES]; /* Entry array used for small dicts to avoid * malloc. When the dict is small, entries points * to this array. */ int staticAllocation[STATIC_ENTRIES]; /* Allocation array used for small dicts to avoid * malloc. When the dict is small, allocation * points to this array. */ Tcl_Obj *chain; /* Linked list used for invalidating the string * reps of updated nested dictionaries. */ }; And DictEntry is: typedef struct DictEntry { unsigned long hash; /* This entry's hash value, for quick comparison * when finding the right entry in the bucket. */ int next; /* Index into the entries array for the next entry * in this hash bucket, or -1 for end of chain. */ int key; /* The entry's index into elements, divided by * two. Multiply by two to get the key index, then * add one to get the value index. If there are no * duplicates, key equals the entry's index in the * allocation array. */ } DictEntry; A "pure" dict has no duplicate keys, so numEntries*2==elemCount. The dict commands produce only pure dicts. The only way to make an impure dict is to build it using list commands then create a dict index by using a read-only dict command. Impure dicts can be read as-is, but modifying or copying it using [dict] commands necessitate rebuilding the list to have no duplicates. This can be done with a simple in-place algorithm, because i<=entries[allocation[i]].key for 0<=i<numEntries. In the following code fragment, elements and elemCount are fields in the List structure, and entries, allocation, and numEntries are fields in the dict structure. if (numEntries * 2 != elemCount) { int i, j; for (i = 0; i < numEntries; ++i) { j = entries[allocation[i]].key; if (i != j) { assert(j > i); memcpy(elements + i * 2, elements + j * 2, sizeof(*elements) * 2); entries[allocation[i]].key = i; } } elemCount = numEntries * 2; } Here's a script example that shows how dict behaves in the face of duplicates. This is current Tcl behavior, which I take pains to preserve. % set data {a 0 b 1 a 2 a 3 c 4} a 0 b 1 a 2 a 3 c 4 % dict get $data a 3 % dict get $data a 3 b 1 c 4 % set data a 0 b 1 a 2 a 3 c 4 % dict set data a -3 a -3 b 1 c 4 % set data a -3 b 1 c 4 [dict get] returns a new pure dict formed from the input list, which the above algorithm permutes as follows: (the / in the allocation list shows the partitioning, determined by numEntries) elements = {a 0 b 1 a 2 a 3 c 4} elemCount = 10 numEntries = 3 allocation = {0 1 2 / 3 4 5 6 7 8 9 10 11} entries.key = {3 1 4 ? ? ? ? ? ? ? ? ?} 1. Initial : a 0 b 1 a 2 a 3 c 4 2. Copy "a" : a 3 b 1 a 2 a 3 c 4 3. Leave "b" alone: a 3 b 1 a 2 a 3 c 4 4. Copy "c" : a 3 b 1 c 4 a 3 c 4 5. Truncate : a 3 b 1 c 4 elements = {a 3 b 1 c 4} elemCount = 6 numEntries = 3 allocation = {0 1 2 / 3 4 5 6 7 8 9 10 11} entries.key = {0 1 2 ? ? ? ? ? ? ? ? ?} Now let's delete an element. % dict unset data b a 3 c 4 This would correspond to: elements = {a 3 c 4} elemCount = 4 numEntries = 2 allocation = {0 2 / 1 3 4 5 6 7 8 9 10 11} entries.key = {0 ? 1 ? ? ? ? ? ? ? ? ?} "b" is looked up in the hash table. The hash function selects a bucket, which is the head of a singly-linked list through entries. One of the linked entries has a matching hash, and a full key comparison is done to confirm the match. The full text of the key comes from the Tcl_Obj pointed to by the entry->key*2'th slot in the elements array. The key'th slot of the allocation array gets obliterated by shifting down all higher-indexed slots, up to numEntries-1 (in this case, allocation[1] = allocation[2]), and similar happens to elements, except that the indexes are doubled (overwrite "b" and "1" with "c" and "4"). The entry is freed by putting its index into numEntries-1 slot (allocation[2] = 1). (It's more like a rotate than a shift.) The keys for the shifted entries get decremented (--entries[2].key), and numEntries and elemCount are decremented as well. Of course, reference counts are decremented for the objects removed from the list. I could discuss a few more algorithms, but I don't want to bore you all to death. I just picked these two to demonstrate the operation of these data structures. Now, here's my big coding quandary. Implementing the foregoing requires that the dict code be able to access some list internals and vice versa. I don't want to merge tclListObj.c and tclDictObj.c (even though list and dict would no longer be distinct types), but I also don't want to de-static list and dict internals and move them into tclInt.h. How should I handle this? Thank you for your comments. This has been an exciting project for me, and I'd like to make it a reality someday. I have further enhancements planned for dict which are made possible by unifying list and dict, which I'll be happy to write emails and even TIPs about if you're interested. -- Andy Goth | http://andy.junkdrome.org./ unununium@{aircanopy.net,openverse.com} |
From: Donal K. F. <don...@ma...> - 2010-01-21 22:06:04
|
On 21/01/2010 15:15, John Kopaz wrote: > Is anyone working real vxworks (5.4 or newer) support for 8.6? > > I saw the patch at http://wiki.tcl.tk/21062 for 8.5.2 as a hack.... > I also saw one for 8.0 and a 7.x version that looked clean. > > I was hoping someone else was also interested in leveraging the new 8.6 > oo:: on vxworks. Are you aware that the TclOO stand-alone package (you can get the sources from SF, or contact me directly for the latest version since the last release is a little old) works just fine with 8.5? If that's the only version of Tcl you've got then you're still OK. (Well, if you've got [load] working that is; I've no idea about how to compile it into Tcl these days, though it should work as a static package...) Generally speaking though, I've no objection to working in VxWorks provided it doesn't badly hurt the other users of Tcl. Configuration changes are fine, huge numbers of extra #ifdefs aren't. :-) FWIW, Tcl 8.6 is much less stack heavy than previous versions of Tcl, so restrained resource environments are much better off than before. Donal (offline so can't read that wiki page...) |
From: John K. <ker...@ea...> - 2010-01-21 15:16:07
|
Is anyone working real vxworks (5.4 or newer) support for 8.6? I saw the patch at http://wiki.tcl.tk/21062 for 8.5.2 as a hack.... I also saw one for 8.0 and a 7.x version that looked clean. I was hoping someone else was also interested in leveraging the new 8.6 oo:: on vxworks. -- --- John Kopaz |
From: Joe E. <jen...@fl...> - 2010-01-14 04:00:35
|
TIP#359 "Extended Window Manager Hint Support" has been accepted 5/0/1. For: JE,JH,JN,DKF,DAS Against: none Present: KBK Addendum (a) "Backport to 8.5" has also been accepted 5/0/0 (same votes as above), and Addendum (b) "Backport to 8.4" has passed 4/0/1 (JN PRESENT). --Joe English jen...@fl... |
From: Donal K. F. <don...@ma...> - 2010-01-08 11:07:55
|
On 08/01/2010 03:43, Joe English wrote: > [ Donal -- could you update the TIP status onhttp://www.tcl.tk/ ? > I do not seem to be able to do so, or maybe just don't know how. ] Done. (It requires an edit operation to the TIP headers that has never been exposed over the web interface; I just directly commit it to the repository. DGP and myself have the access rights.) Donal. |
From: Joe E. <jen...@fl...> - 2010-01-08 03:43:12
|
TIP#360 "Modernize X11 Menus" has passed 6/0/0 For: JE, KBK, DKF, JH, JN, DAS Against: none Present: none [ Donal -- could you update the TIP status on http://www.tcl.tk/ ? I do not seem to be able to do so, or maybe just don't know how. ] --Joe English jen...@fl... |
From: Donal K. F. <don...@ma...> - 2010-01-07 21:20:32
|
On 07/01/2010 17:29, Daniel A. Steffen wrote: > unrelated to the vote/for future consideration, I wonder if for 8.6 > on Aqua it would make sense to fold into [wm attributes] the > functionality of the existing (ridiculously named) > [::tk::unsupported::MacWindowStyle style] command? (old name would > stay in place for backwards compat) > > In addition to the toplevel path, [MacWindowStyle style]] takes one > or two arguments, the first being the platform-specific window class > and the second a list of window attributes (not all attributes are > effective for all classes) When only the class argument is present, > attributes are set to the default for the specified class (c.f. > WmWinStyle() in tkMacOSXWm.c.) > > a new -class option to [wm attributes] and reuse of #359 -type would > seem to be a reasonable and much more accessible replacement? Generally, I feel there more like "you mean you've not already done it?" This is definitely the sort of thing that should be in the attributes. More controversially, some of the other [wm] things should be attributes on X11 and not present everywhere else. In particular, odd things that hardly anyone uses should be shuffled out of the way (like setting the colormap windows, focus model, and who provided the position and size; I know of no correct app that usefully sets *any* of these manually). I'm prepared to wait for Tk 9.0 to do this cleanup. Donal. |
From: Daniel A. S. <dst...@ap...> - 2010-01-07 17:29:52
|
On Jan 6, 2010, at 9:38 AM, Joe English wrote: > TIP#359 "Extended Window Manager Hint Support" TIP#359: YES. this really feels more like a bugfix than a new feature to me, so no objections to a backport: TIP#359 Addendum (a): YES. TIP#359 Addendum (b): YES. also: TIP#360: YES. unrelated to the vote/for future consideration, I wonder if for 8.6 on Aqua it would make sense to fold into [wm attributes] the functionality of the existing (ridiculously named) [::tk::unsupported::MacWindowStyle style] command? (old name would stay in place for backwards compat) In addition to the toplevel path, [MacWindowStyle style]] takes one or two arguments, the first being the platform-specific window class and the second a list of window attributes (not all attributes are effective for all classes) When only the class argument is present, attributes are set to the default for the specified class (c.f. WmWinStyle() in tkMacOSXWm.c.) a new -class option to [wm attributes] and reuse of #359 -type would seem to be a reasonable and much more accessible replacement? Cheers, Daniel |
From: Kevin K. <kev...@gm...> - 2010-01-07 13:02:07
|
Joe English wrote: > > I know it's late in the beta cycle to be adding new features, > but this is an important TIP. X11 window managers are getting > wackier (See: compiz), and lack of support for EWMH window > type hints seriously degrades the usability of Tk apps under > newer desktop environments. Discussion has died down and > everyone concerned is happy with the current TIP. > > So please vote YES on > > TIP#359 "Extended Window Manager Hint Support" TIP#359: PRESENT By which no criticism is intended; I just don't have time to get up to speed on what EWMH type hints are and why they're important. (This is not the X11 of old, that's for sure.) -- 73 de ke9tv/2, Kevin |
From: Joe E. <jen...@fl...> - 2010-01-06 22:11:50
|
Donal K. Fellows wrote: > > TIP#359: YES > TIP#359(a): YES (backport to Tk 8.5) > TIP#359(b): YES (backport to Tk 8.4) > > On the other hand I'm uncertain how much effort we want to put into > maintaining 8.4 anyway. 'Tis your work though and I'm certainly not > going to oppose... [ For the record, FWIW, this was Pat's work, not mine ] This will likely involve simply copying the HEAD version of unix/tkUnixWm.c wholesale onto the 8.5 and 8.4 branches. That's happened a couple times before (as a consequence, [wm] in Tk 8.4.19 has a few features that it's Not Officially Supposed To Have); but sorting new features vs. bugfixes, cleanups, and adaptations to newer WMs simply isn't worth the effort. --Joe English jen...@fl... |
From: Donal K. F. <don...@ma...> - 2010-01-06 20:57:33
|
On 06/01/2010 17:38, Joe English wrote: > TIP#359 "Extended Window Manager Hint Support" TIP#359: YES TIP#359(a): YES (backport to Tk 8.5) TIP#359(b): YES (backport to Tk 8.4) On the other hand I'm uncertain how much effort we want to put into maintaining 8.4 anyway. 'Tis your work though and I'm certainly not going to oppose... Donal. |
From: Jan N. <nij...@us...> - 2010-01-06 20:01:27
|
On 06/01/2010 9:38 AM, Joe English wrote: > TIP#359 Addendum (a): > > The features of TIP#359 shall be backported to the 8.5 branch > and included in the next maintenance release. > > TIP#359 Addendum (b): > > The features of TIP#359 shall be backported to the 8.4 branch > and included in the next maintenance release, should there be one. TIP#359: Yes TIP#359 (a): Yes TIP#359 (b): Present About 359b: Actualy, I don't mind. Not backporting it to 8.4 might give a good argument why upgrading to at least 8.5 is a good idea anyway..... Regards, Jan Nijtmans |
From: Jeff H. <je...@ac...> - 2010-01-06 17:54:13
|
On 06/01/2010 9:38 AM, Joe English wrote: > TIP#359 Addendum (a): > > The features of TIP#359 shall be backported to the 8.5 branch > and included in the next maintenance release. > > TIP#359 Addendum (b): > > The features of TIP#359 shall be backported to the 8.4 branch > and included in the next maintenance release, should there be one. TIP#359: Yes TIP#359 (a): Yes TIP#359 (b): Yes Jeff |
From: Joe E. <jen...@fl...> - 2010-01-06 17:50:36
|
I know it's late in the beta cycle to be adding new features, but this is an important TIP. X11 window managers are getting wackier (See: compiz), and lack of support for EWMH window type hints seriously degrades the usability of Tk apps under newer desktop environments. Discussion has died down and everyone concerned is happy with the current TIP. So please vote YES on TIP#359 "Extended Window Manager Hint Support" by [clock format 1263412800], which is sometime next week. Furthermore: although the established policy is to not add new features on the stable and legacy branches, as mentioned above this is an important TIP, so I would also propose: TIP#359 Addendum (a): The features of TIP#359 shall be backported to the 8.5 branch and included in the next maintenance release. TIP#359 Addendum (b): The features of TIP#359 shall be backported to the 8.4 branch and included in the next maintenance release, should there be one. My votes: TIP#359: YES. TIP#359 Addendum (a): YES. TIP#359 Addendum (b): YES. --Joe English jen...@fl... |
From: Rüdiger H. <r_h...@gm...> - 2010-01-05 19:09:03
|
Hello all, I saw that bug 2727476 (Fix default size of font chooser dialog and assigned minimum sizes for the lists.) was fixed. The patch 2442314 addresses the internationalization and width of the listbox of the fontchooser. Maybe it could be applied, too? Rüdiger |