summaryrefslogtreecommitdiff
path: root/avl-1.4.0/avlt.c
diff options
context:
space:
mode:
authorcvs2git <rtems-devel@rtems.org>2007-08-07 16:14:18 +0000
committercvs2git <rtems-devel@rtems.org>2007-08-07 16:14:18 +0000
commit2c55da25b90fc7c7a59464a90d2c322bbc5047b5 (patch)
tree63d296b347fe8c6ab28ba28e6489f792404625ee /avl-1.4.0/avlt.c
parent66d25567fe424bb55fde088f3d45e9ed044400c1 (diff)
This commit was manufactured by cvs2svn to create tag 'rtems-addon-rtems-addon-packages-4-7-99-2
packages-4-7-99-2'. Sprout from ncurses-gnu 2002-12-19 15:34:54 UTC Eric Norum <WENorum@lbl.gov> 'Latest ncurses add-on' Cherrypick from addons 2002-06-28 21:58:41 UTC Eric Norum <WENorum@lbl.gov> 'Useful add-on libraries': README RTEMS_Makefiles/Makefile.avl RTEMS_Makefiles/Makefile.common RTEMS_Makefiles/Makefile.site avl-1.4.0/AUTHORS avl-1.4.0/COPYING avl-1.4.0/ChangeLog avl-1.4.0/INSTALL avl-1.4.0/Makefile.am avl-1.4.0/Makefile.in avl-1.4.0/NEWS avl-1.4.0/README avl-1.4.0/THANKS avl-1.4.0/TODO avl-1.4.0/aclocal.m4 avl-1.4.0/avl.c avl-1.4.0/avl.h avl-1.4.0/avl.html avl-1.4.0/avl.info avl-1.4.0/avl.texinfo avl-1.4.0/avl.text avl-1.4.0/avlt.c avl-1.4.0/avlt.h avl-1.4.0/avltr.c avl-1.4.0/avltr.h avl-1.4.0/configure avl-1.4.0/configure.in avl-1.4.0/install-sh avl-1.4.0/missing avl-1.4.0/mkinstalldirs avl-1.4.0/rb.c avl-1.4.0/rb.h avl-1.4.0/texinfo.tex avl-1.4.0/thread-test.c examples/avl/BuildTests.sh examples/avl/Makefile examples/avl/README examples/avl/init.c examples/ncurses/BuildTests.sh examples/ncurses/Makefile examples/ncurses/README examples/ncurses/init.c examples/readline/.gdbinit examples/readline/Makefile examples/readline/init.c examples/readline/rlgeneric.c ncurses-5.2/ANNOUNCE ncurses-5.2/Ada95/Makefile.in ncurses-5.2/Ada95/README ncurses-5.2/Ada95/TODO ncurses-5.2/Ada95/gen/Makefile.in ncurses-5.2/Ada95/gen/gen.c ncurses-5.2/Ada95/gen/html.m4 ncurses-5.2/Ada95/gen/normal.m4 ncurses-5.2/Ada95/gen/table.m4 ncurses-5.2/Ada95/gen/terminal_interface-curses-aux.ads.m4 ncurses-5.2/Ada95/gen/terminal_interface-curses-forms-field_types.ads.m4 ncurses-5.2/Ada95/gen/terminal_interface-curses-forms-field_user_data.ads.m4 ncurses-5.2/Ada95/gen/terminal_interface-curses-forms-form_user_data.ads.m4 ncurses-5.2/Ada95/gen/terminal_interface-curses-forms.ads.m4 ncurses-5.2/Ada95/gen/terminal_interface-curses-menus-item_user_data.ads.m4 ncurses-5.2/Ada95/gen/terminal_interface-curses-menus-menu_user_data.ads.m4 ncurses-5.2/Ada95/gen/terminal_interface-curses-menus.ads.m4 ncurses-5.2/Ada95/gen/terminal_interface-curses-mouse.ads.m4 ncurses-5.2/Ada95/gen/terminal_interface-curses-panels-user_data.ads.m4 ncurses-5.2/Ada95/gen/terminal_interface-curses-panels.ads.m4 ncurses-5.2/Ada95/gen/terminal_interface-curses.ads.m4 ncurses-5.2/Ada95/samples/Makefile.in ncurses-5.2/Ada95/samples/README ncurses-5.2/Ada95/samples/explain.txt ncurses-5.2/Ada95/samples/rain.adb ncurses-5.2/Ada95/samples/rain.ads ncurses-5.2/Ada95/samples/sample-curses_demo-attributes.adb ncurses-5.2/Ada95/samples/sample-curses_demo-attributes.ads ncurses-5.2/Ada95/samples/sample-curses_demo-mouse.adb ncurses-5.2/Ada95/samples/sample-curses_demo-mouse.ads ncurses-5.2/Ada95/samples/sample-curses_demo.adb ncurses-5.2/Ada95/samples/sample-curses_demo.ads ncurses-5.2/Ada95/samples/sample-explanation.adb ncurses-5.2/Ada95/samples/sample-explanation.ads ncurses-5.2/Ada95/samples/sample-form_demo-aux.adb ncurses-5.2/Ada95/samples/sample-form_demo-aux.ads ncurses-5.2/Ada95/samples/sample-form_demo-handler.adb ncurses-5.2/Ada95/samples/sample-form_demo-handler.ads ncurses-5.2/Ada95/samples/sample-form_demo.adb ncurses-5.2/Ada95/samples/sample-form_demo.ads ncurses-5.2/Ada95/samples/sample-function_key_setting.adb ncurses-5.2/Ada95/samples/sample-function_key_setting.ads ncurses-5.2/Ada95/samples/sample-header_handler.adb ncurses-5.2/Ada95/samples/sample-header_handler.ads ncurses-5.2/Ada95/samples/sample-helpers.adb ncurses-5.2/Ada95/samples/sample-helpers.ads ncurses-5.2/Ada95/samples/sample-keyboard_handler.adb ncurses-5.2/Ada95/samples/sample-keyboard_handler.ads ncurses-5.2/Ada95/samples/sample-manifest.ads ncurses-5.2/Ada95/samples/sample-menu_demo-aux.adb ncurses-5.2/Ada95/samples/sample-menu_demo-aux.ads ncurses-5.2/Ada95/samples/sample-menu_demo-handler.adb ncurses-5.2/Ada95/samples/sample-menu_demo-handler.ads ncurses-5.2/Ada95/samples/sample-menu_demo.adb ncurses-5.2/Ada95/samples/sample-menu_demo.ads ncurses-5.2/Ada95/samples/sample-my_field_type.adb ncurses-5.2/Ada95/samples/sample-my_field_type.ads ncurses-5.2/Ada95/samples/sample-text_io_demo.adb ncurses-5.2/Ada95/samples/sample-text_io_demo.ads ncurses-5.2/Ada95/samples/sample.adb ncurses-5.2/Ada95/samples/sample.ads ncurses-5.2/Ada95/samples/status.adb ncurses-5.2/Ada95/samples/status.ads ncurses-5.2/Ada95/samples/tour.adb ncurses-5.2/Ada95/samples/tour.ads ncurses-5.2/Ada95/src/Makefile.in ncurses-5.2/Ada95/src/terminal_interface-curses-aux.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-alpha.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-alpha.ads ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-alphanumeric.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-alphanumeric.ads ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-enumeration-ada.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-enumeration-ada.ads ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-enumeration.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-enumeration.ads ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-intfield.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-intfield.ads ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-ipv4_address.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-ipv4_address.ads ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-numeric.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-numeric.ads ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-regexp.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-regexp.ads ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-user-choice.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-user-choice.ads ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-user.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types-user.ads ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_types.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms-field_user_data.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms-form_user_data.adb ncurses-5.2/Ada95/src/terminal_interface-curses-forms.adb ncurses-5.2/Ada95/src/terminal_interface-curses-menus-item_user_data.adb ncurses-5.2/Ada95/src/terminal_interface-curses-menus-menu_user_data.adb ncurses-5.2/Ada95/src/terminal_interface-curses-menus.adb ncurses-5.2/Ada95/src/terminal_interface-curses-mouse.adb ncurses-5.2/Ada95/src/terminal_interface-curses-panels-user_data.adb ncurses-5.2/Ada95/src/terminal_interface-curses-panels.adb ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-aux.adb ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-aux.ads ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-complex_io.adb ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-complex_io.ads ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-decimal_io.adb ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-decimal_io.ads ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-enumeration_io.adb ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-enumeration_io.ads ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-fixed_io.adb ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-fixed_io.ads ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-float_io.adb ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-float_io.ads ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-integer_io.adb ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-integer_io.ads ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-modular_io.adb ncurses-5.2/Ada95/src/terminal_interface-curses-text_io-modular_io.ads ncurses-5.2/Ada95/src/terminal_interface-curses-text_io.adb ncurses-5.2/Ada95/src/terminal_interface-curses-text_io.ads ncurses-5.2/Ada95/src/terminal_interface-curses.adb ncurses-5.2/Ada95/src/terminal_interface.ads ncurses-5.2/INSTALL ncurses-5.2/MANIFEST ncurses-5.2/Makefile.glibc ncurses-5.2/Makefile.in ncurses-5.2/Makefile.os2 ncurses-5.2/NEWS ncurses-5.2/README ncurses-5.2/README.emx ncurses-5.2/README.glibc ncurses-5.2/TO-DO ncurses-5.2/aclocal.m4 ncurses-5.2/announce.html.in ncurses-5.2/c++/Makefile.in ncurses-5.2/c++/NEWS ncurses-5.2/c++/PROBLEMS ncurses-5.2/c++/README-first ncurses-5.2/c++/cursesapp.cc ncurses-5.2/c++/cursesapp.h ncurses-5.2/c++/cursesf.cc ncurses-5.2/c++/cursesf.h ncurses-5.2/c++/cursesm.cc ncurses-5.2/c++/cursesm.h ncurses-5.2/c++/cursesmain.cc ncurses-5.2/c++/cursesp.cc ncurses-5.2/c++/cursesp.h ncurses-5.2/c++/cursespad.cc ncurses-5.2/c++/cursesw.cc ncurses-5.2/c++/cursesw.h ncurses-5.2/c++/cursslk.cc ncurses-5.2/c++/cursslk.h ncurses-5.2/c++/demo.cc ncurses-5.2/c++/edit_cfg.sh ncurses-5.2/c++/etip.h.in ncurses-5.2/c++/headers ncurses-5.2/c++/internal.h ncurses-5.2/c++/modules ncurses-5.2/config.guess ncurses-5.2/config.sub ncurses-5.2/configure ncurses-5.2/configure.in ncurses-5.2/convert_configure.pl ncurses-5.2/dist.mk ncurses-5.2/doc/hackguide.doc ncurses-5.2/doc/html/Ada95.html ncurses-5.2/doc/html/ada/files.htm ncurses-5.2/doc/html/ada/files/T.htm ncurses-5.2/doc/html/ada/funcs.htm ncurses-5.2/doc/html/ada/funcs/A.htm ncurses-5.2/doc/html/ada/funcs/B.htm ncurses-5.2/doc/html/ada/funcs/C.htm ncurses-5.2/doc/html/ada/funcs/D.htm ncurses-5.2/doc/html/ada/funcs/E.htm ncurses-5.2/doc/html/ada/funcs/F.htm ncurses-5.2/doc/html/ada/funcs/G.htm ncurses-5.2/doc/html/ada/funcs/H.htm ncurses-5.2/doc/html/ada/funcs/I.htm ncurses-5.2/doc/html/ada/funcs/K.htm ncurses-5.2/doc/html/ada/funcs/L.htm ncurses-5.2/doc/html/ada/funcs/M.htm ncurses-5.2/doc/html/ada/funcs/N.htm ncurses-5.2/doc/html/ada/funcs/O.htm ncurses-5.2/doc/html/ada/funcs/P.htm ncurses-5.2/doc/html/ada/funcs/Q.htm ncurses-5.2/doc/html/ada/funcs/R.htm ncurses-5.2/doc/html/ada/funcs/S.htm ncurses-5.2/doc/html/ada/funcs/T.htm ncurses-5.2/doc/html/ada/funcs/U.htm ncurses-5.2/doc/html/ada/funcs/V.htm ncurses-5.2/doc/html/ada/funcs/W.htm ncurses-5.2/doc/html/ada/index.htm ncurses-5.2/doc/html/ada/main.htm ncurses-5.2/doc/html/ada/table.html ncurses-5.2/doc/html/ada/terminal_interface-curses-aux__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-aux__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-alpha__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-alpha__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-alphanumeric__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-alphanumeric__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-enumeration-ada__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-enumeration-ada__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-enumeration__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-enumeration__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-intfield__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-intfield__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-ipv4_address__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-ipv4_address__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-numeric__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-numeric__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-regexp__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-regexp__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-user-choice__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-user-choice__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-user__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types-user__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_types__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_user_data__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-field_user_data__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-form_user_data__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms-form_user_data__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-forms__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-menus-item_user_data__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-menus-item_user_data__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-menus-menu_user_data__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-menus-menu_user_data__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-menus__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-menus__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-mouse__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-mouse__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-panels-user_data__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-panels-user_data__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-panels__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-panels__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-aux__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-aux__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-complex_io__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-complex_io__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-decimal_io__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-decimal_io__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-enumeration_io__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-enumeration_io__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-fixed_io__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-fixed_io__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-float_io__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-float_io__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-integer_io__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-integer_io__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-modular_io__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io-modular_io__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses-text_io__ads.htm ncurses-5.2/doc/html/ada/terminal_interface-curses__adb.htm ncurses-5.2/doc/html/ada/terminal_interface-curses__ads.htm ncurses-5.2/doc/html/ada/terminal_interface__ads.htm ncurses-5.2/doc/html/announce.html ncurses-5.2/doc/html/hackguide.html ncurses-5.2/doc/html/index.html ncurses-5.2/doc/html/man/captoinfo.1m.html ncurses-5.2/doc/html/man/clear.1.html ncurses-5.2/doc/html/man/curs_addch.3x.html ncurses-5.2/doc/html/man/curs_addchstr.3x.html ncurses-5.2/doc/html/man/curs_addstr.3x.html ncurses-5.2/doc/html/man/curs_attr.3x.html ncurses-5.2/doc/html/man/curs_beep.3x.html ncurses-5.2/doc/html/man/curs_bkgd.3x.html ncurses-5.2/doc/html/man/curs_border.3x.html ncurses-5.2/doc/html/man/curs_clear.3x.html ncurses-5.2/doc/html/man/curs_color.3x.html ncurses-5.2/doc/html/man/curs_delch.3x.html ncurses-5.2/doc/html/man/curs_deleteln.3x.html ncurses-5.2/doc/html/man/curs_extend.3x.html ncurses-5.2/doc/html/man/curs_getch.3x.html ncurses-5.2/doc/html/man/curs_getstr.3x.html ncurses-5.2/doc/html/man/curs_getyx.3x.html ncurses-5.2/doc/html/man/curs_inch.3x.html ncurses-5.2/doc/html/man/curs_inchstr.3x.html ncurses-5.2/doc/html/man/curs_initscr.3x.html ncurses-5.2/doc/html/man/curs_inopts.3x.html ncurses-5.2/doc/html/man/curs_insch.3x.html ncurses-5.2/doc/html/man/curs_insstr.3x.html ncurses-5.2/doc/html/man/curs_instr.3x.html ncurses-5.2/doc/html/man/curs_kernel.3x.html ncurses-5.2/doc/html/man/curs_mouse.3x.html ncurses-5.2/doc/html/man/curs_move.3x.html ncurses-5.2/doc/html/man/curs_outopts.3x.html ncurses-5.2/doc/html/man/curs_overlay.3x.html ncurses-5.2/doc/html/man/curs_pad.3x.html ncurses-5.2/doc/html/man/curs_print.3x.html ncurses-5.2/doc/html/man/curs_printw.3x.html ncurses-5.2/doc/html/man/curs_refresh.3x.html ncurses-5.2/doc/html/man/curs_scanw.3x.html ncurses-5.2/doc/html/man/curs_scr_dump.3x.html ncurses-5.2/doc/html/man/curs_scroll.3x.html ncurses-5.2/doc/html/man/curs_slk.3x.html ncurses-5.2/doc/html/man/curs_termattrs.3x.html ncurses-5.2/doc/html/man/curs_termcap.3x.html ncurses-5.2/doc/html/man/curs_terminfo.3x.html ncurses-5.2/doc/html/man/curs_touch.3x.html ncurses-5.2/doc/html/man/curs_trace.3x.html ncurses-5.2/doc/html/man/curs_util.3x.html ncurses-5.2/doc/html/man/curs_window.3x.html ncurses-5.2/doc/html/man/default_colors.3x.html ncurses-5.2/doc/html/man/define_key.3x.html ncurses-5.2/doc/html/man/form.3x.html ncurses-5.2/doc/html/man/form_cursor.3x.html ncurses-5.2/doc/html/man/form_data.3x.html ncurses-5.2/doc/html/man/form_driver.3x.html ncurses-5.2/doc/html/man/form_field.3x.html ncurses-5.2/doc/html/man/form_field_attributes.3x.html ncurses-5.2/doc/html/man/form_field_buffer.3x.html ncurses-5.2/doc/html/man/form_field_info.3x.html ncurses-5.2/doc/html/man/form_field_just.3x.html ncurses-5.2/doc/html/man/form_field_new.3x.html ncurses-5.2/doc/html/man/form_field_opts.3x.html ncurses-5.2/doc/html/man/form_field_userptr.3x.html ncurses-5.2/doc/html/man/form_field_validation.3x.html ncurses-5.2/doc/html/man/form_fieldtype.3x.html ncurses-5.2/doc/html/man/form_hook.3x.html ncurses-5.2/doc/html/man/form_new.3x.html ncurses-5.2/doc/html/man/form_new_page.3x.html ncurses-5.2/doc/html/man/form_opts.3x.html ncurses-5.2/doc/html/man/form_page.3x.html ncurses-5.2/doc/html/man/form_post.3x.html ncurses-5.2/doc/html/man/form_requestname.3x.html ncurses-5.2/doc/html/man/form_userptr.3x.html ncurses-5.2/doc/html/man/form_win.3x.html ncurses-5.2/doc/html/man/infocmp.1m.html ncurses-5.2/doc/html/man/infotocap.1m.html ncurses-5.2/doc/html/man/keybound.3x.html ncurses-5.2/doc/html/man/keyok.3x.html ncurses-5.2/doc/html/man/menu.3x.html ncurses-5.2/doc/html/man/menu_attributes.3x.html ncurses-5.2/doc/html/man/menu_cursor.3x.html ncurses-5.2/doc/html/man/menu_driver.3x.html ncurses-5.2/doc/html/man/menu_format.3x.html ncurses-5.2/doc/html/man/menu_hook.3x.html ncurses-5.2/doc/html/man/menu_items.3x.html ncurses-5.2/doc/html/man/menu_mark.3x.html ncurses-5.2/doc/html/man/menu_new.3x.html ncurses-5.2/doc/html/man/menu_opts.3x.html ncurses-5.2/doc/html/man/menu_pattern.3x.html ncurses-5.2/doc/html/man/menu_post.3x.html ncurses-5.2/doc/html/man/menu_requestname.3x.html ncurses-5.2/doc/html/man/menu_spacing.3x.html ncurses-5.2/doc/html/man/menu_userptr.3x.html ncurses-5.2/doc/html/man/menu_win.3x.html ncurses-5.2/doc/html/man/mitem_current.3x.html ncurses-5.2/doc/html/man/mitem_name.3x.html ncurses-5.2/doc/html/man/mitem_new.3x.html ncurses-5.2/doc/html/man/mitem_opts.3x.html ncurses-5.2/doc/html/man/mitem_userptr.3x.html ncurses-5.2/doc/html/man/mitem_value.3x.html ncurses-5.2/doc/html/man/mitem_visible.3x.html ncurses-5.2/doc/html/man/ncurses.3x.html ncurses-5.2/doc/html/man/panel.3x.html ncurses-5.2/doc/html/man/resizeterm.3x.html ncurses-5.2/doc/html/man/term.5.html ncurses-5.2/doc/html/man/term.7.html ncurses-5.2/doc/html/man/terminfo.5.html ncurses-5.2/doc/html/man/tic.1m.html ncurses-5.2/doc/html/man/toe.1m.html ncurses-5.2/doc/html/man/tput.1.html ncurses-5.2/doc/html/man/tset.1.html ncurses-5.2/doc/html/man/wresize.3x.html ncurses-5.2/doc/html/ncurses-intro.html ncurses-5.2/doc/ncurses-intro.doc ncurses-5.2/form/Makefile.in ncurses-5.2/form/READ.ME ncurses-5.2/form/fld_arg.c ncurses-5.2/form/fld_attr.c ncurses-5.2/form/fld_current.c ncurses-5.2/form/fld_def.c ncurses-5.2/form/fld_dup.c ncurses-5.2/form/fld_ftchoice.c ncurses-5.2/form/fld_ftlink.c ncurses-5.2/form/fld_info.c ncurses-5.2/form/fld_just.c ncurses-5.2/form/fld_link.c ncurses-5.2/form/fld_max.c ncurses-5.2/form/fld_move.c ncurses-5.2/form/fld_newftyp.c ncurses-5.2/form/fld_opts.c ncurses-5.2/form/fld_pad.c ncurses-5.2/form/fld_page.c ncurses-5.2/form/fld_stat.c ncurses-5.2/form/fld_type.c ncurses-5.2/form/fld_user.c ncurses-5.2/form/form.h ncurses-5.2/form/form.priv.h ncurses-5.2/form/frm_cursor.c ncurses-5.2/form/frm_data.c ncurses-5.2/form/frm_def.c ncurses-5.2/form/frm_driver.c ncurses-5.2/form/frm_hook.c ncurses-5.2/form/frm_opts.c ncurses-5.2/form/frm_page.c ncurses-5.2/form/frm_post.c ncurses-5.2/form/frm_req_name.c ncurses-5.2/form/frm_scale.c ncurses-5.2/form/frm_sub.c ncurses-5.2/form/frm_user.c ncurses-5.2/form/frm_win.c ncurses-5.2/form/fty_alnum.c ncurses-5.2/form/fty_alpha.c ncurses-5.2/form/fty_enum.c ncurses-5.2/form/fty_int.c ncurses-5.2/form/fty_ipv4.c ncurses-5.2/form/fty_num.c ncurses-5.2/form/fty_regex.c ncurses-5.2/form/headers ncurses-5.2/form/llib-lform ncurses-5.2/form/modules ncurses-5.2/include/Caps ncurses-5.2/include/MKhashsize.sh ncurses-5.2/include/MKncurses_def.sh ncurses-5.2/include/MKparametrized.sh ncurses-5.2/include/MKterm.h.awk.in ncurses-5.2/include/Makefile.in ncurses-5.2/include/capdefaults.c ncurses-5.2/include/curses.h.in ncurses-5.2/include/edit_cfg.sh ncurses-5.2/include/headers ncurses-5.2/include/nc_alloc.h ncurses-5.2/include/nc_panel.h ncurses-5.2/include/ncurses_cfg.hin ncurses-5.2/include/ncurses_defs ncurses-5.2/include/term_entry.h ncurses-5.2/include/termcap.h.in ncurses-5.2/include/tic.h ncurses-5.2/include/unctrl.h.in ncurses-5.2/install-sh ncurses-5.2/man/MKterminfo.sh ncurses-5.2/man/Makefile.in ncurses-5.2/man/captoinfo.1m ncurses-5.2/man/clear.1 ncurses-5.2/man/curs_addch.3x ncurses-5.2/man/curs_addchstr.3x ncurses-5.2/man/curs_addstr.3x ncurses-5.2/man/curs_attr.3x ncurses-5.2/man/curs_beep.3x ncurses-5.2/man/curs_bkgd.3x ncurses-5.2/man/curs_border.3x ncurses-5.2/man/curs_clear.3x ncurses-5.2/man/curs_color.3x ncurses-5.2/man/curs_delch.3x ncurses-5.2/man/curs_deleteln.3x ncurses-5.2/man/curs_extend.3x ncurses-5.2/man/curs_getch.3x ncurses-5.2/man/curs_getstr.3x ncurses-5.2/man/curs_getyx.3x ncurses-5.2/man/curs_inch.3x ncurses-5.2/man/curs_inchstr.3x ncurses-5.2/man/curs_initscr.3x ncurses-5.2/man/curs_inopts.3x ncurses-5.2/man/curs_insch.3x ncurses-5.2/man/curs_insstr.3x ncurses-5.2/man/curs_instr.3x ncurses-5.2/man/curs_kernel.3x ncurses-5.2/man/curs_mouse.3x ncurses-5.2/man/curs_move.3x ncurses-5.2/man/curs_outopts.3x ncurses-5.2/man/curs_overlay.3x ncurses-5.2/man/curs_pad.3x ncurses-5.2/man/curs_print.3x ncurses-5.2/man/curs_printw.3x ncurses-5.2/man/curs_refresh.3x ncurses-5.2/man/curs_scanw.3x ncurses-5.2/man/curs_scr_dump.3x ncurses-5.2/man/curs_scroll.3x ncurses-5.2/man/curs_slk.3x ncurses-5.2/man/curs_termattrs.3x ncurses-5.2/man/curs_termcap.3x ncurses-5.2/man/curs_terminfo.3x ncurses-5.2/man/curs_touch.3x ncurses-5.2/man/curs_trace.3x ncurses-5.2/man/curs_util.3x ncurses-5.2/man/curs_window.3x ncurses-5.2/man/default_colors.3x ncurses-5.2/man/define_key.3x ncurses-5.2/man/form.3x ncurses-5.2/man/form_cursor.3x ncurses-5.2/man/form_data.3x ncurses-5.2/man/form_driver.3x ncurses-5.2/man/form_field.3x ncurses-5.2/man/form_field_attributes.3x ncurses-5.2/man/form_field_buffer.3x ncurses-5.2/man/form_field_info.3x ncurses-5.2/man/form_field_just.3x ncurses-5.2/man/form_field_new.3x ncurses-5.2/man/form_field_opts.3x ncurses-5.2/man/form_field_userptr.3x ncurses-5.2/man/form_field_validation.3x ncurses-5.2/man/form_fieldtype.3x ncurses-5.2/man/form_hook.3x ncurses-5.2/man/form_new.3x ncurses-5.2/man/form_new_page.3x ncurses-5.2/man/form_opts.3x ncurses-5.2/man/form_page.3x ncurses-5.2/man/form_post.3x ncurses-5.2/man/form_requestname.3x ncurses-5.2/man/form_userptr.3x ncurses-5.2/man/form_win.3x ncurses-5.2/man/infocmp.1m ncurses-5.2/man/infotocap.1m ncurses-5.2/man/keybound.3x ncurses-5.2/man/keyok.3x ncurses-5.2/man/make_sed.sh ncurses-5.2/man/man_db.renames ncurses-5.2/man/manlinks.sed ncurses-5.2/man/menu.3x ncurses-5.2/man/menu_attributes.3x ncurses-5.2/man/menu_cursor.3x ncurses-5.2/man/menu_driver.3x ncurses-5.2/man/menu_format.3x ncurses-5.2/man/menu_hook.3x ncurses-5.2/man/menu_items.3x ncurses-5.2/man/menu_mark.3x ncurses-5.2/man/menu_new.3x ncurses-5.2/man/menu_opts.3x ncurses-5.2/man/menu_pattern.3x ncurses-5.2/man/menu_post.3x ncurses-5.2/man/menu_requestname.3x ncurses-5.2/man/menu_spacing.3x ncurses-5.2/man/menu_userptr.3x ncurses-5.2/man/menu_win.3x ncurses-5.2/man/mitem_current.3x ncurses-5.2/man/mitem_name.3x ncurses-5.2/man/mitem_new.3x ncurses-5.2/man/mitem_opts.3x ncurses-5.2/man/mitem_userptr.3x ncurses-5.2/man/mitem_value.3x ncurses-5.2/man/mitem_visible.3x ncurses-5.2/man/ncurses.3x ncurses-5.2/man/panel.3x ncurses-5.2/man/resizeterm.3x ncurses-5.2/man/term.5 ncurses-5.2/man/term.7 ncurses-5.2/man/terminfo.head ncurses-5.2/man/terminfo.tail ncurses-5.2/man/tic.1m ncurses-5.2/man/toe.1m ncurses-5.2/man/tput.1 ncurses-5.2/man/tset.1 ncurses-5.2/man/wresize.3x ncurses-5.2/menu/Makefile.in ncurses-5.2/menu/READ.ME ncurses-5.2/menu/eti.h ncurses-5.2/menu/headers ncurses-5.2/menu/llib-lmenu ncurses-5.2/menu/m_attribs.c ncurses-5.2/menu/m_cursor.c ncurses-5.2/menu/m_driver.c ncurses-5.2/menu/m_format.c ncurses-5.2/menu/m_global.c ncurses-5.2/menu/m_hook.c ncurses-5.2/menu/m_item_cur.c ncurses-5.2/menu/m_item_nam.c ncurses-5.2/menu/m_item_new.c ncurses-5.2/menu/m_item_opt.c ncurses-5.2/menu/m_item_top.c ncurses-5.2/menu/m_item_use.c ncurses-5.2/menu/m_item_val.c ncurses-5.2/menu/m_item_vis.c ncurses-5.2/menu/m_items.c ncurses-5.2/menu/m_new.c ncurses-5.2/menu/m_opts.c ncurses-5.2/menu/m_pad.c ncurses-5.2/menu/m_pattern.c ncurses-5.2/menu/m_post.c ncurses-5.2/menu/m_req_name.c ncurses-5.2/menu/m_scale.c ncurses-5.2/menu/m_spacing.c ncurses-5.2/menu/m_sub.c ncurses-5.2/menu/m_userptr.c ncurses-5.2/menu/m_win.c ncurses-5.2/menu/menu.h ncurses-5.2/menu/menu.priv.h ncurses-5.2/menu/mf_common.h ncurses-5.2/menu/modules ncurses-5.2/misc/Makefile.in ncurses-5.2/misc/chkdef.cmd ncurses-5.2/misc/cleantic.cmd ncurses-5.2/misc/cmpdef.cmd ncurses-5.2/misc/emx.src ncurses-5.2/misc/form.def ncurses-5.2/misc/form.ref ncurses-5.2/misc/indent.pro ncurses-5.2/misc/makedef.cmd ncurses-5.2/misc/makellib ncurses-5.2/misc/menu.def ncurses-5.2/misc/menu.ref ncurses-5.2/misc/ncurses.def ncurses-5.2/misc/ncurses.ref ncurses-5.2/misc/panel.def ncurses-5.2/misc/panel.ref ncurses-5.2/misc/run_tic.in ncurses-5.2/misc/shlib ncurses-5.2/misc/tabset/std ncurses-5.2/misc/tabset/stdcrt ncurses-5.2/misc/tabset/vt100 ncurses-5.2/misc/tabset/vt300 ncurses-5.2/misc/tdlint ncurses-5.2/misc/terminfo.src ncurses-5.2/mk-0th.awk ncurses-5.2/mk-1st.awk ncurses-5.2/mk-2nd.awk ncurses-5.2/mkinstalldirs ncurses-5.2/ncurses/Makefile.in ncurses-5.2/ncurses/README ncurses-5.2/ncurses/SigAction.h ncurses-5.2/ncurses/base/MKkeyname.awk ncurses-5.2/ncurses/base/MKlib_gen.sh ncurses-5.2/ncurses/base/MKunctrl.awk ncurses-5.2/ncurses/base/README ncurses-5.2/ncurses/base/define_key.c ncurses-5.2/ncurses/base/keybound.c ncurses-5.2/ncurses/base/keyok.c ncurses-5.2/ncurses/base/lib_addch.c ncurses-5.2/ncurses/base/lib_addstr.c ncurses-5.2/ncurses/base/lib_beep.c ncurses-5.2/ncurses/base/lib_bkgd.c ncurses-5.2/ncurses/base/lib_box.c ncurses-5.2/ncurses/base/lib_chgat.c ncurses-5.2/ncurses/base/lib_clear.c ncurses-5.2/ncurses/base/lib_clearok.c ncurses-5.2/ncurses/base/lib_clrbot.c ncurses-5.2/ncurses/base/lib_clreol.c ncurses-5.2/ncurses/base/lib_color.c ncurses-5.2/ncurses/base/lib_colorset.c ncurses-5.2/ncurses/base/lib_delch.c ncurses-5.2/ncurses/base/lib_delwin.c ncurses-5.2/ncurses/base/lib_dft_fgbg.c ncurses-5.2/ncurses/base/lib_echo.c ncurses-5.2/ncurses/base/lib_endwin.c ncurses-5.2/ncurses/base/lib_erase.c ncurses-5.2/ncurses/base/lib_flash.c ncurses-5.2/ncurses/base/lib_freeall.c ncurses-5.2/ncurses/base/lib_getch.c ncurses-5.2/ncurses/base/lib_getstr.c ncurses-5.2/ncurses/base/lib_hline.c ncurses-5.2/ncurses/base/lib_immedok.c ncurses-5.2/ncurses/base/lib_inchstr.c ncurses-5.2/ncurses/base/lib_initscr.c ncurses-5.2/ncurses/base/lib_insch.c ncurses-5.2/ncurses/base/lib_insdel.c ncurses-5.2/ncurses/base/lib_insstr.c ncurses-5.2/ncurses/base/lib_instr.c ncurses-5.2/ncurses/base/lib_isendwin.c ncurses-5.2/ncurses/base/lib_leaveok.c ncurses-5.2/ncurses/base/lib_mouse.c ncurses-5.2/ncurses/base/lib_move.c ncurses-5.2/ncurses/base/lib_mvwin.c ncurses-5.2/ncurses/base/lib_newterm.c ncurses-5.2/ncurses/base/lib_newwin.c ncurses-5.2/ncurses/base/lib_nl.c ncurses-5.2/ncurses/base/lib_overlay.c ncurses-5.2/ncurses/base/lib_pad.c ncurses-5.2/ncurses/base/lib_printw.c ncurses-5.2/ncurses/base/lib_redrawln.c ncurses-5.2/ncurses/base/lib_refresh.c ncurses-5.2/ncurses/base/lib_restart.c ncurses-5.2/ncurses/base/lib_scanw.c ncurses-5.2/ncurses/base/lib_screen.c ncurses-5.2/ncurses/base/lib_scroll.c ncurses-5.2/ncurses/base/lib_scrollok.c ncurses-5.2/ncurses/base/lib_scrreg.c ncurses-5.2/ncurses/base/lib_set_term.c ncurses-5.2/ncurses/base/lib_slk.c ncurses-5.2/ncurses/base/lib_slkatr_set.c ncurses-5.2/ncurses/base/lib_slkatrof.c ncurses-5.2/ncurses/base/lib_slkatron.c ncurses-5.2/ncurses/base/lib_slkatrset.c ncurses-5.2/ncurses/base/lib_slkattr.c ncurses-5.2/ncurses/base/lib_slkclear.c ncurses-5.2/ncurses/base/lib_slkcolor.c ncurses-5.2/ncurses/base/lib_slkinit.c ncurses-5.2/ncurses/base/lib_slklab.c ncurses-5.2/ncurses/base/lib_slkrefr.c ncurses-5.2/ncurses/base/lib_slkset.c ncurses-5.2/ncurses/base/lib_slktouch.c ncurses-5.2/ncurses/base/lib_touch.c ncurses-5.2/ncurses/base/lib_ungetch.c ncurses-5.2/ncurses/base/lib_vline.c ncurses-5.2/ncurses/base/lib_wattroff.c ncurses-5.2/ncurses/base/lib_wattron.c ncurses-5.2/ncurses/base/lib_winch.c ncurses-5.2/ncurses/base/lib_window.c ncurses-5.2/ncurses/base/memmove.c ncurses-5.2/ncurses/base/nc_panel.c ncurses-5.2/ncurses/base/resizeterm.c ncurses-5.2/ncurses/base/safe_sprintf.c ncurses-5.2/ncurses/base/sigaction.c ncurses-5.2/ncurses/base/tries.c ncurses-5.2/ncurses/base/version.c ncurses-5.2/ncurses/base/vsscanf.c ncurses-5.2/ncurses/base/wresize.c ncurses-5.2/ncurses/curses.priv.h ncurses-5.2/ncurses/fifo_defs.h ncurses-5.2/ncurses/llib-lncurses ncurses-5.2/ncurses/modules ncurses-5.2/ncurses/tinfo/MKcaptab.awk ncurses-5.2/ncurses/tinfo/MKfallback.sh ncurses-5.2/ncurses/tinfo/MKnames.awk ncurses-5.2/ncurses/tinfo/README ncurses-5.2/ncurses/tinfo/access.c ncurses-5.2/ncurses/tinfo/add_tries.c ncurses-5.2/ncurses/tinfo/alloc_entry.c ncurses-5.2/ncurses/tinfo/alloc_ttype.c ncurses-5.2/ncurses/tinfo/captoinfo.c ncurses-5.2/ncurses/tinfo/comp_error.c ncurses-5.2/ncurses/tinfo/comp_expand.c ncurses-5.2/ncurses/tinfo/comp_hash.c ncurses-5.2/ncurses/tinfo/comp_parse.c ncurses-5.2/ncurses/tinfo/comp_scan.c ncurses-5.2/ncurses/tinfo/doalloc.c ncurses-5.2/ncurses/tinfo/free_ttype.c ncurses-5.2/ncurses/tinfo/getenv_num.c ncurses-5.2/ncurses/tinfo/home_terminfo.c ncurses-5.2/ncurses/tinfo/init_keytry.c ncurses-5.2/ncurses/tinfo/keys.list ncurses-5.2/ncurses/tinfo/lib_acs.c ncurses-5.2/ncurses/tinfo/lib_baudrate.c ncurses-5.2/ncurses/tinfo/lib_cur_term.c ncurses-5.2/ncurses/tinfo/lib_data.c ncurses-5.2/ncurses/tinfo/lib_has_cap.c ncurses-5.2/ncurses/tinfo/lib_kernel.c ncurses-5.2/ncurses/tinfo/lib_longname.c ncurses-5.2/ncurses/tinfo/lib_napms.c ncurses-5.2/ncurses/tinfo/lib_options.c ncurses-5.2/ncurses/tinfo/lib_print.c ncurses-5.2/ncurses/tinfo/lib_raw.c ncurses-5.2/ncurses/tinfo/lib_setup.c ncurses-5.2/ncurses/tinfo/lib_termcap.c ncurses-5.2/ncurses/tinfo/lib_termname.c ncurses-5.2/ncurses/tinfo/lib_tgoto.c ncurses-5.2/ncurses/tinfo/lib_ti.c ncurses-5.2/ncurses/tinfo/lib_tparm.c ncurses-5.2/ncurses/tinfo/lib_tputs.c ncurses-5.2/ncurses/tinfo/lib_ttyflags.c ncurses-5.2/ncurses/tinfo/make_keys.c ncurses-5.2/ncurses/tinfo/name_match.c ncurses-5.2/ncurses/tinfo/parse_entry.c ncurses-5.2/ncurses/tinfo/read_entry.c ncurses-5.2/ncurses/tinfo/read_termcap.c ncurses-5.2/ncurses/tinfo/setbuf.c ncurses-5.2/ncurses/tinfo/strings.c ncurses-5.2/ncurses/tinfo/write_entry.c ncurses-5.2/ncurses/trace/README ncurses-5.2/ncurses/trace/lib_trace.c ncurses-5.2/ncurses/trace/lib_traceatr.c ncurses-5.2/ncurses/trace/lib_tracebits.c ncurses-5.2/ncurses/trace/lib_tracechr.c ncurses-5.2/ncurses/trace/lib_tracedmp.c ncurses-5.2/ncurses/trace/lib_tracemse.c ncurses-5.2/ncurses/trace/trace_buf.c ncurses-5.2/ncurses/trace/trace_tries.c ncurses-5.2/ncurses/trace/trace_xnames.c ncurses-5.2/ncurses/tty/MKexpanded.sh ncurses-5.2/ncurses/tty/hardscroll.c ncurses-5.2/ncurses/tty/hashmap.c ncurses-5.2/ncurses/tty/lib_mvcur.c ncurses-5.2/ncurses/tty/lib_tstp.c ncurses-5.2/ncurses/tty/lib_twait.c ncurses-5.2/ncurses/tty/lib_vidattr.c ncurses-5.2/ncurses/tty/tty_display.h ncurses-5.2/ncurses/tty/tty_input.h ncurses-5.2/ncurses/tty/tty_update.c ncurses-5.2/panel/Makefile.in ncurses-5.2/panel/headers ncurses-5.2/panel/llib-lpanel ncurses-5.2/panel/modules ncurses-5.2/panel/p_above.c ncurses-5.2/panel/p_below.c ncurses-5.2/panel/p_bottom.c ncurses-5.2/panel/p_delete.c ncurses-5.2/panel/p_hidden.c ncurses-5.2/panel/p_hide.c ncurses-5.2/panel/p_move.c ncurses-5.2/panel/p_new.c ncurses-5.2/panel/p_replace.c ncurses-5.2/panel/p_show.c ncurses-5.2/panel/p_top.c ncurses-5.2/panel/p_update.c ncurses-5.2/panel/p_user.c ncurses-5.2/panel/p_win.c ncurses-5.2/panel/panel.c ncurses-5.2/panel/panel.h ncurses-5.2/panel/panel.priv.h ncurses-5.2/progs/MKtermsort.sh ncurses-5.2/progs/Makefile.in ncurses-5.2/progs/capconvert ncurses-5.2/progs/clear.c ncurses-5.2/progs/clear.sh ncurses-5.2/progs/dump_entry.c ncurses-5.2/progs/dump_entry.h ncurses-5.2/progs/infocmp.c ncurses-5.2/progs/modules ncurses-5.2/progs/progs.priv.h ncurses-5.2/progs/tic.c ncurses-5.2/progs/toe.c ncurses-5.2/progs/tput.c ncurses-5.2/progs/tset.c ncurses-5.2/sysdeps/unix/sysv/linux/Makefile ncurses-5.2/sysdeps/unix/sysv/linux/alpha/configure ncurses-5.2/sysdeps/unix/sysv/linux/configure ncurses-5.2/sysdeps/unix/sysv/linux/edit_man.sed ncurses-5.2/sysdeps/unix/sysv/linux/edit_man.sh ncurses-5.2/sysdeps/unix/sysv/linux/run_tic.sh ncurses-5.2/tack/COPYING ncurses-5.2/tack/HISTORY ncurses-5.2/tack/Makefile.in ncurses-5.2/tack/README ncurses-5.2/tack/ansi.c ncurses-5.2/tack/charset.c ncurses-5.2/tack/color.c ncurses-5.2/tack/control.c ncurses-5.2/tack/crum.c ncurses-5.2/tack/edit.c ncurses-5.2/tack/fun.c ncurses-5.2/tack/init.c ncurses-5.2/tack/menu.c ncurses-5.2/tack/modes.c ncurses-5.2/tack/modules ncurses-5.2/tack/output.c ncurses-5.2/tack/pad.c ncurses-5.2/tack/scan.c ncurses-5.2/tack/sync.c ncurses-5.2/tack/sysdep.c ncurses-5.2/tack/tack.1 ncurses-5.2/tack/tack.c ncurses-5.2/tack/tack.h ncurses-5.2/tar-copy.sh ncurses-5.2/test/Makefile.in ncurses-5.2/test/README ncurses-5.2/test/blue.c ncurses-5.2/test/bs.6 ncurses-5.2/test/bs.c ncurses-5.2/test/cardfile.c ncurses-5.2/test/cardfile.dat ncurses-5.2/test/configure ncurses-5.2/test/configure.in ncurses-5.2/test/ditto.c ncurses-5.2/test/dots.c ncurses-5.2/test/filter.c ncurses-5.2/test/firework.c ncurses-5.2/test/firstlast.c ncurses-5.2/test/gdc.6 ncurses-5.2/test/gdc.c ncurses-5.2/test/hanoi.c ncurses-5.2/test/hashtest.c ncurses-5.2/test/keynames.c ncurses-5.2/test/knight.c ncurses-5.2/test/lrtest.c ncurses-5.2/test/modules ncurses-5.2/test/ncurses.c ncurses-5.2/test/ncurses_tst.hin ncurses-5.2/test/newdemo.c ncurses-5.2/test/railroad.c ncurses-5.2/test/rain.c ncurses-5.2/test/tclock.c ncurses-5.2/test/test.priv.h ncurses-5.2/test/testaddch.c ncurses-5.2/test/testcurs.c ncurses-5.2/test/testscanw.c ncurses-5.2/test/tracemunch ncurses-5.2/test/view.c ncurses-5.2/test/worm.c ncurses-5.2/test/xmas.c Cherrypick from master 2007-08-07 16:14:17 UTC Joel Sherrill <joel.sherrill@OARcorp.com> '2007-08-07 Joel Sherrill <joel.sherrill@OARcorp.com>': ChangeLog RTEMS_Makefiles/Makefile.bfd RTEMS_Makefiles/Makefile.libtecla RTEMS_Makefiles/Makefile.ncurses RTEMS_Makefiles/Makefile.ncurses-5.3 RTEMS_Makefiles/Makefile.readline-4.3 RTEMS_Makefiles/Makefile.zlib SUPPORT VERSION bit bit_bfd libtecla-1.4.1/CHANGES libtecla-1.4.1/INSTALL libtecla-1.4.1/LICENSE.TERMS libtecla-1.4.1/Makefile libtecla-1.4.1/Makefile.in libtecla-1.4.1/Makefile.rules libtecla-1.4.1/Makefile.stub libtecla-1.4.1/PORTING libtecla-1.4.1/README libtecla-1.4.1/RELEASE.NOTES libtecla-1.4.1/config.guess libtecla-1.4.1/config.sub libtecla-1.4.1/configure libtecla-1.4.1/configure.in libtecla-1.4.1/cplfile.c libtecla-1.4.1/cplfile.h libtecla-1.4.1/cplmatch.c libtecla-1.4.1/demo.c libtecla-1.4.1/demo2.c libtecla-1.4.1/direader.c libtecla-1.4.1/direader.h libtecla-1.4.1/enhance.c libtecla-1.4.1/expand.c libtecla-1.4.1/freelist.c libtecla-1.4.1/freelist.h libtecla-1.4.1/getline.c libtecla-1.4.1/getline.h libtecla-1.4.1/hash.c libtecla-1.4.1/hash.h libtecla-1.4.1/history.c libtecla-1.4.1/history.h libtecla-1.4.1/homedir.c libtecla-1.4.1/homedir.h libtecla-1.4.1/html/changes.html libtecla-1.4.1/html/cpl_complete_word.html libtecla-1.4.1/html/ef_expand_file.html libtecla-1.4.1/html/enhance.html libtecla-1.4.1/html/gl_get_line.html libtecla-1.4.1/html/index.html libtecla-1.4.1/html/libtecla.html libtecla-1.4.1/html/pca_lookup_file.html libtecla-1.4.1/html/release.html libtecla-1.4.1/install-sh libtecla-1.4.1/keytab.c libtecla-1.4.1/keytab.h libtecla-1.4.1/libtecla.h libtecla-1.4.1/libtecla.map libtecla-1.4.1/man3/cfc_file_start.3 libtecla-1.4.1/man3/cfc_literal_escapes.3 libtecla-1.4.1/man3/cfc_set_check_fn.3 libtecla-1.4.1/man3/cpl_add_completion.3 libtecla-1.4.1/man3/cpl_complete_word.3 libtecla-1.4.1/man3/cpl_file_completions.3 libtecla-1.4.1/man3/cpl_last_error.3 libtecla-1.4.1/man3/cpl_list_completions.3 libtecla-1.4.1/man3/cpl_record_error.3 libtecla-1.4.1/man3/del_CplFileConf.3 libtecla-1.4.1/man3/del_ExpandFile.3 libtecla-1.4.1/man3/del_GetLine.3 libtecla-1.4.1/man3/del_PathCache.3 libtecla-1.4.1/man3/del_PcaPathConf.3 libtecla-1.4.1/man3/del_WordCompletion.3 libtecla-1.4.1/man3/ef_expand_file.3 libtecla-1.4.1/man3/ef_last_error.3 libtecla-1.4.1/man3/ef_list_expansions.3 libtecla-1.4.1/man3/enhance.3 libtecla-1.4.1/man3/gl_change_terminal.3 libtecla-1.4.1/man3/gl_clear_history.3 libtecla-1.4.1/man3/gl_configure_getline.3 libtecla-1.4.1/man3/gl_customize_completion.3 libtecla-1.4.1/man3/gl_echo_mode.3 libtecla-1.4.1/man3/gl_get_line.3 libtecla-1.4.1/man3/gl_group_history.3 libtecla-1.4.1/man3/gl_ignore_signal.3 libtecla-1.4.1/man3/gl_last_signal.3 libtecla-1.4.1/man3/gl_limit_history.3 libtecla-1.4.1/man3/gl_load_history.3 libtecla-1.4.1/man3/gl_lookup_history.3 libtecla-1.4.1/man3/gl_prompt_style.3 libtecla-1.4.1/man3/gl_range_of_history.3 libtecla-1.4.1/man3/gl_resize_history.3 libtecla-1.4.1/man3/gl_save_history.3 libtecla-1.4.1/man3/gl_show_history.3 libtecla-1.4.1/man3/gl_size_of_history.3 libtecla-1.4.1/man3/gl_state_of_history.3 libtecla-1.4.1/man3/gl_terminal_size.3 libtecla-1.4.1/man3/gl_toggle_history.3 libtecla-1.4.1/man3/gl_trap_signal.3 libtecla-1.4.1/man3/gl_watch_fd.3 libtecla-1.4.1/man3/libtecla.3 libtecla-1.4.1/man3/libtecla_version.3 libtecla-1.4.1/man3/new_CplFileConf.3 libtecla-1.4.1/man3/new_ExpandFile.3 libtecla-1.4.1/man3/new_GetLine.3 libtecla-1.4.1/man3/new_PathCache.3 libtecla-1.4.1/man3/new_PcaPathConf.3 libtecla-1.4.1/man3/new_WordCompletion.3 libtecla-1.4.1/man3/pca_last_error.3 libtecla-1.4.1/man3/pca_lookup_file.3 libtecla-1.4.1/man3/pca_path_completions.3 libtecla-1.4.1/man3/pca_scan_path.3 libtecla-1.4.1/man3/pca_set_check_fn.3 libtecla-1.4.1/man3/ppc_file_start.3 libtecla-1.4.1/man3/ppc_literal_escapes.3 libtecla-1.4.1/pathutil.c libtecla-1.4.1/pathutil.h libtecla-1.4.1/pcache.c libtecla-1.4.1/stringrp.c libtecla-1.4.1/stringrp.h libtecla-1.4.1/strngmem.c libtecla-1.4.1/strngmem.h libtecla-1.4.1/update_html libtecla-1.4.1/update_version libtecla-1.4.1/version.c ncurses-5.3/config.sub ncurses-5.3/misc/run_tic.sh readline-4.3.orig/CHANGELOG readline-4.3.orig/CHANGES readline-4.3.orig/COPYING readline-4.3.orig/INSTALL readline-4.3.orig/MANIFEST readline-4.3.orig/Makefile.in readline-4.3.orig/README readline-4.3.orig/USAGE readline-4.3.orig/aclocal.m4 readline-4.3.orig/ansi_stdlib.h readline-4.3.orig/bind.c readline-4.3.orig/callback.c readline-4.3.orig/chardefs.h readline-4.3.orig/compat.c readline-4.3.orig/complete.c readline-4.3.orig/config.h.in readline-4.3.orig/configure readline-4.3.orig/configure.in readline-4.3.orig/display.c readline-4.3.orig/doc/Makefile.in readline-4.3.orig/doc/hist.texinfo readline-4.3.orig/doc/history.0 readline-4.3.orig/doc/history.3 readline-4.3.orig/doc/history.dvi readline-4.3.orig/doc/history.html readline-4.3.orig/doc/history.info readline-4.3.orig/doc/history.ps readline-4.3.orig/doc/history_3.ps readline-4.3.orig/doc/hstech.texinfo readline-4.3.orig/doc/hsuser.texinfo readline-4.3.orig/doc/manvers.texinfo readline-4.3.orig/doc/readline.0 readline-4.3.orig/doc/readline.3 readline-4.3.orig/doc/readline.dvi readline-4.3.orig/doc/readline.html readline-4.3.orig/doc/readline.info readline-4.3.orig/doc/readline.ps readline-4.3.orig/doc/readline_3.ps readline-4.3.orig/doc/rlman.texinfo readline-4.3.orig/doc/rltech.texinfo readline-4.3.orig/doc/rluser.texinfo readline-4.3.orig/doc/rluserman.dvi readline-4.3.orig/doc/rluserman.html readline-4.3.orig/doc/rluserman.info readline-4.3.orig/doc/rluserman.ps readline-4.3.orig/doc/rluserman.texinfo readline-4.3.orig/doc/texi2dvi readline-4.3.orig/doc/texi2html readline-4.3.orig/doc/texinfo.tex readline-4.3.orig/emacs_keymap.c readline-4.3.orig/examples/Inputrc readline-4.3.orig/examples/Makefile.in readline-4.3.orig/examples/excallback.c readline-4.3.orig/examples/fileman.c readline-4.3.orig/examples/histexamp.c readline-4.3.orig/examples/manexamp.c readline-4.3.orig/examples/readlinebuf.h readline-4.3.orig/examples/rl.c readline-4.3.orig/examples/rlcat.c readline-4.3.orig/examples/rlfe.c readline-4.3.orig/examples/rltest.c readline-4.3.orig/examples/rlversion.c readline-4.3.orig/funmap.c readline-4.3.orig/histexpand.c readline-4.3.orig/histfile.c readline-4.3.orig/histlib.h readline-4.3.orig/history.c readline-4.3.orig/history.h readline-4.3.orig/histsearch.c readline-4.3.orig/input.c readline-4.3.orig/isearch.c readline-4.3.orig/keymaps.c readline-4.3.orig/keymaps.h readline-4.3.orig/kill.c readline-4.3.orig/macro.c readline-4.3.orig/mbutil.c readline-4.3.orig/misc.c readline-4.3.orig/nls.c readline-4.3.orig/parens.c readline-4.3.orig/posixdir.h readline-4.3.orig/posixjmp.h readline-4.3.orig/posixstat.h readline-4.3.orig/readline.c readline-4.3.orig/readline.h readline-4.3.orig/rlconf.h readline-4.3.orig/rldefs.h readline-4.3.orig/rlmbutil.h readline-4.3.orig/rlprivate.h readline-4.3.orig/rlshell.h readline-4.3.orig/rlstdc.h readline-4.3.orig/rltty.c readline-4.3.orig/rltty.h readline-4.3.orig/rltypedefs.h readline-4.3.orig/rlwinsize.h readline-4.3.orig/savestring.c readline-4.3.orig/search.c readline-4.3.orig/shell.c readline-4.3.orig/shlib/Makefile.in readline-4.3.orig/signals.c readline-4.3.orig/support/config.guess readline-4.3.orig/support/config.sub readline-4.3.orig/support/install.sh readline-4.3.orig/support/mkdirs readline-4.3.orig/support/mkdist readline-4.3.orig/support/shlib-install readline-4.3.orig/support/shobj-conf readline-4.3.orig/support/wcwidth.c readline-4.3.orig/tcap.h readline-4.3.orig/terminal.c readline-4.3.orig/text.c readline-4.3.orig/tilde.c readline-4.3.orig/tilde.h readline-4.3.orig/undo.c readline-4.3.orig/util.c readline-4.3.orig/vi_keymap.c readline-4.3.orig/vi_mode.c readline-4.3.orig/xmalloc.c readline-4.3.orig/xmalloc.h readline-4.3/CHANGELOG-ReadLine readline-4.3/CHANGES readline-4.3/COPYING readline-4.3/INSTALL readline-4.3/MANIFEST readline-4.3/Makefile.in readline-4.3/README readline-4.3/USAGE readline-4.3/aclocal.m4 readline-4.3/ansi_stdlib.h readline-4.3/bind.c readline-4.3/callback.c readline-4.3/chardefs.h readline-4.3/compat.c readline-4.3/complete.c readline-4.3/config.h.in readline-4.3/configure readline-4.3/configure.in readline-4.3/display.c readline-4.3/doc/Makefile.in readline-4.3/doc/hist.texinfo readline-4.3/doc/history.3 readline-4.3/doc/hstech.texinfo readline-4.3/doc/hsuser.texinfo readline-4.3/doc/manvers.texinfo readline-4.3/doc/readline.3 readline-4.3/doc/rlman.texinfo readline-4.3/doc/rltech.texinfo readline-4.3/doc/rluser.texinfo readline-4.3/doc/rluserman.texinfo readline-4.3/doc/texi2dvi readline-4.3/doc/texi2html readline-4.3/doc/texinfo.tex readline-4.3/emacs_keymap.c readline-4.3/examples/Inputrc readline-4.3/examples/Makefile.in readline-4.3/examples/excallback.c readline-4.3/examples/fileman.c readline-4.3/examples/histexamp.c readline-4.3/examples/manexamp.c readline-4.3/examples/readlinebuf.h readline-4.3/examples/rl.c readline-4.3/examples/rlcat.c readline-4.3/examples/rlfe.c readline-4.3/examples/rltest.c readline-4.3/examples/rlversion.c readline-4.3/funmap.c readline-4.3/histexpand.c readline-4.3/histfile.c readline-4.3/histlib.h readline-4.3/history.c readline-4.3/history.h readline-4.3/histsearch.c readline-4.3/input.c readline-4.3/isearch.c readline-4.3/keymaps.c readline-4.3/keymaps.h readline-4.3/kill.c readline-4.3/macro.c readline-4.3/mbutil.c readline-4.3/misc.c readline-4.3/nls.c readline-4.3/parens.c readline-4.3/posixdir.h readline-4.3/posixjmp.h readline-4.3/posixstat.h readline-4.3/readline.c readline-4.3/readline.h readline-4.3/rlconf.h readline-4.3/rldefs.h readline-4.3/rlmbutil.h readline-4.3/rlprivate.h readline-4.3/rlshell.h readline-4.3/rlstdc.h readline-4.3/rltty.c readline-4.3/rltty.h readline-4.3/rltypedefs.h readline-4.3/rlwinsize.h readline-4.3/savestring.c readline-4.3/search.c readline-4.3/shell.c readline-4.3/shlib/Makefile.in readline-4.3/signals.c readline-4.3/support/config.guess readline-4.3/support/config.sub readline-4.3/support/install.sh readline-4.3/support/mkdirs readline-4.3/support/mkdist readline-4.3/support/shlib-install readline-4.3/support/shobj-conf readline-4.3/support/wcwidth.c readline-4.3/tcap.h readline-4.3/terminal.c readline-4.3/text.c readline-4.3/tilde.c readline-4.3/tilde.h readline-4.3/undo.c readline-4.3/util.c readline-4.3/vi_keymap.c readline-4.3/vi_mode.c readline-4.3/xmalloc.c readline-4.3/xmalloc.h readline-doc-4.3/MANIFEST.doc readline-doc-4.3/doc/history.0 readline-doc-4.3/doc/history.dvi readline-doc-4.3/doc/history.html readline-doc-4.3/doc/history.info readline-doc-4.3/doc/history.ps readline-doc-4.3/doc/history_3.ps readline-doc-4.3/doc/readline.0 readline-doc-4.3/doc/readline.dvi readline-doc-4.3/doc/readline.html readline-doc-4.3/doc/readline.info readline-doc-4.3/doc/readline.ps readline-doc-4.3/doc/readline_3.ps readline-doc-4.3/doc/rluserman.dvi readline-doc-4.3/doc/rluserman.html readline-doc-4.3/doc/rluserman.info readline-doc-4.3/doc/rluserman.ps zlib-1.1.4/ChangeLog zlib-1.1.4/FAQ zlib-1.1.4/INDEX zlib-1.1.4/Make_vms.com zlib-1.1.4/Makefile zlib-1.1.4/Makefile.in zlib-1.1.4/Makefile.riscos zlib-1.1.4/README zlib-1.1.4/adler32.c zlib-1.1.4/algorithm.txt zlib-1.1.4/amiga/Makefile.pup zlib-1.1.4/amiga/Makefile.sas zlib-1.1.4/compress.c zlib-1.1.4/configure zlib-1.1.4/contrib/README.contrib zlib-1.1.4/contrib/asm386/gvmat32.asm zlib-1.1.4/contrib/asm386/gvmat32c.c zlib-1.1.4/contrib/asm386/mkgvmt32.bat zlib-1.1.4/contrib/asm386/zlibvc.def zlib-1.1.4/contrib/asm386/zlibvc.dsp zlib-1.1.4/contrib/asm386/zlibvc.dsw zlib-1.1.4/contrib/asm586/README.586 zlib-1.1.4/contrib/asm586/match.S zlib-1.1.4/contrib/asm686/README.686 zlib-1.1.4/contrib/asm686/match.S zlib-1.1.4/contrib/delphi/zlib.mak zlib-1.1.4/contrib/delphi/zlibdef.pas zlib-1.1.4/contrib/delphi2/d_zlib.bpr zlib-1.1.4/contrib/delphi2/d_zlib.cpp zlib-1.1.4/contrib/delphi2/readme.txt zlib-1.1.4/contrib/delphi2/zlib.bpg zlib-1.1.4/contrib/delphi2/zlib.bpr zlib-1.1.4/contrib/delphi2/zlib.cpp zlib-1.1.4/contrib/delphi2/zlib.pas zlib-1.1.4/contrib/delphi2/zlib32.bpr zlib-1.1.4/contrib/delphi2/zlib32.cpp zlib-1.1.4/contrib/iostream/test.cpp zlib-1.1.4/contrib/iostream/zfstream.cpp zlib-1.1.4/contrib/iostream/zfstream.h zlib-1.1.4/contrib/iostream2/zstream.h zlib-1.1.4/contrib/iostream2/zstream_test.cpp zlib-1.1.4/contrib/minizip/ChangeLogUnzip zlib-1.1.4/contrib/minizip/Makefile zlib-1.1.4/contrib/minizip/miniunz.c zlib-1.1.4/contrib/minizip/minizip.c zlib-1.1.4/contrib/minizip/readme.txt zlib-1.1.4/contrib/minizip/unzip.c zlib-1.1.4/contrib/minizip/unzip.def zlib-1.1.4/contrib/minizip/unzip.h zlib-1.1.4/contrib/minizip/zip.c zlib-1.1.4/contrib/minizip/zip.def zlib-1.1.4/contrib/minizip/zip.h zlib-1.1.4/contrib/minizip/zlibvc.def zlib-1.1.4/contrib/minizip/zlibvc.dsp zlib-1.1.4/contrib/minizip/zlibvc.dsw zlib-1.1.4/contrib/untgz/Makefile zlib-1.1.4/contrib/untgz/makefile.w32 zlib-1.1.4/contrib/untgz/untgz.c zlib-1.1.4/contrib/visual-basic.txt zlib-1.1.4/crc32.c zlib-1.1.4/deflate.c zlib-1.1.4/deflate.h zlib-1.1.4/descrip.mms zlib-1.1.4/example.c zlib-1.1.4/gzio.c zlib-1.1.4/infblock.c zlib-1.1.4/infblock.h zlib-1.1.4/infcodes.c zlib-1.1.4/infcodes.h zlib-1.1.4/inffast.c zlib-1.1.4/inffast.h zlib-1.1.4/inffixed.h zlib-1.1.4/inflate.c zlib-1.1.4/inftrees.c zlib-1.1.4/inftrees.h zlib-1.1.4/infutil.c zlib-1.1.4/infutil.h zlib-1.1.4/maketree.c zlib-1.1.4/minigzip.c zlib-1.1.4/msdos/Makefile.b32 zlib-1.1.4/msdos/Makefile.bor zlib-1.1.4/msdos/Makefile.dj2 zlib-1.1.4/msdos/Makefile.emx zlib-1.1.4/msdos/Makefile.msc zlib-1.1.4/msdos/Makefile.tc zlib-1.1.4/msdos/Makefile.w32 zlib-1.1.4/msdos/Makefile.wat zlib-1.1.4/msdos/zlib.def zlib-1.1.4/msdos/zlib.rc zlib-1.1.4/nt/Makefile.emx zlib-1.1.4/nt/Makefile.gcc zlib-1.1.4/nt/Makefile.nt zlib-1.1.4/nt/zlib.dnt zlib-1.1.4/os2/Makefile.os2 zlib-1.1.4/os2/zlib.def zlib-1.1.4/trees.c zlib-1.1.4/trees.h zlib-1.1.4/uncompr.c zlib-1.1.4/zconf.h zlib-1.1.4/zlib.3 zlib-1.1.4/zlib.h zlib-1.1.4/zlib.html zlib-1.1.4/zutil.c zlib-1.1.4/zutil.h
Diffstat (limited to 'avl-1.4.0/avlt.c')
-rw-r--r--avl-1.4.0/avlt.c1597
1 files changed, 1597 insertions, 0 deletions
diff --git a/avl-1.4.0/avlt.c b/avl-1.4.0/avlt.c
new file mode 100644
index 0000000..d050fba
--- /dev/null
+++ b/avl-1.4.0/avlt.c
@@ -0,0 +1,1597 @@
+/* libavl - manipulates AVL trees.
+ Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2 of the
+ License, or (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ The author may be contacted at <pfaffben@pilot.msu.edu> on the
+ Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA
+ through more mundane means. */
+
+/* This is file avlt.c in libavl. */
+
+#if HAVE_CONFIG_H
+#include <config.h>
+#endif
+#if SELF_TEST
+#include <limits.h>
+#include <time.h>
+#endif
+#include <stdio.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <assert.h>
+#include "avlt.h"
+
+/* Tag types. */
+#define PLUS +1
+#define MINUS -1
+
+#if !__GCC__ && !defined (inline)
+#define inline
+#endif
+
+#if __GNUC__ >= 2
+#define unused __attribute__ ((unused))
+#else
+#define unused
+#endif
+
+#ifdef HAVE_XMALLOC
+void *xmalloc (size_t);
+#else /* !HAVE_XMALLOC */
+/* Allocates SIZE bytes of space using malloc(). Aborts if out of
+ memory. */
+static void *
+xmalloc (size_t size)
+{
+ void *vp;
+ if (size == 0)
+ return NULL;
+ vp = malloc (size);
+ assert (vp != NULL);
+ if (vp == NULL)
+ {
+ fprintf (stderr, "virtual memory exhausted\n");
+ exit (EXIT_FAILURE);
+ }
+ return vp;
+}
+#endif /* !HAVE_XMALLOC */
+
+/* Creates an AVL tree in arena OWNER (which can be NULL). The arena
+ is owned by the caller, not by the AVL tree. CMP is a order
+ function for the data to be stored in the tree. PARAM is arbitrary
+ data that becomes an argument to the comparison function. */
+avlt_tree *
+avlt_create (avl_comparison_func cmp, void *param)
+{
+ avlt_tree *tree;
+
+ assert (cmp != NULL);
+ tree = xmalloc (sizeof (avlt_tree));
+
+ tree->root.link[0] = tree->root.link[1] = &tree->root;
+ tree->root.tag[0] = MINUS;
+ tree->root.tag[1] = PLUS;
+ tree->cmp = cmp;
+ tree->count = 0;
+ tree->param = param;
+
+ return tree;
+}
+
+/* Destroy tree TREE. Function FREE_FUNC is called for every node in
+ the tree as it is destroyed.
+
+ No effect if the tree has an arena owner and free_func is NULL.
+ The caller owns the arena and must destroy it itself.
+
+ Do not attempt to reuse the tree after it has been freed. Create a
+ new one. */
+void
+avlt_destroy (avlt_tree *tree, avl_node_func free_func)
+{
+ assert (tree != NULL);
+
+ if (tree->root.link[0] != &tree->root)
+ {
+ /* Uses Knuth's Algorithm 2.3.1T as modified in exercise 13
+ (postorder traversal). */
+
+ /* T1. */
+ avlt_node *an[AVL_MAX_HEIGHT]; /* Stack A: nodes. */
+ char ab[AVL_MAX_HEIGHT]; /* Stack A: bits. */
+ int ap = 0; /* Stack A: height. */
+ avlt_node *p = tree->root.link[0];
+
+ for (;;)
+ {
+ /* T2. */
+ for (;;)
+ {
+ /* T3. */
+ ab[ap] = 0;
+ an[ap++] = p;
+ if (p->tag[0] == MINUS)
+ break;
+ p = p->link[0];
+ }
+
+ /* T4. */
+ for (;;)
+ {
+ if (ap == 0)
+ goto done;
+
+ p = an[--ap];
+ if (ab[ap] == 0)
+ {
+ ab[ap++] = 1;
+ if (p->tag[1] == MINUS)
+ continue;
+ p = p->link[1];
+ break;
+ }
+
+ if (free_func)
+ free_func (p->data, tree->param);
+ free (p);
+ }
+ }
+ }
+
+ done:
+ free (tree);
+}
+
+/* avlt_destroy() with FREE_FUNC hardcoded as free(). */
+void
+avlt_free (avlt_tree *tree)
+{
+ avlt_destroy (tree, (avl_node_func) free);
+}
+
+/* Return the number of nodes in TREE. */
+int
+avlt_count (const avlt_tree *tree)
+{
+ assert (tree != NULL);
+ return tree->count;
+}
+
+/* Copy the contents of TREE to a new tree in arena OWNER. If COPY is
+ non-NULL, then each data item is passed to function COPY, and the
+ return values are inserted into the new tree; otherwise, the items
+ are copied verbatim from the old tree to the new tree. Returns the
+ new tree. */
+avlt_tree *
+avlt_copy (const avlt_tree *tree, avl_copy_func copy)
+{
+ /* Knuth's Algorithm 2.3.1C (copying a binary tree). Additionally
+ uses Algorithm 2.3.1I (insertion into a threaded binary tree) and
+ Algorithm 2.3.1 exercise 17 (preorder successor in threaded
+ binary tree). */
+
+ avlt_tree *new_tree;
+
+ const avlt_node *p;
+ avlt_node *q;
+
+ assert (tree != NULL);
+ new_tree = avlt_create (tree->cmp, tree->param);
+ new_tree->count = tree->count;
+ p = &tree->root;
+ if (p->link[0] == p)
+ return new_tree;
+ q = &new_tree->root;
+
+ for (;;)
+ {
+ /* C4. This is Algorithm 2.3.1I modified for insertion to the
+ left. Step I2 is not necessary. */
+ if (p->tag[0] == PLUS)
+ {
+ avlt_node *r = xmalloc (sizeof (avlt_node));
+
+ r->link[0] = q->link[0];
+ r->tag[0] = q->tag[0];
+ q->link[0] = r;
+ q->tag[0] = PLUS;
+ r->link[1] = q;
+ r->tag[1] = MINUS;
+ }
+
+ /* C5: Find preorder successors of P and Q. This is Algorithm
+ 2.3.1 exercise 17 but applies its actions to Q as well as
+ P. */
+ if (p->tag[0] == PLUS)
+ {
+ p = p->link[0];
+ q = q->link[0];
+ }
+ else
+ {
+ while (p->tag[1] == MINUS)
+ {
+ p = p->link[1];
+ q = q->link[1];
+ }
+ p = p->link[1];
+ q = q->link[1];
+ }
+
+ /* C6. */
+ if (p == &tree->root)
+ {
+ assert (q == &new_tree->root);
+ return new_tree;
+ }
+
+ /* C2. This is Algorithm 2.3.1I. Step I2 is not necessary. */
+ if (p->tag[1] == PLUS)
+ {
+ avlt_node *r = xmalloc (sizeof (avlt_node));
+
+ r->link[1] = q->link[1];
+ r->tag[1] = q->tag[1];
+ q->link[1] = r;
+ q->tag[1] = PLUS;
+ r->link[0] = q;
+ r->tag[0] = MINUS;
+ }
+
+ /* C3. */
+ q->bal = p->bal;
+ if (copy == NULL)
+ q->data = p->data;
+ else
+ q->data = copy (p->data, tree->param);
+ }
+}
+
+/* Threads the unthreaded AVL tree TREE in-place, and returns TREE cast to
+ avlt_tree *. */
+avlt_tree *
+avlt_thread (struct avl_tree *_tree)
+{
+ /* Uses Knuth's Algorithm 2.3.1 exercise 30 (thread an unthreaded
+ tree, with Algorithm 2.3.1T (inorder traversal) for computing
+ Q$. */
+
+ avlt_tree *tree = (avlt_tree *) _tree;
+
+ /* Algorithm T's variables. */
+ avlt_node *an[AVL_MAX_HEIGHT]; /* Stack A: nodes. */
+ avlt_node **ap; /* Stack A: stack pointer. */
+ avlt_node *tp; /* P. */
+
+ /* Algorithm L's variables. */
+ avlt_node *p, *q;
+
+ assert (tree != NULL);
+
+ /* T1. */
+ ap = an;
+ tp = tree->root.link[0];
+
+ /* L1. */
+ q = &tree->root;
+ q->link[1] = q;
+
+ for (;;)
+ {
+ /* L2. */
+ {
+ /* T2. */
+ while (tp != NULL)
+ {
+ /* T3. */
+ *ap++ = tp;
+ tp = tp->link[0];
+ }
+
+ /* T4. Modified to visit HEAD after fully traversing the
+ tree. */
+ if (ap == an)
+ tp = &tree->root;
+ else
+ tp = *--ap;
+
+ /* T5: Visit P. */
+ p = tp;
+ }
+
+ /* L3. */
+ if (q->link[1] == NULL)
+ {
+ q->link[1] = p;
+ q->tag[1] = MINUS;
+ }
+ else
+ q->tag[1] = PLUS;
+
+ if (p->link[0] == NULL)
+ {
+ p->link[0] = q;
+ p->tag[0] = MINUS;
+ }
+ else
+ p->tag[0] = PLUS;
+
+ /* L4. */
+ if (p == &tree->root)
+ return tree;
+ q = p;
+
+ /* T5: Next. */
+ tp = tp->link[1];
+ }
+}
+
+/* Unthreads the threaded tree TREE in-place, and returns TREE cast to
+ avl_tree *. */
+struct avl_tree *
+avlt_unthread (avlt_tree *tree)
+{
+ /* Uses Knuth's Algorithm 2.3.1T as modified in exercise 13
+ (postorder traversal). */
+
+ /* T1. */
+ avlt_node *an[AVL_MAX_HEIGHT]; /* Stack A: nodes. */
+ char ab[AVL_MAX_HEIGHT]; /* Stack A: bits. */
+ int ap = 0; /* Stack A: height. */
+ avlt_node *p;
+
+ assert (tree != NULL);
+ p = tree->root.link[0];
+ if (p != &tree->root)
+ for (;;)
+ {
+ /* T2. */
+ for (;;)
+ {
+ /* T3. */
+ ab[ap] = 0;
+ an[ap++] = p;
+ if (p->tag[0] == MINUS)
+ break;
+ p = p->link[0];
+ }
+
+ /* T4. */
+ for (;;)
+ {
+ if (ap == 0)
+ goto done;
+
+ p = an[--ap];
+ if (ab[ap] == 0)
+ {
+ ab[ap++] = 1;
+ if (p->tag[1] == MINUS)
+ continue;
+ p = p->link[1];
+ break;
+ }
+
+ if (p->tag[0] == MINUS)
+ p->link[0] = NULL;
+ if (p->tag[1] == MINUS)
+ p->link[1] = NULL;
+ }
+ }
+ else
+ tree->root.link[0] = NULL;
+
+ done:
+ tree->root.link[1] = NULL;
+ return (struct avl_tree *) tree;
+}
+
+/* Walk tree TREE in inorder, calling WALK_FUNC at each node. Passes
+ PARAM to WALK_FUNC. */
+void
+avlt_walk (const avlt_tree *tree, avl_node_func walk_func, void *param)
+{
+ const avlt_node *p;
+
+ /* Uses Knuth's algorithm 2.3.1D (threaded inorder successor). */
+ assert (tree && walk_func);
+
+ p = &tree->root;
+ for (;;)
+ {
+ if (p->tag[1] == MINUS)
+ p = p->link[1];
+ else
+ {
+ p = p->link[1];
+ while (p->tag[0] == PLUS)
+ p = p->link[0];
+ }
+
+ if (p == &tree->root)
+ return;
+
+ walk_func (p->data, param);
+ }
+}
+
+/* Each call to this function for a given TREE and TRAV return the
+ next item in the tree in inorder. Initialize the first element of
+ TRAV (init) to 0 before calling the first time. Returns NULL when
+ out of elements. */
+void *
+avlt_traverse (const avlt_tree *tree, avlt_traverser *trav)
+{
+ const avlt_node *p;
+
+ assert (tree && trav);
+
+ if (trav->init == 0)
+ {
+ p = &tree->root;
+ trav->init = 1;
+ }
+ else
+ p = trav->p;
+
+ /* Knuth's Algorithm 2.3.1S (threaded inorder successor). */
+ if (p->tag[1] == MINUS)
+ p = p->link[1];
+ else
+ {
+ p = p->link[1];
+ while (p->tag[0] == PLUS)
+ p = p->link[0];
+ }
+
+ if (p == &tree->root)
+ {
+ trav->init = 0;
+ return NULL;
+ }
+ else
+ {
+ trav->p = p;
+ return (void *) p->data;
+ }
+}
+
+/* Given ITEM, a pointer to a data item in TREE (or NULL), returns a
+ pointer to the next item in the tree in comparison order, or NULL
+ if ITEM is the last item. */
+void **
+avlt_next (const avlt_tree *tree, void **item)
+{
+ const avlt_node *p;
+
+ assert (tree != NULL);
+ if (item == NULL)
+ p = &tree->root;
+ else
+ p = (avlt_node *) (((char *) item) - offsetof (avlt_node, data));
+
+ /* Knuth's Algorithm 2.3.1S (threaded inorder successor). */
+ if (p->tag[1] == MINUS)
+ p = p->link[1];
+ else
+ {
+ p = p->link[1];
+ while (p->tag[0] == PLUS)
+ p = p->link[0];
+ }
+
+ if (p == &tree->root)
+ return NULL;
+
+ return (void **) &p->data;
+}
+
+/* Given ITEM, a pointer to a data item in TREE (or NULL), returns a
+ pointer to the previous item in the tree in comparison order, or
+ NULL if ITEM is the first item. */
+void **
+avlt_prev (const avlt_tree *tree, void **item)
+{
+ const avlt_node *p;
+
+ assert (tree != NULL);
+ if (item == NULL)
+ {
+ /* Find node with greatest value. */
+ p = tree->root.link[0];
+ if (p == &tree->root)
+ return NULL;
+ while (p->tag[1] == PLUS)
+ p = p->link[1];
+ }
+ else
+ {
+ p = (avlt_node *) (((char *) item) - offsetof (avlt_node, data));
+
+ /* Knuth's Algorithm 2.3.1S (threaded inorder successor)
+ modified to find the predecessor node. */
+ if (p->tag[0] == MINUS)
+ p = p->link[0];
+ else
+ {
+ assert (p->tag[0] == PLUS);
+ p = p->link[0];
+ while (p->tag[1] == PLUS)
+ p = p->link[1];
+ }
+ }
+
+ if (p == &tree->root)
+ return NULL;
+
+ return (void **) &p->data;
+}
+
+/* Search TREE for an item matching ITEM. If found, returns a pointer
+ to the address of the item. If none is found, ITEM is inserted
+ into the tree, and a pointer to the address of ITEM is returned.
+ In either case, the pointer returned can be changed by the caller,
+ or the returned data item can be directly edited, but the key data
+ in the item must not be changed. */
+void **
+avlt_probe (avlt_tree *tree, void *item)
+{
+ /* Uses Knuth's Algorithm 6.2.3A (balanced tree search and
+ insertion), modified for a threaded binary tree. Caches results
+ of comparisons. In empirical tests this eliminates about 25% of
+ the comparisons seen under random insertions. */
+
+ /* A1. */
+ avlt_node *t;
+ avlt_node *s, *p, *q, *r;
+
+ assert (tree != NULL);
+ t = &tree->root;
+ s = p = t->link[0];
+
+ if (t->tag[0] == MINUS)
+ {
+ tree->count++;
+ assert (tree->count == 1);
+ t->tag[0] = PLUS;
+ q = t->link[0] = xmalloc (sizeof (avlt_node));
+ q->data = item;
+ q->link[0] = q->link[1] = t;
+ q->tag[0] = q->tag[1] = MINUS;
+ q->bal = 0;
+ return &q->data;
+ }
+
+ for (;;)
+ {
+ /* A2. */
+ int diff = tree->cmp (item, p->data, tree->param);
+
+ /* A3. */
+ if (diff < 0)
+ {
+ p->cache = 0;
+ q = p->link[0];
+ if (p->tag[0] == MINUS)
+ {
+ q = xmalloc (sizeof (avlt_node));
+ q->link[0] = p->link[0];
+ q->tag[0] = p->tag[0];
+ p->link[0] = q;
+ p->tag[0] = PLUS;
+ q->link[1] = p;
+ q->tag[1] = MINUS;
+ break;
+ }
+ }
+ /* A4. */
+ else if (diff > 0)
+ {
+ p->cache = 1;
+ q = p->link[1];
+ if (p->tag[1] == MINUS)
+ {
+ q = xmalloc (sizeof (avlt_node));
+ q->link[1] = p->link[1];
+ q->tag[1] = p->tag[1];
+ p->link[1] = q;
+ p->tag[1] = PLUS;
+ q->link[0] = p;
+ q->tag[0] = MINUS;
+ break;
+ }
+ }
+ else
+ /* A2. */
+ return &p->data;
+
+ /* A3, A4. */
+ if (q->bal != 0)
+ t = p, s = q;
+ p = q;
+ }
+
+ /* A5. */
+ tree->count++;
+ q->data = item;
+ q->bal = 0;
+
+ /* A6. */
+ r = p = s->link[(int) s->cache];
+ while (p != q)
+ {
+ p->bal = p->cache * 2 - 1;
+ p = p->link[(int) p->cache];
+ }
+
+ /* A7. */
+ if (s->cache == 0)
+ {
+ /* a = -1. */
+ if (s->bal == 0)
+ {
+ s->bal = -1;
+ return &q->data;
+ }
+ else if (s->bal == +1)
+ {
+ s->bal = 0;
+ return &q->data;
+ }
+
+ assert (s->bal == -1);
+ if (r->bal == -1)
+ {
+ /* A8. */
+ p = r;
+ s->link[0] = r->link[1];
+ s->tag[0] = r->tag[1];
+ r->link[1] = s;
+ r->tag[1] = PLUS;
+ if (s->link[0] == s)
+ {
+ s->link[0] = r;
+ s->tag[0] = MINUS;
+ }
+ r->tag[0] = r->tag[1] = PLUS;
+ s->bal = r->bal = 0;
+ }
+ else
+ {
+ /* A9. */
+ assert (r->bal == +1);
+ p = r->link[1];
+ r->link[1] = p->link[0];
+ p->link[0] = r;
+ s->link[0] = p->link[1];
+ p->link[1] = s;
+ if (p->bal == -1)
+ s->bal = 1, r->bal = 0;
+ else if (p->bal == 0)
+ s->bal = r->bal = 0;
+ else
+ {
+ assert (p->bal == +1);
+ s->bal = 0, r->bal = -1;
+ }
+ p->bal = 0;
+ p->tag[0] = p->tag[1] = PLUS;
+ if (s->link[0] == s)
+ {
+ s->link[0] = p;
+ s->tag[0] = MINUS;
+ }
+ if (r->link[1] == r)
+ {
+ r->link[1] = p;
+ r->tag[1] = MINUS;
+ }
+ }
+ }
+ else
+ {
+ /* a == +1. */
+ if (s->bal == 0)
+ {
+ s->bal = 1;
+ return &q->data;
+ }
+ else if (s->bal == -1)
+ {
+ s->bal = 0;
+ return &q->data;
+ }
+
+ assert (s->bal == +1);
+ if (r->bal == +1)
+ {
+ /* A8. */
+ p = r;
+ s->link[1] = r->link[0];
+ s->tag[1] = r->tag[0];
+ r->link[0] = s;
+ r->tag[0] = PLUS;
+ if (s->link[1] == s)
+ {
+ s->link[1] = r;
+ s->tag[1] = MINUS;
+ }
+ s->bal = r->bal = 0;
+ }
+ else
+ {
+ /* A9. */
+ assert (r->bal == -1);
+ p = r->link[0];
+ r->link[0] = p->link[1];
+ p->link[1] = r;
+ s->link[1] = p->link[0];
+ p->link[0] = s;
+ if (p->bal == +1)
+ s->bal = -1, r->bal = 0;
+ else if (p->bal == 0)
+ s->bal = r->bal = 0;
+ else
+ {
+ assert (p->bal == -1);
+ s->bal = 0, r->bal = 1;
+ }
+ p->tag[0] = p->tag[1] = PLUS;
+ if (s->link[1] == s)
+ {
+ s->link[1] = p;
+ s->tag[1] = MINUS;
+ }
+ if (r->link[0] == r)
+ {
+ r->link[0] = p;
+ r->tag[0] = MINUS;
+ }
+ p->bal = 0;
+ }
+ }
+
+ /* A10. */
+ if (t != &tree->root && s == t->link[1])
+ t->link[1] = p;
+ else
+ t->link[0] = p;
+
+ return &q->data;
+}
+
+/* Search TREE for an item matching ITEM, and return a pointer to it
+ if found. */
+void **
+avlt_find (const avlt_tree *tree, const void *item)
+{
+ const avlt_node *p;
+
+ assert (tree != NULL);
+ if (tree->root.tag[0] == MINUS)
+ /* Tree is empty. */
+ return NULL;
+
+ p = tree->root.link[0];
+ for (;;)
+ {
+ int diff = tree->cmp (item, p->data, tree->param);
+ int t;
+
+ /* A3. */
+ if (diff < 0)
+ t = 0;
+ else if (diff > 0)
+ t = 1;
+ else
+ return (void **) &p->data;
+
+ if (p->tag[t] == PLUS)
+ p = p->link[t];
+ else
+ return NULL;
+ }
+}
+
+/* Search TREE for an item close to the value of ITEM, and return it.
+ This function will return a null pointer only if TREE is empty. */
+void **
+avlt_find_close (const avlt_tree *tree, const void *item)
+{
+ const avlt_node *p;
+
+ assert (tree != NULL);
+ if (tree->root.tag[0] == MINUS)
+ /* Tree is empty. */
+ return NULL;
+
+ p = tree->root.link[0];
+ for (;;)
+ {
+ int diff = tree->cmp (item, p->data, tree->param);
+ int t;
+
+ /* A3. */
+ if (diff < 0)
+ t = 0;
+ else if (diff > 0)
+ t = 1;
+ else
+ return (void **) &p->data;
+
+ if (p->tag[t] == PLUS)
+ p = p->link[t];
+ else
+ return (void **) &p->data;
+ }
+}
+
+/* Searches AVL tree TREE for an item matching ITEM. If found, the
+ item is removed from the tree and the actual item found is returned
+ to the caller. If no item matching ITEM exists in the tree,
+ returns NULL. */
+void *
+avlt_delete (avlt_tree *tree, const void *item)
+{
+ /* Uses my Algorithm DT, which can be found at
+ http://www.msu.edu/user/pfaffben/avl. Algorithm DT is based on
+ Knuth's Algorithms 6.2.2D (Tree deletion), 6.2.3A (Balanced tree
+ search and insertion), 2.3.1I (Insertion into a threaded binary
+ trees), and the notes on pages 465-466 of Vol. 3. */
+
+ /* D1. */
+ avlt_node *pa[AVL_MAX_HEIGHT]; /* Stack P: Nodes. */
+ unsigned char a[AVL_MAX_HEIGHT]; /* Stack P: Bits. */
+ int k = 1; /* Stack P: Pointer. */
+
+ avlt_node *p;
+
+ assert (tree != NULL);
+
+ if (tree->root.tag[0] == MINUS)
+ /* Empty tree. */
+ return NULL;
+
+ a[0] = 0;
+ pa[0] = &tree->root;
+ p = tree->root.link[0];
+ for (;;)
+ {
+ /* D2. */
+ int diff = tree->cmp (item, p->data, tree->param);
+
+ if (diff == 0)
+ break;
+
+ /* D3, D4. */
+ pa[k] = p;
+ if (diff < 0)
+ {
+ if (p->tag[0] == PLUS)
+ {
+ p = p->link[0];
+ a[k] = 0;
+ }
+ else
+ return NULL;
+ }
+ else if (diff > 0)
+ {
+ if (p->tag[1] == PLUS)
+ {
+ p = p->link[1];
+ a[k] = 1;
+ }
+ else
+ return NULL;
+ }
+
+ k++;
+ }
+ tree->count--;
+
+ item = p->data;
+
+ {
+ avlt_node *t = p;
+ avlt_node **q = &pa[k - 1]->link[(int) a[k - 1]];
+
+ /* D5. */
+ if (t->tag[1] == MINUS)
+ {
+ if (t->tag[0] == PLUS)
+ {
+ avlt_node *const x = t->link[0];
+
+ *q = x;
+ (*q)->bal = 0;
+ if (x->tag[1] == MINUS)
+ {
+ if (a[k - 1] == 1)
+ x->link[1] = t->link[1];
+ else
+ x->link[1] = pa[k - 1];
+ }
+ }
+ else
+ {
+ *q = t->link[a[k - 1]];
+ pa[k - 1]->tag[a[k - 1]] = MINUS;
+ }
+ }
+ else
+ {
+ /* D6. */
+ avlt_node *r = t->link[1];
+ if (r->tag[0] == MINUS)
+ {
+ r->link[0] = t->link[0];
+ r->tag[0] = t->tag[0];
+ r->bal = t->bal;
+ if (r->tag[0] == PLUS)
+ {
+ avlt_node *s = r->link[0];
+ while (s->tag[1] == PLUS)
+ s = s->link[1];
+ assert (s->tag[1] == MINUS);
+ s->link[1] = r;
+ }
+ *q = r;
+ a[k] = 1;
+ pa[k++] = r;
+ }
+ else
+ {
+ /* D7. */
+ avlt_node *s = r->link[0];
+
+ a[k] = 1;
+ pa[k++] = t;
+
+ a[k] = 0;
+ pa[k++] = r;
+
+ /* D8. */
+ while (s->tag[0] != MINUS)
+ {
+ r = s;
+ s = r->link[0];
+ a[k] = 0;
+ pa[k++] = r;
+ }
+
+ /* D9. */
+ t->data = s->data;
+ if (s->tag[1] == MINUS)
+ {
+ r->tag[0] = MINUS;
+ r->link[0] = t;
+ }
+ else
+ {
+ r->link[0] = s->link[1];
+ if (s->link[1]->tag[0] == MINUS)
+ s->link[1]->link[0] = t;
+ }
+ p = s;
+ }
+ }
+ }
+
+ free (p);
+
+ assert (k > 0);
+ /* D10. */
+ while (--k)
+ {
+ avlt_node *const s = pa[k];
+
+ if (a[k] == 0)
+ {
+ avlt_node *const r = s->link[1];
+
+ /* D10. */
+ if (s->bal == -1)
+ {
+ s->bal = 0;
+ continue;
+ }
+ else if (s->bal == 0)
+ {
+ s->bal = +1;
+ break;
+ }
+
+ assert (s->bal == +1);
+ if (s->tag[1] == MINUS || r->bal == 0)
+ {
+ /* D11. */
+ s->link[1] = r->link[0];
+ r->link[0] = s;
+ r->bal = -1;
+ pa[k - 1]->link[(int) a[k - 1]] = r;
+ break;
+ }
+ else if (r->bal == +1)
+ {
+ /* D12. */
+ if (PLUS == (s->tag[1] = r->tag[0]))
+ s->link[1] = r->link[0];
+ r->link[0] = s;
+ r->tag[0] = PLUS;
+ s->bal = r->bal = 0;
+ pa[k - 1]->link[a[k - 1]] = r;
+ }
+ else
+ {
+ /* D13. */
+ assert (r->bal == -1);
+ p = r->link[0];
+ if (PLUS == (r->tag[0] = p->tag[1]))
+ r->link[0] = p->link[1];
+ p->link[1] = r;
+ p->tag[1] = PLUS;
+ if (MINUS == (s->tag[1] = p->tag[0]))
+ s->link[1] = p;
+ else
+ s->link[1] = p->link[0];
+ p->link[0] = s;
+ p->tag[0] = PLUS;
+ if (p->bal == +1)
+ s->bal = -1, r->bal = 0;
+ else if (p->bal == 0)
+ s->bal = r->bal = 0;
+ else
+ {
+ assert (p->bal == -1);
+ s->bal = 0, r->bal = +1;
+ }
+ p->bal = 0;
+ pa[k - 1]->link[(int) a[k - 1]] = p;
+ pa[k - 1]->tag[(int) a[k - 1]] = PLUS;
+ }
+ }
+ else
+ {
+ avlt_node *const r = s->link[0];
+
+ /* D10. */
+ if (s->bal == +1)
+ {
+ s->bal = 0;
+ continue;
+ }
+ else if (s->bal == 0)
+ {
+ s->bal = -1;
+ break;
+ }
+
+ assert (s->bal == -1);
+ if (s->tag[0] == MINUS || r->bal == 0)
+ {
+ /* D11. */
+ s->link[0] = r->link[1];
+ r->link[1] = s;
+ r->bal = +1;
+ pa[k - 1]->link[(int) a[k - 1]] = r;
+ break;
+ }
+ else if (r->bal == -1)
+ {
+ /* D12. */
+ if (PLUS == (s->tag[0] = r->tag[1]))
+ s->link[0] = r->link[1];
+ r->link[1] = s;
+ r->tag[1] = PLUS;
+ s->bal = r->bal = 0;
+ pa[k - 1]->link[a[k - 1]] = r;
+ }
+ else
+ {
+ /* D13. */
+ assert (r->bal == +1);
+ p = r->link[1];
+ if (PLUS == (r->tag[1] = p->tag[0]))
+ r->link[1] = p->link[0];
+ p->link[0] = r;
+ p->tag[0] = PLUS;
+ if (MINUS == (s->tag[0] = p->tag[1]))
+ s->link[0] = p;
+ else
+ s->link[0] = p->link[1];
+ p->link[1] = s;
+ p->tag[1] = PLUS;
+ if (p->bal == -1)
+ s->bal = +1, r->bal = 0;
+ else if (p->bal == 0)
+ s->bal = r->bal = 0;
+ else
+ {
+ assert (p->bal == +1);
+ s->bal = 0, r->bal = -1;
+ }
+ p->bal = 0;
+ pa[k - 1]->link[(int) a[k - 1]] = p;
+ pa[k - 1]->tag[(int) a[k - 1]] = PLUS;
+ }
+ }
+ }
+
+ return (void *) item;
+}
+
+/* Inserts ITEM into TREE. Returns NULL if the item was inserted,
+ otherwise a pointer to the duplicate item. */
+void *
+avlt_insert (avlt_tree *tree, void *item)
+{
+ void **p;
+
+ assert (tree != NULL);
+
+ p = avlt_probe (tree, item);
+ return (*p == item) ? NULL : *p;
+}
+
+/* If ITEM does not exist in TREE, inserts it and returns NULL. If a
+ matching item does exist, it is replaced by ITEM and the item
+ replaced is returned. The caller is responsible for freeing the
+ item returned. */
+void *
+avlt_replace (avlt_tree *tree, void *item)
+{
+ void **p;
+
+ assert (tree != NULL);
+
+ p = avlt_probe (tree, item);
+ if (*p == item)
+ return NULL;
+ else
+ {
+ void *r = *p;
+ *p = item;
+ return r;
+ }
+}
+
+/* Delete ITEM from TREE when you know that ITEM must be in TREE. For
+ debugging purposes. */
+void *
+(avlt_force_delete) (avlt_tree *tree, void *item)
+{
+ void *found = avlt_delete (tree, item);
+ assert (found != NULL);
+ return found;
+}
+
+#if SELF_TEST
+
+/* Size of the tree used for testing. */
+#define TREE_SIZE 1024
+
+/* Used to flag delayed aborting. */
+int done = 0;
+
+/* Count the number of nodes in TREE below and including NODE. */
+int
+count (avlt_tree *tree, avlt_node *node)
+{
+ int n = 1;
+ if (node->tag[0] == PLUS)
+ n += count (tree, node->link[0]);
+ if (node->tag[1] == PLUS)
+ n += count (tree, node->link[1]);
+ return n;
+}
+
+/* Print the structure of node NODE of an avl tree, which is LEVEL
+ levels from the top of the tree. Uses different delimiters to
+ visually distinguish levels. */
+void
+print_structure (avlt_tree *tree, avlt_node *node, int level)
+{
+ char lc[] = "([{<`";
+ char rc[] = ")]}>'";
+
+ assert (node != NULL);
+ if (level >= 10)
+ {
+ printf ("Too deep, giving up.\n");
+ done = 1;
+ return;
+ }
+ if (node == &tree->root)
+ {
+ printf (" root");
+ return;
+ }
+ printf (" %c%d", lc[level % 5], (int) node->data);
+ fflush (stdout);
+
+ {
+ int i;
+
+ for (i = 0; i <= 1; i++)
+ {
+ if (node->tag[i] == PLUS)
+ print_structure (tree, node->link[i], level + 1);
+ else if (node->link[i] != &tree->root)
+ printf (" :%d", (int) node->link[i]->data);
+ else
+ printf (" :r");
+ fflush (stdout);
+ }
+ }
+ printf ("%c", rc[level % 5]);
+ fflush (stdout);
+}
+
+/* Compare two integers A and B and return a strcmp()-type result. */
+int
+compare_ints (const void *a, const void *b, void *param unused)
+{
+ return ((int) a) - ((int) b);
+}
+
+/* Print the value of integer A. */
+void
+print_int (void *a, void *param unused)
+{
+ printf (" %d", (int) a);
+}
+
+/* Linearly print contents of TREE. */
+void
+print_contents (avlt_tree *tree)
+{
+ avlt_walk (tree, print_int, NULL);
+ printf ("\n");
+}
+
+/* Examine NODE in a avl tree. *COUNT is increased by the number of
+ nodes in the tree, including the current one. If the node is the
+ root of the tree, PARENT should be INT_MIN, otherwise it should be
+ the parent node value. DIR is the direction that the current node
+ is linked from the parent: -1 for left child, +1 for right child;
+ it is not used if PARENT is INT_MIN. Returns the height of the
+ tree rooted at NODE. */
+int
+recurse_tree (avlt_tree *tree, avlt_node *node, int *count, int parent,
+ int dir, unsigned char *nodes, unsigned char *threads)
+{
+ if (node != &tree->root)
+ {
+ int d = (int) node->data;
+ int nl = 0;
+ int nr = 0;
+
+ (*count)++;
+
+ assert (d >= 0 && d < TREE_SIZE);
+ if (nodes[d / 8] & (1 << (d % 8)))
+ {
+ printf (" Arrived at node %d by two different paths.\n", d);
+ done = 1;
+ }
+ else
+ nodes[d / 8] |= 1 << (d % 8);
+
+ if (node->tag[0] == PLUS)
+ nl = recurse_tree (tree, node->link[0], count, d, -1, nodes, threads);
+ else if (node->link[0] != &tree->root)
+ {
+ int dl = (int) node->link[0]->data;
+ assert (dl >= 0 && dl < TREE_SIZE);
+ threads[dl / 8] |= 1 << (dl % 8);
+ }
+
+ if (node->tag[1] == PLUS)
+ nr = recurse_tree (tree, node->link[1], count, d, 1, nodes, threads);
+ else if (node->link[1] != &tree->root)
+ {
+ int dr = (int) node->link[1]->data;
+ assert (dr >= 0 && dr < TREE_SIZE);
+ threads[dr / 8] |= 1 << (dr % 8);
+ }
+
+ if (nr - nl != node->bal)
+ {
+ printf (" Node %d has incorrect balance: right height=%d, "
+ "left height=%d, difference=%d, but balance factor=%d.\n",
+ d, nr, nl, nr - nl, node->bal);
+ done = 1;
+ }
+
+ if (node->bal < -1 || node->bal > 1)
+ {
+ printf (" Node %d has invalid balance factor %d.\n",
+ d, node->bal);
+ done = 1;
+ }
+
+ if (parent != INT_MIN)
+ {
+ assert (dir == -1 || dir == +1);
+ if (dir == -1 && d > parent)
+ {
+ printf (" Node %d is smaller than its left child %d.\n",
+ parent, d);
+ done = 1;
+ }
+ else if (dir == +1 && d < parent)
+ {
+ printf (" Node %d is larger than its right child %d.\n",
+ parent, d);
+ done = 1;
+ }
+ }
+ assert (node->bal >= -1 && node->bal <= 1);
+ return 1 + (nl > nr ? nl : nr);
+ }
+ else return 0;
+}
+
+/* Check that everything about TREE is kosher. */
+void
+verify_tree (avlt_tree *tree)
+{
+ {
+ unsigned char nodes[(TREE_SIZE + 7) / 8];
+ unsigned char threads[(TREE_SIZE + 7) / 8];
+
+ int count = 0;
+ int i;
+
+ memset (nodes, 0, (TREE_SIZE + 7) / 8);
+ memset (threads, 0, (TREE_SIZE + 7) / 8);
+
+ recurse_tree (tree, tree->root.link[0], &count, INT_MIN, 0, nodes,
+ threads);
+
+ if (count != tree->count)
+ {
+ printf (" Tree should have %d nodes, but tree count by recursive "
+ "descent is %d.\n", tree->count, count);
+ done = 1;
+ }
+
+ for (i = 0; i < TREE_SIZE; i++)
+ {
+ int thread = threads[i / 8] & (1 << (i % 8));
+ int node = nodes[i / 8] & (1 << (i % 8));
+
+ if (thread && !node)
+ {
+ printf (" A thread leads to ``node'' %d, which is "
+ "not in the tree.", i);
+ done = 1;
+ }
+ }
+ }
+
+ /* Check right threads. */
+ {
+ int count = 0;
+ int last = INT_MIN;
+ void **data = NULL;
+
+ while (NULL != (data = avlt_next (tree, data)))
+ {
+ if (((int) *data) < last)
+ {
+ printf (" Misordered right threads.\n");
+ abort ();
+ }
+ else if (((int) *data) == last)
+ {
+ printf (" Loop in right threads detected on %d.\n", last);
+ abort ();
+ }
+ last = (int) *data;
+ count++;
+ }
+ if (count != tree->count)
+ {
+ printf (" Tree should have %d nodes, but tree count by right threads "
+ "is %d.\n", tree->count, count);
+ done = 1;
+ }
+ }
+
+ /* Check left threads. */
+ {
+ int count = 0;
+ int last = INT_MAX;
+ void **data = NULL;
+
+ while (NULL != (data = avlt_prev (tree, data)))
+ {
+ if (((int) *data) > last)
+ {
+ printf (" Misordered left threads.\n");
+ abort ();
+ }
+ else if (((int) *data) == last)
+ {
+ printf (" Loop in left threads detected on %d.\n", last);
+ abort ();
+ }
+ last = (int) *data;
+ count++;
+ }
+ if (count != tree->count)
+ {
+ printf (" Tree should have %d nodes, but tree count by left threads "
+ "is %d.\n", tree->count, count);
+ done = 1;
+ }
+ }
+
+ if (done)
+ abort ();
+}
+
+/* Arrange the N elements of ARRAY in random order. */
+void
+shuffle (int *array, int n)
+{
+ int i;
+
+ for (i = 0; i < n; i++)
+ {
+ int j = i + rand () % (n - i);
+ int t = array[j];
+ array[j] = array[i];
+ array[i] = t;
+ }
+}
+
+/* Compares avl trees rooted at A and B, making sure that they are
+ identical. */
+void
+compare_trees (avlt_node *a, avlt_node *b)
+{
+ int diff = 0;
+
+ assert (a && b);
+
+ /* Separating these conditions makes it easier to pinpoint bad data
+ under a memory debugger like Checker because each test is a
+ separate statement. */
+ diff |= a->data != b->data;
+ diff |= a->bal != b->bal;
+ diff |= ((a->tag[0] == PLUS) ^ (b->tag[0] == PLUS));
+ diff |= ((a->tag[1] == PLUS) ^ (b->tag[1] == PLUS));
+ if (diff)
+ {
+ printf (" Copied nodes differ: %d b=%d a->bal=%d b->bal=%d a:",
+ (int) a->data, (int) b->data, a->bal, b->bal);
+ if (a->link[0])
+ printf ("l");
+ if (a->link[1])
+ printf ("r");
+ printf (" b:");
+ if (b->link[0])
+ printf ("l");
+ if (b->link[1])
+ printf ("r");
+ printf ("\n");
+ abort ();
+ }
+ if (a->tag[0] == PLUS)
+ compare_trees (a->link[0], b->link[0]);
+ if (a->tag[1] == PLUS)
+ compare_trees (a->link[1], b->link[1]);
+}
+
+/* Simple stress test procedure for the AVL tree routines. Does the
+ following:
+
+ * Generate a random number seed. By default this is generated from
+ the current time. You can also pass a seed value on the command
+ line if you want to test the same case. The seed value is
+ displayed.
+
+ * Create a tree and insert the integers from 0 up to TREE_SIZE - 1
+ into it, in random order. Verify the tree structure after each
+ insertion.
+
+ * Remove each integer from the tree, in a different random order.
+ After each deletion, verify the tree structure; also, make a copy
+ of the tree into a new tree, verify the copy and compare it to the
+ original, then destroy the copy.
+
+ * Destroy the tree, increment the random seed value, and start over.
+
+ If you make any modifications to the avl tree routines, then you
+ might want to insert some calls to print_structure() at strategic
+ places in order to be able to see what's really going on. Also,
+ memory debuggers like Checker or Purify are very handy. */
+#define N_ITERATIONS 16
+int
+main (int argc, char **argv)
+{
+ int array[TREE_SIZE];
+ int seed;
+ int iteration;
+
+ if (argc == 2)
+ seed = atoi (argv[1]);
+ else
+ seed = time (0) * 257 % 32768;
+
+ fputs ("Testing avlt...\n", stdout);
+
+ for (iteration = 1; iteration <= N_ITERATIONS; iteration++)
+ {
+ avlt_tree *tree;
+ int i;
+
+ printf ("Iteration %4d/%4d: seed=%5d", iteration, N_ITERATIONS, seed);
+ fflush (stdout);
+
+ srand (seed++);
+
+ for (i = 0; i < TREE_SIZE; i++)
+ array[i] = i;
+ shuffle (array, TREE_SIZE);
+
+ tree = avlt_create (compare_ints, NULL);
+ for (i = 0; i < TREE_SIZE; i++)
+ avlt_force_insert (tree, (void *) (array[i]));
+ verify_tree (tree);
+
+ shuffle (array, TREE_SIZE);
+ for (i = 0; i < TREE_SIZE; i++)
+ {
+ avlt_tree *copy;
+
+ avlt_delete (tree, (void *) (array[i]));
+ verify_tree (tree);
+
+ copy = avlt_copy (tree, NULL);
+ verify_tree (copy);
+ if (tree->root.link[0] != &tree->root)
+ compare_trees (tree->root.link[0], copy->root.link[0]);
+ else if (copy->root.link[1] != &copy->root)
+ printf (" Empty tree results in nonempty copy.\n"), abort ();
+ avlt_destroy (copy, NULL);
+
+ if (i % 128 == 0)
+ {
+ putchar ('.');
+ fflush (stdout);
+ }
+ }
+ fputs (" good.\n", stdout);
+
+ avlt_destroy (tree, NULL);
+ }
+
+ return 0;
+}
+#endif /* SELF_TEST */
+
+/*
+ Local variables:
+ compile-command: "gcc -DSELF_TEST=1 -W -Wall -I. -o ./avlt-test avlt.c"
+ End:
+*/
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-01 17:59:56 +0000