diff -Nru logtop-0.1/CHANGELOG logtop-0.3/CHANGELOG --- logtop-0.1/CHANGELOG 2011-01-16 19:31:46.000000000 +0000 +++ logtop-0.3/CHANGELOG 2011-06-11 11:25:40.000000000 +0000 @@ -1,3 +1,155 @@ +commit 8049a047c00ecce2d0883364d01f7900d46dadbe +Author: Julien +Date: Tue May 31 18:43:43 2011 +0200 + + Adding a missing build dependency in the README file (uthash-dev) + +commit ed1e9befb8414d1c5fb4db77368b4bec85c3eaa9 +Author: Julien +Date: Tue May 31 18:31:07 2011 +0200 + + Addin an 'About libavl' in the README file + +commit 9173816f68403eed3e736c5f7629fcfb39da08f1 +Author: Julien +Date: Tue May 31 18:24:29 2011 +0200 + + Updating README to reflect the actual implementation, and fixing a typo + +commit 14ec7f22988ebbd17a8a067dad1d97725bdeb753 +Author: Julien +Date: Tue May 3 23:47:50 2011 +0200 + + Replacing strings storage, from an AVL tree to an hashtable, + little gain in performance (~20%) + But keeping an AVL tree for the rank (as it needs to be sorted) + +commit 88c217e50fa8593afa57fa92c6501926735dc53a +Author: Julien +Date: Sat Apr 16 12:30:42 2011 +0200 + + FIX: If a line does not end with \n (the last?) it was reported as an empty + string. + NEW: Compatibility with lines ending with CR+LF, LF+CR, LF, or CR + (and any other combinations !) + +commit 0a613e0b38ae2444ba16db7ad9e304138c245d01 +Author: Julien +Date: Sat Apr 16 12:17:22 2011 +0200 + + Some corretion to the manpage + +commit fd4f01ce719327bf6a408e3303fb4abf2956623d +Merge: 7dd641b e1297af +Author: Julien +Date: Sat Apr 16 12:07:46 2011 +0200 + + Merge branch 'master' of github.com:JulienPalard/logtop + +commit 7dd641b0f8c55a4d6066b7cbf86ba058fae1cc23 +Author: Julien +Date: Sat Apr 16 12:06:25 2011 +0200 + + Rewriting the README to remove livavl dependencies + +commit e1297afe02efbf283b7097a2b9be18e95ae0c211 +Author: Julien Palard +Date: Wed Mar 16 22:47:48 2011 +0100 + + FIX: Forgotten .o in libavl folder while make clean + +commit 48ba928d91c57f08469540d7a9c11784eb8d8f6d +Author: Julien Palard +Date: Wed Mar 16 08:51:45 2011 +0100 + + Fixed a bug that makes some entry to appear more than once in the result. + +commit b80e8ac8a51e3fed021b63e7e8061d2a0650752c +Author: Julien Palard +Date: Tue Mar 15 23:07:01 2011 +0100 + + Fixing display bug + +commit a36398cc512cd4e83be330ddab98bdc36062f1ab +Author: Julien Palard +Date: Tue Mar 15 23:06:24 2011 +0100 + + Removing a useless strlen + +commit bb88531f819a3d32cfe8ff09228f2e3bf023f1be +Author: Julien Palard +Date: Tue Mar 15 23:01:58 2011 +0100 + + traverse_log_lines can yield NULL, so we have to check it + +commit d578251e91d8ef0cc863f7c9add9f36b9d7eddd2 +Author: Julien Palard +Date: Tue Mar 15 22:51:07 2011 +0100 + + Simple refactoring of writers + +commit 99130d175dadbd46d7759c0a8e899a44e0ec9f37 +Author: Julien Palard +Date: Tue Mar 15 20:41:29 2011 +0100 + + Removing one line in the stdout output module to keep the first line of + result, previously dropped due to the appearing shell line of the user + +commit b4e7ce5133d5537f38ce1824a33475c1a7a2476a +Author: Julien Palard +Date: Tue Mar 15 20:39:29 2011 +0100 + + Removing the unused UNUSED define and protecting STRINGIFY + +commit 1e19ee9d10ec2c621de087c257e1f93513fa4344 +Author: Julien Palard +Date: Tue Mar 15 20:35:26 2011 +0100 + + Dropping dependency to Debian's libavl in favor of the pfaff's one, + statically build + +commit a68ce57035b92f02086c62e7b7f5d4b008f2f2a9 +Author: Julien +Date: Sun Jan 16 20:32:26 2011 +0100 + + Adding Debian changelog + +commit 3baa3447757da760a10eb417f58a6c92ed239c65 +Author: mandark +Date: Tue Dec 28 10:15:17 2010 +0100 + + Refactorig for readeability + +commit b597c950277555d15191ace04b9c1ba252f35c8f +Author: mandark +Date: Tue Dec 28 09:46:32 2010 +0100 + + Moving history structure to history.h + +commit 1a7dca7680a8bc52b0e4d2a8ecea4f85b995bd29 +Author: mandark +Date: Tue Dec 28 09:42:26 2010 +0100 + + Updating licences + +commit 05fb3773ced37f5e3328d5ecae752e01f5c0fd69 +Author: mandark +Date: Tue Dec 28 09:20:37 2010 +0100 + + Refactoring for readeability + +commit 4d4e20ddd51a301b809fb70c9e27d5a9767461d7 +Author: mandark +Date: Tue Dec 28 08:51:29 2010 +0100 + + Splitting history managment in history.c + +commit afbee48ee250e83bdbcebae0ff929c0e02d56938 +Author: Julien +Date: Mon Dec 27 08:41:17 2010 +0100 + + Fixing manpage + commit 7d02ea927e14beeb32322edfb939c6a616c03013 Author: mandark Date: Sun Dec 12 20:57:50 2010 +0100 @@ -64,7 +216,7 @@ Date: Sat Nov 13 21:45:03 2010 +0100 Improving a bit the UI adding the number of log lines read by second ... - + On my box, a $ strings /dev/urandom | ./logtop -s 100000 gaves me : diff -Nru logtop-0.1/debian/changelog logtop-0.3/debian/changelog --- logtop-0.1/debian/changelog 2010-12-27 07:33:21.000000000 +0000 +++ logtop-0.3/debian/changelog 2011-06-11 10:57:37.000000000 +0000 @@ -1,3 +1,12 @@ +logtop (0.3-1) unstable; urgency=low + + * New upstream release + * Replacing the AVL tree used to store strings by an hashtable. + * Replacing the Wessel Dankers' libavl dependency with the statically compiled + Ben Pfaff's one (see README.Debian). + + -- Julien Palard Tue, 31 May 2011 18:45:09 +0200 + logtop (0.1-1) unstable; urgency=low * Initial release. Closes: #605904 diff -Nru logtop-0.1/debian/control logtop-0.3/debian/control --- logtop-0.1/debian/control 2010-12-27 07:33:21.000000000 +0000 +++ logtop-0.3/debian/control 2011-06-11 11:11:35.000000000 +0000 @@ -2,8 +2,8 @@ Section: admin Priority: optional Maintainer: Julien Palard -Build-Depends: debhelper (>= 7), libavl-dev, libncurses5-dev -Standards-Version: 3.9.1 +Build-Depends: debhelper (>= 7), libncurses5-dev, uthash-dev +Standards-Version: 3.9.2 Homepage: http://github.com/JulienPalard/logtop Package: logtop diff -Nru logtop-0.1/debian/copyright logtop-0.3/debian/copyright --- logtop-0.1/debian/copyright 2010-12-27 07:33:21.000000000 +0000 +++ logtop-0.3/debian/copyright 2011-06-11 11:09:04.000000000 +0000 @@ -1,17 +1,11 @@ -Format-Specification: http://svn.debian.org/wsvn/dep/web/deps/dep5.mdwn?op=file&rev=135 -Name: logtop -Maintainer: Julien Palard +Format: http://svn.debian.org/wsvn/dep/web/deps/dep5.mdwn?op=file&rev=174 +Upstream-Name: logtop +Upstream-Contact: Julien Palard Source: http://github.com/JulienPalard/logtop -Files: * +Files: * src/* doc/* Copyright: 2010 Julien Palard. All rights reserved. License: FreeBSD License - -Files: debian/* -Copyright: 2010 Julien Palard. All rights reserved. -License: FreeBSD License - -License: FreeBSD License Copyright 2010 Julien Palard. All rights reserved. . Redistribution and use in source and binary forms, with or without modification, are @@ -37,3 +31,25 @@ The views and conclusions contained in the software and documentation are those of the authors and should not be interpreted as representing official policies, either expressed or implied, of Julien Palard. + +Files: src/libavl/* +Copyright: Copyright (C) 1998-2002, 2004 Free Software Foundation, Inc. +License: GPL-2+ + 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., 51 Franklin St, Fifth Floor, Boston, + MA 02110-1301 USA + . + On Debian systems, the full text of the GNU General Public + License version 1 can be found in the file + `/usr/share/common-licenses/GPL-2'. diff -Nru logtop-0.1/debian/README.Debian logtop-0.3/debian/README.Debian --- logtop-0.1/debian/README.Debian 1970-01-01 00:00:00.000000000 +0000 +++ logtop-0.3/debian/README.Debian 2011-04-23 17:59:54.000000000 +0000 @@ -0,0 +1,24 @@ +Choosing the avl implementation : + +In version 0.1, logtop was built against Wessel Dankers' libavl, the one +packaged for Debian under the name `libavl`. +On version 0.2, logtop is built against Ben Pfaff's one, which is statically +linked, as Ben Pfaff whiches. You can read about it here : + * http://lists.debian.org/debian-devel/2001/07/msg01303.html +and in its INSTALL file that I quote for you here : + +8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< 8< + Installing + ---------- + + libavl is not intended to be installed as a shared library. Instead, + its source files are meant to be included in programs directly. A + given program normally uses only one or two of libavl's tree + structures. Only the C source and header files for those structures + need to be included. Refer to the libavl manual for more information. + + As a result, there is no real "installation procedure" for libavl. If + you like, you can install the test and demo programs in a convenient + location, but it hard to imagine a practical use for them other than + as tests and demonstrations. +>8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 >8 diff -Nru logtop-0.1/doc/logtop.1 logtop-0.3/doc/logtop.1 --- logtop-0.1/doc/logtop.1 2011-01-16 20:00:14.000000000 +0000 +++ logtop-0.3/doc/logtop.1 2011-04-16 10:16:30.000000000 +0000 @@ -2,17 +2,18 @@ .\" First parameter, NAME, should be all caps .\" Second parameter, SECTION, should be 1-8, maybe w/ subsection .\" other parameters are allowed: see man(7), man(1) -.TH LOGTOP 1 "December 27, 2010" +.TH LOGTOP 1 "April 16, 2011" .\" Please adjust this date whenever revising the manpage. .SH "NAME" logtop \- Realtime log line rate analyser .SH "SYNOPSIS" .B logtop -[\fIOPTION\fR]... [\fIFILE\fR]... +.RI [ OPTIONS ] +.RI [ FILE ] .SH "DESCRIPTION" \fBlogtop\fP is a System Administrator tool to analyze line rate taking log file as input. It reads on stdin and print a constantly updated result - using curses, displaying in columns: + displaying, in columns: Line number, count, frequency, and the actual line. $ tail \-f FILE | \fBlogtop\fP diff -Nru logtop-0.1/Makefile logtop-0.3/Makefile --- logtop-0.1/Makefile 2010-12-05 19:03:03.000000000 +0000 +++ logtop-0.3/Makefile 2011-04-16 10:07:46.000000000 +0000 @@ -7,13 +7,14 @@ NAME = logtop DSRC = src -SRC = $(DSRC)/logtop.c $(DSRC)/avl.c $(DSRC)/curses.c $(DSRC)/stdout.c +SRC = $(DSRC)/logtop.c $(DSRC)/avl.c $(DSRC)/history.c $(DSRC)/curses.c \ + $(DSRC)/stdout.c $(DSRC)/libavl/avl.c OBJ = $(SRC:.c=.o) CC = gcc INCLUDE = . DEFINE = _GNU_SOURCE -LIB = -lavl -lncurses #-lefence -CFLAGS = -fPIC -g3 -O3 -W -Wall -ansi -pedantic -I$(INCLUDE) +LIB = -lncurses #-lefence +CFLAGS = -O3 -W -Wall -ansi -pedantic -I$(INCLUDE) RM = rm -f $(NAME): $(OBJ) @@ -30,6 +31,7 @@ $(CC) -D $(DEFINE) -c $(CFLAGS) $< -o $(<:.c=.o) clean: - $(RM) $(NAME) $(DSRC)/*~ $(DSRC)/#*# $(DSRC)/*.o $(DSRC)/*.core + $(RM) $(NAME) $(DSRC)/*~ $(DSRC)/#*# $(DSRC)/*.o $(DSRC)/*.core \ + $(DSRC)/libavl/*.o re: clean all diff -Nru logtop-0.1/README logtop-0.3/README --- logtop-0.1/README 2010-12-14 19:47:38.000000000 +0000 +++ logtop-0.3/README 2011-05-31 16:43:21.000000000 +0000 @@ -5,15 +5,13 @@ See http://julien.palard.fr or ask me questions at : julien at palard in fr -This project is tested on 32 and 64 bits platforms. - Compile : You will need : - $ aptitude install libavl-dev libncurses5-dev + $ aptitude install libncurses5-dev uthash-dev Run : - Wou will need : - $ aptitude install libavl1 libncurses5 + You will need : + $ aptitude install libncurses5 Usage : logtop displays real-time count of strings recieved in standard input. @@ -35,15 +33,20 @@ ) Compile (Dependencies) : - Package: libavl-dev - Version: 0.3.5-3 Package: libncurses5-dev Version: 5.7+20100313-1 Development : - I use AVL trees to store strings and counts, so i can fetch by string AND - fetch ordered to display the top-strings. A simple ordered list can do the - trick for the counts. + I use a hashtable to store strings and an AVL tree to store frequencies, + so I can fetch by string or fetch ordered by frequency to display the + top-strings. + +About libavl: + The libavl used here is the Ben Pfaff's one, statically build with logtop, as + Ben want it to be (see INSTALL file and here : + http://lists.debian.org/debian-devel/2001/07/msg01303.html) + So this libavl is NOT packaged as a library for Debian, the libavl you'll + found in Debian repositories is the Wessel Dankers's one. TODO : Better integration with curses (resize...) diff -Nru logtop-0.1/src/avl.c logtop-0.3/src/avl.c --- logtop-0.1/src/avl.c 2010-12-05 19:09:25.000000000 +0000 +++ logtop-0.3/src/avl.c 2011-05-03 21:46:13.000000000 +0000 @@ -26,95 +26,128 @@ #include #include #include - #include "logtop.h" -static int compare_string(const void *element1, const void *element2) -{ - return (strcmp(((log_line*)element1)->string, - ((log_line*)element2)->string)); -} - -static int compare_count(const void *element1, const void *element2) +static int compare_log_lines_count(const void *log_line1, + const void *log_line2, + void *avl_param) { - if (((log_line*)element1)->count == ((log_line*)element2)->count) - return (long)element1 - (long)element2; - return (((log_line*)element2)->count - ((log_line*)element1)->count); -} - -static void freeitem(void *element) -{ - free(((log_line*)element)->string); - free(((log_line*)element)->repr); - free(element); -} - -void init_data_structures() -{ - gl_env.history = (history_element_t*)calloc(sizeof(history_element_t), - gl_env.history_size); - gl_env.history_start = 0; - gl_env.last_update_time = time(NULL); - gl_env.strings = avl_alloc_tree(compare_string, freeitem); - gl_env.top = avl_alloc_tree(compare_count, NULL); - if (gl_env.strings == NULL || gl_env.top == NULL) + (void) avl_param; + if (((log_line_t*)log_line1)->count != ((log_line_t*)log_line2)->count) { - fputs("Not enough memory to create storage", stderr); - exit(EXIT_FAILURE); + if (((log_line_t*)log_line2)->count > ((log_line_t*)log_line1)->count) + return 1; + else + return -1; } + return (strcmp(((log_line_t*)log_line1)->string, + ((log_line_t*)log_line2)->string)); + } -void die() +static void die() { fputs("Ran out of memory, commit suicide for important tasks to live !", stderr); exit(EXIT_FAILURE); } -log_line *create_log_entry(char *string) +static char *repr(const char *str) +{ + char *clean; + int i; + + clean = strdup(str); + if (clean == NULL) + return NULL; + for (i = 0; clean[i] != '\0'; ++i) + if (clean[i] < ' ' || clean[i] > '~') + clean[i] = '.'; + return clean; +} + +static log_line_t *create_log_entry(char *string) { - log_line *entry; - int i; + log_line_t *entry; - entry = (log_line*)malloc(sizeof(log_line)); + entry = (log_line_t*)malloc(sizeof(*entry)); if (entry == NULL) die(); entry->count = 0; entry->string = strdup(string); if (entry->string == NULL) die(); - string[strlen(string) - 1] = '\0'; - for (i = 0; string[i]; ++i) - if (string[i] < ' ' || string[i] > '~') - string[i] = '.'; - entry->repr = strdup(string); + entry->repr = repr(string); if (entry->repr == NULL) die(); - entry->string_node = avl_insert(gl_env.strings, entry); - entry->top_node = avl_insert(gl_env.top, entry); + HASH_ADD_KEYPTR(hh, gl_env.strings, entry->string, strlen(entry->string), + entry); + avl_insert(gl_env.top, entry); return entry; } -log_line *get_log_entry(char *string) +static void delete_log_entry(log_line_t *log_entry) { - avl_node_t *node; - log_line search; + HASH_DEL(gl_env.strings, log_entry); + free(log_entry->string); + free(log_entry->repr); + free(log_entry); +} - search.string = string; - node = avl_search(gl_env.strings, &search); +void init_avl() +{ + gl_env.history_start = 0; + gl_env.last_update_time = time(NULL); + gl_env.strings = NULL; + gl_env.top = avl_create(compare_log_lines_count, NULL, NULL); + if (gl_env.top == NULL) + { + fputs("Not enough memory to create storage", stderr); + exit(EXIT_FAILURE); + } +} + +log_line_t *get_log_entry(char *string) +{ + log_line_t *node; + + HASH_FIND_STR(gl_env.strings, string, node); if (node != NULL) - return (log_line*)node->item; + return node; else return create_log_entry(string); } -/* -** The entry count have changed : -** The only solution to update the tree, is to unlink and reinsert -** the entry in the tree. -*/ -void update_log_entry(log_line *log_entry) +void increment_log_entry_count(log_line_t *log_entry) { - avl_unlink_node(gl_env.top, log_entry->top_node); - avl_insert_node(gl_env.top, log_entry->top_node); + avl_delete(gl_env.top, log_entry); + log_entry->count += 1; + avl_insert(gl_env.top, log_entry); +} + +void decrement_log_entry_count(log_line_t *log_entry) +{ + avl_delete(gl_env.top, log_entry); + log_entry->count -= 1; + if (log_entry->count != 0) + avl_insert(gl_env.top, log_entry); + else + delete_log_entry(log_entry); +} + +void traverse_log_lines(struct avl_table *tree, unsigned int length, + void (*visitor)(void *data, int index, void *user_data), + void *user_data) +{ + struct avl_traverser trav; + void *node; + unsigned int last; + + last = length; + node = avl_t_first(&trav, tree); + while (length-- > 0 && node != NULL) + { + visitor(node, last - length, user_data); + node = avl_t_next(&trav); + } } diff -Nru logtop-0.1/src/avl.h logtop-0.3/src/avl.h --- logtop-0.1/src/avl.h 1970-01-01 00:00:00.000000000 +0000 +++ logtop-0.3/src/avl.h 2011-05-03 21:46:13.000000000 +0000 @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2010 Julien Palard. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __AVL_H__ +#define __AVL_H__ + +#include "libavl/avl.h" +#include + +typedef struct s_log_line +{ + char *string; + char *repr; + unsigned int count; + UT_hash_handle hh; +} log_line_t; + +void init_avl(); +log_line_t *get_log_entry(char *); +void increment_log_entry_count(log_line_t *); +void decrement_log_entry_count(log_line_t *); +void traverse_log_lines(struct avl_table *tree, unsigned int length, + void (*visitor)(void *data, int index, void *user_data), + void *user_data); + +#endif diff -Nru logtop-0.1/src/curses.c logtop-0.3/src/curses.c --- logtop-0.1/src/curses.c 2010-12-11 23:17:47.000000000 +0000 +++ logtop-0.3/src/curses.c 2011-04-16 10:07:47.000000000 +0000 @@ -27,6 +27,7 @@ #include #include #include "logtop.h" +#include "history.h" void curses_setup() { @@ -45,62 +46,71 @@ endwin(); } -void curses_update() +struct line_metadata { - avl_node_t *node; - unsigned int i; - time_t current_time; - double duration; - log_line *log_entry; - history_element_t *oldest_element; - history_element_t *newest_element; - unsigned int qte_of_elements; + double duration; +}; - duration = 0; +static void display_line_with_freq(void *data, int index, void *metadata) +{ + log_line_t *line; + double duration; + + line = (log_line_t *)data; + duration = ((struct line_metadata *)metadata)->duration; + mvprintw(index, 0, "%4d %4d %4.2f/s %s", + index, + line->count, + line->count / duration, + line->repr); +} + +static void display_line_without_freq(void *data, int index, void *metadata) +{ + log_line_t *line; + + (void) metadata; + line = (log_line_t *)data; + mvprintw(index, 0, "%4d %4d %s", + index, + line->count, + line->repr); +} + +void curses_update() +{ + struct line_metadata line_data; + time_t current_time; + history_element_t *oldest_element; + history_element_t *newest_element; + unsigned int qte_of_elements; + + line_data.duration = 0; oldest_element = oldest_element_in_history(); newest_element = newest_element_in_history(); if (oldest_element != NULL && newest_element != NULL) - duration = difftime(newest_element->time, oldest_element->time); - i = 0; + line_data.duration = difftime(newest_element->time, + oldest_element->time); current_time = time(NULL); if (current_time == gl_env.last_update_time) - { return; - } gl_env.last_update_time = current_time; - i = 0; qte_of_elements = qte_of_elements_in_history(); clear(); - if (duration > 0) - mvprintw(i++, 0, "%d elements in %d seconds (%.2f elements/s)\n", + if (line_data.duration > 0) + mvprintw(0, 0, "%d elements in %d seconds (%.2f elements/s)\n", qte_of_elements, - (unsigned int)duration, - qte_of_elements / (double)duration); + (unsigned int)line_data.duration, + qte_of_elements / (double)line_data.duration); else - mvprintw(i++, 0, "%d elements in %d seconds\n", + mvprintw(0, 0, "%d elements in %d seconds\n", qte_of_elements, - (unsigned int)duration); - for (node = gl_env.top->head; - node != NULL && i < gl_env.display_height; - node = node->next) - { - log_entry = (log_line*)node->item; - if (duration > 0) - { - mvprintw(i, 0, "%4d %4d %4.2f/s %s", - i, - log_entry->count, - log_entry->count / (double)duration, - log_entry->repr); - } - else - { - mvprintw(i, 0, "%4d %4d %s", - i, - log_entry->count, - log_entry->repr); - } - i += 1; - } + (unsigned int)line_data.duration); + if (line_data.duration > 0) + traverse_log_lines(gl_env.top, gl_env.display_height, + display_line_with_freq, &line_data); + else + traverse_log_lines(gl_env.top, gl_env.display_height, + display_line_without_freq, &line_data); refresh(); } diff -Nru logtop-0.1/src/history.c logtop-0.3/src/history.c --- logtop-0.1/src/history.c 1970-01-01 00:00:00.000000000 +0000 +++ logtop-0.3/src/history.c 2011-04-16 10:07:47.000000000 +0000 @@ -0,0 +1,88 @@ +/* + * Copyright (c) 2010 Julien Palard. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include "logtop.h" + +/* +** If the element under history_start is null +** then the history is not full. +*/ +unsigned int qte_of_elements_in_history() +{ + if (gl_env.history[gl_env.history_start].log_entry == NULL) + return gl_env.history_start; + else + return gl_env.history_size; +} + +history_element_t *oldest_element_in_history() +{ + if (gl_env.history[gl_env.history_start].log_entry != NULL) + { + return &(gl_env.history[gl_env.history_start]); + } + else + { + if (gl_env.history_start == 0) + return NULL; + return &(gl_env.history[0]); + } +} + +history_element_t *newest_element_in_history() +{ + int newest_item_index; + + newest_item_index = gl_env.history_start == 0 + ? gl_env.history_size - 1 + : gl_env.history_start - 1; + if (gl_env.history[newest_item_index].log_entry == NULL) + return NULL; + else + return &(gl_env.history[newest_item_index]); +} + +void update_history(log_line_t *element) +{ + history_element_t *history_element; + log_line_t *log_entry; + + history_element = &(gl_env.history[gl_env.history_start]); + log_entry = history_element->log_entry; + if (log_entry != NULL) + decrement_log_entry_count(log_entry); + gl_env.history[gl_env.history_start].log_entry = element; + gl_env.history[gl_env.history_start].time = time(NULL); + gl_env.history_start += 1; + if (gl_env.history_start >= gl_env.history_size) + gl_env.history_start = 0; +} + +void init_history() +{ + gl_env.history = (history_element_t*)calloc(sizeof(history_element_t), + gl_env.history_size); +} diff -Nru logtop-0.1/src/history.h logtop-0.3/src/history.h --- logtop-0.1/src/history.h 1970-01-01 00:00:00.000000000 +0000 +++ logtop-0.3/src/history.h 2011-04-16 10:07:47.000000000 +0000 @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2010 Julien Palard. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef __HISTORY__ +#define __HISTORY__ + +#include "avl.h" + +typedef struct s_history_element +{ + log_line_t *log_entry; + time_t time; +} history_element_t; + +void init_history(); +history_element_t *oldest_element_in_history(); +history_element_t *newest_element_in_history(); +unsigned int qte_of_elements_in_history(); +void update_history(log_line_t *element); + +#endif diff -Nru logtop-0.1/src/libavl/avl.c logtop-0.3/src/libavl/avl.c --- logtop-0.1/src/libavl/avl.c 1970-01-01 00:00:00.000000000 +0000 +++ logtop-0.3/src/libavl/avl.c 2011-04-16 10:07:47.000000000 +0000 @@ -0,0 +1,893 @@ +/* Produced by texiweb from libavl.w. */ + +/* libavl - library for manipulation of binary trees. + Copyright (C) 1998-2002, 2004 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 on the Internet, or + write to Ben Pfaff, Stanford University, Computer Science Dept., 353 + Serra Mall, Stanford CA 94305, USA. +*/ + +#include +#include +#include +#include +#include "avl.h" + +/* Creates and returns a new table + with comparison function |compare| using parameter |param| + and memory allocator |allocator|. + Returns |NULL| if memory allocation failed. */ +struct avl_table * +avl_create (avl_comparison_func *compare, void *param, + struct libavl_allocator *allocator) +{ + struct avl_table *tree; + + assert (compare != NULL); + + if (allocator == NULL) + allocator = &avl_allocator_default; + + tree = allocator->libavl_malloc (allocator, sizeof *tree); + if (tree == NULL) + return NULL; + + tree->avl_root = NULL; + tree->avl_compare = compare; + tree->avl_param = param; + tree->avl_alloc = allocator; + tree->avl_count = 0; + tree->avl_generation = 0; + + return tree; +} + +/* Search |tree| for an item matching |item|, and return it if found. + Otherwise return |NULL|. */ +void * +avl_find (const struct avl_table *tree, const void *item) +{ + const struct avl_node *p; + + assert (tree != NULL && item != NULL); + for (p = tree->avl_root; p != NULL; ) + { + int cmp = tree->avl_compare (item, p->avl_data, tree->avl_param); + + if (cmp < 0) + p = p->avl_link[0]; + else if (cmp > 0) + p = p->avl_link[1]; + else /* |cmp == 0| */ + return p->avl_data; + } + + return NULL; +} + +/* Inserts |item| into |tree| and returns a pointer to |item|'s address. + If a duplicate item is found in the tree, + returns a pointer to the duplicate without inserting |item|. + Returns |NULL| in case of memory allocation failure. */ +void ** +avl_probe (struct avl_table *tree, void *item) +{ + struct avl_node *y, *z; /* Top node to update balance factor, and parent. */ + struct avl_node *p, *q; /* Iterator, and parent. */ + struct avl_node *n; /* Newly inserted node. */ + struct avl_node *w; /* New root of rebalanced subtree. */ + int dir; /* Direction to descend. */ + + unsigned char da[AVL_MAX_HEIGHT]; /* Cached comparison results. */ + int k = 0; /* Number of cached results. */ + + assert (tree != NULL && item != NULL); + + z = (struct avl_node *) &tree->avl_root; + y = tree->avl_root; + dir = 0; + for (q = z, p = y; p != NULL; q = p, p = p->avl_link[dir]) + { + int cmp = tree->avl_compare (item, p->avl_data, tree->avl_param); + if (cmp == 0) + return &p->avl_data; + + if (p->avl_balance != 0) + z = q, y = p, k = 0; + da[k++] = dir = cmp > 0; + } + + n = q->avl_link[dir] = + tree->avl_alloc->libavl_malloc (tree->avl_alloc, sizeof *n); + if (n == NULL) + return NULL; + + tree->avl_count++; + n->avl_data = item; + n->avl_link[0] = n->avl_link[1] = NULL; + n->avl_balance = 0; + if (y == NULL) + return &n->avl_data; + + for (p = y, k = 0; p != n; p = p->avl_link[da[k]], k++) + if (da[k] == 0) + p->avl_balance--; + else + p->avl_balance++; + + if (y->avl_balance == -2) + { + struct avl_node *x = y->avl_link[0]; + if (x->avl_balance == -1) + { + w = x; + y->avl_link[0] = x->avl_link[1]; + x->avl_link[1] = y; + x->avl_balance = y->avl_balance = 0; + } + else + { + assert (x->avl_balance == +1); + w = x->avl_link[1]; + x->avl_link[1] = w->avl_link[0]; + w->avl_link[0] = x; + y->avl_link[0] = w->avl_link[1]; + w->avl_link[1] = y; + if (w->avl_balance == -1) + x->avl_balance = 0, y->avl_balance = +1; + else if (w->avl_balance == 0) + x->avl_balance = y->avl_balance = 0; + else /* |w->avl_balance == +1| */ + x->avl_balance = -1, y->avl_balance = 0; + w->avl_balance = 0; + } + } + else if (y->avl_balance == +2) + { + struct avl_node *x = y->avl_link[1]; + if (x->avl_balance == +1) + { + w = x; + y->avl_link[1] = x->avl_link[0]; + x->avl_link[0] = y; + x->avl_balance = y->avl_balance = 0; + } + else + { + assert (x->avl_balance == -1); + w = x->avl_link[0]; + x->avl_link[0] = w->avl_link[1]; + w->avl_link[1] = x; + y->avl_link[1] = w->avl_link[0]; + w->avl_link[0] = y; + if (w->avl_balance == +1) + x->avl_balance = 0, y->avl_balance = -1; + else if (w->avl_balance == 0) + x->avl_balance = y->avl_balance = 0; + else /* |w->avl_balance == -1| */ + x->avl_balance = +1, y->avl_balance = 0; + w->avl_balance = 0; + } + } + else + return &n->avl_data; + z->avl_link[y != z->avl_link[0]] = w; + + tree->avl_generation++; + return &n->avl_data; +} + +/* Inserts |item| into |table|. + Returns |NULL| if |item| was successfully inserted + or if a memory allocation error occurred. + Otherwise, returns the duplicate item. */ +void * +avl_insert (struct avl_table *table, void *item) +{ + void **p = avl_probe (table, item); + return p == NULL || *p == item ? NULL : *p; +} + +/* Inserts |item| into |table|, replacing any duplicate item. + Returns |NULL| if |item| was inserted without replacing a duplicate, + or if a memory allocation error occurred. + Otherwise, returns the item that was replaced. */ +void * +avl_replace (struct avl_table *table, void *item) +{ + void **p = avl_probe (table, item); + if (p == NULL || *p == item) + return NULL; + else + { + void *r = *p; + *p = item; + return r; + } +} + +/* Deletes from |tree| and returns an item matching |item|. + Returns a null pointer if no matching item found. */ +void * +avl_delete (struct avl_table *tree, const void *item) +{ + /* Stack of nodes. */ + struct avl_node *pa[AVL_MAX_HEIGHT]; /* Nodes. */ + unsigned char da[AVL_MAX_HEIGHT]; /* |avl_link[]| indexes. */ + int k; /* Stack pointer. */ + + struct avl_node *p; /* Traverses tree to find node to delete. */ + int cmp; /* Result of comparison between |item| and |p|. */ + + assert (tree != NULL && item != NULL); + + k = 0; + p = (struct avl_node *) &tree->avl_root; + for (cmp = -1; cmp != 0; + cmp = tree->avl_compare (item, p->avl_data, tree->avl_param)) + { + int dir = cmp > 0; + + pa[k] = p; + da[k++] = dir; + + p = p->avl_link[dir]; + if (p == NULL) + return NULL; + } + item = p->avl_data; + + if (p->avl_link[1] == NULL) + pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0]; + else + { + struct avl_node *r = p->avl_link[1]; + if (r->avl_link[0] == NULL) + { + r->avl_link[0] = p->avl_link[0]; + r->avl_balance = p->avl_balance; + pa[k - 1]->avl_link[da[k - 1]] = r; + da[k] = 1; + pa[k++] = r; + } + else + { + struct avl_node *s; + int j = k++; + + for (;;) + { + da[k] = 0; + pa[k++] = r; + s = r->avl_link[0]; + if (s->avl_link[0] == NULL) + break; + + r = s; + } + + s->avl_link[0] = p->avl_link[0]; + r->avl_link[0] = s->avl_link[1]; + s->avl_link[1] = p->avl_link[1]; + s->avl_balance = p->avl_balance; + + pa[j - 1]->avl_link[da[j - 1]] = s; + da[j] = 1; + pa[j] = s; + } + } + + tree->avl_alloc->libavl_free (tree->avl_alloc, p); + + assert (k > 0); + while (--k > 0) + { + struct avl_node *y = pa[k]; + + if (da[k] == 0) + { + y->avl_balance++; + if (y->avl_balance == +1) + break; + else if (y->avl_balance == +2) + { + struct avl_node *x = y->avl_link[1]; + if (x->avl_balance == -1) + { + struct avl_node *w; + assert (x->avl_balance == -1); + w = x->avl_link[0]; + x->avl_link[0] = w->avl_link[1]; + w->avl_link[1] = x; + y->avl_link[1] = w->avl_link[0]; + w->avl_link[0] = y; + if (w->avl_balance == +1) + x->avl_balance = 0, y->avl_balance = -1; + else if (w->avl_balance == 0) + x->avl_balance = y->avl_balance = 0; + else /* |w->avl_balance == -1| */ + x->avl_balance = +1, y->avl_balance = 0; + w->avl_balance = 0; + pa[k - 1]->avl_link[da[k - 1]] = w; + } + else + { + y->avl_link[1] = x->avl_link[0]; + x->avl_link[0] = y; + pa[k - 1]->avl_link[da[k - 1]] = x; + if (x->avl_balance == 0) + { + x->avl_balance = -1; + y->avl_balance = +1; + break; + } + else + x->avl_balance = y->avl_balance = 0; + } + } + } + else + { + y->avl_balance--; + if (y->avl_balance == -1) + break; + else if (y->avl_balance == -2) + { + struct avl_node *x = y->avl_link[0]; + if (x->avl_balance == +1) + { + struct avl_node *w; + assert (x->avl_balance == +1); + w = x->avl_link[1]; + x->avl_link[1] = w->avl_link[0]; + w->avl_link[0] = x; + y->avl_link[0] = w->avl_link[1]; + w->avl_link[1] = y; + if (w->avl_balance == -1) + x->avl_balance = 0, y->avl_balance = +1; + else if (w->avl_balance == 0) + x->avl_balance = y->avl_balance = 0; + else /* |w->avl_balance == +1| */ + x->avl_balance = -1, y->avl_balance = 0; + w->avl_balance = 0; + pa[k - 1]->avl_link[da[k - 1]] = w; + } + else + { + y->avl_link[0] = x->avl_link[1]; + x->avl_link[1] = y; + pa[k - 1]->avl_link[da[k - 1]] = x; + if (x->avl_balance == 0) + { + x->avl_balance = +1; + y->avl_balance = -1; + break; + } + else + x->avl_balance = y->avl_balance = 0; + } + } + } + } + + tree->avl_count--; + tree->avl_generation++; + return (void *) item; +} + +/* Refreshes the stack of parent pointers in |trav| + and updates its generation number. */ +static void +trav_refresh (struct avl_traverser *trav) +{ + assert (trav != NULL); + + trav->avl_generation = trav->avl_table->avl_generation; + + if (trav->avl_node != NULL) + { + avl_comparison_func *cmp = trav->avl_table->avl_compare; + void *param = trav->avl_table->avl_param; + struct avl_node *node = trav->avl_node; + struct avl_node *i; + + trav->avl_height = 0; + for (i = trav->avl_table->avl_root; i != node; ) + { + assert (trav->avl_height < AVL_MAX_HEIGHT); + assert (i != NULL); + + trav->avl_stack[trav->avl_height++] = i; + i = i->avl_link[cmp (node->avl_data, i->avl_data, param) > 0]; + } + } +} + +/* Initializes |trav| for use with |tree| + and selects the null node. */ +void +avl_t_init (struct avl_traverser *trav, struct avl_table *tree) +{ + trav->avl_table = tree; + trav->avl_node = NULL; + trav->avl_height = 0; + trav->avl_generation = tree->avl_generation; +} + +/* Initializes |trav| for |tree| + and selects and returns a pointer to its least-valued item. + Returns |NULL| if |tree| contains no nodes. */ +void * +avl_t_first (struct avl_traverser *trav, struct avl_table *tree) +{ + struct avl_node *x; + + assert (tree != NULL && trav != NULL); + + trav->avl_table = tree; + trav->avl_height = 0; + trav->avl_generation = tree->avl_generation; + + x = tree->avl_root; + if (x != NULL) + while (x->avl_link[0] != NULL) + { + assert (trav->avl_height < AVL_MAX_HEIGHT); + trav->avl_stack[trav->avl_height++] = x; + x = x->avl_link[0]; + } + trav->avl_node = x; + + return x != NULL ? x->avl_data : NULL; +} + +/* Initializes |trav| for |tree| + and selects and returns a pointer to its greatest-valued item. + Returns |NULL| if |tree| contains no nodes. */ +void * +avl_t_last (struct avl_traverser *trav, struct avl_table *tree) +{ + struct avl_node *x; + + assert (tree != NULL && trav != NULL); + + trav->avl_table = tree; + trav->avl_height = 0; + trav->avl_generation = tree->avl_generation; + + x = tree->avl_root; + if (x != NULL) + while (x->avl_link[1] != NULL) + { + assert (trav->avl_height < AVL_MAX_HEIGHT); + trav->avl_stack[trav->avl_height++] = x; + x = x->avl_link[1]; + } + trav->avl_node = x; + + return x != NULL ? x->avl_data : NULL; +} + +/* Searches for |item| in |tree|. + If found, initializes |trav| to the item found and returns the item + as well. + If there is no matching item, initializes |trav| to the null item + and returns |NULL|. */ +void * +avl_t_find (struct avl_traverser *trav, struct avl_table *tree, void *item) +{ + struct avl_node *p, *q; + + assert (trav != NULL && tree != NULL && item != NULL); + trav->avl_table = tree; + trav->avl_height = 0; + trav->avl_generation = tree->avl_generation; + for (p = tree->avl_root; p != NULL; p = q) + { + int cmp = tree->avl_compare (item, p->avl_data, tree->avl_param); + + if (cmp < 0) + q = p->avl_link[0]; + else if (cmp > 0) + q = p->avl_link[1]; + else /* |cmp == 0| */ + { + trav->avl_node = p; + return p->avl_data; + } + + assert (trav->avl_height < AVL_MAX_HEIGHT); + trav->avl_stack[trav->avl_height++] = p; + } + + trav->avl_height = 0; + trav->avl_node = NULL; + return NULL; +} + +/* Attempts to insert |item| into |tree|. + If |item| is inserted successfully, it is returned and |trav| is + initialized to its location. + If a duplicate is found, it is returned and |trav| is initialized to + its location. No replacement of the item occurs. + If a memory allocation failure occurs, |NULL| is returned and |trav| + is initialized to the null item. */ +void * +avl_t_insert (struct avl_traverser *trav, struct avl_table *tree, void *item) +{ + void **p; + + assert (trav != NULL && tree != NULL && item != NULL); + + p = avl_probe (tree, item); + if (p != NULL) + { + trav->avl_table = tree; + trav->avl_node = + ((struct avl_node *) + ((char *) p - offsetof (struct avl_node, avl_data))); + trav->avl_generation = tree->avl_generation - 1; + return *p; + } + else + { + avl_t_init (trav, tree); + return NULL; + } +} + +/* Initializes |trav| to have the same current node as |src|. */ +void * +avl_t_copy (struct avl_traverser *trav, const struct avl_traverser *src) +{ + assert (trav != NULL && src != NULL); + + if (trav != src) + { + trav->avl_table = src->avl_table; + trav->avl_node = src->avl_node; + trav->avl_generation = src->avl_generation; + if (trav->avl_generation == trav->avl_table->avl_generation) + { + trav->avl_height = src->avl_height; + memcpy (trav->avl_stack, (const void *) src->avl_stack, + sizeof *trav->avl_stack * trav->avl_height); + } + } + + return trav->avl_node != NULL ? trav->avl_node->avl_data : NULL; +} + +/* Returns the next data item in inorder + within the tree being traversed with |trav|, + or if there are no more data items returns |NULL|. */ +void * +avl_t_next (struct avl_traverser *trav) +{ + struct avl_node *x; + + assert (trav != NULL); + + if (trav->avl_generation != trav->avl_table->avl_generation) + trav_refresh (trav); + + x = trav->avl_node; + if (x == NULL) + { + return avl_t_first (trav, trav->avl_table); + } + else if (x->avl_link[1] != NULL) + { + assert (trav->avl_height < AVL_MAX_HEIGHT); + trav->avl_stack[trav->avl_height++] = x; + x = x->avl_link[1]; + + while (x->avl_link[0] != NULL) + { + assert (trav->avl_height < AVL_MAX_HEIGHT); + trav->avl_stack[trav->avl_height++] = x; + x = x->avl_link[0]; + } + } + else + { + struct avl_node *y; + + do + { + if (trav->avl_height == 0) + { + trav->avl_node = NULL; + return NULL; + } + + y = x; + x = trav->avl_stack[--trav->avl_height]; + } + while (y == x->avl_link[1]); + } + trav->avl_node = x; + + return x->avl_data; +} + +/* Returns the previous data item in inorder + within the tree being traversed with |trav|, + or if there are no more data items returns |NULL|. */ +void * +avl_t_prev (struct avl_traverser *trav) +{ + struct avl_node *x; + + assert (trav != NULL); + + if (trav->avl_generation != trav->avl_table->avl_generation) + trav_refresh (trav); + + x = trav->avl_node; + if (x == NULL) + { + return avl_t_last (trav, trav->avl_table); + } + else if (x->avl_link[0] != NULL) + { + assert (trav->avl_height < AVL_MAX_HEIGHT); + trav->avl_stack[trav->avl_height++] = x; + x = x->avl_link[0]; + + while (x->avl_link[1] != NULL) + { + assert (trav->avl_height < AVL_MAX_HEIGHT); + trav->avl_stack[trav->avl_height++] = x; + x = x->avl_link[1]; + } + } + else + { + struct avl_node *y; + + do + { + if (trav->avl_height == 0) + { + trav->avl_node = NULL; + return NULL; + } + + y = x; + x = trav->avl_stack[--trav->avl_height]; + } + while (y == x->avl_link[0]); + } + trav->avl_node = x; + + return x->avl_data; +} + +/* Returns |trav|'s current item. */ +void * +avl_t_cur (struct avl_traverser *trav) +{ + assert (trav != NULL); + + return trav->avl_node != NULL ? trav->avl_node->avl_data : NULL; +} + +/* Replaces the current item in |trav| by |new| and returns the item replaced. + |trav| must not have the null item selected. + The new item must not upset the ordering of the tree. */ +void * +avl_t_replace (struct avl_traverser *trav, void *new) +{ + void *old; + + assert (trav != NULL && trav->avl_node != NULL && new != NULL); + old = trav->avl_node->avl_data; + trav->avl_node->avl_data = new; + return old; +} + +/* Destroys |new| with |avl_destroy (new, destroy)|, + first setting right links of nodes in |stack| within |new| + to null pointers to avoid touching uninitialized data. */ +static void +copy_error_recovery (struct avl_node **stack, int height, + struct avl_table *new, avl_item_func *destroy) +{ + assert (stack != NULL && height >= 0 && new != NULL); + + for (; height > 2; height -= 2) + stack[height - 1]->avl_link[1] = NULL; + avl_destroy (new, destroy); +} + +/* Copies |org| to a newly created tree, which is returned. + If |copy != NULL|, each data item in |org| is first passed to |copy|, + and the return values are inserted into the tree, + with |NULL| return values taken as indications of failure. + On failure, destroys the partially created new tree, + applying |destroy|, if non-null, to each item in the new tree so far, + and returns |NULL|. + If |allocator != NULL|, it is used for allocation in the new tree. + Otherwise, the same allocator used for |org| is used. */ +struct avl_table * +avl_copy (const struct avl_table *org, avl_copy_func *copy, + avl_item_func *destroy, struct libavl_allocator *allocator) +{ + struct avl_node *stack[2 * (AVL_MAX_HEIGHT + 1)]; + int height = 0; + + struct avl_table *new; + const struct avl_node *x; + struct avl_node *y; + + assert (org != NULL); + new = avl_create (org->avl_compare, org->avl_param, + allocator != NULL ? allocator : org->avl_alloc); + if (new == NULL) + return NULL; + new->avl_count = org->avl_count; + if (new->avl_count == 0) + return new; + + x = (const struct avl_node *) &org->avl_root; + y = (struct avl_node *) &new->avl_root; + for (;;) + { + while (x->avl_link[0] != NULL) + { + assert (height < 2 * (AVL_MAX_HEIGHT + 1)); + + y->avl_link[0] = + new->avl_alloc->libavl_malloc (new->avl_alloc, + sizeof *y->avl_link[0]); + if (y->avl_link[0] == NULL) + { + if (y != (struct avl_node *) &new->avl_root) + { + y->avl_data = NULL; + y->avl_link[1] = NULL; + } + + copy_error_recovery (stack, height, new, destroy); + return NULL; + } + + stack[height++] = (struct avl_node *) x; + stack[height++] = y; + x = x->avl_link[0]; + y = y->avl_link[0]; + } + y->avl_link[0] = NULL; + + for (;;) + { + y->avl_balance = x->avl_balance; + if (copy == NULL) + y->avl_data = x->avl_data; + else + { + y->avl_data = copy (x->avl_data, org->avl_param); + if (y->avl_data == NULL) + { + y->avl_link[1] = NULL; + copy_error_recovery (stack, height, new, destroy); + return NULL; + } + } + + if (x->avl_link[1] != NULL) + { + y->avl_link[1] = + new->avl_alloc->libavl_malloc (new->avl_alloc, + sizeof *y->avl_link[1]); + if (y->avl_link[1] == NULL) + { + copy_error_recovery (stack, height, new, destroy); + return NULL; + } + + x = x->avl_link[1]; + y = y->avl_link[1]; + break; + } + else + y->avl_link[1] = NULL; + + if (height <= 2) + return new; + + y = stack[--height]; + x = stack[--height]; + } + } +} + +/* Frees storage allocated for |tree|. + If |destroy != NULL|, applies it to each data item in inorder. */ +void +avl_destroy (struct avl_table *tree, avl_item_func *destroy) +{ + struct avl_node *p, *q; + + assert (tree != NULL); + + for (p = tree->avl_root; p != NULL; p = q) + if (p->avl_link[0] == NULL) + { + q = p->avl_link[1]; + if (destroy != NULL && p->avl_data != NULL) + destroy (p->avl_data, tree->avl_param); + tree->avl_alloc->libavl_free (tree->avl_alloc, p); + } + else + { + q = p->avl_link[0]; + p->avl_link[0] = q->avl_link[1]; + q->avl_link[1] = p; + } + + tree->avl_alloc->libavl_free (tree->avl_alloc, tree); +} + +/* Allocates |size| bytes of space using |malloc()|. + Returns a null pointer if allocation fails. */ +void * +avl_malloc (struct libavl_allocator *allocator, size_t size) +{ + assert (allocator != NULL && size > 0); + return malloc (size); +} + +/* Frees |block|. */ +void +avl_free (struct libavl_allocator *allocator, void *block) +{ + assert (allocator != NULL && block != NULL); + free (block); +} + +/* Default memory allocator that uses |malloc()| and |free()|. */ +struct libavl_allocator avl_allocator_default = + { + avl_malloc, + avl_free + }; + +#undef NDEBUG +#include + +/* Asserts that |avl_insert()| succeeds at inserting |item| into |table|. */ +void +(avl_assert_insert) (struct avl_table *table, void *item) +{ + void **p = avl_probe (table, item); + assert (p != NULL && *p == item); +} + +/* Asserts that |avl_delete()| really removes |item| from |table|, + and returns the removed item. */ +void * +(avl_assert_delete) (struct avl_table *table, void *item) +{ + void *p = avl_delete (table, item); + assert (p != NULL); + return p; +} + diff -Nru logtop-0.1/src/libavl/avl.h logtop-0.3/src/libavl/avl.h --- logtop-0.1/src/libavl/avl.h 1970-01-01 00:00:00.000000000 +0000 +++ logtop-0.3/src/libavl/avl.h 2011-04-16 10:07:47.000000000 +0000 @@ -0,0 +1,115 @@ +/* Produced by texiweb from libavl.w. */ + +/* libavl - library for manipulation of binary trees. + Copyright (C) 1998-2002, 2004 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 on the Internet, or + write to Ben Pfaff, Stanford University, Computer Science Dept., 353 + Serra Mall, Stanford CA 94305, USA. +*/ + +#ifndef AVL_H +#define AVL_H 1 + +#include + +/* Function types. */ +typedef int avl_comparison_func (const void *avl_a, const void *avl_b, + void *avl_param); +typedef void avl_item_func (void *avl_item, void *avl_param); +typedef void *avl_copy_func (void *avl_item, void *avl_param); + +#ifndef LIBAVL_ALLOCATOR +#define LIBAVL_ALLOCATOR +/* Memory allocator. */ +struct libavl_allocator + { + void *(*libavl_malloc) (struct libavl_allocator *, size_t libavl_size); + void (*libavl_free) (struct libavl_allocator *, void *libavl_block); + }; +#endif + +/* Default memory allocator. */ +extern struct libavl_allocator avl_allocator_default; +void *avl_malloc (struct libavl_allocator *, size_t); +void avl_free (struct libavl_allocator *, void *); + +/* Maximum AVL height. */ +#ifndef AVL_MAX_HEIGHT +#define AVL_MAX_HEIGHT 32 +#endif + +/* Tree data structure. */ +struct avl_table + { + struct avl_node *avl_root; /* Tree's root. */ + avl_comparison_func *avl_compare; /* Comparison function. */ + void *avl_param; /* Extra argument to |avl_compare|. */ + struct libavl_allocator *avl_alloc; /* Memory allocator. */ + size_t avl_count; /* Number of items in tree. */ + unsigned long avl_generation; /* Generation number. */ + }; + +/* An AVL tree node. */ +struct avl_node + { + struct avl_node *avl_link[2]; /* Subtrees. */ + void *avl_data; /* Pointer to data. */ + signed char avl_balance; /* Balance factor. */ + }; + +/* AVL traverser structure. */ +struct avl_traverser + { + struct avl_table *avl_table; /* Tree being traversed. */ + struct avl_node *avl_node; /* Current node in tree. */ + struct avl_node *avl_stack[AVL_MAX_HEIGHT]; + /* All the nodes above |avl_node|. */ + size_t avl_height; /* Number of nodes in |avl_parent|. */ + unsigned long avl_generation; /* Generation number. */ + }; + +/* Table functions. */ +struct avl_table *avl_create (avl_comparison_func *, void *, + struct libavl_allocator *); +struct avl_table *avl_copy (const struct avl_table *, avl_copy_func *, + avl_item_func *, struct libavl_allocator *); +void avl_destroy (struct avl_table *, avl_item_func *); +void **avl_probe (struct avl_table *, void *); +void *avl_insert (struct avl_table *, void *); +void *avl_replace (struct avl_table *, void *); +void *avl_delete (struct avl_table *, const void *); +void *avl_find (const struct avl_table *, const void *); +void avl_assert_insert (struct avl_table *, void *); +void *avl_assert_delete (struct avl_table *, void *); + +#define avl_count(table) ((size_t) (table)->avl_count) + +/* Table traverser functions. */ +void avl_t_init (struct avl_traverser *, struct avl_table *); +void *avl_t_first (struct avl_traverser *, struct avl_table *); +void *avl_t_last (struct avl_traverser *, struct avl_table *); +void *avl_t_find (struct avl_traverser *, struct avl_table *, void *); +void *avl_t_insert (struct avl_traverser *, struct avl_table *, void *); +void *avl_t_copy (struct avl_traverser *, const struct avl_traverser *); +void *avl_t_next (struct avl_traverser *); +void *avl_t_prev (struct avl_traverser *); +void *avl_t_cur (struct avl_traverser *); +void *avl_t_replace (struct avl_traverser *, void *); + +#endif /* avl.h */ diff -Nru logtop-0.1/src/logtop.c logtop-0.3/src/logtop.c --- logtop-0.1/src/logtop.c 2010-12-14 19:47:38.000000000 +0000 +++ logtop-0.3/src/logtop.c 2011-04-16 10:29:07.000000000 +0000 @@ -29,105 +29,51 @@ #include #include #include "logtop.h" +#include "history.h" +#include "avl.h" env_t gl_env; -/* -** If the element under history_start is null -** then the history is not full. -*/ -unsigned int qte_of_elements_in_history() +void got_a_new_string(char *string) { - if (gl_env.history[gl_env.history_start].log_entry == NULL) - return gl_env.history_start; - else - return gl_env.history_size; -} - -history_element_t *oldest_element_in_history() -{ - if (gl_env.history[gl_env.history_start].log_entry != NULL) - { - return &(gl_env.history[gl_env.history_start]); - } - else - { - if (gl_env.history_start == 0) - return NULL; - return &(gl_env.history[0]); - } -} - -history_element_t *newest_element_in_history() -{ - int newest_item_index; - - newest_item_index = gl_env.history_start == 0 - ? gl_env.history_size - 1 - : gl_env.history_start - 1; - if (gl_env.history[newest_item_index].log_entry == NULL) - return NULL; - else - return &(gl_env.history[newest_item_index]); -} - -void update_history(log_line *element) -{ - history_element_t *history_element; - log_line *log_entry; - - history_element = &(gl_env.history[gl_env.history_start]); - log_entry = history_element->log_entry; - if (log_entry != NULL) - { - log_entry->count--; - if (log_entry->count == 0) - { - avl_delete_node(gl_env.top, log_entry->top_node); - avl_delete_node(gl_env.strings, log_entry->string_node); - } - else - { - update_log_entry(log_entry); - } - } - gl_env.history[gl_env.history_start].log_entry = element; - gl_env.history[gl_env.history_start].time = time(NULL); - gl_env.history_start += 1; - if (gl_env.history_start >= gl_env.history_size) - gl_env.history_start = 0; -} - -void got_a_new_string(char *string) -{ - log_line *element; + log_line_t *element; element = get_log_entry(string); - element->count += 1; - update_log_entry(element); + increment_log_entry_count(element); update_history(element); curses_update(); } -void run() +void run() { - char *string; - size_t size; + char *string; + size_t size; + ssize_t str_length; string = NULL; size = 0; - while (getline(&string, &size, stdin) != -1) + while ((str_length = getline(&string, &size, stdin)) != -1) + { + while (str_length > 0 && (string[str_length - 1] == '\n' + || string[str_length - 1] == '\r')) + { + string[str_length - 1] = '\0'; + str_length -= 1; + } got_a_new_string(string); + } if (string != NULL) free(string); } void usage_and_exit(char* program_name) { - fprintf(stderr, "Usage: tail something |" \ - " %s [-s history_size]\n", program_name); - fprintf(stderr, " history_size: Number of log line to keep\n"); - fprintf(stderr, " Defaults to 10000 lines.\n"); + fprintf(stderr, + "Usage: tail something | %s [-s history_size]\n" + " history_size: Number of log line to keep in memory\n" + " Defaults to " STRINGIFY(DEFAULT_HISTORY_SIZE) + " lines.\n", + program_name); exit(EXIT_FAILURE); } @@ -142,7 +88,7 @@ int opt; gl_env.history_size = 0; - while ((opt = getopt(ac, av, "hvs:c:")) != -1) + while ((opt = getopt(ac, av, "hvs:")) != -1) { switch (opt) { @@ -157,14 +103,14 @@ } } if (gl_env.history_size == 0) - gl_env.history_size = 10000; + gl_env.history_size = DEFAULT_HISTORY_SIZE; } - -int main(int ac, char **av) +int main(int ac, char **av) { parse_args(ac, av); - init_data_structures(); + init_history(); + init_avl(); curses_setup(); run(); curses_release(); diff -Nru logtop-0.1/src/logtop.h logtop-0.3/src/logtop.h --- logtop-0.1/src/logtop.h 2010-12-03 08:57:18.000000000 +0000 +++ logtop-0.3/src/logtop.h 2011-05-03 21:46:13.000000000 +0000 @@ -26,30 +26,22 @@ #ifndef __LOGTOP_H__ #define __LOGTOP_H__ -#include #include -#define UNUSED(x) x __attribute__((unused)) +#include "avl.h" +#include "history.h" -typedef struct s_log_line -{ - char *string; - char *repr; - unsigned int count; - avl_node_t *string_node; - avl_node_t *top_node; -} log_line; +#ifndef STRINGIFY +# define __LOGTOP_STRINGIFY(x) #x +# define STRINGIFY(x) __LOGTOP_STRINGIFY(x) +#endif -typedef struct s_history_element -{ - log_line *log_entry; - time_t time; -} history_element_t; +#define DEFAULT_HISTORY_SIZE 10000 typedef struct s_env { - avl_tree_t *strings; - avl_tree_t *top; + log_line_t *strings; + struct avl_table *top; history_element_t *history; unsigned int history_start; unsigned int history_size; @@ -59,26 +51,10 @@ extern env_t gl_env; -/* -** In avl.c -*/ - -/* -** Adds or increments a string in the AVL and returns its -** representing log_line -*/ -log_line *get_log_entry(char *); -void update_log_entry(log_line *); -void init_data_structures(); - -void curses_setup(); -void curses_release(); -void curses_update(); - -void stdout_update(); - -history_element_t *oldest_element_in_history(); -history_element_t *newest_element_in_history(); -unsigned int qte_of_elements_in_history(); +void curses_setup(); +void curses_release(); +void curses_update(); + +void stdout_update(); #endif diff -Nru logtop-0.1/src/stdout.c logtop-0.3/src/stdout.c --- logtop-0.1/src/stdout.c 2010-12-05 19:09:25.000000000 +0000 +++ logtop-0.3/src/stdout.c 2011-04-16 10:07:47.000000000 +0000 @@ -25,52 +25,66 @@ #include #include "logtop.h" +#include "history.h" -void stdout_update() +struct line_metadata { - avl_node_t *node; - unsigned int i; - history_element_t *oldest_element; - history_element_t *newest_element; - double duration; - log_line *log_entry; - unsigned int qte_of_elements; + double duration; +}; - duration = 0; +static void display_line_with_freq(void *data, int index, void *metadata) +{ + log_line_t *line; + double duration; + + line = (log_line_t *)data; + duration = ((struct line_metadata *)metadata)->duration; + printf("%4d %4d %4.2f/s %s\n", + index, + line->count, + line->count / duration, + line->repr); +} + +static void display_line_without_freq(void *data, int index, + void *metadata) +{ + log_line_t *line; + + (void) metadata; + line = (log_line_t *)data; + printf("%4d %4d %s\n", + index, + line->count, + line->repr); +} + +void stdout_update() +{ + history_element_t *oldest_element; + history_element_t *newest_element; + struct line_metadata line_metadata; + unsigned int qte_of_elements; + + line_metadata.duration = 0; oldest_element = oldest_element_in_history(); newest_element = newest_element_in_history(); if (oldest_element != NULL && newest_element != NULL) - duration = difftime(newest_element->time, oldest_element->time); - i = 0; + line_metadata.duration = difftime(newest_element->time, + oldest_element->time); qte_of_elements = qte_of_elements_in_history(); - if (duration > 0) + if (line_metadata.duration > 0) printf("%d elements in %d seconds (%.2f elements/s)\n", qte_of_elements, - (unsigned int)duration, - qte_of_elements / (double)duration); + (unsigned int)line_metadata.duration, + qte_of_elements / (double)line_metadata.duration); else printf("%d elements\n", qte_of_elements); - for (node = gl_env.top->head; - node != NULL && i < gl_env.display_height; - node = node->next) - { - log_entry = (log_line*)node->item; - if (duration > 0) - { - printf("%4d %4d %4.2f/s %s\n", - i + 1, - log_entry->count, - log_entry->count / (double)duration, - log_entry->repr); - } - else - { - printf("%4d %4d %s\n", - i + 1, - log_entry->count, - log_entry->repr); - } - i += 1; - } + if (line_metadata.duration > 0) + traverse_log_lines(gl_env.top, gl_env.display_height - 1, + display_line_with_freq, &line_metadata); + else + traverse_log_lines(gl_env.top, gl_env.display_height - 1, + display_line_without_freq, &line_metadata); }