Menu
▾
▴
[frontierkernel-commits] Frontier/Common/source langhash.c,1.4.2.13,1.4.2.14 tableops.c,1.3.2.3,1.3.2.4 tablepopup.c,1.3,1.3.2.1 tablescrap.c,1.3.2.1,1.3.2.2 tableverbs.c,1.3,1.3.2.1
|
From: Andre R. <and...@us...> - 2004-11-20 23:04:04
|
Update of /cvsroot/frontierkernel/Frontier/Common/source In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv16602/Common/source Modified Files: Tag: New_Tables_Experiment-branch langhash.c tableops.c tablepopup.c tablescrap.c tableverbs.c Log Message: All callers of hashresort are now expected to supply the position of the node in the current sort order if they only want us to resort that node. This eliminates a costly linear search through the array containing the sort order. The callers have been updated to determine this index before making the change that causes the node to become unsorted. Index: tablescrap.c =================================================================== RCS file: /cvsroot/frontierkernel/Frontier/Common/source/tablescrap.c,v retrieving revision 1.3.2.1 retrieving revision 1.3.2.2 diff -C2 -d -r1.3.2.1 -r1.3.2.2 *** tablescrap.c 15 Nov 2004 20:52:24 -0000 1.3.2.1 --- tablescrap.c 20 Nov 2004 23:03:20 -0000 1.3.2.2 *************** *** 522,528 **** tableexiteditmode (); ! #ifdef fltablesortorderisarray ! /*** FIXME: what are we supposed to do here??? ***/ ! #else tableoverridesort ((**hnode).sortedlink); /*retain original sort position*/ #endif --- 522,535 ---- tableexiteditmode (); ! #ifndef fltablesortorderisarray ! /* ! 2004-11-20 aradke: could this potentially destroy the sort order of the table? ! if so, we can no longer allow it with the new table implementation because ! it relies on the table being sorted when locating nodes via a binary search. ! ! as far as i can tell, disabling this override of the sort order doesn't ! have any observable effect anyway. ! */ ! tableoverridesort ((**hnode).sortedlink); /*retain original sort position*/ #endif *************** *** 530,536 **** hashinsertnode (hnode, htable); ! #ifdef fltablesortorderisarray ! /*** FIXME: what are we supposed to do here??? ***/ ! #else tablerestoresort (); #endif --- 537,541 ---- hashinsertnode (hnode, htable); ! #ifndef fltablesortorderisarray tablerestoresort (); #endif Index: tablepopup.c =================================================================== RCS file: /cvsroot/frontierkernel/Frontier/Common/source/tablepopup.c,v retrieving revision 1.3 retrieving revision 1.3.2.1 diff -C2 -d -r1.3 -r1.3.2.1 *** tablepopup.c 31 Oct 2004 20:41:10 -0000 1.3 --- tablepopup.c 20 Nov 2004 23:03:19 -0000 1.3.2.1 *************** *** 573,576 **** --- 573,578 ---- 6.2b16 AR: Take headnode param instead of bsnew bigstring. + + 2004-11-20 aradke: update for new table implementation */ *************** *** 579,583 **** boolean flvalidate = true; long newlength; ! assert (headnode != nil); --- 581,588 ---- boolean flvalidate = true; long newlength; ! #ifdef fltablesortorderisarray ! long ix; ! #endif ! assert (headnode != nil); *************** *** 625,628 **** --- 630,641 ---- } + #ifdef fltablesortorderisarray + + /*get the index of the node before changing the hash key*/ + + hashgetsortedindex (ht, hnode, &ix); + + #endif + if (!hashsetnodekey (ht, hnode, bsnew)) return (false); *************** *** 631,639 **** if (!(**ht).flxml) #endif ! if (flediting) hashresort (ht, hnode); else tableresort (ht, hnode); return (true); --- 644,658 ---- if (!(**ht).flxml) #endif ! #ifdef fltablesortorderisarray ! if (flediting) ! hashresort (ht, hnode, ix); ! else ! tableresort (ht, hnode, ix); ! #else if (flediting) hashresort (ht, hnode); else tableresort (ht, hnode); + #endif return (true); Index: langhash.c =================================================================== RCS file: /cvsroot/frontierkernel/Frontier/Common/source/langhash.c,v retrieving revision 1.4.2.13 retrieving revision 1.4.2.14 diff -C2 -d -r1.4.2.13 -r1.4.2.14 *** langhash.c 20 Nov 2004 19:18:35 -0000 1.4.2.13 --- langhash.c 20 Nov 2004 23:03:19 -0000 1.4.2.14 *************** *** 2617,2621 **** ! boolean hashresort (hdlhashtable htable, hdlhashnode hresort) { /* --- 2617,2626 ---- ! #ifdef fltablesortorderisarray ! boolean hashresort (hdlhashtable htable, hdlhashnode hresort, long ix) ! #else ! boolean hashresort (hdlhashtable htable, hdlhashnode hresort) ! #endif ! { /* *************** *** 2626,2663 **** node needs to be resorted. using the quicksort routine, it's especially important not to resort a mostly-sorted list just to move one node. */ register hdlhashtable ht = htable; - #ifdef fltablesortorderisarray - unsigned long ix; - #endif if (hresort == nil) return (hashquicksort (ht)); ! pushhashtable (ht); ! #ifdef fltablesortorderisarray ! ! /* ! FIXME: we really should do the search before modifying the value because ! then the list is still sorted and we can do a fast binary search instead. ! */ ! ! if (!listlinearsearch ((**ht).sortedlist, (Handle) hresort, &ix)) { ! pophashtable (); ! return (false); ! } ! ! listresort ((**ht).sortedlist, ix, &hashcompare); ! #else ! hashsorteddelete (hresort); ! ! hashsortedinsert (hresort); ! #endif ! pophashtable (); --- 2631,2658 ---- node needs to be resorted. using the quicksort routine, it's especially important not to resort a mostly-sorted list just to move one node. + + 2004-11-20 aradke: if a single node is affected, we rely on the caller + to determine the index of the node before changing its hash key or value. */ register hdlhashtable ht = htable; if (hresort == nil) return (hashquicksort (ht)); ! pushhashtable (ht); ! #ifdef fltablesortorderisarray ! listresort ((**ht).sortedlist, ix, &hashcompare); ! ! #else ! hashsorteddelete (hresort); ! ! hashsortedinsert (hresort); ! #endif ! pophashtable (); *************** *** 4002,4006 **** --- 3997,4005 ---- if (!flsorted) + #ifdef fltablesortorderisarray + hashresort (htable, nil, -1); + #else hashresort (htable, nil); + #endif if (!fl) *************** *** 4158,4166 **** the index is 0-based. */ #ifdef fltablesortorderisarray ! return (listlinearsearch ((**htable).sortedlist, (Handle) hnode, (unsigned long *) &index)); #else --- 4157,4180 ---- the index is 0-based. + + 2004-11-20 aradke: the table should always be sorted and we know that the node + is in the list, so we can use the binary search successfully. however, just + to be sure we try a linearsearch if the binary search fails. */ #ifdef fltablesortorderisarray ! boolean flfound; ! ! pushhashtable (htable); /*for hashcompare*/ ! ! flfound = listbinarysearchexact ((**htable).sortedlist, (Handle) hnode, index, &hashcompare); ! ! pophashtable (); ! ! if (flfound) ! return (true); ! ! return (listlinearsearch ((**htable).sortedlist, (Handle) hnode, index)); #else Index: tableops.c =================================================================== RCS file: /cvsroot/frontierkernel/Frontier/Common/source/tableops.c,v retrieving revision 1.3.2.3 retrieving revision 1.3.2.4 diff -C2 -d -r1.3.2.3 -r1.3.2.4 *** tableops.c 15 Nov 2004 22:43:07 -0000 1.3.2.3 --- tableops.c 20 Nov 2004 23:03:19 -0000 1.3.2.4 *************** *** 955,959 **** */ ! boolean tableresort (hdlhashtable ht, hdlhashnode hresort) { /* --- 955,964 ---- */ ! #ifdef fltablesortorderisarray ! boolean tableresort (hdlhashtable ht, hdlhashnode hresort, long ix) ! #else ! boolean tableresort (hdlhashtable ht, hdlhashnode hresort) ! #endif ! { /* *************** *** 962,965 **** --- 967,972 ---- 3/31/93 dmb: added hresort parameter. if it's not nil, then only that node needs to be resorted. + + 2004-11-20 aradke: update for new table implementation */ *************** *** 973,978 **** opsaveeditbuffer (); ! fl = hashresort (ht, hresort); ! opmoveto (hcursor); --- 980,989 ---- opsaveeditbuffer (); ! #ifdef fltablesortorderisarray ! fl = hashresort (ht, hresort, ix); ! #else ! fl = hashresort (ht, hresort); ! #endif ! opmoveto (hcursor); *************** *** 993,996 **** --- 1004,1009 ---- /* 3/23/93 dmb: set watch cursor before sorting + + 2004-11-20 aradke: update for new table implementation */ *************** *** 1007,1011 **** shellforcecursoradjust (); /*make sure it reverts ASAP*/ ! tableresort (ht, nil); opvisibarcursor (); --- 1020,1028 ---- shellforcecursoradjust (); /*make sure it reverts ASAP*/ ! #ifdef fltablesortorderisarray ! tableresort (ht, nil, -1); ! #else ! tableresort (ht, nil); ! #endif opvisibarcursor (); Index: tableverbs.c =================================================================== RCS file: /cvsroot/frontierkernel/Frontier/Common/source/tableverbs.c,v retrieving revision 1.3 retrieving revision 1.3.2.1 diff -C2 -d -r1.3 -r1.3.2.1 *** tableverbs.c 31 Oct 2004 20:41:10 -0000 1.3 --- tableverbs.c 20 Nov 2004 23:03:20 -0000 1.3.2.1 *************** *** 299,302 **** --- 299,304 ---- 5.1.4 dmb: disallow rename if new name is already in use; generate errors if item doesn't exist + + 2004-11-20 aradke: update for new table implementation */ *************** *** 304,307 **** --- 306,312 ---- bigstring bs, bsname; hdlhashnode hnode; + #ifdef fltablesortorderisarray + long ix; + #endif if (!getvarparam (hparam1, 1, &htable, bs)) *************** *** 319,322 **** --- 324,335 ---- return (false); } + + #ifdef fltablesortorderisarray + + /*get the index of the node before changing the hash key*/ + + hashgetsortedindex (htable, hnode, &ix); + + #endif if (!equalidentifiers (bs, bsname)) { *************** *** 333,337 **** } ! hashresort (htable, hnode); return (setaddressvalue (htable, bsname, v)); --- 346,354 ---- } ! #ifdef fltablesortorderisarray ! hashresort (htable, hnode, ix); ! #else ! hashresort (htable, hnode); ! #endif return (setaddressvalue (htable, bsname, v)); |
