123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440 |
- /* GNU/Linux splay tree test program based on oct 2021 gcc version
- * this may use all ram and disk swap then the programs stops but GNU/Linux does not crash or crashe other programs
- * https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libiberty/splay-tree.c;h=7c8973c63c8fead8e1363f4f42a5f686fb16ac8c;hb=HEAD
- * int stack_ptr in foreach() allows only splay tree with max size of 2G, should be size_t
- * splay_tree_xmalloc_allocate(int size, void *data ATTRIBUTE_UNUSED) should use size_t size
- * 1000*1000*280 are 280 million splay tree nodes hits already a limit on debian Linux
- * splay_tree_foreach4() reaches 423 million splay tree nodes on Fedora Linux on test machine
- * splay_tree_foreach() is the gcc original
- * splay_tree_foreach2() is the memory saving version
- * splay_tree_foreach3() does not use realloc()
- * splay_tree_foreach4() does not use realloc() and is slower
- * used compiler settings from airbus aerospace
- * see https://github.com/airbus-seclab/c-compiler-security
- * -Wtraditional-conversion [temp turned off -- too much]
- * AIRBUS_GCC_COMPILER_WARNING="$CFLAGS -O2 -Wall -Wextra -Wpedantic -Wformat=2 -Wformat-overflow=2 -Wformat-truncation=2 -Wformat-security -Wnull-dereference -Wstack-protector -Wtrampolines -Walloca -Wvla -Warray-bounds=2 -Wimplicit-fallthrough=3 -Wshift-overflow=2 -Wcast-qual -Wstringop-overflow=4 -Wconversion -Warith-conversion -Wlogical-op -Wduplicated-cond -Wduplicated-branches -Wformat-signedness -Wshadow -Wstrict-overflow=4 -Wundef -Wstrict-prototypes -Wswitch-default -Wswitch-enum -Wstack-usage=1000000 -Wcast-align=strict -D_FORTIFY_SOURCE=2 -fstack-protector-strong -fstack-clash-protection -fPIE -Wl,-z,relro -Wl,-z,now -Wl,-z,noexecstack -Wl,-z,separate-code"
- * for gcc -fanalyzer option newest gcc version 11.2 is needed
- * ./spt
- * testing old splay_tree_foreach()
- * status=0 10 tree nodes stack used max 100 entries using 0 megabyte 800 bytes 0 realloc()'s
- * testing old splay_tree_foreach()
- * status=0 1000 tree nodes stack used max 1600 entries using 0 megabyte 12800 bytes 4 realloc()'s
- * testing new splay_tree_foreach()
- * status=0 1000 tree nodes stack used max 1000 entries using 0 megabyte 8000 bytes 1 realloc()'s saved 0 Mb
- * testing old splay_tree_foreach()
- * status=0 100000000 tree nodes stack used max 104857600 entries using 800 megabyte 838860800 bytes 20 realloc()'s
- * testing new splay_tree_foreach()
- * status=0 100000000 tree nodes stack used max 100000000 entries using 762 megabyte 800000000 bytes 1 realloc()'s saved 37 Mb
- * testing old splay_tree_foreach()
- * status=0 280000000 tree nodes stack used max 419430400 entries using 3200 megabyte 3355443200 bytes 22 realloc()'s
- * testing new splay_tree_foreach()
- * status=0 280000000 tree nodes stack used max 280000000 entries using 2136 megabyte 2240000000 bytes 1 realloc()'s saved 1063 Mb
- * testing splay_tree_foreach() without realloc()
- * splay_tree_foreach3(): splay tree has 3000000 nodes
- * status=0 3000000 tree nodes stack used max 3000000 entries using 22 megabyte 24000000 bytes 0 realloc()'s
- * On debian Linux the limit is 280 million splay tree nodes
- * at more the program stops and is killed by some security software on debian Linux
- * testing old splay_tree_foreach()
- * status=0 350000000 tree nodes stack used max 419430400 entries using 3200 megabyte 3355443200 bytes 22 realloc()'s
- * testing new splay_tree_foreach()
- * status=0 350000000 tree nodes stack used max 350000000 entries using 2670 megabyte 2800000000 bytes 1 realloc()'s saved 529 Mb
- * On Fedora Linux the limit is 350 million splay tree nodes
- * at more the Fedora desktop causes a logout and the program stops
- * at using only the splay_tree_foreach2() ith less memory consumption
- * testing new splay_tree_foreach() with maximum test machine limit
- * status=0 370000000 tree nodes stack used max 370000000 entries using 2822 megabyte 2960000000 bytes 1 realloc()'s
- * At more all ram and all disk swap space is used on the test computer.
- * tested on a Linux computer with 128 GB memory it works with more splay tree nodes.
- * using slower splay_tree_foreach4() Linux server with 128 GB ram can handle 3384 million nodes.
- * Now try this on WSL
- * Need to measure how much slower splay_tree_foreach4() is compared to splay_tree_foreach()
- */
- /* A splay-tree datatype.
- Copyright (C) 1998-2021 Free Software Foundation, Inc.
- Contributed by Mark Mitchell (mark@markmitchell.com).
- This file is part of GNU CC.
- GNU CC 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, or (at your option)
- any later version.
- GNU CC 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 GNU CC; see the file COPYING. If not, write to
- the Free Software Foundation, 51 Franklin Street - Fifth Floor,
- Boston, MA 02110-1301, USA. */
- /* For an easily readable description of splay-trees, see:
- Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
- Algorithms. Harper-Collins, Inc. 1991. */
- /*
- SPDX-License-Identifier: GPL-3.0+
- */
- /* orig
- #ifdef HAVE_CONFIG_H
- #include "config.h"
- #endif
- #ifdef HAVE_STDLIB_H
- #include <stdlib.h>
- #endif
- #ifdef HAVE_STRING_H
- #include <string.h>
- #endif
- #include <stdio.h>
- #include "libiberty.h"
- #include "splay-tree.h"
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <unistd.h> /* should define sync() and syncfs() */
- /* just in case if sync() is still not defined */
- extern void sync(void);
- /* needed for type unintptr_t or use long long int */
- #include <stdint.h>
- #define ATTRIBUTE_UNUSED /**/
- /* how many stack entries used max 4 Giga */
- static unsigned int maxstack = 0;
- /* how many realloc() done */
- static int nrealloc = 0;
- /* Use typedefs for the key and data types to facilitate changing
- these types, if necessary. These types should be sufficiently wide
- that any pointer or scalar can be cast to these types, and then
- cast back, without loss of precision. */
- typedef uintptr_t splay_tree_key; /* 64bits unsigned int */
- typedef uintptr_t splay_tree_value;
- /* Forward declaration for a node in the tree. */
- typedef struct splay_tree_node_s *splay_tree_node;
- /* The type of a function which compares two splay-tree keys. The
- function should return values as for qsort. */
- typedef int (*splay_tree_compare_fn)(splay_tree_key, splay_tree_key);
- /* The type of a function used to deallocate any resources associated
- with the key. If you provide this function, the splay tree
- will take the ownership of the memory of the splay_tree_key arg
- of splay_tree_insert. This function is called to release the keys
- present in the tree when calling splay_tree_delete or splay_tree_remove.
- If splay_tree_insert is called with a key equal to a key already
- present in the tree, the old key and old value will be released. */
- typedef void (*splay_tree_delete_key_fn)(splay_tree_key);
- /* The type of a function used to deallocate any resources associated
- with the value. If you provide this function, the memory of the
- splay_tree_value arg of splay_tree_insert is managed similarly to
- the splay_tree_key memory: see splay_tree_delete_key_fn. */
- typedef void (*splay_tree_delete_value_fn)(splay_tree_value);
- /* The type of a function used to iterate over the tree. */
- typedef int (*splay_tree_foreach_fn)(splay_tree_node, void *);
- /* The type of a function used to allocate memory for tree root and
- node structures. The first argument is the number of bytes needed;
- the second is a data pointer the splay tree functions pass through
- to the allocator. This function must never return zero. */
- /* old typedef void *(*splay_tree_allocate_fn)(int, void *); */
- typedef void *(*splay_tree_allocate_fn)(size_t, void *);
- /* The type of a function used to free memory allocated using the
- corresponding splay_tree_allocate_fn. The first argument is the
- memory to be freed; the latter is a data pointer the splay tree
- functions pass through to the freer. */
- typedef void (*splay_tree_deallocate_fn)(void *, void *);
- /* The nodes in the splay tree. */
- struct splay_tree_node_s {
- /* The key. */
- splay_tree_key key;
- /* The value. */
- splay_tree_value value;
- /* The left and right children, respectively. */
- splay_tree_node left;
- splay_tree_node right;
- };
- /* The splay tree itself. */
- struct splay_tree_s {
- /* The root of the tree. */
- splay_tree_node root;
- /* The comparision function. */
- splay_tree_compare_fn comp;
- /* The deallocate-key function. NULL if no cleanup is necessary. */
- splay_tree_delete_key_fn delete_key;
- /* The deallocate-value function. NULL if no cleanup is necessary. */
- splay_tree_delete_value_fn delete_value;
- /* Node allocate function. Takes allocate_data as a parameter. */
- splay_tree_allocate_fn allocate;
- /* Free function for nodes and trees. Takes allocate_data as a parameter. */
- splay_tree_deallocate_fn deallocate;
- /* Parameter for allocate/free functions. */
- void *allocate_data;
- };
- typedef struct splay_tree_s *splay_tree;
- /* these routines are here */
- extern splay_tree splay_tree_new(splay_tree_compare_fn, splay_tree_delete_key_fn, splay_tree_delete_value_fn);
- extern splay_tree splay_tree_new_with_allocator(splay_tree_compare_fn,
- splay_tree_delete_key_fn,
- splay_tree_delete_value_fn,
- splay_tree_allocate_fn, splay_tree_deallocate_fn, void *);
- extern splay_tree splay_tree_new_typed_alloc(splay_tree_compare_fn,
- splay_tree_delete_key_fn,
- splay_tree_delete_value_fn,
- splay_tree_allocate_fn, splay_tree_allocate_fn, splay_tree_deallocate_fn, void *);
- extern void splay_tree_delete(splay_tree);
- extern splay_tree_node splay_tree_insert(splay_tree, splay_tree_key, splay_tree_value);
- extern void splay_tree_remove(splay_tree, splay_tree_key);
- extern splay_tree_node splay_tree_lookup(splay_tree, splay_tree_key);
- extern splay_tree_node splay_tree_predecessor(splay_tree, splay_tree_key);
- extern splay_tree_node splay_tree_successor(splay_tree, splay_tree_key);
- extern splay_tree_node splay_tree_max(splay_tree);
- extern splay_tree_node splay_tree_min(splay_tree);
- extern int splay_tree_foreach(splay_tree, splay_tree_foreach_fn, void *);
- extern int splay_tree_compare_ints(splay_tree_key, splay_tree_key);
- extern int splay_tree_compare_pointers(splay_tree_key, splay_tree_key);
- extern int splay_tree_compare_strings(splay_tree_key, splay_tree_key);
- extern void splay_tree_delete_pointers(splay_tree_value);
- /* old static void *splay_tree_xmalloc_allocate(int size, void *data ATTRIBUTE_UNUSED); */
- static void *splay_tree_xmalloc_allocate(size_t size, void *data ATTRIBUTE_UNUSED);
- static void splay_tree_xmalloc_deallocate(void *object, void *data ATTRIBUTE_UNUSED);
- /* liberty.h Array allocators. */
- #define XALLOCAVEC(T, N) ((T *) alloca (sizeof (T) * (N)))
- #define XNEWVEC(T, N) ((T *) xmalloc (sizeof (T) * (N)))
- #define XCNEWVEC(T, N) ((T *) xcalloc ((N), sizeof (T)))
- #define XDUPVEC(T, P, N) ((T *) xmemdup ((P), sizeof (T) * (N), sizeof (T) * (N)))
- #define XRESIZEVEC(T, P, N) ((T *) xrealloc ((void *) (P), sizeof (T) * (N)))
- #define XDELETEVEC(P) free ((void*) (P))
- /* xmalloc substitute */
- #define xmalloc(x) calloc((size_t)1,x)
- #define xrealloc(p,n) realloc(p,n)
- static void splay_tree_delete_helper(splay_tree, splay_tree_node);
- static inline void rotate_left(splay_tree_node *, splay_tree_node, splay_tree_node);
- static inline void rotate_right(splay_tree_node *, splay_tree_node, splay_tree_node);
- static void splay_tree_splay(splay_tree, splay_tree_key);
- static int splay_tree_foreach_helper(splay_tree_node, splay_tree_foreach_fn, void *);
- /* Deallocate NODE (a member of SP), and all its sub-trees. */
- static void splay_tree_delete_helper(splay_tree sp, splay_tree_node node)
- {
- splay_tree_node pending = 0;
- splay_tree_node active = 0;
- if (!node)
- return;
- #define KDEL(x) if (sp->delete_key) (*sp->delete_key)(x);
- #define VDEL(x) if (sp->delete_value) (*sp->delete_value)(x);
- KDEL(node->key);
- VDEL(node->value);
- /* We use the "key" field to hold the "next" pointer. */
- node->key = (splay_tree_key) pending;
- pending = (splay_tree_node) node;
- /* Now, keep processing the pending list until there aren't any
- more. This is a little more complicated than just recursing, but
- it doesn't toast the stack for large trees. */
- while (pending) {
- active = pending;
- pending = 0;
- while (active) {
- splay_tree_node temp;
- /* active points to a node which has its key and value
- deallocated, we just need to process left and right. */
- if (active->left) {
- KDEL(active->left->key);
- VDEL(active->left->value);
- active->left->key = (splay_tree_key) pending;
- pending = (splay_tree_node) (active->left);
- }
- if (active->right) {
- KDEL(active->right->key);
- VDEL(active->right->value);
- active->right->key = (splay_tree_key) pending;
- pending = (splay_tree_node) (active->right);
- }
- temp = active;
- active = (splay_tree_node) (temp->key);
- (*sp->deallocate) ((char *)temp, sp->allocate_data);
- }
- }
- #undef KDEL
- #undef VDEL
- }
- /* Rotate the edge joining the left child N with its parent P. PP is the
- grandparents' pointer to P. */
- static inline void rotate_left(splay_tree_node * pp, splay_tree_node p, splay_tree_node n)
- {
- splay_tree_node tmp;
- tmp = n->right;
- n->right = p;
- p->left = tmp;
- *pp = n;
- }
- /* Rotate the edge joining the right child N with its parent P. PP is the
- grandparents' pointer to P. */
- static inline void rotate_right(splay_tree_node * pp, splay_tree_node p, splay_tree_node n)
- {
- splay_tree_node tmp;
- tmp = n->left;
- n->left = p;
- p->right = tmp;
- *pp = n;
- }
- /* Bottom up splay of key. */
- static void splay_tree_splay(splay_tree sp, splay_tree_key key)
- {
- if (sp->root == 0)
- return;
- do {
- int cmp1, cmp2;
- splay_tree_node n, c;
- n = sp->root;
- cmp1 = (*sp->comp) (key, n->key);
- /* Found. */
- if (cmp1 == 0)
- return;
- /* Left or right? If no child, then we're done. */
- if (cmp1 < 0)
- c = n->left;
- else
- c = n->right;
- if (!c)
- return;
- /* Next one left or right? If found or no child, we're done
- after one rotation. */
- cmp2 = (*sp->comp) (key, c->key);
- if (cmp2 == 0 || (cmp2 < 0 && !c->left) || (cmp2 > 0 && !c->right)) {
- if (cmp1 < 0)
- rotate_left(&sp->root, n, c);
- else
- rotate_right(&sp->root, n, c);
- return;
- }
- /* Now we have the four cases of double-rotation. */
- if (cmp1 < 0 && cmp2 < 0) {
- rotate_left(&n->left, c, c->left);
- rotate_left(&sp->root, n, n->left);
- } else if (cmp1 > 0 && cmp2 > 0) {
- rotate_right(&n->right, c, c->right);
- rotate_right(&sp->root, n, n->right);
- } else if (cmp1 < 0 && cmp2 > 0) {
- rotate_right(&n->left, c, c->right);
- rotate_left(&sp->root, n, n->left);
- } else if (cmp1 > 0 && cmp2 < 0) {
- rotate_left(&n->right, c, c->left);
- rotate_right(&sp->root, n, n->right);
- }
- }
- while (1);
- }
- /* Call FN, passing it the DATA, for every node below NODE, all of
- which are from SP, following an in-order traversal. If FN every
- returns a non-zero value, the iteration ceases immediately, and the
- value is returned. Otherwise, this function returns 0. */
- static int splay_tree_foreach_helper(splay_tree_node node, splay_tree_foreach_fn fn, void *data)
- {
- int val;
- splay_tree_node *stack;
- int stack_ptr, stack_size;
- /* A non-recursive implementation is used to avoid filling the stack
- for large trees. Splay trees are worst case O(n) in the depth of
- the tree. */
- #define INITIAL_STACK_SIZE 100
- stack_size = INITIAL_STACK_SIZE;
- stack_ptr = 0;
- stack = XNEWVEC(splay_tree_node, (long unsigned int)stack_size);
- val = 0;
- for (;;) {
- /* added */
- if ((unsigned int)stack_size > maxstack) {
- maxstack = (unsigned int)stack_size;
- }
- while (node != NULL) {
- if (stack_ptr == stack_size) {
- stack_size *= 2;
- stack = XRESIZEVEC(splay_tree_node, stack, (long unsigned int)stack_size);
- /* how many realloc()'s */
- nrealloc++;
- }
- stack[stack_ptr++] = node;
- node = node->left;
- }
- if (stack_ptr == 0)
- break;
- node = stack[--stack_ptr];
- val = (*fn) (node, data);
- if (val)
- break;
- node = node->right;
- }
- XDELETEVEC(stack);
- return val;
- }
- /* Call FN, passing it the DATA, for every node below NODE, all of
- which are from SP, following an in-order traversal. If FN every
- returns a non-zero value, the iteration ceases immediately, and the
- value is returned. Otherwise, this function returns 0. */
- /* modified */
- static int splay_tree_foreach_helper2(splay_tree_node node, splay_tree_foreach_fn fn, void *data)
- {
- int val;
- splay_tree_node *stack;
- splay_tree_node sn;
- int stack_ptr, stack_size; /* this allows only 2G entries */
- /* A non-recursive implementation is used to avoid filling the stack
- for large trees. Splay trees are worst case O(n) in the depth of
- the tree. */
- #define INITIAL_STACK_SIZE 100
- stack_size = INITIAL_STACK_SIZE;
- stack_ptr = 0;
- stack = XNEWVEC(splay_tree_node, (long unsigned int)stack_size);
- val = 0;
- for (;;) {
- /* added */
- if ((unsigned int)stack_size > maxstack) {
- maxstack = (unsigned int)stack_size;
- }
- sn = node; /* save copy */
- val = 0;
- /* count how many */
- while (node != NULL) {
- val++;
- node = node->left;
- }
- if (val) {
- if (val > stack_size) {
- stack_size = val;
- if ((unsigned int)stack_size > maxstack) {
- maxstack = (unsigned int)stack_size;
- }
- /* allocate exact as much as needed */
- stack = XRESIZEVEC(splay_tree_node, stack, (long unsigned int)stack_size);
- /* how many realloc()'s */
- nrealloc++;
- }
- }
- /* copy the pointers */
- while (sn != NULL) {
- stack[stack_ptr++] = sn;
- sn = sn->left;
- }
- if (stack_ptr == 0)
- break;
- node = stack[--stack_ptr];
- val = (*fn) (node, data);
- if (val)
- break;
- node = node->right;
- }
- XDELETEVEC(stack);
- return val;
- }
- /* Call FN, passing it the DATA, for every node below NODE, all of
- which are from SP, following an in-order traversal. If FN every
- returns a non-zero value, the iteration ceases immediately, and the
- value is returned. Otherwise, this function returns 0. */
- /* modified does not use realloc() in XRESIZEVEC() */
- static int splay_tree_foreach_helper3(splay_tree_node node, splay_tree_foreach_fn fn, void *data, unsigned int count)
- {
- int val;
- splay_tree_node *stack;
- unsigned int stack_ptr = 0;
- unsigned int stack_size = 0; /* this allows only 4G entries */
- /* A non-recursive implementation is used to avoid filling the stack
- for large trees. Splay trees are worst case O(n) in the depth of
- the tree. */
- stack_size = count;
- stack_ptr = 0;
- stack = XNEWVEC(splay_tree_node, (long unsigned int)stack_size);
- val = 0;
- for (;;) {
- /* added */
- if (stack_size > maxstack) {
- maxstack = stack_size;
- }
- /* copy the pointers */
- while (node != NULL) {
- stack[stack_ptr++] = node;
- node = node->left;
- }
- if (stack_ptr == 0)
- break;
- node = stack[--stack_ptr];
- val = (*fn) (node, data);
- if (val)
- break;
- node = node->right;
- }
- XDELETEVEC(stack);
- return val;
- }
- /* An allocator and deallocator based on xmalloc. */
- static void *splay_tree_xmalloc_allocate(size_t size, void *data ATTRIBUTE_UNUSED)
- {
- if (data) { /* not used */
- }
- return (void *)xmalloc((size_t)size);
- }
- static void splay_tree_xmalloc_deallocate(void *object, void *data ATTRIBUTE_UNUSED)
- {
- if (object) {
- free(object);
- }
- if (data) { /* not used */
- }
- }
- /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
- DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
- values. Use xmalloc to allocate the splay tree structure, and any
- nodes added. */
- splay_tree
- splay_tree_new(splay_tree_compare_fn compare_fn, splay_tree_delete_key_fn delete_key_fn, splay_tree_delete_value_fn delete_value_fn)
- {
- return (splay_tree_new_with_allocator
- (compare_fn, delete_key_fn, delete_value_fn, splay_tree_xmalloc_allocate, splay_tree_xmalloc_deallocate, 0));
- }
- /* Allocate a new splay tree, using COMPARE_FN to compare nodes,
- DELETE_KEY_FN to deallocate keys, and DELETE_VALUE_FN to deallocate
- values. */
- splay_tree
- splay_tree_new_with_allocator(splay_tree_compare_fn compare_fn,
- splay_tree_delete_key_fn delete_key_fn,
- splay_tree_delete_value_fn delete_value_fn,
- splay_tree_allocate_fn allocate_fn, splay_tree_deallocate_fn deallocate_fn, void *allocate_data)
- {
- return
- splay_tree_new_typed_alloc(compare_fn, delete_key_fn, delete_value_fn,
- allocate_fn, allocate_fn, deallocate_fn, allocate_data);
- }
- /*
- @deftypefn Supplemental splay_tree splay_tree_new_with_typed_alloc @
- (splay_tree_compare_fn @var{compare_fn}, @
- splay_tree_delete_key_fn @var{delete_key_fn}, @
- splay_tree_delete_value_fn @var{delete_value_fn}, @
- splay_tree_allocate_fn @var{tree_allocate_fn}, @
- splay_tree_allocate_fn @var{node_allocate_fn}, @
- splay_tree_deallocate_fn @var{deallocate_fn}, @
- void * @var{allocate_data})
- This function creates a splay tree that uses two different allocators
- @var{tree_allocate_fn} and @var{node_allocate_fn} to use for allocating the
- tree itself and its nodes respectively. This is useful when variables of
- different types need to be allocated with different allocators.
- The splay tree will use @var{compare_fn} to compare nodes,
- @var{delete_key_fn} to deallocate keys, and @var{delete_value_fn} to
- deallocate values. Keys and values will be deallocated when the
- tree is deleted using splay_tree_delete or when a node is removed
- using splay_tree_remove. splay_tree_insert will release the previously
- inserted key and value using @var{delete_key_fn} and @var{delete_value_fn}
- if the inserted key is already found in the tree.
- @end deftypefn
- */
- splay_tree
- splay_tree_new_typed_alloc(splay_tree_compare_fn compare_fn,
- splay_tree_delete_key_fn delete_key_fn,
- splay_tree_delete_value_fn delete_value_fn,
- splay_tree_allocate_fn tree_allocate_fn,
- splay_tree_allocate_fn node_allocate_fn, splay_tree_deallocate_fn deallocate_fn, void *allocate_data)
- {
- splay_tree sp = (splay_tree) (*tree_allocate_fn)
- (sizeof(struct splay_tree_s), allocate_data);
- sp->root = 0;
- sp->comp = compare_fn;
- sp->delete_key = delete_key_fn;
- sp->delete_value = delete_value_fn;
- sp->allocate = node_allocate_fn;
- sp->deallocate = deallocate_fn;
- sp->allocate_data = allocate_data;
- return sp;
- }
- /* Deallocate SP. */
- void splay_tree_delete(splay_tree sp)
- {
- splay_tree_delete_helper(sp, sp->root);
- (*sp->deallocate) ((char *)sp, sp->allocate_data);
- }
- /* Insert a new node (associating KEY with DATA) into SP. If a
- previous node with the indicated KEY exists, its data is replaced
- with the new value. Returns the new node. */
- splay_tree_node splay_tree_insert(splay_tree sp, splay_tree_key key, splay_tree_value value)
- {
- int comparison = 0;
- splay_tree_splay(sp, key);
- if (sp->root)
- comparison = (*sp->comp) (sp->root->key, key);
- if (sp->root && comparison == 0) {
- /* If the root of the tree already has the indicated KEY, delete
- the old key and old value, and replace them with KEY and VALUE. */
- if (sp->delete_key)
- (*sp->delete_key) (sp->root->key);
- if (sp->delete_value)
- (*sp->delete_value) (sp->root->value);
- sp->root->key = key;
- sp->root->value = value;
- } else {
- /* Create a new node, and insert it at the root. */
- splay_tree_node node;
- node = ((splay_tree_node)
- (*sp->allocate) (sizeof(struct splay_tree_node_s), sp->allocate_data));
- node->key = key;
- node->value = value;
- if (!sp->root)
- node->left = node->right = 0;
- else if (comparison < 0) {
- node->left = sp->root;
- node->right = node->left->right;
- node->left->right = 0;
- } else {
- node->right = sp->root;
- node->left = node->right->left;
- node->right->left = 0;
- }
- sp->root = node;
- }
- return sp->root;
- }
- /* Remove KEY from SP. It is not an error if it did not exist. */
- void splay_tree_remove(splay_tree sp, splay_tree_key key)
- {
- splay_tree_splay(sp, key);
- if (sp->root && (*sp->comp) (sp->root->key, key) == 0) {
- splay_tree_node left, right;
- left = sp->root->left;
- right = sp->root->right;
- /* Delete the root node itself. */
- if (sp->delete_key)
- (*sp->delete_key) (sp->root->key);
- if (sp->delete_value)
- (*sp->delete_value) (sp->root->value);
- (*sp->deallocate) (sp->root, sp->allocate_data);
- /* One of the children is now the root. Doesn't matter much
- which, so long as we preserve the properties of the tree. */
- if (left) {
- sp->root = left;
- /* If there was a right child as well, hang it off the
- right-most leaf of the left child. */
- if (right) {
- while (left->right)
- left = left->right;
- left->right = right;
- }
- } else
- sp->root = right;
- }
- }
- /* Lookup KEY in SP, returning VALUE if present, and NULL
- otherwise. */
- splay_tree_node splay_tree_lookup(splay_tree sp, splay_tree_key key)
- {
- splay_tree_splay(sp, key);
- if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
- return sp->root;
- else
- return 0;
- }
- /* Return the node in SP with the greatest key. */
- splay_tree_node splay_tree_max(splay_tree sp)
- {
- splay_tree_node n = sp->root;
- if (!n)
- return NULL;
- while (n->right)
- n = n->right;
- return n;
- }
- /* Return the node in SP with the smallest key. */
- splay_tree_node splay_tree_min(splay_tree sp)
- {
- splay_tree_node n = sp->root;
- if (!n)
- return NULL;
- while (n->left)
- n = n->left;
- return n;
- }
- /* Return the immediate predecessor KEY, or NULL if there is no
- predecessor. KEY need not be present in the tree. */
- splay_tree_node splay_tree_predecessor(splay_tree sp, splay_tree_key key)
- {
- int comparison;
- splay_tree_node node;
- /* If the tree is empty, there is certainly no predecessor. */
- if (!sp->root)
- return NULL;
- /* Splay the tree around KEY. That will leave either the KEY
- itself, its predecessor, or its successor at the root. */
- splay_tree_splay(sp, key);
- comparison = (*sp->comp) (sp->root->key, key);
- /* If the predecessor is at the root, just return it. */
- if (comparison < 0)
- return sp->root;
- /* Otherwise, find the rightmost element of the left subtree. */
- node = sp->root->left;
- if (node)
- while (node->right)
- node = node->right;
- return node;
- }
- /* Return the immediate successor KEY, or NULL if there is no
- successor. KEY need not be present in the tree. */
- splay_tree_node splay_tree_successor(splay_tree sp, splay_tree_key key)
- {
- int comparison;
- splay_tree_node node;
- /* If the tree is empty, there is certainly no successor. */
- if (!sp->root)
- return NULL;
- /* Splay the tree around KEY. That will leave either the KEY
- itself, its predecessor, or its successor at the root. */
- splay_tree_splay(sp, key);
- comparison = (*sp->comp) (sp->root->key, key);
- /* If the successor is at the root, just return it. */
- if (comparison > 0)
- return sp->root;
- /* Otherwise, find the leftmost element of the right subtree. */
- node = sp->root->right;
- if (node)
- while (node->left)
- node = node->left;
- return node;
- }
- /* Call FN, passing it the DATA, for every node in SP, following an
- in-order traversal. If FN every returns a non-zero value, the
- iteration ceases immediately, and the value is returned.
- Otherwise, this function returns 0. */
- int splay_tree_foreach(splay_tree sp, splay_tree_foreach_fn fn, void *data)
- {
- return splay_tree_foreach_helper(sp->root, fn, data);
- }
- /* other way */
- int splay_tree_foreach2(splay_tree sp, splay_tree_foreach_fn fn, void *data)
- {
- return splay_tree_foreach_helper2(sp->root, fn, data);
- }
- /* other way does not use realloc() */
- int splay_tree_foreach3(splay_tree sp, splay_tree_foreach_fn fn, void *data)
- {
- splay_tree_node spn;
- splay_tree_key key;
- unsigned int count = 0; /* allows 4 Giga tree nodes */
- if ((splay_tree) 0 == sp) {
- /* no data */
- return (0);
- }
- if (!sp->root) {
- /* no data */
- return (0);
- }
- /* this counting is very slow
- * or splay tree should maintain the count
- * of number of nodes in the splay tree
- */
- spn = splay_tree_min(sp);
- while (spn) {
- key = (splay_tree_key) spn->key;
- count++;
- spn = splay_tree_successor(sp, key);
- }
- if (count == 0) {
- /* no data */
- }
- printf("%s(): splay tree has %u nodes\n", __func__, count);
- fflush(stdout);
- return splay_tree_foreach_helper3(sp->root, fn, data, count);
- }
- /* other way does not use realloc() */
- int splay_tree_foreach4(splay_tree sp, splay_tree_foreach_fn fn, void *data)
- {
- splay_tree_node spn;
- splay_tree_key key;
- unsigned int count = 0; /* allows 4 Giga tree nodes */
- int val = 0;
- if ((splay_tree) 0 == sp) {
- /* no data */
- return (0);
- }
- if (!sp->root) {
- /* no data */
- return (0);
- }
- /* this is slow but will run with bigger splay tree */
- printf("%s(): starting ...\n", __func__);
- fflush(stdout);
- val = 0;
- spn = splay_tree_min(sp);
- while (spn) {
- key = (splay_tree_key) spn->key;
- count++;
- val = (*fn) (spn, data);
- /* stop if callback routine returns <> 0 */
- if (val)
- break;
- spn = splay_tree_successor(sp, key);
- }
- if (count == 0) {
- /* no data */
- }
- printf("%s(): splay tree has %u nodes return status is %d\n", __func__, count, val);
- fflush(stdout);
- return (val);
- }
- /* Splay-tree comparison function, treating the keys as ints. */
- int splay_tree_compare_ints(splay_tree_key k1, splay_tree_key k2)
- {
- if ((int)k1 < (int)k2)
- return -1;
- else if ((int)k1 > (int)k2)
- return 1;
- else
- return 0;
- }
- /* Splay-tree comparison function, treating the keys as pointers. */
- int splay_tree_compare_pointers(splay_tree_key k1, splay_tree_key k2)
- {
- if ((char *)k1 < (char *)k2)
- return -1;
- else if ((char *)k1 > (char *)k2)
- return 1;
- else
- return 0;
- }
- /* Splay-tree comparison function, treating the keys as strings. */
- int splay_tree_compare_strings(splay_tree_key k1, splay_tree_key k2)
- {
- return strcmp((char *)k1, (char *)k2);
- }
- /* Splay-tree delete function, simply using free. */
- void splay_tree_delete_pointers(splay_tree_value value)
- {
- if (value) {
- free((void *)value);
- }
- }
- /* fn0 small splay tree The type of a function used to iterate over the tree. */
- int fn0(splay_tree_node spn, void *data)
- {
- if (spn == (splay_tree_node) 0) {
- /* sgould not happen */
- return (1);
- }
- printf("%d ", (int)spn->key);
- if (data) { /* not used */
- }
- /* return 0 to continue */
- return (0);
- }
- /* fn1 bigger splay tree The type of a function used to iterate over the tree. */
- int fn1(splay_tree_node spn, void *data)
- {
- if (spn == (splay_tree_node) 0) {
- /* sgould not happen */
- return (1);
- }
- if (((int)spn->key % 100) == 0) {
- printf("%d \n", (int)spn->key);
- }
- if (data) { /* not used */
- }
- /* return 0 to continue */
- return (0);
- }
- /* fn3 even bigger splay tree The type of a function used to iterate over the tree. */
- int fn3(splay_tree_node spn, void *data)
- {
- if (spn == (splay_tree_node) 0) {
- /* sgould not happen */
- return (1);
- }
- if (data) { /* not used */
- }
- /* return 0 to continue */
- return (0);
- }
- /* the test code */
- int main(int argc, char *argv[])
- {
- splay_tree spt;
- unsigned long long int n; /* 64bits */
- unsigned long long int mb = 0; /* mem use in mb */
- unsigned long long int mbs = 0; /* saved mem use in mb */
- splay_tree_node spn;
- int status = 0;
- unsigned int v0 = 0;
- unsigned int v1 = 0;
- if (argc) {
- }
- if (argv) {
- }
- /* maybe safer to do a sync() here */
- sync();
- printf
- ("this may try to use more ram and disk swap memory then available\nstatus=0 means everything is ok\ntesting old splay_tree_foreach()\n");
- spt = splay_tree_new(splay_tree_compare_ints /* compare_fn */ ,
- (splay_tree_delete_key_fn) 0 /* delete_key_fn */ ,
- (splay_tree_delete_value_fn) 0 /* delete_value_fn */
- );
- /* create small splay tree does not use realloc() */
- for (n = 0; n < 10; n++) {
- spn /* splay_tree_node */ =
- splay_tree_insert((splay_tree) spt, (splay_tree_key) n, (splay_tree_value) 0);
- if (!spn) { /* shouldnothappen */
- }
- }
- /* how much stack used */
- maxstack = 0;
- nrealloc = 0;
- /* traverse */
- status = splay_tree_foreach((splay_tree) spt, (splay_tree_foreach_fn) fn0, (void *)0 /* data */ );
- /* how much mem used */
- mb = sizeof(splay_tree_node);
- mb = mb * maxstack;
- mb = mb / 1024; /* kb */
- mb = mb / 1024; /* mb */
- printf
- ("status=%d %llu tree nodes stack used max %u entries using %llu megabyte %lu bytes %d realloc()'s\n",
- status, n, maxstack, mb, sizeof(splay_tree_node) * maxstack, nrealloc);
- splay_tree_delete((splay_tree) spt);
- printf("testing old splay_tree_foreach()\n");
- spt = splay_tree_new(splay_tree_compare_ints /* compare_fn */ ,
- (splay_tree_delete_key_fn) 0 /* delete_key_fn */ ,
- (splay_tree_delete_value_fn) 0 /* delete_value_fn */
- );
- /* create bigher splay tree causes realloc */
- for (n = 0; n < 1000; n++) {
- spn /* splay_tree_node */ =
- splay_tree_insert((splay_tree) spt, (splay_tree_key) n, (splay_tree_value) 0);
- if (!spn) { /* shouldnothappen */
- }
- }
- /* how much stack used */
- maxstack = 0;
- nrealloc = 0;
- /* traverse */
- status = splay_tree_foreach((splay_tree) spt, (splay_tree_foreach_fn) fn1, (void *)0 /* data */ );
- v0 = maxstack;
- /* how much mem used */
- mb = sizeof(splay_tree_node);
- mb = mb * maxstack;
- mb = mb / 1024; /* kb */
- mb = mb / 1024; /* mb */
- printf
- ("status=%d %llu tree nodes stack used max %u entries using %llu megabyte %lu bytes %d realloc()'s\n",
- status, n, maxstack, mb, sizeof(splay_tree_node) * maxstack, nrealloc);
- splay_tree_delete((splay_tree) spt);
- printf("testing new splay_tree_foreach()\n");
- /* now same with other foreach */
- spt = splay_tree_new(splay_tree_compare_ints /* compare_fn */ ,
- (splay_tree_delete_key_fn) 0 /* delete_key_fn */ ,
- (splay_tree_delete_value_fn) 0 /* delete_value_fn */
- );
- /* create bigger splay tree causes realloc */
- for (n = 0; n < 1000; n++) {
- spn /* splay_tree_node */ =
- splay_tree_insert((splay_tree) spt, (splay_tree_key) n, (splay_tree_value) 0);
- if (!spn) { /* shouldnothappen */
- }
- }
- /* how much stack used */
- maxstack = 0;
- nrealloc = 0;
- /* traverse */
- status = splay_tree_foreach2((splay_tree) spt, (splay_tree_foreach_fn) fn1, (void *)0 /* data */ );
- v1 = maxstack;
- /* how much mem used */
- mb = sizeof(splay_tree_node);
- mb = mb * maxstack;
- mb = mb / 1024; /* kb */
- mb = mb / 1024; /* mb */
- /* how much mem saved */
- mbs = sizeof(splay_tree_node);
- mbs = mbs * (v0 - v1);
- mbs = mbs / 1024; /* kb */
- mbs = mbs / 1024; /* mb */
- printf
- ("status=%d %llu tree nodes stack used max %u entries using %llu megabyte %lu bytes %d realloc()'s saved %llu Mb\n",
- status, n, maxstack, mb, sizeof(splay_tree_node) * maxstack, nrealloc, mbs);
- splay_tree_delete((splay_tree) spt);
- printf("testing old splay_tree_foreach()\n");
- /* now going really big but not more the 2G nodes because that is too much but can be fixed */
- spt = splay_tree_new(splay_tree_compare_ints /* compare_fn */ ,
- (splay_tree_delete_key_fn) 0 /* delete_key_fn */ ,
- (splay_tree_delete_value_fn) 0 /* delete_value_fn */
- );
- /* create bigger splay tree causes realloc */
- for (n = 0; n < 1000 * 1000 * 100; n++) {
- spn /* splay_tree_node */ =
- splay_tree_insert((splay_tree) spt, (splay_tree_key) n, (splay_tree_value) 0);
- if (!spn) { /* shouldnothappen */
- }
- }
- /* how much stack used */
- maxstack = 0;
- nrealloc = 0;
- /* traverse */
- status = splay_tree_foreach((splay_tree) spt, (splay_tree_foreach_fn) fn3, (void *)0 /* data */ );
- v0 = maxstack;
- /* how much mem used */
- mb = sizeof(splay_tree_node);
- mb = mb * maxstack;
- mb = mb / 1024; /* kb */
- mb = mb / 1024; /* mb */
- printf
- ("status=%d %llu tree nodes stack used max %u entries using %llu megabyte %lu bytes %d realloc()'s\n",
- status, n, maxstack, mb, sizeof(splay_tree_node) * maxstack, nrealloc);
- splay_tree_delete((splay_tree) spt);
- printf("testing new splay_tree_foreach()\n");
- /* now going really big but not more the 2G nodes because that is too much but can be fixed */
- spt = splay_tree_new(splay_tree_compare_ints /* compare_fn */ ,
- (splay_tree_delete_key_fn) 0 /* delete_key_fn */ ,
- (splay_tree_delete_value_fn) 0 /* delete_value_fn */
- );
- /* create bigger splay tree causes realloc */
- for (n = 0; n < 1000 * 1000 * 100; n++) {
- spn /* splay_tree_node */ =
- splay_tree_insert((splay_tree) spt, (splay_tree_key) n, (splay_tree_value) 0);
- if (!spn) { /* shouldnothappen */
- }
- }
- /* how much stack used */
- maxstack = 0;
- nrealloc = 0;
- /* traverse */
- status = splay_tree_foreach2((splay_tree) spt, (splay_tree_foreach_fn) fn3, (void *)0 /* data */ );
- v1 = maxstack;
- /* how much mem saved */
- mbs = sizeof(splay_tree_node);
- mbs = mbs * (v0 - v1);
- mbs = mbs / 1024; /* kb */
- mbs = mbs / 1024; /* mb */
- /* how much mem used */
- mb = sizeof(splay_tree_node);
- mb = mb * maxstack;
- mb = mb / 1024; /* kb */
- mb = mb / 1024; /* mb */
- printf
- ("status=%d %llu tree nodes stack used max %u entries using %llu megabyte %lu bytes %d realloc()'s saved %llu Mb\n",
- status, n, maxstack, mb, sizeof(splay_tree_node) * maxstack, nrealloc, mbs);
- splay_tree_delete((splay_tree) spt);
- /* maybe safer to do a sync() here */
- sync();
- printf("testing old splay_tree_foreach()\n");
- /* now going really big but not more the 2G nodes because that is too much but can be fixed */
- spt = splay_tree_new(splay_tree_compare_ints /* compare_fn */ ,
- (splay_tree_delete_key_fn) 0 /* delete_key_fn */ ,
- (splay_tree_delete_value_fn) 0 /* delete_value_fn */
- );
- /* create bigger splay tree causes realloc */
- for (n = 0; n < 1000 * 1000 * 256; n++) { /* fedora: 350 */
- spn /* splay_tree_node */ =
- splay_tree_insert((splay_tree) spt, (splay_tree_key) n, (splay_tree_value) 0);
- if (!spn) { /* shouldnothappen */
- }
- }
- /* how much stack used */
- maxstack = 0;
- nrealloc = 0;
- /* traverse */
- status = splay_tree_foreach((splay_tree) spt, (splay_tree_foreach_fn) fn3, (void *)0 /* data */ );
- v0 = maxstack;
- /* how much mem used */
- mb = sizeof(splay_tree_node);
- mb = mb * maxstack;
- mb = mb / 1024; /* kb */
- mb = mb / 1024; /* mb */
- printf
- ("status=%d %llu tree nodes stack used max %u entries using %llu megabyte %lu bytes %d realloc()'s\n",
- status, n, maxstack, mb, sizeof(splay_tree_node) * maxstack, nrealloc);
- splay_tree_delete((splay_tree) spt);
- /* maybe safer to do a sync() here */
- sync();
- printf("testing new splay_tree_foreach()\n");
- /* now going really big but not more the 2G nodes because that is too much but can be fixed */
- spt = splay_tree_new(splay_tree_compare_ints /* compare_fn */ ,
- (splay_tree_delete_key_fn) 0 /* delete_key_fn */ ,
- (splay_tree_delete_value_fn) 0 /* delete_value_fn */
- );
- /* create bigger splay tree causes realloc */
- for (n = 0; n < 1000 * 1000 * 256; n++) { /* fedora 350 */
- spn /* splay_tree_node */ =
- splay_tree_insert((splay_tree) spt, (splay_tree_key) n, (splay_tree_value) 0);
- if (!spn) { /* shouldnothappen */
- }
- }
- /* how much stack used */
- maxstack = 0;
- nrealloc = 0;
- /* traverse */
- status = splay_tree_foreach2((splay_tree) spt, (splay_tree_foreach_fn) fn3, (void *)0 /* data */ );
- v1 = maxstack;
- /* how much mem saved */
- mbs = sizeof(splay_tree_node);
- mbs = mbs * (v0 - v1);
- mbs = mbs / 1024; /* kb */
- mbs = mbs / 1024; /* mb */
- /* how much mem used */
- mb = sizeof(splay_tree_node);
- mb = mb * maxstack;
- mb = mb / 1024; /* kb */
- mb = mb / 1024; /* mb */
- printf
- ("status=%d %llu tree nodes stack used max %u entries using %llu megabyte %lu bytes %d realloc()'s saved %llu Mb\n",
- status, n, maxstack, mb, sizeof(splay_tree_node) * maxstack, nrealloc, mbs);
- splay_tree_delete((splay_tree) spt);
- printf("testing splay_tree_foreach() without realloc()\n");
- /* now going really big but not more the 2G nodes because that is too much but can be fixed */
- spt = splay_tree_new(splay_tree_compare_ints /* compare_fn */ ,
- (splay_tree_delete_key_fn) 0 /* delete_key_fn */ ,
- (splay_tree_delete_value_fn) 0 /* delete_value_fn */
- );
- /* create bigger splay tree no realloc */
- for (n = 0; n < 1000 * 3; n++) {
- spn /* splay_tree_node */ =
- splay_tree_insert((splay_tree) spt, (splay_tree_key) n, (splay_tree_value) 0);
- if (!spn) { /* shouldnothappen */
- }
- }
- /* how much stack used */
- maxstack = 0;
- nrealloc = 0;
- /* traverse */
- status = splay_tree_foreach3((splay_tree) spt, (splay_tree_foreach_fn) fn3, (void *)0 /* data */ );
- v0 = maxstack;
- /* how much mem used */
- mb = sizeof(splay_tree_node);
- mb = mb * maxstack;
- mb = mb / 1024; /* kb */
- mb = mb / 1024; /* mb */
- printf
- ("status=%d %llu tree nodes stack used max %u entries using %llu megabyte %lu bytes %d realloc()'s\n",
- status, n, maxstack, mb, sizeof(splay_tree_node) * maxstack, nrealloc);
- splay_tree_delete((splay_tree) spt);
- /* maybe safer to do a sync() here */
- sync();
- printf("testing new splay_tree_foreach() with maximum test machine limit using all physical ram and all disk swap space\n");
- /* now going really big but not more the 2G nodes because that is too much but can be fixed */
- spt = splay_tree_new(splay_tree_compare_ints /* compare_fn */ ,
- (splay_tree_delete_key_fn) 0 /* delete_key_fn */ ,
- (splay_tree_delete_value_fn) 0 /* delete_value_fn */
- );
- /* create bigger splay tree causes realloc */
- for (n = 0; n < 1000 * 1000 * 256; n++) { /* fedora 370 */
- spn /* splay_tree_node */ =
- splay_tree_insert((splay_tree) spt, (splay_tree_key) n, (splay_tree_value) 0);
- if (!spn) { /* shouldnothappen */
- }
- }
- /* how much stack used */
- maxstack = 0;
- nrealloc = 0;
- /* traverse and do NOT waste memory */
- status = splay_tree_foreach2((splay_tree) spt, (splay_tree_foreach_fn) fn3, (void *)0 /* data */ );
- v0 = maxstack;
- /* how much mem used */
- mb = sizeof(splay_tree_node);
- mb = mb * maxstack;
- mb = mb / 1024; /* kb */
- mb = mb / 1024; /* mb */
- printf
- ("status=%d %llu tree nodes stack used max %u entries using %llu megabyte %lu bytes %d realloc()'s\n",
- status, n, maxstack, mb, sizeof(splay_tree_node) * maxstack, nrealloc);
- splay_tree_delete((splay_tree) spt);
- /* maybe safer to do a sync() here */
- sync();
- /* this reaches more on debian Linux */
- printf("testing another slower new splay_tree_foreach() without realloc()\nadding splay tree nodes ...\n");
- /* now going really big but not more the 2G nodes because that is too much but can be fixed */
- spt = splay_tree_new(splay_tree_compare_ints /* compare_fn */ ,
- (splay_tree_delete_key_fn) 0 /* delete_key_fn */ ,
- (splay_tree_delete_value_fn) 0 /* delete_value_fn */
- );
- /* create bigger splay tree causes realloc */
- for (n = 0; n < 1000 * 1000 * 423; n++) { /* on debian 300 fedora 423 million */
- spn /* splay_tree_node */ =
- splay_tree_insert((splay_tree) spt, (splay_tree_key) n, (splay_tree_value) 0);
- if (!spn) { /* shouldnothappen or maximum reached */
- break;
- }
- }
- /* maybe safer to do a sync() here */
- sync();
- /* how much stack used */
- maxstack = 0;
- nrealloc = 0;
- /* traverse and do NOT waste memory */
- status = splay_tree_foreach4((splay_tree) spt, (splay_tree_foreach_fn) fn3, (void *)0 /* data */ );
- printf("%s(): status=%d\n", __func__, status);
- fflush(stdout);
- splay_tree_delete((splay_tree) spt);
- /* maybe safer to do a sync() here */
- sync();
- printf("%s(): no memory leaks at exit\n", __func__);
- return (0);
- }
- /* end. */
|