/*
- * $Id: splay.cc,v 1.3 2003/04/22 01:37:44 robertc Exp $
+ * Copyright (C) 1996-2015 The Squid Software Foundation and contributors
*
+ * Squid software is distributed under GPLv2+ license and includes
+ * contributions from numerous individuals and organizations.
+ * Please see the COPYING and CONTRIBUTORS files for details.
+ */
+
+/*
* based on ftp://ftp.cs.cmu.edu/user/sleator/splaying/top-down-splay.c
* http://bobo.link.cs.cmu.edu/cgi-bin/splay/splay-cgi.pl
*/
-#include "config.h"
+#include "squid.h"
-#if HAVE_STDIO_H
-#include <stdio.h>
-#endif
-#if HAVE_STDLIB_H
-#include <stdlib.h>
-#endif
+#include <cstdlib>
#if HAVE_UNISTD_H
#include <unistd.h>
#endif
#include "splay.h"
#include "util.h"
-typedef struct {
+class intnode
+{
+
+public:
+ intnode() : i(0) {}
+
+ intnode (int anInt) : i (anInt) {}
+
int i;
-} intnode;
+};
int
compareintvoid(void * const &a, void * const &n)
class SplayCheck
{
- public:
+
+public:
static void BeginWalk();
static int LastValue;
static bool ExpectedFail;
SplayCheck::CheckNode(intnode const &A)
{
if (LastValue > A.i) {
- /* failure */
- if (!ExpectedFail)
- exit (1);
+ /* failure */
+
+ if (!ExpectedFail)
+ exit (1);
} else
- /* success */
- if (ExpectedFail)
- exit (1);
+ /* success */
+ if (ExpectedFail)
+ exit (1);
+
LastValue = A.i;
}
void
destintref (intnode &)
-{
-}
+{}
int
main(int argc, char *argv[])
{
- {
- int i;
- intnode *I;
- /* test void * splay containers */
- splayNode *top = NULL;
- srandom(time(NULL));
- for (i = 0; i < 100; i++) {
- I = (intnode *)xcalloc(sizeof(intnode), 1);
- I->i = random();
- top = splay_insert(I, top, compareintvoid);
+ {
+ int i;
+ intnode *I;
+ /* test void * splay containers */
+ splayNode *top = NULL;
+ squid_srandom(time(NULL));
+
+ for (i = 0; i < 100; ++i) {
+ I = (intnode *)xcalloc(sizeof(intnode), 1);
+ I->i = squid_random();
+ if (top)
+ top = top->insert(I, compareintvoid);
+ else
+ top = new splayNode(static_cast<void*>(new intnode(101)));
+ }
+
+ SplayCheck::BeginWalk();
+ top->walk(SplayCheck::WalkVoid, NULL);
+
+ SplayCheck::BeginWalk();
+ top->walk(SplayCheck::WalkVoid, NULL);
+ top->destroy(destintvoid);
}
- SplayCheck::BeginWalk();
- splay_walk(top, SplayCheck::WalkVoid, NULL);
-
- SplayCheck::BeginWalk();
- top->walk(SplayCheck::WalkVoid, NULL);
- top->destroy(destintvoid);
- /* check we don't segfault on NULL splay calls */
- top = NULL;
- top->splay(NULL, compareintvoid);
- }
+
/* test typesafe splay containers */
- {
- /* intnode* */
- SplayNode<intnode *> *safeTop = NULL;
- for ( int i = 0; i < 100; i++) {
- intnode *I;
- I = new intnode;
- I->i = random();
- safeTop = safeTop->insert(I, compareint);
+ {
+ /* intnode* */
+ SplayNode<intnode *> *safeTop = new SplayNode<intnode *>(new intnode(101));
+
+ for ( int i = 0; i < 100; ++i) {
+ intnode *I;
+ I = new intnode;
+ I->i = squid_random();
+ safeTop = safeTop->insert(I, compareint);
+ }
+
+ SplayCheck::BeginWalk();
+ safeTop->walk(SplayCheck::WalkNode, NULL);
+
+ safeTop->destroy(destint);
}
- SplayCheck::BeginWalk();
- safeTop->walk(SplayCheck::WalkNode, NULL);
-
- safeTop->destroy(destint);
- /* check we don't segfault on NULL splay calls */
- safeTop = NULL;
- safeTop->splay(NULL, compareint);
- }
- {
- /* intnode */
- SplayNode<intnode> *safeTop = NULL;
- for (int i = 0; i < 100; i++) {
- intnode I;
- I.i = random();
- safeTop = safeTop->insert(I, compareintref);
+ {
+ /* intnode */
+ SplayNode<intnode> *safeTop = new SplayNode<intnode>(101);
+
+ for (int i = 0; i < 100; ++i) {
+ intnode I;
+ I.i = squid_random();
+ safeTop = safeTop->insert(I, compareintref);
+ }
+
+ SplayCheck::BeginWalk();
+ safeTop->walk(SplayCheck::WalkNodeRef, NULL);
+
+ safeTop->destroy(destintref);
}
- SplayCheck::BeginWalk();
- safeTop->walk(SplayCheck::WalkNodeRef, NULL);
-
- safeTop->destroy(destintref);
- /* check we don't segfault on NULL splay calls */
- safeTop = NULL;
- safeTop->splay(intnode(), compareintref);
- SplayCheck::BeginWalk();
- safeTop->walk(SplayCheck::WalkNodeRef, NULL);
-}
+
/* check the check routine */
- SplayCheck::BeginWalk();
- intnode I;
- I.i = 1;
- SplayCheck::WalkNodeRef(I, NULL);
- I.i = 0;
- SplayCheck::ExpectedFail = true;
- SplayCheck::WalkNodeRef(I, NULL);
+ {
+ SplayCheck::BeginWalk();
+ intnode I;
+ I.i = 1;
+ /* check we don't segfault on NULL splay calls */
+ SplayCheck::WalkNodeRef(I, NULL);
+ I.i = 0;
+ SplayCheck::ExpectedFail = true;
+ SplayCheck::WalkNodeRef(I, NULL);
+ }
+
+ {
+ /* check for begin() */
+ Splay<intnode> *safeTop = new Splay<intnode>();
+
+ if (safeTop->start() != NULL)
+ exit (1);
+
+ if (safeTop->finish() != NULL)
+ exit (1);
+
+ for (int i = 0; i < 100; ++i) {
+ intnode I;
+ I.i = squid_random();
+
+ if (I.i > 50 && I.i < 10000000)
+ safeTop->insert(I, compareintref);
+ }
+
+ {
+ intnode I;
+ I.i = 50;
+ safeTop->insert (I, compareintref);
+ I.i = 10000000;
+ safeTop->insert (I, compareintref);
+ }
+
+ if (!safeTop->start())
+ exit (1);
+
+ if (safeTop->start()->data.i != 50)
+ exit (1);
+
+ if (!safeTop->finish())
+ exit (1);
+
+ if (safeTop->finish()->data.i != 10000000)
+ exit (1);
+
+ safeTop->destroy(destintref);
+ }
+
+ {
+ Splay<intnode *> aSplay;
+
+ if (aSplay.start() != NULL)
+ exit (1);
+
+ if (aSplay.size() != 0)
+ exit (1);
+
+ aSplay.insert (new intnode(5), compareint);
+
+ if (aSplay.start() == NULL)
+ exit (1);
+
+ if (aSplay.size() != 1)
+ exit (1);
+
+ aSplay.destroy(destint);
+
+ if (aSplay.start() != NULL)
+ exit (1);
+
+ if (aSplay.size() != 0)
+ exit (1);
+ }
+
+ /* TODO: also test the other Splay API */
+
return 0;
}
+
projects / thirdparty / squid.git / blobdiff