[Hexane-developers] SF.net SVN: hexane: [2] trunk
Status: Planning
Brought to you by:
brianahr
Menu
▾
▴
[Hexane-developers] SF.net SVN: hexane: [2] trunk
|
From: <bri...@us...> - 2006-10-08 04:49:20
|
Revision: 2
http://svn.sourceforge.net/hexane/?rev=2&view=rev
Author: brianahr
Date: 2006-10-07 21:49:06 -0700 (Sat, 07 Oct 2006)
Log Message:
-----------
Initial Commit
Added Paths:
-----------
trunk/BUILDING
trunk/COPYING
trunk/SConstruct
trunk/TODO
trunk/docs/
trunk/docs/tree.dia
trunk/docs/uml.dia
trunk/engine/
trunk/engine/SConscript
trunk/engine/engine.cpp
trunk/engine/engine.h
trunk/engine/hxtree.hxx
trunk/engine/process.cpp
trunk/engine/process.h
trunk/global.h
trunk/hexane.cpp
trunk/session/
trunk/session/SConscript
trunk/session/bookmark.cpp
trunk/session/bookmark.h
trunk/session/goto.cpp
trunk/session/goto.h
trunk/session/manageable.h
trunk/session/manager.cpp
trunk/session/manager.h
trunk/session/tool.cpp
trunk/session/tool.h
trunk/test/
trunk/test/SConscript
trunk/test/examples/
trunk/test/examples/fixtures.cpp
trunk/test/examples/named.cpp
trunk/test/examples/simple.cpp
trunk/test/hxtest.h
trunk/test/hxtreetester.cpp
trunk/util/
trunk/util/SConscript
trunk/util/algorithm.h
trunk/util/baseconv.cpp
trunk/util/baseconv.h
trunk/util/botan.cpp
trunk/util/botan.h
trunk/util/getopts.cpp
trunk/util/getopts.h
trunk/util/hxml.cpp
trunk/util/hxml.h
Added: trunk/BUILDING
===================================================================
--- trunk/BUILDING (rev 0)
+++ trunk/BUILDING 2006-10-08 04:49:06 UTC (rev 2)
@@ -0,0 +1,44 @@
+Hexane currently requires the following to be installed:
+
+libraries:
+----------
+* Botan: http://botan.randombit.net/
+
+
+tools:
+------
+* scons: http://www.scons.org
+
+
+optional:
+---------
+* Dia, for viewing diagrams in the doc/ directory
+
+
+build instructions
+------------------
+To compile the Hexane source code:
+$ scons
+
+To clean the directory:
+$ scons -c
+
+To build the test drivers:
+$ scons test
+
+To clean the test drivers:
+$ scons test -c
+
+
+Note
+----
+* Currently there is no configure or install options.
+ These will be added once Hexane reaches alpha.
+
+* Libraries are subject to change. As Hexane matures,
+ the following libraries will probably become dependancies:
+ GTK+: http://www.gtk.org
+ Glade: http://glade.gnome.org
+ GDL: http://ftp.gnome.org/pub/GNOME/sources/gdl/0.6/
+ VTE: http://www.gnome.org
+ Doxygen: http://www.doxygen.org
Added: trunk/COPYING
===================================================================
--- trunk/COPYING (rev 0)
+++ trunk/COPYING 2006-10-08 04:49:06 UTC (rev 2)
@@ -0,0 +1,339 @@
+ GNU GENERAL PUBLIC LICENSE Version 2, June 1991
+
+ Copyright (C) 1989, 1991 Free Software Foundation, Inc. 51 Franklin St,
+ Fifth Floor, Boston, MA 02110-1301 USA Everyone is permitted to copy
+ and distribute verbatim copies of this license document, but changing
+ it is not allowed.
+
+ Preamble
+
+ The licenses for most software are designed to take away your freedom
+to share and change it. By contrast, the GNU General Public License is
+intended to guarantee your freedom to share and change free software--to
+make sure the software is free for all its users. This General Public
+License applies to most of the Free Software Foundation's software and
+to any other program whose authors commit to using it. (Some other Free
+Software Foundation software is covered by the GNU Library General
+Public License instead.) You can apply it to your programs, too.
+
+ When we speak of free software, we are referring to freedom, not
+price. Our General Public Licenses are designed to make sure that you
+have the freedom to distribute copies of free software (and charge for
+this service if you wish), that you receive source code or can get it if
+you want it, that you can change the software or use pieces of it in new
+free programs; and that you know you can do these things.
+
+ To protect your rights, we need to make restrictions that forbid
+anyone to deny you these rights or to ask you to surrender the rights.
+These restrictions translate to certain responsibilities for you if you
+distribute copies of the software, or if you modify it.
+
+ For example, if you distribute copies of such a program, whether
+gratis or for a fee, you must give the recipients all the rights that
+you have. You must make sure that they, too, receive or can get the
+source code. And you must show them these terms so they know their
+rights.
+
+ We protect your rights with two steps: (1) copyright the software, and
+(2) offer you this license which gives you legal permission to copy,
+distribute and/or modify the software.
+
+ Also, for each author's protection and ours, we want to make certain
+that everyone understands that there is no warranty for this free
+software. If the software is modified by someone else and passed on, we
+want its recipients to know that what they have is not the original, so
+that any problems introduced by others will not reflect on the original
+authors' reputations.
+
+ Finally, any free program is threatened constantly by software
+patents. We wish to avoid the danger that redistributors of a free
+program will individually obtain patent licenses, in effect making the
+program proprietary. To prevent this, we have made it clear that any
+patent must be licensed for everyone's free use or not licensed at all.
+
+ The precise terms and conditions for copying, distribution and
+modification follow.
+
+ GNU GENERAL PUBLIC LICENSE TERMS AND CONDITIONS FOR COPYING,
+ DISTRIBUTION AND MODIFICATION
+
+ 0. This License applies to any program or other work which contains a
+notice placed by the copyright holder saying it may be distributed under
+the terms of this General Public License. The "Program", below, refers
+to any such program or work, and a "work based on the Program" means
+either the Program or any derivative work under copyright law: that is
+to say, a work containing the Program or a portion of it, either
+verbatim or with modifications and/or translated into another language.
+(Hereinafter, translation is included without limitation in the term
+"modification".) Each licensee is addressed as "you".
+
+Activities other than copying, distribution and modification are not
+covered by this License; they are outside its scope. The act of running
+the Program is not restricted, and the output from the Program is
+covered only if its contents constitute a work based on the Program
+(independent of having been made by running the Program). Whether that
+is true depends on what the Program does.
+
+ 1. You may copy and distribute verbatim copies of the Program's source
+code as you receive it, in any medium, provided that you conspicuously
+and appropriately publish on each copy an appropriate copyright notice
+and disclaimer of warranty; keep intact all the notices that refer to
+this License and to the absence of any warranty; and give any other
+recipients of the Program a copy of this License along with the Program.
+
+You may charge a fee for the physical act of transferring a copy, and
+you may at your option offer warranty protection in exchange for a fee.
+
+ 2. You may modify your copy or copies of the Program or any portion of
+it, thus forming a work based on the Program, and copy and distribute
+such modifications or work under the terms of Section 1 above, provided
+that you also meet all of these conditions:
+
+ a) You must cause the modified files to carry prominent notices
+ stating that you changed the files and the date of any change.
+
+ b) You must cause any work that you distribute or publish, that in
+ whole or in part contains or is derived from the Program or any part
+ thereof, to be licensed as a whole at no charge to all third parties
+ under the terms of this License.
+
+ c) If the modified program normally reads commands interactively
+ when run, you must cause it, when started running for such
+ interactive use in the most ordinary way, to print or display an
+ announcement including an appropriate copyright notice and a notice
+ that there is no warranty (or else, saying that you provide a
+ warranty) and that users may redistribute the program under these
+ conditions, and telling the user how to view a copy of this License.
+ (Exception: if the Program itself is interactive but does not
+ normally print such an announcement, your work based on the Program
+ is not required to print an announcement.)
+
+These requirements apply to the modified work as a whole. If
+identifiable sections of that work are not derived from the Program,
+and can be reasonably considered independent and separate works in
+themselves, then this License, and its terms, do not apply to those
+sections when you distribute them as separate works. But when you
+distribute the same sections as part of a whole which is a work based on
+the Program, the distribution of the whole must be on the terms of this
+License, whose permissions for other licensees extend to the entire
+whole, and thus to each and every part regardless of who wrote it.
+
+Thus, it is not the intent of this section to claim rights or contest
+your rights to work written entirely by you; rather, the intent is to
+exercise the right to control the distribution of derivative or
+collective works based on the Program.
+
+In addition, mere aggregation of another work not based on the Program
+with the Program (or with a work based on the Program) on a volume of a
+storage or distribution medium does not bring the other work under the
+scope of this License.
+
+ 3. You may copy and distribute the Program (or a work based on it,
+under Section 2) in object code or executable form under the terms of
+Sections 1 and 2 above provided that you also do one of the following:
+
+ a) Accompany it with the complete corresponding machine-readable
+ source code, which must be distributed under the terms of Sections 1
+ and 2 above on a medium customarily used for software interchange;
+ or,
+
+ b) Accompany it with a written offer, valid for at least three
+ years, to give any third party, for a charge no more than your
+ cost of physically performing source distribution, a complete
+ machine-readable copy of the corresponding source code, to be
+ distributed under the terms of Sections 1 and 2 above on a medium
+ customarily used for software interchange; or,
+
+ c) Accompany it with the information you received as to the offer to
+ distribute corresponding source code. (This alternative is allowed
+ only for noncommercial distribution and only if you received the
+ program in object code or executable form with such an offer, in
+ accord with Subsection b above.)
+
+The source code for a work means the preferred form of the work for
+making modifications to it. For an executable work, complete source code
+means all the source code for all modules it contains, plus any
+associated interface definition files, plus the scripts used to control
+compilation and installation of the executable. However, as a special
+exception, the source code distributed need not include anything that is
+normally distributed (in either source or binary form) with the major
+components (compiler, kernel, and so on) of the operating system on
+which the executable runs, unless that component itself accompanies the
+executable.
+
+If distribution of executable or object code is made by offering access
+to copy from a designated place, then offering equivalent access to copy
+the source code from the same place counts as distribution of the source
+code, even though third parties are not compelled to copy the source
+along with the object code.
+
+ 4. You may not copy, modify, sublicense, or distribute the Program
+except as expressly provided under this License. Any attempt otherwise
+to copy, modify, sublicense or distribute the Program is void, and will
+automatically terminate your rights under this License. However, parties
+who have received copies, or rights, from you under this License will
+not have their licenses terminated so long as such parties remain in
+full compliance.
+
+ 5. You are not required to accept this License, since you have not
+signed it. However, nothing else grants you permission to modify or
+distribute the Program or its derivative works. These actions are
+prohibited by law if you do not accept this License. Therefore, by
+modifying or distributing the Program (or any work based on the
+Program), you indicate your acceptance of this License to do so, and all
+its terms and conditions for copying, distributing or modifying the
+Program or works based on it.
+
+ 6. Each time you redistribute the Program (or any work based on the
+Program), the recipient automatically receives a license from the
+original licensor to copy, distribute or modify the Program subject to
+these terms and conditions. You may not impose any further restrictions
+on the recipients' exercise of the rights granted herein. You are not
+responsible for enforcing compliance by third parties to this License.
+
+ 7. If, as a consequence of a court judgment or allegation of patent
+infringement or for any other reason (not limited to patent issues),
+conditions are imposed on you (whether by court order, agreement or
+otherwise) that contradict the conditions of this License, they do not
+excuse you from the conditions of this License. If you cannot distribute
+so as to satisfy simultaneously your obligations under this License and
+any other pertinent obligations, then as a consequence you may not
+distribute the Program at all. For example, if a patent license would
+not permit royalty-free redistribution of the Program by all those who
+receive copies directly or indirectly through you, then the only way you
+could satisfy both it and this License would be to refrain entirely from
+distribution of the Program.
+
+If any portion of this section is held invalid or unenforceable under
+any particular circumstance, the balance of the section is intended to
+apply and the section as a whole is intended to apply in other
+circumstances.
+
+It is not the purpose of this section to induce you to infringe any
+patents or other property right claims or to contest validity of
+any such claims; this section has the sole purpose of protecting
+the integrity of the free software distribution system, which is
+implemented by public license practices. Many people have made generous
+contributions to the wide range of software distributed through that
+system in reliance on consistent application of that system; it is up to
+the author/donor to decide if he or she is willing to distribute
+software through any other system and a licensee cannot impose that
+choice.
+
+This section is intended to make thoroughly clear what is believed to be
+a consequence of the rest of this License.
+
+ 8. If the distribution and/or use of the Program is restricted in
+certain countries either by patents or by copyrighted interfaces, the
+original copyright holder who places the Program under this License
+may add an explicit geographical distribution limitation excluding
+those countries, so that distribution is permitted only in or among
+countries not thus excluded. In such case, this License incorporates the
+limitation as if written in the body of this License.
+
+ 9. The Free Software Foundation may publish revised and/or new
+versions of the General Public License from time to time. Such new
+versions will be similar in spirit to the present version, but may
+differ in detail to address new problems or concerns.
+
+Each version is given a distinguishing version number. If the Program
+specifies a version number of this License which applies to it and "any
+later version", you have the option of following the terms and
+conditions either of that version or of any later version published by
+the Free Software Foundation. If the Program does not specify a version
+number of this License, you may choose any version ever published by the
+Free Software Foundation.
+
+ 10. If you wish to incorporate parts of the Program into other free
+programs whose distribution conditions are different, write to the
+author to ask for permission. For software which is copyrighted by the
+Free Software Foundation, write to the Free Software Foundation; we
+sometimes make exceptions for this. Our decision will be guided by the
+two goals of preserving the free status of all derivatives of our free
+software and of promoting the sharing and reuse of software generally.
+
+ NO WARRANTY
+
+ 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO
+WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.
+EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR
+OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND,
+EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE
+ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH
+YOU. SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL
+NECESSARY SERVICING, REPAIR OR CORRECTION.
+
+ 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN
+WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY
+AND/OR REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR
+DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL
+DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE PROGRAM
+(INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED
+INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF
+THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS), EVEN IF SUCH HOLDER OR
+OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
+
+ END OF TERMS AND CONDITIONS
+
+ How to Apply These Terms to Your New Programs
+
+ If you develop a new program, and you want it to be of the greatest
+possible use to the public, the best way to achieve this is to make it
+free software which everyone can redistribute and change under these
+terms.
+
+ To do so, attach the following notices to the program. It is safest to
+attach them to the start of each source file to most effectively convey
+the exclusion of warranty; and each file should have at least the
+"copyright" line and a pointer to where the full notice is found.
+
+ <one line to give the program's name and a brief idea of what it>
+ does. Copyright (C) <year> <name of author >
+
+ 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
+
+
+Also add information on how to contact you by electronic and paper mail.
+
+If the program is interactive, make it output a short notice like this
+when it starts in an interactive mode:
+
+ Gnomovision version 69, Copyright (C) year name of author
+ Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type
+ `show w'. This is free software, and you are welcome to redistribute
+ it under certain conditions; type `show c' for details.
+
+The hypothetical commands `show w' and `show c' should show the
+appropriate parts of the General Public License. Of course, the commands
+you use may be called something other than `show w' and `show c'; they
+could even be mouse-clicks or menu items--whatever suits your program.
+
+You should also get your employer (if you work as a programmer) or your
+school, if any, to sign a "copyright disclaimer" for the program, if
+necessary. Here is a sample; alter the names:
+
+ Yoyodyne, Inc., hereby disclaims all copyright interest in the program
+ `Gnomovision' (which makes passes at compilers) written by James
+ Hacker.
+
+ <signature of Ty Coon>, 1 April 1989 Ty Coon, President of Vice
+
+This General Public License does not permit incorporating your program
+into proprietary programs. If your program is a subroutine library, you
+may consider it more useful to permit linking proprietary applications
+with the library. If this is what you want to do, use the GNU Library
+General Public License instead of this License.
Added: trunk/SConstruct
===================================================================
--- trunk/SConstruct (rev 0)
+++ trunk/SConstruct 2006-10-08 04:49:06 UTC (rev 2)
@@ -0,0 +1,42 @@
+#
+# Build file for Hexane. See COPYING for Licence details.
+# (C) Brian Ahr 2005 - 2006.
+#
+
+import os.path;
+
+env = Environment(
+ CC='gcc',
+ CCFLAGS='-O -g -Wall',
+ LIBS=["-lm", "-lbotan"]
+);
+
+#
+# Build Subdirectories
+#
+
+dirs = [
+ 'util',
+ 'engine',
+ 'session'
+# 'gui'
+];
+
+objs = []
+for dir in dirs:
+ script = os.path.join(dir,'SConscript');
+ objs += env.SConscript(script, exports='env');
+
+#
+# Build Hexane
+#
+
+hexane = env.Program(['hexane.cpp'] + objs);
+Default(hexane);
+
+#
+# Build Tests
+#
+
+env.SConscript('test/SConscript', exports=['env', 'objs']);
+
Added: trunk/TODO
===================================================================
--- trunk/TODO (rev 0)
+++ trunk/TODO 2006-10-08 04:49:06 UTC (rev 2)
@@ -0,0 +1,23 @@
+engine/hxtree
+--------------
+* Allow runtime configuration of HxTree options
+* Implement FreeAtEmpty in HxTree
+
+engine/engine
+-------------
+* Loading & Editing Files
+* Prebuffering
+* Page Cache
+* Limit Undo Levels
+
+engine/write, engine/writecopy
+------------------------------
+* Implement inplace, and copy methods for saving files
+
+engine/process
+--------------
+* implement process editing
+
+util/Hxml
+---------
+* add support for off64_t type
Added: trunk/docs/tree.dia
===================================================================
(Binary files differ)
Property changes on: trunk/docs/tree.dia
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Added: trunk/docs/uml.dia
===================================================================
(Binary files differ)
Property changes on: trunk/docs/uml.dia
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Added: trunk/engine/SConscript
===================================================================
--- trunk/engine/SConscript (rev 0)
+++ trunk/engine/SConscript 2006-10-08 04:49:06 UTC (rev 2)
@@ -0,0 +1,8 @@
+Import('env');
+
+objs = env.Object([
+ 'engine.cpp',
+ 'process.cpp'
+]);
+
+Return('objs');
Added: trunk/engine/engine.cpp
===================================================================
--- trunk/engine/engine.cpp (rev 0)
+++ trunk/engine/engine.cpp 2006-10-08 04:49:06 UTC (rev 2)
@@ -0,0 +1,521 @@
+/*
+ * Hexane Hex Editor. (C) Brian Ahr 2005-2006.
+ * Licensed and Distributed under GPL v2.
+ * See COPYING for details.
+ */
+
+#define _LARGEFILE_SOURCE
+#define _LARGEFILE64_SOURCE
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#include <algorithm>
+#include <vector>
+#include <stack>
+
+#include "../util/getopts.h"
+#include "../global.h"
+
+#include "hxtree.hxx"
+#include "engine.h"
+
+#define HX_FINDRESULT HxTree<Page *>::FindResult
+#define HX_LNODE(y) ((HxTree<Page *>::LeafNode *)(y))
+#define HX_INODE(y) ((HxTree<Page *>::InnerNode *)(y))
+#define HX_NODE(y) ((HxTree<Page *>::Node *)(y))
+
+// *******************************
+// Action Implementation
+// *******************************
+
+Action::Action(ActionType t, unsigned int length, unsigned char *data, off64_t addr) : type(t) {
+ this->length = length;
+ this->data = data;
+ this->address = addr;
+}
+
+Action::~Action() {
+ delete[] data;
+}
+
+void Action::undo(HxEngine *engine) {
+ switch(type) {
+ case INSERT:
+ engine->seek(address, SEEK_SET);
+ engine->remove(length);
+ break;
+ case DELETE:
+ engine->seek(address, SEEK_SET);
+ engine->insert(data, length);
+ break;
+ default:
+ break;
+ };
+}
+
+void Action::redo(HxEngine *engine) {
+ switch(type) {
+ case INSERT:
+ engine->seek(address, SEEK_SET);
+ engine->insert(data, length);
+ break;
+ case DELETE:
+ engine->seek(address, SEEK_SET);
+ engine->remove(length);
+ break;
+ default:
+ break;
+ };
+}
+
+// *******************************
+// Engine Implementation
+// *******************************
+
+HxEngine::HxEngine(off64_t pageSize, off64_t windowsize, unsigned int order) {
+ tree = new HxTree<Page *>();
+ undostack = new stack<Action *>();
+ redostack = new stack<Action *>();
+ pagecache = new map<off64_t, Page *>();
+
+ opts = GetOpts::Instance();
+
+ this->pagesize = pageSize;
+ this->windowsize = windowsize;
+ this->isopen = false;
+ this->offset = 0;
+ this->origfilesize = 0;
+ this->filesize = 0;
+ this->file = NULL;
+ this->numpages = 0;
+ this->pages = 0;
+ this->first = -1;
+ this->last = -1;
+}
+
+HxEngine::~HxEngine() {
+ if(isopen)
+ close();
+
+ delete tree;
+ delete pagecache;
+ delete undostack;
+ delete redostack;
+}
+
+bool HxEngine::can_undo() {
+ return !(undostack->empty());
+}
+
+bool HxEngine::can_redo() {
+ return !(redostack->empty());
+}
+
+bool HxEngine::undo() {
+ if(!isopen || undostack->empty())
+ return false;
+
+ Action *a = undostack->top();
+ undostack->pop();
+
+ a->undo(this);
+ redostack->push(a);
+
+ return true;
+}
+
+bool HxEngine::redo() {
+ if(!isopen || redostack->empty())
+ return false;
+
+ Action *a = redostack->top();
+ redostack->pop();
+
+ a->redo(this);
+ undostack->push(a);
+
+ return true;
+}
+
+bool HxEngine::open(char *filename, bool readonly) {
+ if(!filename)
+ return false;
+
+ // close any existing files
+ if(isopen) {
+ if(!close())
+ return false;
+ }
+
+ // stat the file
+ struct stat buf;
+ int i = stat(filename, &buf);
+
+ if(i == 0) {
+ this->filename.assign(filename);
+ this->filesize = buf.st_size;
+ this->origfilesize = buf.st_size;
+
+ if(filesize)
+ this->numpages = filesize / pagesize + 1;
+
+ } else {
+ return false;
+ }
+
+ // call fopen()
+ if(readonly)
+ file = fopen64(this->filename.c_str(), "rb");
+ else
+ file = fopen64(this->filename.c_str(), "rb+");
+
+ // if error, unset the stuff we changed
+ if(!file) {
+ filesize = 0;
+ origfilesize = 0;
+ this->filename.clear();
+ return false;
+ }
+
+ this->readonly = readonly;
+ isopen = true;
+ return true;
+}
+
+// return true on success
+bool HxEngine::close() {
+ if(isopen) {
+ filename.clear();
+ tree->clear();
+
+ isopen = false;
+ first = -1;
+ last = -1;
+ filesize = 0;
+ origfilesize = 0;
+ offset = 0;
+
+ while(! undostack->empty()) {
+ Action *a = undostack->top();
+ undostack->pop();
+ delete a;
+ }
+
+ while(! redostack->empty()) {
+ Action *a = redostack->top();
+ redostack->pop();
+ delete a;
+ }
+
+ if(!fclose(file))
+ return false;
+
+ return true;
+ }
+
+ return false;
+}
+
+bool HxEngine::eof() {
+ if(!isopen)
+ return false;
+
+ return _eof;
+}
+
+off64_t HxEngine::tell() {
+ if(!isopen)
+ return -1;
+
+ return offset;
+}
+
+string *HxEngine::off64t_to_a(off64_t n) {
+ const char *digits = "0123456789";
+ string *result = new string();
+
+ do {
+ result->append(1, digits[n % 10]);
+ } while((n /= 10) > 0);
+
+ reverse(result->begin(), result->end());
+ return result;
+}
+
+string *HxEngine::tempname(off64_t n) {
+ string *idxstr = off64t_to_a(n);
+ idxstr->insert(0, ".");
+ idxstr->insert(0, filename);
+ idxstr->insert(0, "/");
+// idxstr->insert(0, opts->tmpdir); // TODO: FIXME
+ return idxstr;
+}
+
+bool HxEngine::spacefor(off64_t length) {
+ if(length <= dist(windowsize, loadeddata) && loadeddata < windowsize)
+ return true;
+
+ return false;
+}
+
+off64_t HxEngine::dist(off64_t a, off64_t b) {
+ return (a > b) ? a - b : b - a ;
+}
+
+// *******************************
+// Core Routines
+// *******************************
+
+// NOTE: call with index of page in file, not in tree!
+bool HxEngine::load_page(off64_t idx) {
+ if(!isopen || idx < 0 || idx > numpages)
+ return false;
+
+ if(idx >= first || idx <= last)
+ return true;
+
+ struct stat buf;
+ string *name = tempname(idx);
+ int i = stat(name->c_str(), &buf);
+ off64_t weight = (i == 0)? buf.st_size : pagesize;
+
+ if(weight > windowsize) {
+ delete name;
+ printf("Error: Page larger than windowsize!\n");
+ return false;
+ }
+
+ while(!spacefor(weight)) {
+ if(dist(first, idx) > dist(last, idx))
+ unload_page(first);
+ else
+ unload_page(last);
+ }
+
+ Page *p = new Page();
+ p->reserve( weight * sizeof(unsigned char) );
+
+ if(i == 0) {
+ FILE *tmp = fopen64(name->c_str(), "rb");
+ unsigned char buf[pagesize];
+ off64_t read = 0;
+
+ while(read < weight) {
+ size_t in = fread(&(buf[0]), sizeof(unsigned char), pagesize, tmp);
+
+ for(unsigned int i = 0; i < in; i++)
+ p->push_back(buf[i]);
+
+ read += in;
+ }
+
+ fclose(tmp);
+ p->set_dirty();
+ } else {
+ unsigned char buf[pagesize];
+ off64_t pageoffset = idx * pagesize;
+ size_t in = 0;
+
+ fseeko(file, pageoffset, SEEK_SET);
+ in = fread(&(buf[0]), sizeof(unsigned char), pagesize, file);
+
+ for(unsigned int i = 0; i < in; i++)
+ p->push_back(buf[i]);
+ }
+
+ if(idx == first - 1) {
+ first--;
+ offset -= p->size();
+ tree->insert(0, weight, p);
+ } else if(idx == last + 1) {
+ last++;
+ tree->insert(last - first + 1, weight, p);
+ }
+
+ loadeddata += p->size();
+ pages++;
+
+ delete name;
+ return true;
+}
+
+// NOTE: call with index of page in file, not in tree!
+bool HxEngine::unload_page(off64_t idx) {
+ if(!isopen || idx < 0 || idx > numpages)
+ return false;
+
+ if(idx < first || idx > last)
+ return false;
+
+ Page *p = tree->at(idx);
+ tree->remove(idx);
+
+ if(p->is_dirty()) {
+ string *tmpname = tempname(idx);
+ FILE *out = fopen64(tmpname->c_str(), "wb");
+ fwrite(&(p[0]), sizeof(unsigned char), p->size(), file);
+ fclose(out);
+ delete tmpname;
+ }
+
+ if(idx == first) {
+ first++;
+ offset += p->size();
+ } else if(idx == last)
+ last--;
+
+ loadeddata -= p->size();
+ pages--;
+
+ delete p;
+ return true;
+}
+
+off64_t HxEngine::seek(off64_t delta, int whence) {
+ if(!isopen)
+ return -1;
+
+ off64_t dest_addr = 0;
+ switch(whence) {
+ case SEEK_SET:
+ if(delta >= 0)
+ dest_addr = delta;
+ break;
+
+ case SEEK_CUR:
+ if(cursor + delta >= 0)
+ dest_addr = cursor + delta;
+ break;
+
+ case SEEK_END:
+ if(filesize + delta >= 0)
+ dest_addr = filesize + delta;
+ break;
+
+ default:
+ return -1;
+ break;
+ }
+
+ // examine window and load or unload pages accordingly
+
+ cursor = dest_addr;
+ _eof = false;
+ return offset;
+}
+
+bool HxEngine::can_read(off64_t count) {
+ return offset + count < offset + tree->totalWeight();
+}
+
+off64_t HxEngine::read(unsigned char *dest, off64_t length) {
+ if(!isopen || dest == NULL || length < 0)
+ return -1;
+
+ // check that we can read length bytes
+ // if not, set length to max bytes we can read
+
+ // check if the read spans multiple pages
+ // if so
+ // get list of pages
+ // check that necessary pages are loaded
+
+ // for each page in list
+ // read page contents into dest
+ // update number of bytes left to read
+
+ *dest = 0;
+
+ return 0;
+}
+
+off64_t HxEngine::insert(unsigned char *buf, off64_t length, bool undoable) {
+ if(!isopen || buf == NULL || readonly || length < 0)
+ return -1;
+
+ if(undoable) {
+ undostack->push(new Action(INSERT, length, buf, cursor));
+ }
+
+ HX_FINDRESULT *marker = tree->find_address(cursor);
+
+ Page *p = HX_LNODE(marker->node)->pages[marker->node_index];
+
+ for(off64_t i = 0; i < length; i++)
+ p->insert(p->begin() + marker->local_index + i, buf[i]);
+
+ p->set_dirty();
+
+ tree->updateWeight(HX_LNODE(marker->node), marker->node_index, length);
+
+ delete marker;
+ return 0;
+}
+
+off64_t HxEngine::overwrite(unsigned char *buf, off64_t bufsize, off64_t length, bool undoable) {
+ if(!isopen || buf == NULL || readonly || bufsize < 0)
+ return -1;
+
+ length = (length == -1) ? bufsize : length;
+
+ // TODO: check that we can overwite length
+ // TODO: check if overwrite spans multiple pages
+ // TODO: handle overwrite spanning multiple pages
+
+ if(undoable) {
+ unsigned char *data = new unsigned char[length];
+ read(data, length);
+
+ undostack->push(new Action(DELETE, length, data, cursor));
+ undostack->push(new Action(INSERT, bufsize, buf, cursor));
+ }
+
+ HX_FINDRESULT *marker = tree->find_address(cursor);
+
+ Page *p = HX_LNODE(marker->node)->pages[marker->node_index];
+ p->erase(p->begin() + marker->local_index, p->begin() + marker->local_index + length);
+
+ for(off64_t i = 0; i < bufsize; i++)
+ p->insert(p->begin() + marker->local_index + i, buf[i]);
+
+ p->set_dirty();
+
+ tree->updateWeight(HX_LNODE(marker->node), marker->node_index, bufsize - length);
+
+ delete marker;
+ return 0;
+}
+
+off64_t HxEngine::remove(off64_t length, bool undoable) {
+ if(!isopen || readonly || length < 0)
+ return -1;
+
+ // TODO: check that we can remove length
+ // TODO: check if remove spans multiple pages
+ // TODO: handle remove spanning multiple pages
+
+ if(undoable) {
+ unsigned char *data = new unsigned char[length];
+ read(data, length);
+
+ undostack->push(new Action(DELETE, length, data, cursor));
+ }
+
+ HX_FINDRESULT *marker = tree->find_address(cursor);
+
+ Page *p = HX_LNODE(marker->node)->pages[marker->node_index];
+ p->erase(p->begin() + marker->local_index, p->begin() + marker->local_index + length);
+ p->set_dirty();
+
+ tree->updateWeight(HX_LNODE(marker->node), marker->node_index, -length);
+
+ delete marker;
+ return 0;
+}
+
Added: trunk/engine/engine.h
===================================================================
--- trunk/engine/engine.h (rev 0)
+++ trunk/engine/engine.h 2006-10-08 04:49:06 UTC (rev 2)
@@ -0,0 +1,140 @@
+/*
+ * Hexane Hex Editor. (C) Brian Ahr 2005-2006.
+ * Licensed and Distributed under GPL v2.
+ * See COPYING for details.
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#include <vector>
+#include <string>
+#include <stack>
+#include <map>
+
+#include "../util/getopts.h"
+#include "hxtree.hxx"
+
+#ifndef _HXENGINE_
+#define _HXENGINE_
+
+using namespace std;
+
+class HxEngine;
+
+typedef bool (*export_func)(char *filename, HxEngine *engine, off64_t start, off64_t end);
+
+class Page : public vector<unsigned char> {
+ private:
+ bool changed;
+
+ public:
+
+ Page() : vector<unsigned char>() {
+ changed = false;
+ }
+
+ bool is_dirty() {
+ return changed;
+ }
+
+ void set_dirty() {
+ changed = true;
+ }
+
+ void clear_dirty() {
+ changed = false;
+ }
+};
+
+enum ActionType {
+ INSERT,
+ DELETE,
+};
+
+class Action {
+ public:
+ const ActionType type;
+ unsigned char *data;
+ int length;
+ off64_t address;
+
+ Action(ActionType t, unsigned int length, unsigned char *data, off64_t addr);
+ ~Action();
+ void undo(HxEngine *engine);
+ void redo(HxEngine *engine);
+};
+
+class HxEngine {
+ private:
+ HxTree<Page *> *tree;
+ stack<Action *> *undostack;
+ stack<Action *> *redostack;
+ map<off64_t, Page *> *pagecache;
+
+ FILE *file; // file pointer
+ string filename; // file name
+ bool readonly; // open in readonly mode?
+ bool isopen; // is the file open?
+ bool _eof; // have we seen EOF ?
+
+ off64_t cursor; // current cursor position
+ off64_t offset; // start address (leftmost page)
+ off64_t filesize; // current file size
+ off64_t origfilesize; // unmodified file size
+
+ off64_t windowsize; // total amount of data to keep in RAM
+ off64_t loadeddata; // total amount of data currently in RAM
+
+ off64_t cachesize; // current size of page cache
+ off64_t maxcachesize; // max size of page cache
+
+ off64_t undosize; // current size of undo stack
+ off64_t redosize; // current size of redo stack
+ off64_t maxundosize; // max size of undo+redo stacks
+ off64_t maxundodepth; // max depth of undo+redo stacks
+
+ off64_t pagesize; // page size (kB) - should not be more than about 40Mb
+ off64_t numpages; // number of pages in the file
+ off64_t pages; // number of pages currently loaded
+ off64_t first; // index of leftmost tree page, relative to file
+ off64_t last; // index of rightmost tree page, relative to file
+
+ GetOpts *opts;
+
+ protected:
+ bool load_page(off64_t idx);
+ bool unload_page(off64_t idx);
+
+ public:
+ HxEngine(off64_t pageSize = 4096, off64_t windowsize = 50, unsigned int order = 4);
+ ~HxEngine();
+
+ bool open(char *filename, bool readOnly = false);
+ bool close();
+
+ bool can_undo();
+ bool can_redo();
+ bool undo();
+ bool redo();
+
+ bool eof();
+ off64_t tell();
+
+ off64_t seek(off64_t offset, int whence);
+ off64_t read(unsigned char *buf, off64_t count);
+ off64_t insert(unsigned char *buf, off64_t count, bool undoable=true);
+ off64_t overwrite(unsigned char *buf, off64_t bufsize, off64_t length=-1, bool undoable=true);
+ off64_t remove(off64_t count, bool undoable=true);
+
+ bool can_read(off64_t count);
+ bool spacefor(off64_t length);
+ string *off64t_to_a(off64_t n);
+ string *tempname(off64_t n);
+ off64_t dist(off64_t a, off64_t b);
+};
+
+#endif
+
Added: trunk/engine/hxtree.hxx
===================================================================
--- trunk/engine/hxtree.hxx (rev 0)
+++ trunk/engine/hxtree.hxx 2006-10-08 04:49:06 UTC (rev 2)
@@ -0,0 +1,926 @@
+/*
+ * Hexane Hex Editor. (C) Brian Ahr 2005-2006.
+ * Licensed and Distributed under GPL v2.
+ * See COPYING for details.
+ */
+
+// ********************************************************************
+// HxTree - The main engine data structure used in Hexane.
+//
+// This class implements a self-balancing tree based on a B+ Tree.
+// More specifically, this is basically an augmented B+ tree; ie,
+// a B+ tree with the following power-ups:
+//
+// - Instead of the normal sequence set, (ie, singly-linked
+// list of leaf nodes) this implementation uses a doubly
+// linked list, allowing forwards and backwards traversal.
+//
+// - All nodes have parent pointers
+//
+// - There are no keys stored in this tree, only values. The
+// tree uses relative addressing (from the front of the tree)
+// to determine the address of the desired data in the tree.
+//
+// Leaf nodes store multiple pages of data. Each page has a
+// length. The "weight" of a leaf node is the sum of the
+// lengths of the pages it contains. Similarly, the weight
+// of an inner node is the sum of the weights of the children
+// it contains. A particular address can be found by using a
+// level-wise traversal of the tree, and summing up the weights
+// of the nodes, to locate the desired leaf node and page. A
+// similar scheme is used to index the pages sequentially.
+//
+//
+// ******** TODO ********
+// - change tree_size to hold number of leafnodes in the tree
+// - Documentation
+// - Allow specification of order at runtime (via template?)
+// - Allow specification of address type (via template?)
+// - implement FreeAtEmpty
+//
+// ******* TODO: Someday ******
+// - fix cheap hack (How to do this??)
+// - multithreading
+//
+// ********************************************************************
+//
+// Available Functions:
+// template <class Type> class HxTree {
+// HxTree();
+// ~HxTree();
+//
+// FindResult *find_address(unsigned int address);
+// FindResult *find_index(unsigned int index);
+// Type at(int index);
+// Type containing_address(int address);
+//
+// void insert(unsigned int index, unsigned int weight, Type entry);
+// bool remove(unsigned int index);
+//
+// int getMaxEntries();
+// int depth();
+// int size(); // number of nodes in the tree
+// int subnodes(); // get number of Type in the tree
+// int totalWeight();
+// bool isEmpty();
+// void clear();
+//
+// void recalculateWeight(Node *node);
+// void weightChanged(LeafNode *leaf);
+//
+// #if HAVE_PRINT
+// void print(void (p(Type t)));
+// #endif
+// };
+//
+// ********************************************************************
+
+#include <stdio.h>
+#include <stdlib.h>
+
+using namespace std;
+
+#ifndef _HXTREE_
+#define _HXTREE_
+
+// **************************************
+// Configuration
+// **************************************
+
+// Order of the tree (must be at least 4)
+#define MAX_ENTRIES 4
+
+// Set this to (MAX_ENTRIES / 2)
+#define MIN_ENTRIES 2
+
+// include the code to print the tree?
+#define HAVE_PRINT 1
+
+// Should the tree call delete() on Type data ??
+#define FREEDATA 0
+
+// set this to delete[] if you want to store
+// dynamic arrays in the tree (eg. char*)
+#define DELETECMD delete
+
+// **************************************
+// Useful Shortcuts
+// **************************************
+#define MAX(x,y) (((x) > (y)) ? (x) : (y))
+#define LNODE(x) ((LeafNode *)x)
+#define INODE(x) ((InnerNode *)x)
+#define NODE(x) ((Node *)x)
+
+enum NodeType { INNER = 0x90DE, LEAF = 0x134F };
+
+// fix a compiling problem if Type is scalar
+#ifdef NULL
+ #undef NULL
+ #define NULL 0
+#endif
+
+template <class Type> class HxTree {
+
+ // **************************************
+ // Construction
+ // **************************************
+
+ public:
+ HxTree() {
+ tree_size = 0;
+ tree_depth = 0;
+ root = new LeafNode(NULL);
+ }
+
+ ~HxTree() {
+ if(root) {
+ if(root->isa(LEAF))
+ delete LNODE(root);
+ else
+ delete INODE(root);
+ }
+ }
+
+ // **************************************
+ // Declarations
+ // **************************************
+
+ struct Node {
+ const NodeType type;
+ unsigned int size;
+ unsigned int weight;
+ unsigned int subnodes;
+ Node *parent;
+
+ Node(NodeType t, Node *a_parent) : type(t) {
+ parent = a_parent;
+ size = 0;
+ weight = 0;
+ subnodes = 0;
+ }
+
+ ~Node() {
+ }
+
+ bool isa(NodeType t) {
+ return type == t;
+ }
+ };
+
+ struct InnerNode : Node {
+ Node *children[MAX_ENTRIES + 1];
+
+ InnerNode(Node *parent) : Node(INNER, parent) {
+ for(unsigned int i = 0; i < MAX_ENTRIES + 1; i++)
+ children[i] = NULL;
+ }
+
+ ~InnerNode() {
+ for(unsigned int i = 0; i < size; i++) {
+ if(children[i]->type == INNER)
+ delete INODE(children[i]);
+ else
+ delete LNODE(children[i]);
+ }
+ }
+ };
+
+ struct LeafNode : Node {
+ unsigned int weights[MAX_ENTRIES + 1];
+ Type pages[MAX_ENTRIES + 1];
+ LeafNode *prev;
+ LeafNode *next;
+
+ LeafNode(Node *parent) : Node(LEAF, parent) {
+ prev = NULL;
+ next = NULL;
+ for(unsigned int i = 0; i < MAX_ENTRIES + 1; i++)
+ pages[i] = 0;
+ }
+
+ ~LeafNode() {
+ #if FREEDATA
+ for(unsigned int i = 0; i < size; i++) {
+ if(pages[i])
+ DELETECMD pages[i];
+ }
+ #endif
+ }
+ };
+
+ struct FindResult {
+ unsigned int local_index; // index (in container) of desired item
+ unsigned int node_index; // index (in node) of the container holding desired item
+ Node *node;
+
+ FindResult(unsigned int local, unsigned int idx, Node *n) {
+ local_index = local;
+ node_index = idx;
+ node = n;
+ }
+
+ ~FindResult() {
+ }
+ };
+
+ // **************************************
+ // Search
+ // **************************************
+
+ FindResult *find_address(unsigned int address) {
+ InnerNode *inner;
+ Node *node = root;
+ unsigned int d = tree_depth;
+ unsigned int addr = 0;
+
+ while(d-- != 0) {
+ inner = INODE(node);
+
+ for(unsigned int i = 0; i < inner->size; i++) {
+ if(address < addr + inner->children[i]->weight) {
+ node = inner->children[i];
+ break;
+ } else {
+ addr += inner->children[i]->weight;
+ }
+ }
+ }
+
+ if(! node->isa(LEAF))
+ return NULL;
+
+ for(unsigned int i = 0; i < node->size; i++) {
+ if(address < addr + LNODE(node)->weights[i]) {
+ return new FindResult(address-addr, i, node);
+ } else {
+ addr += LNODE(node)->weights[i];
+ }
+ }
+
+ return NULL; //LNODE(node);
+ }
+
+ FindResult *find_index(unsigned int index) {
+ Node *inner = NODE(root);
+ unsigned int d = tree_depth;
+ unsigned int addr = 0;
+
+ while(d-- != 0) {
+ if(inner->isa(LEAF))
+ break;
+
+ for(unsigned int i = 0; i < INODE(inner)->size; i++) {
+ if(index < addr + INODE(inner)->children[i]->subnodes) {
+ inner = INODE(inner)->children[i];
+ break;
+ } else {
+ addr += INODE(inner)->children[i]->subnodes;
+ }
+ }
+ }
+
+ if(! inner->isa(LEAF))
+ return NULL;
+
+ for(unsigned int i = 0; i < inner->size; i++) {
+ if(index < addr + LNODE(inner)->weights[i]) {
+ return new FindResult(index-addr, i, inner);
+ } else {
+ addr += LNODE(inner)->weights[i];
+ }
+ }
+
+ return NULL; //LNODE(inner);
+ }
+
+ Type at(int index) {
+ FindResult *result = find_index(index);
+
+ if(!result)
+ return NULL;
+
+ Type t = LNODE(result->node)->pages[result->node_index];
+ delete result;
+ return t;
+ }
+
+ Type containing_address(int address) {
+ FindResult *result = find_address(address);
+
+ if(!result)
+ return NULL;
+
+ Type t = LNODE(result->node)->pages[result->node_index];
+ delete result;
+ return t;
+ }
+
+ // FIXME: A bug somewhere causes this method not not work correctly
+ //
+ // Symptoms:
+ // - insert only works if the following line is:
+ // if(index <= addr + start->children[i]->subnodes) {
+ // - remove only works if that same line is:
+ // if(index <= addr + start->children[i]->subnodes -1) {
+ //
+ // Workaround:
+ // - set the hack variable accordingly
+ //
+ // Verification:
+ // - the remove bug is evident by enabling INSERT_ZERO_TESTS
+ // followed by a remove(5), remove(3)
+ // - the insert bug is evident by enabling the APPEND_TESTS
+ FindResult *next_level_by_index(InnerNode *start, unsigned int index, int hack = 0) {
+ if(start->isa(LEAF)) {
+ return NULL;
+ } else if(start->subnodes >= index && index >= 0) {
+ unsigned int addr = 0;
+ for(unsigned int i = 0; i < start->size; i++) {
+ if(index <= addr + start->children[i]->subnodes - hack) { // BUG: Obob on insert(), if appending to a full node
+ return new FindResult(index-addr, i, start->children[i]);
+ } else {
+ addr += start->children[i]->subnodes;
+ }
+ }
+ }
+ // out of bounds
+ return NULL;
+ }
+
+ // **************************************
+ // Insert
+ // **************************************
+
+ void insert(unsigned int index, unsigned int weight, Type entry) {
+ if(index < 0 || index > tree_size + 1) {
+ printf(" %%%%%%%%%%%%%% Insert Address out of bounds! %%%%%%%%%%%%%%\n");
+ return;
+ }
+
+ Node *ins = insert(root, entry, index, weight);
+
+ if(ins != NULL) {
+ InnerNode *new_root = new InnerNode(NULL);
+ new_root->children[0] = root;
+ new_root->children[0]->parent = new_root;
+ new_root->children[1] = ins;
+ new_root->children[1]->parent = new_root;
+ new_root->size = 2;
+ new_root->subnodes = new_root->children[0]->subnodes + new_root->children[1]->subnodes;
+ new_root->weight = new_root->children[0]->weight + new_root->children[1]->weight;
+ root = new_root;
+ tree_depth++;
+ }
+ }
+
+ Node *insert(Node *node, Type entry, unsigned int index, unsigned int weight) {
+ if(node->isa(LEAF)) {
+ for(unsigned int i = node->size; i > index; --i) {
+ LNODE(node)->pages[i] = LNODE(node)->pages[i - 1];
+ LNODE(node)->weights[i] = LNODE(node)->weights[i-1];
+ }
+
+ LNODE(node)->pages[index] = entry;
+ LNODE(node)->weights[index] = weight;
+ node->weight += weight;
+ node->subnodes++;
+ tree_size++;
+
+ if(node->size < MAX_ENTRIES) {
+ node->size++;
+ return NULL;
+ } else {
+ LeafNode *new_leaf = new LeafNode(node->parent);
+ index = 0;
+
+ for(int i = MIN_ENTRIES; i <= MAX_ENTRIES; ++i) {
+ new_leaf->weights[index] = LNODE(node)->weights[i];
+ new_leaf->pages[index] = LNODE(node)->pages[i];
+ new_leaf->subnodes++;
+ LNODE(node)->pages[i] = NULL;
+ node->subnodes--;
+ node->weight -= LNODE(node)->weights[i];
+ new_leaf->weight += LNODE(node)->weights[i];
+ LNODE(node)->weights[i] = 0;
+ index++;
+ }
+
+ node->size = MIN_ENTRIES;
+ new_leaf->size = index;
+
+ new_leaf->next = LNODE(node)->next;
+ new_leaf->prev = LNODE(node);
+ if(LNODE(node)->next)
+ LNODE(node)->next->prev = new_leaf;
+ LNODE(node)->next = new_leaf;
+ return new_leaf;
+ }
+ } else {
+ FindResult *r = next_level_by_index(INODE(node), index);
+
+ if(r == NULL || r->node == NULL) {
+ printf("\n\n%%%%%%%%%%%% ERROR %%%%%%%%%%%%%%%%\n\n"); // TODO
+ exit(1);
+ }
+
+ Node *ins = insert(r->node, entry, r->local_index, weight);
+
+ if(ins == NULL) {
+ node->subnodes++;
+ node->weight += weight;
+ delete r;
+ return NULL;
+ }
+
+ int idx = r->node_index + 1;
+ for(int i = node->size; i > idx; --i) {
+ INODE(node)->children[i] = INODE(node)->children[i-1];
+ }
+
+ INODE(node)->children[idx] = ins;
+ node->subnodes++;
+ node->weight += weight;
+ delete r;
+
+ if(node->size < MAX_ENTRIES) {
+ node->size++;
+ return NULL;
+ } else {
+ InnerNode *new_node = new InnerNode(node->parent);
+ index = 0;
+
+ for(int i = MIN_ENTRIES; i <= MAX_ENTRIES; ++i) {
+ new_node->children[index] = INODE(node)->children[i];
+ new_node->children[index]->parent = new_node;
+ new_node->subnodes += INODE(node)->children[i]->subnodes;
+ node->subnodes -= INODE(node)->children[i]->subnodes;
+ new_node->weight += INODE(node)->children[i]->weight;
+ node->weight -= INODE(node)->children[i]->weight;
+ INODE(node)->children[i] = NULL;
+ index++;
+
+ }
+
+ node->size = MIN_ENTRIES;
+ new_node->size = index;
+
+ return new_node;
+ }
+ }
+ }
+
+ // **************************************
+ // Remove
+ // **************************************
+
+ bool remove(unsigned int index) {
+ return remove(root, NULL, NULL, NULL, NULL, index);
+ }
+
+ bool remove(Node *node, Node *left_node, Node *right_node, Node *left_anchor, Node *right_anchor, unsigned int index) {
+ if(node->isa(INNER)) {
+ FindResult *r = next_level_by_index(INODE(node), index, 1);
+ unsigned int child_index = r->node_index;
+ Node *next_node = r->node;
+
+ Node *next_left, *next_right, *next_left_anchor, *next_right_anchor;
+ if(child_index == 0) {
+ next_left = (left_node != NULL) ? INODE(left_node)->children[left_node->size] : NULL;
+ next_left_anchor = left_anchor;
+ } else {
+ next_left = INODE(node)->children[child_index - 1];
+ next_left_anchor = node;
+ }
+
+ if(child_index == node->size) {
+ next_right = (right_node != NULL)? INODE(right_node)->children[0] : NULL;
+ next_right_anchor = right_anchor;
+ } else {
+ next_right = INODE(node)->children[child_index + 1];
+ next_right_anchor = node;
+ }
+
+ bool removed = remove(next_node, next_left, next_right, next_left_anchor, next_right_anchor, r->local_index);
+
+ if(node == root) {
+ if(node->size == 1) {
+ Node *temp = root;
+ root = INODE(node)->children[0];
+ root->parent = NULL;
+ temp->size = 0;
+ delete temp;
+ } else {
+ recalculateWeight(node);
+ }
+ } else if(node->size < MIN_ENTRIES) {
+ Node *max_neighbor = (left_node != NULL)? left_node : right_node;
+ if((right_node != NULL) && (right_node->size > max_neighbor->size)) {
+ max_neighbor = right_node;
+ }
+
+ if(max_neighbor->size > MIN_ENTRIES) {
+ if(max_neighbor == left_node) {
+ shiftNonLeaf(node, left_node, left_anchor, false);
+ } else {
+ shiftNonLeaf(node, right_node, right_anchor, true);
+ }
+ } else {
+ if(node->parent == left_anchor) {
+ mergeNonLeaf(left_node, node, left_anchor);
+ } else {
+ mergeNonLeaf(node, right_node, right_anchor);
+ }
+ }
+ } else {
+ recalculateWeight(node);
+ }
+ delete r;
+ return removed;
+ } else {
+ unsigned int delete_index = index;
+
+ if((delete_index >= node->size)) {
+ return false;
+ }
+
+ #if FREEDATA
+ Type deleted = LNODE(node)->pages[delete_index];
+ DELETECMD deleted;
+ #endif
+
+ unsigned int weight = LNODE(node)->weights[delete_index];
+
+ for(unsigned int i = delete_index + 1; i <= node->size; ++i) {
+ LNODE(node)->pages[i-1] = LNODE(node)->pages[i];
+ LNODE(node)->weights[i-1] = LNODE(node)->weights[i];
+ }
+
+ node->size--;
+ tree_size--;
+ node->weight -= weight;
+ node->subnodes--;
+ LNODE(node)->pages[node->size] = NULL;
+ LNODE(node)->weights[node->size] = 0;
+
+ if((node != root) && (node->size < MIN_ENTRIES)) {
+ Node *max_neighbor = (left_node != NULL)? left_node : right_node;
+ if((right_node != NULL) && (right_node->size > max_neighbor->size)) {
+ max_neighbor = right_node;
+ }
+
+ if(max_neighbor->size > MIN_ENTRIES) {
+ if(max_neighbor == left_node) {
+ shiftLeaf(node, left_node, left_anchor, false);
+ } else {
+ shiftLeaf(node, right_node, right_anchor, true);
+ }
+ } else {
+ if(node->parent == left_anchor) {
+ mergeLeaf(left_node, node, left_anchor);
+ } else {
+ mergeLeaf(node, right_node, right_anchor);
+ }
+ }
+ }
+ return true;
+ }
+ }
+
+ void shiftLeaf(Node *node, Node *neighbor_node, Node *anchor_node, bool copy_from_right) {
+ unsigned int num_copy = (neighbor_node->size + 1 - node->size) / 2;
+
+ if(copy_from_right) {
+ for(unsigned int i = 0; i < num_copy; ++i) {
+ LNODE(node)->pages[node->size + i] = LNODE(neighbor_node)->pages[i];
+ LNODE(node)->weights[node->size + i] = LNODE(neighbor_node)->weights[i];
+ }
+
+ for(unsigned int i = 0; i < neighbor_node->size - num_copy; ++i) {
+ LNODE(neighbor_node)->pages[i] = LNODE(neighbor_node)->pages[i + num_copy];
+ LNODE(neighbor_node)->weights[i] = LNODE(neighbor_node)->weights[i + num_copy];
+ }
+
+ for(unsigned int i = neighbor_node->size - num_copy; i < neighbor_node->size; ++i) {
+ LNODE(neighbor_node)->pages[i] = NULL;
+ LNODE(neighbor_node)->weights[i] = 0;
+ }
+
+ } else {
+ for(int i = node->size -1; i >= 0; --i) {
+ LNODE(node)->pages[i + num_copy] = LNODE(node)->pages[i];
+ LNODE(node)->weights[i + num_copy] = LNODE(node)->weights[i];
+ }
+
+ for(unsigned int i = 0; i < num_copy; ++i) {
+ LNODE(node)->pages[i] = LNODE(neighbor_node)->pages[neighbor_node->size - num_copy + i];
+ LNODE(neighbor_node)->pages[neighbor_node->size - num_copy + i] = NULL;
+
+ LNODE(node)->weights[i] = LNODE(neighbor_node)->weights[neighbor_node->size - num_copy + i];
+ LNODE(neighbor_node)->weights[neighbor_node->size - num_copy + i] = 0;
+ }
+
+ }
+
+ node->size += num_copy;
+ neighbor_node->size -= num_copy;
+
+ recalculateWeight(node);
+ recalculateWeight(neighbor_node);
+ }
+
+ void shiftNonLeaf(Node *node, Node *neighbor_node, Node *anchor_node, bool copy_from_right) {
+ unsigned int num_copy = (neighbor_node->size + 1 - node->size) / 2;
+
+ if(copy_from_right) {
+
+ for(unsigned int i = 0; i < num_copy ; ++i) {
+ INODE(node)->children[node->size + i] = INODE(neighbor_node)->children[i];
+ INODE(node)->children[node->size + i]->parent = node;
+ }
+
+ for(unsigned int i = 0; i < neighbor_node->size - num_copy; ++i) {
+ INODE(neighbor_node)->children[i] = INODE(neighbor_node)->children[i + num_copy];
+ }
+
+ INODE(neighbor_node)->children[neighbor_node->size - num_copy] =
+ INODE(neighbor_node)->children[neighbor_node->size];
+
+ for(unsigned int i = neighbor_node->size - num_copy; i < neighbor_node->size; ++i) {
+ INODE(neighbor_node)->children[i + 1] = NULL;
+ }
+ } else {
+ INODE(node)->children[node->size + num_copy] = INODE(node)->children[node->size];
+
+ for(int i = node->size - 1; i >= 0; --i) {
+ INODE(node)->children[i + num_copy] = INODE(node)->children[i];
+ }
+
+ for(unsigned int i = 0; i < num_copy; ++i) {
+ INODE(node)->children[i] = INODE(neighbor_node)->children[neighbor_node->size - num_copy + i];
+ INODE(neighbor_node)->children[neighbor_node->size - num_copy + i] = NULL;
+ INODE(node)->children[i]->parent = node;
+ }
+ }
+
+ node->size += num_copy;
+ neighbor_node->size -= num_copy;
+
+ recalculateWeight(node);
+ recalculateWeight(neighbor_node);
+ }
+
+ void mergeLeaf(Node *left_node, Node *right_node, Node *parent_node) {
+ int sep_pos = -1;
+
+ for(unsigned int i = 0; i < parent_node->size; i++) {
+ if(INODE(parent_node)->children[i] == right_node) {
+ sep_pos = i;
+ break;
+ }
+ }
+
+ if(sep_pos == -1) {
+ printf("RIGHT_NODE index not found in parent! Aborting!\n");
+ exit(1);
+ }
+
+ for(unsigned int i = sep_pos; i < parent_node->size; ++i) {
+ INODE(parent_node)->children[i] = INODE(parent_node)->children[i + 1];
+ }
+ INODE(parent_node)->children[parent_node->size-1] = NULL;
+
+ for(unsigned int i = 0; i < right_node->size; ++i) {
+ LNODE(left_node)->pages[left_node->size + i] = LNODE(right_node)->pages[i];
+ LNODE(left_node)->weights[left_node->size + i] = LNODE(right_node)->weights[i];
+ }
+
+ left_node->size += right_node->size;
+ parent_node->size--;
+ LNODE(left_node)->next = LNODE(right_node)->next;
+
+ if(LNODE(right_node)->next)
+ LNODE(right_node)->next->prev = LNODE(left_node);
+
+ recalculateWeight(left_node);
+
+ right_node->size = 0;
+ delete right_node;
+ }
+
+ void mergeNonLeaf(Node *left_node, Node *right_node, Node *parent_node) {
+ int sep_pos = -1;
+
+ for(unsigned int i = 0; i < parent_node->size; i++) {
+ if(INODE(parent_node)->children[i] == right_node) {
+ sep_pos = i;
+ break;
+ }
+ }
+
+ if(sep_pos == -1) {
+ printf("RIGHT_NODE index not found in parent! Aborting!\n");
+ exit(1);
+ }
+
+ for(unsigned int i = sep_pos; i < parent_node->size; ++i) {
+ INODE(parent_node)->children[i] = INODE(parent_node)->children[i + 1];
+ }
+
+ INODE(parent_node)->children[parent_node->size] = NULL;
+
+ for(unsigned int i = 0; i < right_node->size; ++i) {
+ INODE(left_node)->children[left_node->size + i] = INODE(right_node)->children[i];
+ INODE(left_node)->children[left_node->size + i]->parent = left_node;
+ }
+
+ left_node->size += right_node->size;
+ parent_node->size--;
+ recalculateWeight(left_node);
+
+ right_node->size = 0;
+ delete right_node;
+ }
+
+ // **************************************
+ // Miscellaneous Methods
+ // **************************************
+
+ int getMaxEntries() {
+ return MAX_ENTRIES;
+ }
+
+ void clear() {
+ if(root) {
+ tree_depth = 0;
+ tree_size = 0;
+ if(root->isa(LEAF))
+ delete LNODE(root);
+ else
+ delete INODE(root);
+ root = new LeafNode(NULL);
+ }
+ }
+
+ int depth() {
+ return tree_depth;
+ }
+
+ Node *getroot() {
+ return root;
+ }
+
+ // number of nodes in the tree
+ int size() {
+ return tree_size;
+ }
+
+ // number of Type in the tree
+ int subnodes() {
+ return root->subnodes;
+ }
+
+ int totalWeight() {
+ return...
[truncated message content] |
