[haiku-commits] haiku: hrev48681 - in src: tests/add-ons/kernel/file_systems/bfs/btree apps/sudoku
- From: axeld@xxxxxxxxxxxxxxxx
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Thu, 15 Jan 2015 20:31:02 +0100 (CET)
hrev48681 adds 5 changesets to branch 'master'
old head: eb27e2297ac06460d8dc2a73a53de0767bb85535
new head: 7fb1396861fb37acddc0eca58fa55de2100f98a7
overview:
http://cgit.haiku-os.org/haiku/log/?qt=range&q=7fb1396861fb+%5Eeb27e2297ac0
----------------------------------------------------------------------------
f982c9ed8859: BFS btreeTest: fixed DEBUG build.
758cfd808a56: BFS B+tree test: style cleanup.
aeb121ec03aa: Sudoku: consolidated set value code paths.
* Renamed _ToggleValue() to _SetValue(), and only let it do that.
* It's now called from _InsertKey(), and _SolveSingle() as well which
results in a correct visual update (ie. completed values, and the
value hints are updated correctly).
* _SolveSingle() would also not test for a completed game.
9b61a43ad63d: MediaPlayer: make sure info window is on screen.
7fb1396861fb: BFS B+tree test: use set to ensure string uniqueness.
* The previous solution was rather slow, and also could produce
duplicates under some circumstance.
[ Axel Dörfler <axeld@xxxxxxxxxxxxxxxx> ]
----------------------------------------------------------------------------
5 files changed, 285 insertions(+), 256 deletions(-)
src/apps/mediaplayer/InfoWin.cpp | 8 +
src/apps/sudoku/SudokuView.cpp | 37 +-
src/apps/sudoku/SudokuView.h | 3 +-
.../kernel/file_systems/bfs/btree/stubs.cpp | 24 +-
.../kernel/file_systems/bfs/btree/test.cpp | 469 ++++++++++---------
############################################################################
Commit: f982c9ed88597ae902878c24bc64be38a4238763
URL: http://cgit.haiku-os.org/haiku/commit/?id=f982c9ed8859
Author: Axel Dörfler <axeld@xxxxxxxxxxxxxxxx>
Date: Tue Jan 13 07:54:34 2015 UTC
BFS btreeTest: fixed DEBUG build.
----------------------------------------------------------------------------
diff --git a/src/tests/add-ons/kernel/file_systems/bfs/btree/stubs.cpp
b/src/tests/add-ons/kernel/file_systems/bfs/btree/stubs.cpp
index 262e483..0d57e0c 100644
--- a/src/tests/add-ons/kernel/file_systems/bfs/btree/stubs.cpp
+++ b/src/tests/add-ons/kernel/file_systems/bfs/btree/stubs.cpp
@@ -1,4 +1,11 @@
-#include "fs_interface.h"
+/*
+ * Copyright 2014-2015, Haiku, Inc. All rights reserved.
+ * Distributed under the terms of the MIT License.
+ */
+
+
+#include <fs_interface.h>
+#include <kscheduler.h>
status_t
@@ -13,3 +20,18 @@ put_vnode(fs_volume* volume, ino_t vnodeID)
{
return B_OK;
}
+
+
+// #pragma mark -
+
+
+void
+scheduler_enqueue_in_run_queue(Thread* thread)
+{
+}
+
+
+void
+scheduler_reschedule(int32 next_state)
+{
+}
############################################################################
Commit: 758cfd808a56bf632530959206ddb447f96a649e
URL: http://cgit.haiku-os.org/haiku/commit/?id=758cfd808a56
Author: Axel Dörfler <axeld@xxxxxxxxxxxxxxxx>
Date: Tue Jan 13 16:37:28 2015 UTC
BFS B+tree test: style cleanup.
----------------------------------------------------------------------------
diff --git a/src/tests/add-ons/kernel/file_systems/bfs/btree/test.cpp
b/src/tests/add-ons/kernel/file_systems/bfs/btree/test.cpp
index e06c363..65eb96e 100644
--- a/src/tests/add-ons/kernel/file_systems/bfs/btree/test.cpp
+++ b/src/tests/add-ons/kernel/file_systems/bfs/btree/test.cpp
@@ -1,21 +1,23 @@
-/* test - BFS B+Tree torture test
-**
-** Initial version by Axel Dörfler, axeld@xxxxxxxxxxxxxxxx
-** This file may be used under the terms of the OpenBeOS License.
-*/
+/*
+ * Copyright 2001-2015, Axel Dörfler, axeld@xxxxxxxxxxxxxxxx.
+ * This file may be used under the terms of the MIT License.
+ */
-#include "Volume.h"
-#include "Inode.h"
-#include "BPlusTree.h"
+//! BFS B+Tree torture test
-#include <List.h>
-#include <sys/stat.h>
-#include <string.h>
-#include <stdlib.h>
-#include <stdio.h>
#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+
+#include <List.h>
+
+#include "BPlusTree.h"
+#include "Inode.h"
+#include "Volume.h"
#define DEFAULT_ITERATIONS 10
@@ -26,21 +28,21 @@
#define MAX_STRING 256
struct key {
- void *data;
+ void* data;
uint32 length;
int32 in;
int32 count;
off_t value;
};
-key *gKeys;
+key* gKeys;
int32 gNum = DEFAULT_NUM_KEYS;
int32 gType = DEFAULT_KEY_TYPE;
int32 gTreeCount = 0;
bool gVerbose, gExcessive;
int32 gIterations = DEFAULT_ITERATIONS;
int32 gHard = 1;
-Volume *gVolume;
+Volume* gVolume;
int32 gSeed = 42;
// from cache.cpp (yes, we are that mean)
@@ -49,9 +51,9 @@ extern BList gBlocks;
// prototypes
void bailOut();
-void bailOutWithKey(void *key, uint16 length);
+void bailOutWithKey(void* key, uint16 length);
void dumpTree();
-void dumpKey(void *key, int32 length);
+void dumpKey(void* key, int32 length);
void dumpKeys();
@@ -60,15 +62,15 @@ dumpTree()
{
puts("\n*** Tree-Dump:\n");
- bplustree_header *header = (bplustree_header *)gBlocks.ItemAt(0);
+ bplustree_header* header = (bplustree_header*)gBlocks.ItemAt(0);
dump_bplustree_header(header);
- for (int32 i = 1;i < gBlocks.CountItems();i++) {
- bplustree_node *node = (bplustree_node *)gBlocks.ItemAt(i);
+ for (int32 i = 1; i < gBlocks.CountItems(); i++) {
+ bplustree_node* node = (bplustree_node*)gBlocks.ItemAt(i);
printf("\n--- %s node at %ld
--------------------------------------\n",
node->overflow_link == BPLUSTREE_NULL ? "leaf"
: "index",
i * BPLUSTREE_NODE_SIZE);
- dump_bplustree_node(node,header,gVolume);
+ dump_bplustree_node(node, header, gVolume);
}
}
@@ -82,13 +84,13 @@ bailOut()
}
// in any case, write the tree back to disk
- shutdown_cache(gVolume->Device(),gVolume->BlockSize());
+ shutdown_cache(gVolume->Device(), gVolume->BlockSize());
exit(-1);
}
void
-bailOutWithKey(void *key, uint16 length)
+bailOutWithKey(void* key, uint16 length)
{
dumpKey(key, length);
putchar('\n');
@@ -97,44 +99,44 @@ bailOutWithKey(void *key, uint16 length)
void
-dumpKey(void *key, int32 length)
+dumpKey(void* key, int32 length)
{
switch (gType) {
case S_STR_INDEX:
- printf("\"%s\" (%ld bytes)", (char *)key, length);
+ printf("\"%s\" (%ld bytes)", (char*)key, length);
break;
case S_INT_INDEX:
- printf("%ld", *(int32 *)key);
+ printf("%ld", *(int32*)key);
break;
case S_UINT_INDEX:
- printf("%lu", *(uint32 *)key);
+ printf("%lu", *(uint32*)key);
break;
case S_LONG_LONG_INDEX:
- printf("%Ld", *(int64 *)key);
+ printf("%Ld", *(int64*)key);
break;
case S_ULONG_LONG_INDEX:
- printf("%Lu", *(uint64 *)key);
+ printf("%Lu", *(uint64*)key);
break;
case S_FLOAT_INDEX:
- printf("%g", *(float *)key);
+ printf("%g", *(float*)key);
break;
case S_DOUBLE_INDEX:
- printf("%g", *(double *)key);
+ printf("%g", *(double*)key);
break;
}
- if ((gType == S_INT_INDEX || gType == S_UINT_INDEX || gType ==
S_FLOAT_INDEX)
- && length != 4)
- printf(" (wrong length %ld)",length);
- else if ((gType == S_LONG_LONG_INDEX || gType == S_ULONG_LONG_INDEX ||
gType == S_DOUBLE_INDEX)
- && length != 8)
- printf(" (wrong length %ld)",length);
+ if ((gType == S_INT_INDEX || gType == S_UINT_INDEX
+ || gType == S_FLOAT_INDEX) && length != 4)
+ printf(" (wrong length %ld)", length);
+ else if ((gType == S_LONG_LONG_INDEX || gType == S_ULONG_LONG_INDEX
+ || gType == S_DOUBLE_INDEX) && length != 8)
+ printf(" (wrong length %ld)", length);
}
void
dumpKeys()
{
- const char *type;
+ const char* type;
switch (gType) {
case S_STR_INDEX:
type = "string";
@@ -161,24 +163,21 @@ dumpKeys()
debugger("unknown type in gType");
return;
}
- printf("Dumping %ld keys of type %s\n",gNum,type);
-
- for (int32 i = 0;i < gNum;i++) {
- printf("% 8ld. (%3ld) key = ",i,gKeys[i].in);
- dumpKey(gKeys[i].data,gKeys[i].length);
+ printf("Dumping %ld keys of type %s\n", gNum, type);
+
+ for (int32 i = 0; i < gNum; i++) {
+ printf("% 8ld. (%3ld) key = ", i, gKeys[i].in);
+ dumpKey(gKeys[i].data, gKeys[i].length);
putchar('\n');
}
}
-// #pragma mark -
-//
-// Functions to generate the keys in every available type
-//
+// #pragma mark - Key generation
void
-generateName(int32 i,char *name,int32 *_length)
+generateName(int32 i, char* name, int32* _length)
{
// We're using the index position as a hint for the length
// of the string - this way, it's much less expansive to
@@ -186,7 +185,7 @@ generateName(int32 i,char *name,int32 *_length)
// We don't want to sort the strings to have more realistic
// access patterns to the tree (only true for the strings test).
int32 length = i % (MAX_STRING - MIN_STRING) + MIN_STRING;
- for (int32 i = 0;i < length;i++) {
+ for (int32 i = 0; i < length; i++) {
int32 c = int32(52.0 * rand() / RAND_MAX);
if (c >= 26)
name[i] = 'A' + c - 26;
@@ -199,43 +198,43 @@ generateName(int32 i,char *name,int32 *_length)
void
-fillBuffer(void *buffer,int32 start)
+fillBuffer(void* buffer, int32 start)
{
- for (int32 i = 0;i < gNum;i++) {
+ for (int32 i = 0; i < gNum; i++) {
switch (gType) {
case S_INT_INDEX:
{
- int32 *array = (int32 *)buffer;
+ int32* array = (int32*)buffer;
array[i] = start + i;
break;
}
case S_UINT_INDEX:
{
- uint32 *array = (uint32 *)buffer;
+ uint32* array = (uint32*)buffer;
array[i] = start + i;
break;
}
case S_LONG_LONG_INDEX:
{
- int64 *array = (int64 *)buffer;
+ int64* array = (int64*)buffer;
array[i] = start + i;
break;
}
case S_ULONG_LONG_INDEX:
{
- uint64 *array = (uint64 *)buffer;
+ uint64* array = (uint64*)buffer;
array[i] = start + i;
break;
}
case S_FLOAT_INDEX:
{
- float *array = (float *)buffer;
+ float* array = (float*)buffer;
array[i] = start + i * 1.0001;
break;
}
case S_DOUBLE_INDEX:
{
- double *array = (double *)buffer;
+ double* array = (double*)buffer;
array[i] = start + i * 1.0001;
break;
}
@@ -246,9 +245,9 @@ fillBuffer(void *buffer,int32 start)
bool
-findKey(void *key, int32 length, int32 maxIndex)
+findKey(void* key, int32 length, int32 maxIndex)
{
- for (int32 i = length;i < maxIndex;i += MAX_STRING - MIN_STRING) {
+ for (int32 i = length; i < maxIndex; i += MAX_STRING - MIN_STRING) {
if (length == (int32)gKeys[i].length
&& !memcpy(key, gKeys[i].data, length))
return true;
@@ -260,21 +259,22 @@ findKey(void *key, int32 length, int32 maxIndex)
status_t
createKeys()
{
- gKeys = (key *)malloc(gNum * sizeof(key));
+ gKeys = (key*)malloc(gNum * sizeof(key));
if (gKeys == NULL)
return B_NO_MEMORY;
if (gType == S_STR_INDEX) {
- for (int32 i = 0;i < gNum;i++) {
+ for (int32 i = 0; i < gNum; i++) {
char name[B_FILE_NAME_LENGTH];
- int32 length,tries = 0;
+ int32 length;
+ int32 tries = 0;
bool last;
// create unique keys!
do {
- generateName(i,name,&length);
- } while ((last = findKey(name,length,i)) && tries++ <
100);
-
+ generateName(i, name, &length);
+ } while ((last = findKey(name, length, i)) && tries++ <
100);
+
if (last) {
printf("Couldn't create unique key list!\n");
dumpKeys();
@@ -282,7 +282,7 @@ createKeys()
}
gKeys[i].data = malloc(length + 1);
- memcpy(gKeys[i].data,name,length + 1);
+ memcpy(gKeys[i].data, name, length + 1);
gKeys[i].length = length;
gKeys[i].in = 0;
gKeys[i].count = 0;
@@ -307,58 +307,60 @@ createKeys()
default:
return B_BAD_VALUE;
}
- uint8 *buffer = (uint8 *)malloc(length * gNum);
+ uint8* buffer = (uint8*)malloc(length * gNum);
if (buffer == NULL)
return B_NO_MEMORY;
- for (int32 i = 0;i < gNum;i++) {
- gKeys[i].data = (void *)(buffer + i * length);
+ for (int32 i = 0; i < gNum; i++) {
+ gKeys[i].data = (void*)(buffer + i * length);
gKeys[i].length = length;
gKeys[i].in = 0;
gKeys[i].count = 0;
}
- fillBuffer(buffer,start);
+ fillBuffer(buffer, start);
}
return B_OK;
}
-// #pragma mark -
-//
-// Tree validity checker
-//
+// #pragma mark - Validity checker
void
-checkTreeContents(BPlusTree *tree)
+checkTreeContents(BPlusTree* tree)
{
// reset counter
- for (int32 i = 0;i < gNum;i++)
+ for (int32 i = 0; i < gNum; i++)
gKeys[i].count = 0;
TreeIterator iterator(tree);
char key[B_FILE_NAME_LENGTH];
- uint16 length,duplicate;
+ uint16 length;
+ uint16 duplicate;
off_t value;
status_t status;
- while ((status =
iterator.GetNextEntry(key,&length,B_FILE_NAME_LENGTH,&value,&duplicate)) ==
B_OK) {
+ while ((status = iterator.GetNextEntry(key, &length, B_FILE_NAME_LENGTH,
+ &value, &duplicate)) == B_OK) {
if (value < 0 || value >= gNum) {
iterator.Dump();
- printf("\ninvalid value %Ld in tree: ",value);
- bailOutWithKey(key,length);
+ printf("\ninvalid value %Ld in tree: ", value);
+ bailOutWithKey(key, length);
}
if (gKeys[value].value != value) {
iterator.Dump();
- printf("\nkey pointing to the wrong value %Ld (should
be %Ld)\n",value,gKeys[value].value);
- bailOutWithKey(key,length);
+ printf("\nkey pointing to the wrong value %Ld (should
be %Ld)\n",
+ value, gKeys[value].value);
+ bailOutWithKey(key, length);
}
if (length != gKeys[value].length
- || memcmp(key,gKeys[value].data,length)) {
+ || memcmp(key, gKeys[value].data, length)) {
iterator.Dump();
- printf("\nkeys don't match (key index = %Ld, %ld times
in tree, %ld. occassion):\n\tfound: ",value,gKeys[value].in,gKeys[value].count
+ 1);
- dumpKey(key,length);
+ printf("\nkeys don't match (key index = %Ld, %ld times
in tree, "
+ "%ld. occassion):\n\tfound: ", value,
gKeys[value].in,
+ gKeys[value].count + 1);
+ dumpKey(key, length);
printf("\n\texpected: ");
- dumpKey(gKeys[value].data,gKeys[value].length);
+ dumpKey(gKeys[value].data, gKeys[value].length);
putchar('\n');
bailOut();
}
@@ -366,46 +368,46 @@ checkTreeContents(BPlusTree *tree)
gKeys[value].count++;
}
if (status != B_ENTRY_NOT_FOUND) {
- printf("TreeIterator::GetNext() returned:
%s\n",strerror(status));
+ printf("TreeIterator::GetNext() returned: %s\n",
strerror(status));
iterator.Dump();
bailOut();
}
- for (int32 i = 0;i < gNum;i++) {
+ for (int32 i = 0; i < gNum; i++) {
if (gKeys[i].in != gKeys[i].count) {
printf("Key ");
- dumpKey(gKeys[i].data,gKeys[i].length);
- printf(" found only %ld from
%ld\n",gKeys[i].count,gKeys[i].in);
+ dumpKey(gKeys[i].data, gKeys[i].length);
+ printf(" found only %ld from %ld\n", gKeys[i].count,
gKeys[i].in);
bailOut();
}
}
}
+/*! Simple test, just seeks down to every key - if it's in and couldn't
+ be found or it's not in and can be found, something must be wrong
+*/
void
-checkTreeIntegrity(BPlusTree *tree)
+checkTreeIntegrity(BPlusTree* tree)
{
- // simple test, just seeks down to every key - if it's in and couldn't
- // be found or it's not in and can be found, something must be wrong
-
TreeIterator iterator(tree);
- for (int32 i = 0;i < gNum;i++) {
- status_t status = iterator.Find((uint8
*)gKeys[i].data,gKeys[i].length);
+ for (int32 i = 0; i < gNum; i++) {
+ status_t status = iterator.Find((uint8*)gKeys[i].data,
gKeys[i].length);
if (gKeys[i].in == 0) {
if (status == B_OK) {
printf("found key %" B_PRId32 " even though
it's not in!\n", i);
bailOutWithKey(gKeys[i].data, gKeys[i].length);
}
} else if (status != B_OK) {
- printf("TreeIterator::Find() returned:
%s\n",strerror(status));
- bailOutWithKey(gKeys[i].data,gKeys[i].length);
+ printf("TreeIterator::Find() returned: %s\n",
strerror(status));
+ bailOutWithKey(gKeys[i].data, gKeys[i].length);
}
}
}
void
-checkTree(BPlusTree *tree)
+checkTree(BPlusTree* tree)
{
if (!gExcessive)
printf("* Check tree...\n");
@@ -422,25 +424,22 @@ checkTree(BPlusTree *tree)
}
-// #pragma mark -
-//
-// The tree "torture" functions
-//
+// #pragma mark - "Torture" functions
void
-addAllKeys(Transaction &transaction, BPlusTree *tree)
+addAllKeys(Transaction& transaction, BPlusTree* tree)
{
printf("*** Adding all keys to the tree...\n");
- for (int32 i = 0;i < gNum;i++) {
- status_t status = tree->Insert(transaction,(uint8
*)gKeys[i].data,gKeys[i].length,gKeys[i].value);
- if (status < B_OK) {
- printf("BPlusTree::Insert() returned:
%s\n",strerror(status));
+ for (int32 i = 0; i < gNum; i++) {
+ status_t status = tree->Insert(transaction,
(uint8*)gKeys[i].data,
+ gKeys[i].length, gKeys[i].value);
+ if (status != B_OK) {
+ printf("BPlusTree::Insert() returned: %s\n",
strerror(status));
printf("key: ");
- dumpKey(gKeys[i].data,gKeys[i].length);
+ dumpKey(gKeys[i].data, gKeys[i].length);
putchar('\n');
- }
- else {
+ } else {
gKeys[i].in++;
gTreeCount++;
}
@@ -450,54 +449,56 @@ addAllKeys(Transaction &transaction, BPlusTree *tree)
void
-removeAllKeys(Transaction &transaction, BPlusTree *tree)
+removeAllKeys(Transaction& transaction, BPlusTree* tree)
{
printf("*** Removing all keys from the tree...\n");
- for (int32 i = 0;i < gNum;i++) {
+ for (int32 i = 0; i < gNum; i++) {
while (gKeys[i].in > 0) {
- status_t status = tree->Remove(transaction, (uint8
*)gKeys[i].data,
+ status_t status = tree->Remove(transaction,
(uint8*)gKeys[i].data,
gKeys[i].length, gKeys[i].value);
- if (status < B_OK) {
+ if (status != B_OK) {
printf("BPlusTree::Remove() returned: %s\n",
strerror(status));
printf("key: ");
dumpKey(gKeys[i].data, gKeys[i].length);
putchar('\n');
- }
- else {
+ } else {
gKeys[i].in--;
gTreeCount--;
}
}
}
checkTree(tree);
-
+
}
void
-duplicateTest(Transaction &transaction,BPlusTree *tree)
+duplicateTest(Transaction& transaction, BPlusTree* tree)
{
int32 index = int32(1.0 * gNum * rand() / RAND_MAX);
if (index == gNum)
index = gNum - 1;
printf("*** Duplicate test with key ");
- dumpKey(gKeys[index].data,gKeys[index].length);
+ dumpKey(gKeys[index].data, gKeys[index].length);
puts("...");
status_t status;
int32 insertTotal = 0;
- for (int32 i = 0;i < 8;i++) {
+ for (int32 i = 0; i < 8; i++) {
int32 insertCount = int32(1000.0 * rand() / RAND_MAX);
- if (gVerbose)
- printf("* insert %ld to %ld old
entries...\n",insertCount,insertTotal + gKeys[index].in);
-
- for (int32 j = 0;j < insertCount;j++) {
- status = tree->Insert(transaction,(uint8
*)gKeys[index].data,gKeys[index].length,gKeys[index].value);
- if (status < B_OK) {
- printf("BPlusTree::Insert() returned:
%s\n",strerror(status));
-
bailOutWithKey(gKeys[index].data,gKeys[index].length);
+ if (gVerbose) {
+ printf("* insert %ld to %ld old entries...\n",
insertCount,
+ insertTotal + gKeys[index].in);
+ }
+
+ for (int32 j = 0; j < insertCount; j++) {
+ status = tree->Insert(transaction,
(uint8*)gKeys[index].data,
+ gKeys[index].length, gKeys[index].value);
+ if (status != B_OK) {
+ printf("BPlusTree::Insert() returned: %s\n",
strerror(status));
+ bailOutWithKey(gKeys[index].data,
gKeys[index].length);
}
insertTotal++;
gTreeCount++;
@@ -515,14 +516,18 @@ duplicateTest(Transaction &transaction,BPlusTree *tree)
} else
count = insertTotal;
- if (gVerbose)
- printf("* remove %ld from %ld
entries...\n",count,insertTotal + gKeys[index].in);
+ if (gVerbose) {
+ printf("* remove %ld from %ld entries...\n", count,
+ insertTotal + gKeys[index].in);
+ }
- for (int32 j = 0;j < count;j++) {
- status_t status = tree->Remove(transaction,(uint8
*)gKeys[index].data,gKeys[index].length,gKeys[index].value);
- if (status < B_OK) {
- printf("BPlusTree::Remove() returned:
%s\n",strerror(status));
-
bailOutWithKey(gKeys[index].data,gKeys[index].length);
+ for (int32 j = 0; j < count; j++) {
+ status_t status = tree->Remove(transaction,
+ (uint8*)gKeys[index].data, gKeys[index].length,
+ gKeys[index].value);
+ if (status != B_OK) {
+ printf("BPlusTree::Remove() returned: %s\n",
strerror(status));
+ bailOutWithKey(gKeys[index].data,
gKeys[index].length);
}
insertTotal--;
gTreeCount--;
@@ -539,22 +544,26 @@ duplicateTest(Transaction &transaction,BPlusTree *tree)
void
-addRandomSet(Transaction &transaction,BPlusTree *tree,int32 num)
+addRandomSet(Transaction& transaction, BPlusTree* tree, int32 num)
{
- printf("*** Add random set to tree (%ld to %ld old
entries)...\n",num,gTreeCount);
+ printf("*** Add random set to tree (%ld to %ld old entries)...\n",
+ num, gTreeCount);
- for (int32 i = 0;i < num;i++) {
+ for (int32 i = 0; i < num; i++) {
int32 index = int32(1.0 * gNum * rand() / RAND_MAX);
if (index == gNum)
index = gNum - 1;
- if (gVerbose)
- printf("adding key %ld (%ld times in the
tree)\n",index,gKeys[index].in);
+ if (gVerbose) {
+ printf("adding key %ld (%ld times in the tree)\n",
index,
+ gKeys[index].in);
+ }
- status_t status = tree->Insert(transaction,(uint8
*)gKeys[index].data,gKeys[index].length,gKeys[index].value);
- if (status < B_OK) {
- printf("BPlusTree::Insert() returned:
%s\n",strerror(status));
- bailOutWithKey(gKeys[index].data,gKeys[index].length);
+ status_t status = tree->Insert(transaction,
(uint8*)gKeys[index].data,
+ gKeys[index].length, gKeys[index].value);
+ if (status != B_OK) {
+ printf("BPlusTree::Insert() returned: %s\n",
strerror(status));
+ bailOutWithKey(gKeys[index].data, gKeys[index].length);
}
gKeys[index].in++;
gTreeCount++;
@@ -568,13 +577,14 @@ addRandomSet(Transaction &transaction,BPlusTree
*tree,int32 num)
void
-removeRandomSet(Transaction &transaction,BPlusTree *tree,int32 num)
+removeRandomSet(Transaction& transaction, BPlusTree* tree, int32 num)
{
- printf("*** Remove random set from tree (%ld from %ld
entries)...\n",num,gTreeCount);
+ printf("*** Remove random set from tree (%ld from %ld entries)...\n",
+ num, gTreeCount);
int32 tries = 500;
- for (int32 i = 0;i < num;i++) {
+ for (int32 i = 0; i < num; i++) {
if (gTreeCount < 1)
break;
@@ -589,13 +599,16 @@ removeRandomSet(Transaction &transaction,BPlusTree
*tree,int32 num)
continue;
}
- if (gVerbose)
- printf("removing key %ld (%ld times in the
tree)\n",index,gKeys[index].in);
+ if (gVerbose) {
+ printf("removing key %ld (%ld times in the tree)\n",
index,
+ gKeys[index].in);
+ }
- status_t status = tree->Remove(transaction,(uint8
*)gKeys[index].data,gKeys[index].length,gKeys[index].value);
- if (status < B_OK) {
- printf("BPlusTree::Remove() returned:
%s\n",strerror(status));
- bailOutWithKey(gKeys[index].data,gKeys[index].length);
+ status_t status = tree->Remove(transaction,
(uint8*)gKeys[index].data,
+ gKeys[index].length, gKeys[index].value);
+ if (status != B_OK) {
+ printf("BPlusTree::Remove() returned: %s\n",
strerror(status));
+ bailOutWithKey(gKeys[index].data, gKeys[index].length);
}
gKeys[index].in--;
gTreeCount--;
@@ -612,11 +625,12 @@ removeRandomSet(Transaction &transaction,BPlusTree
*tree,int32 num)
void
-usage(char *program)
+usage(char* program)
{
- if (strrchr(program,'/'))
- program = strrchr(program,'/') + 1;
- fprintf(stderr,"usage: %s [-veh] [-t type] [-n keys] [-i iterations]
[-h times] [-r seed]\n"
+ if (strrchr(program, '/'))
+ program = strrchr(program, '/') + 1;
+ fprintf(stderr, "usage: %s [-veh] [-t type] [-n keys] [-i iterations] "
+ "[-h times] [-r seed]\n"
"BFS B+Tree torture test\n"
"\t-t\ttype is one of string, int32, uint32, int64, uint64,
float,\n"
"\t\tor double; defaults to string.\n"
@@ -625,7 +639,8 @@ usage(char *program)
"\t-i\titerations is the number of the test cycles, defaults to
%d.\n"
"\t-r\tthe seed for the random function, defaults to %ld.\n"
"\t-h\tremoves the keys and start over again for x times.\n"
- "\t-e\texcessive validity tests: tree contents will be tested
after every operation\n"
+ "\t-e\texcessive validity tests: tree contents will be tested
after "
+ "every operation\n"
"\t-v\tfor verbose output.\n",
program, DEFAULT_NUM_KEYS, DEFAULT_ITERATIONS, gSeed);
exit(0);
@@ -633,22 +648,18 @@ usage(char *program)
int
-main(int argc,char **argv)
+main(int argc, char** argv)
{
- char *program = argv[0];
+ char* program = argv[0];
- while (*++argv)
- {
- char *arg = *argv;
- if (*arg == '-')
- {
+ while (*++argv) {
+ char* arg = *argv;
+ if (*arg == '-') {
if (arg[1] == '-')
usage(program);
- while (*++arg && isalpha(*arg))
- {
- switch (*arg)
- {
+ while (*++arg && isalpha(*arg)) {
+ switch (*arg) {
case 'v':
gVerbose = true;
break;
@@ -659,23 +670,23 @@ main(int argc,char **argv)
if (*++argv == NULL)
usage(program);
- if (!strcmp(*argv,"string"))
+ if (!strcmp(*argv, "string"))
gType = S_STR_INDEX;
- else if (!strcmp(*argv,"int32")
- || !strcmp(*argv,"int"))
+ else if (!strcmp(*argv, "int32")
+ || !strcmp(*argv,
"int"))
gType = S_INT_INDEX;
- else if (!strcmp(*argv,"uint32")
- ||
!strcmp(*argv,"uint"))
+ else if (!strcmp(*argv,
"uint32")
+ || !strcmp(*argv,
"uint"))
gType = S_UINT_INDEX;
- else if (!strcmp(*argv,"int64")
- ||
!strcmp(*argv,"llong"))
+ else if (!strcmp(*argv, "int64")
+ || !strcmp(*argv,
"llong"))
gType =
S_LONG_LONG_INDEX;
- else if (!strcmp(*argv,"uint64")
- ||
!strcmp(*argv,"ullong"))
+ else if (!strcmp(*argv,
"uint64")
+ || !strcmp(*argv,
"ullong"))
gType =
S_ULONG_LONG_INDEX;
- else if (!strcmp(*argv,"float"))
+ else if (!strcmp(*argv,
"float"))
gType = S_FLOAT_INDEX;
- else if
(!strcmp(*argv,"double"))
+ else if (!strcmp(*argv,
"double"))
gType = S_DOUBLE_INDEX;
else
usage(program);
@@ -683,7 +694,7 @@ main(int argc,char **argv)
case 'n':
if (*++argv == NULL ||
!isdigit(**argv))
usage(program);
-
+
gNum = atoi(*argv);
if (gNum < 1)
gNum = 1;
@@ -707,62 +718,62 @@ main(int argc,char **argv)
case 'r':
if (*++argv == NULL ||
!isdigit(**argv))
usage(program);
-
+
gSeed = atoi(*argv);
break;
}
}
- }
- else
+ } else
break;
}
// we do want to have reproducible random keys
if (gVerbose)
- printf("Set seed to %ld\n",gSeed);
+ printf("Set seed to %ld\n", gSeed);
srand(gSeed);
-
- Inode inode("tree.data",gType | S_ALLOW_DUPS);
+
+ Inode inode("tree.data", gType | S_ALLOW_DUPS);
rw_lock_write_lock(&inode.Lock());
gVolume = inode.GetVolume();
- Transaction transaction(gVolume,0);
+ Transaction transaction(gVolume, 0);
- init_cache(gVolume->Device(),gVolume->BlockSize());
+ init_cache(gVolume->Device(), gVolume->BlockSize());
- //
// Create the tree, the keys, and add all keys to the tree initially
- //
- BPlusTree tree(transaction,&inode);
- status_t status;
- if ((status = tree.InitCheck()) < B_OK) {
- fprintf(stderr,"creating tree failed: %s\n",strerror(status));
+ BPlusTree tree(transaction, &inode);
+ status_t status = tree.InitCheck();
+ if (status != B_OK) {
+ fprintf(stderr, "creating tree failed: %s\n", strerror(status));
bailOut();
}
- printf("*** Creating %ld keys...\n",gNum);
- if ((status = createKeys()) < B_OK) {
- fprintf(stderr,"creating keys failed: %s\n",strerror(status));
+
+ printf("*** Creating %ld keys...\n", gNum);
+ status = createKeys();
+ if (status != B_OK) {
+ fprintf(stderr, "creating keys failed: %s\n", strerror(status));
bailOut();
}
if (gVerbose)
dumpKeys();
- for (int32 j = 0; j < gHard; j++ ) {
+ for (int32 j = 0; j < gHard; j++) {
addAllKeys(transaction, &tree);
- //
// Run the tests (they will exit the app, if an error occurs)
- //
-
- for (int32 i = 0;i < gIterations;i++) {
- printf("---------- Test iteration %ld
---------------------------------\n",i+1);
-
- addRandomSet(transaction,&tree,int32(1.0 * gNum *
rand() / RAND_MAX));
- removeRandomSet(transaction,&tree,int32(1.0 * gNum *
rand() / RAND_MAX));
- duplicateTest(transaction,&tree);
+
+ for (int32 i = 0; i < gIterations; i++) {
+ printf("---------- Test iteration %ld
--------------------------\n",
+ i + 1);
+
+ addRandomSet(transaction, &tree,
+ int32(1.0 * gNum * rand() / RAND_MAX));
+ removeRandomSet(transaction, &tree,
+ int32(1.0 * gNum * rand() / RAND_MAX));
+ duplicateTest(transaction, &tree);
}
-
+
removeAllKeys(transaction, &tree);
}
@@ -771,7 +782,7 @@ main(int argc,char **argv)
// of course, we would have to free all our memory in a real
application here...
// write the cache back to the tree
- shutdown_cache(gVolume->Device(),gVolume->BlockSize());
+ shutdown_cache(gVolume->Device(), gVolume->BlockSize());
return 0;
}
############################################################################
Commit: aeb121ec03aaf91a3e46f7e50b393a2786af4776
URL: http://cgit.haiku-os.org/haiku/commit/?id=aeb121ec03aa
Author: Axel Dörfler <axeld@xxxxxxxxxxxxxxxx>
Date: Tue Jan 13 17:23:59 2015 UTC
Sudoku: consolidated set value code paths.
* Renamed _ToggleValue() to _SetValue(), and only let it do that.
* It's now called from _InsertKey(), and _SolveSingle() as well which
results in a correct visual update (ie. completed values, and the
value hints are updated correctly).
* _SolveSingle() would also not test for a completed game.
----------------------------------------------------------------------------
diff --git a/src/apps/sudoku/SudokuView.cpp b/src/apps/sudoku/SudokuView.cpp
index 87ba676..fd0adbb 100644
--- a/src/apps/sudoku/SudokuView.cpp
+++ b/src/apps/sudoku/SudokuView.cpp
@@ -618,7 +618,7 @@ SudokuView::MouseDown(BPoint where)
| B_TERTIARY_MOUSE_BUTTON)) != 0) {
// Double click or other buttons set or remove a value
if (!fField->IsInitialValue(x, y))
- _ToggleValue(x, y, value, field);
+ _SetValue(x, y, fField->ValueAt(x, y) == 0 ? value + 1
: 0);
return;
}
@@ -1068,9 +1068,7 @@ SudokuView::_InsertKey(char rawKey, int32 modifiers)
fField->SetHintMaskAt(fKeyboardX, fKeyboardY, hintMask);
} else {
_PushUndo();
- fField->SetValueAt(fKeyboardX, fKeyboardY, value);
- if (value)
- BMessenger(this).SendMessage(kMsgCheckSolved);
+ _SetValue(fKeyboardX, fKeyboardY, value);
}
}
@@ -1112,37 +1110,37 @@ SudokuView::_GetFieldFor(BPoint where, uint32& x,
uint32& y)
void
-SudokuView::_ToggleValue(uint32 x, uint32 y, uint32 value, uint32 field)
+SudokuView::_SetValue(uint32 x, uint32 y, uint32 value)
{
bool wasCompleted;
- if (fField->ValueAt(x, y) > 0) {
+ if (value == 0) {
// Remove value
- value = fField->ValueAt(x, y) - 1;
- wasCompleted = fField->IsValueCompleted(value + 1);
+ value = fField->ValueAt(x, y);
+ wasCompleted = fField->IsValueCompleted(value);
fField->SetValueAt(x, y, 0);
fShowHintX = x;
fShowHintY = y;
} else {
// Set value
- wasCompleted = fField->IsValueCompleted(value + 1);
+ wasCompleted = fField->IsValueCompleted(value);
- fField->SetValueAt(x, y, value + 1);
+ fField->SetValueAt(x, y, value);
BMessenger(this).SendMessage(kMsgCheckSolved);
_RemoveHintValues(x, y, value);
// allow dragging to remove the hint from other fields
fLastHintValueSet = false;
- fLastHintValue = value;
- fLastField = field;
+ fLastHintValue = value - 1;
+ fLastField = x + y * fField->Size();
}
- if (value + 1 != fValueHintValue && fValueHintValue != ~0UL)
- _SetValueHintValue(value + 1);
+ if (value != fValueHintValue && fValueHintValue != ~0UL)
+ _SetValueHintValue(value);
- if (wasCompleted != fField->IsValueCompleted(value + 1))
- _InvalidateValue(value + 1, false, x, y);
+ if (wasCompleted != fField->IsValueCompleted(value))
+ _InvalidateValue(value, false, x, y);
else
_InvalidateField(x, y);
}
@@ -1181,7 +1179,7 @@ SudokuView::_RemoveHintValues(uint32 atX, uint32 atY,
uint32 value)
uint32 blockSize = fField->BlockSize();
uint32 blockX = (atX / blockSize) * blockSize;
uint32 blockY = (atY / blockSize) * blockSize;
- uint32 valueMask = 1UL << value;
+ uint32 valueMask = 1UL << (value - 1);
for (uint32 y = blockY; y < blockY + blockSize; y++) {
for (uint32 x = blockX; x < blockX + blockSize; x++) {
@@ -1259,9 +1257,8 @@ SudokuView::_SolveSingle()
y = rand() % fField->Size();
} while (fField->ValueAt(x, y));
- fField->SetValueAt(x, y,
- solver.SolutionAt(0)->ValueAt(x, y));
- _InvalidateField(x, y);
+ uint32 value = solver.SolutionAt(0)->ValueAt(x, y);
+ _SetValue(x, y, value);
} else
beep();
}
diff --git a/src/apps/sudoku/SudokuView.h b/src/apps/sudoku/SudokuView.h
index c0d00ed..15239bd 100644
--- a/src/apps/sudoku/SudokuView.h
+++ b/src/apps/sudoku/SudokuView.h
@@ -106,8 +106,7 @@ private:
uint32
y, uint32& hintX, uint32& hintY);
bool _GetFieldFor(BPoint
where, uint32& x,
uint32&
y);
- void _ToggleValue(uint32 x,
uint32 y, uint32 value,
- uint32
field);
+ void _SetValue(uint32 x,
uint32 y, uint32 value);
void _ToggleHintValue(uint32
x, uint32 y,
uint32
hintX, uint32 hintY,
uint32
value, uint32 field);
############################################################################
Commit: 9b61a43ad63dd0318405458cb9ff0e59f88e3d7f
URL: http://cgit.haiku-os.org/haiku/commit/?id=9b61a43ad63d
Author: Axel Dörfler <axeld@xxxxxxxxxxxxxxxx>
Date: Wed Jan 14 07:59:17 2015 UTC
MediaPlayer: make sure info window is on screen.
----------------------------------------------------------------------------
diff --git a/src/apps/mediaplayer/InfoWin.cpp b/src/apps/mediaplayer/InfoWin.cpp
index a066688..1839c61 100644
--- a/src/apps/mediaplayer/InfoWin.cpp
+++ b/src/apps/mediaplayer/InfoWin.cpp
@@ -32,6 +32,7 @@
#include <MessageFormat.h>
#include <Mime.h>
#include <NodeInfo.h>
+#include <Screen.h>
#include <String.h>
#include <StringForRate.h>
#include <StringView.h>
@@ -219,6 +220,13 @@ InfoWin::InfoWin(BPoint leftTop, Controller* controller)
fController->AddListener(fControllerObserver);
Update();
+ // Move window on screen if needed
+ BScreen screen(this);
+ if (screen.Frame().bottom < Frame().bottom)
+ MoveBy(0, screen.Frame().bottom - Frame().bottom);
+ if (screen.Frame().right < Frame().right)
+ MoveBy(0, screen.Frame().right - Frame().right);
+
Show();
}
############################################################################
Revision: hrev48681
Commit: 7fb1396861fb37acddc0eca58fa55de2100f98a7
URL: http://cgit.haiku-os.org/haiku/commit/?id=7fb1396861fb
Author: Axel Dörfler <axeld@xxxxxxxxxxxxxxxx>
Date: Wed Jan 14 16:30:15 2015 UTC
BFS B+tree test: use set to ensure string uniqueness.
* The previous solution was rather slow, and also could produce
duplicates under some circumstance.
----------------------------------------------------------------------------
diff --git a/src/tests/add-ons/kernel/file_systems/bfs/btree/test.cpp
b/src/tests/add-ons/kernel/file_systems/bfs/btree/test.cpp
index 65eb96e..97d052e 100644
--- a/src/tests/add-ons/kernel/file_systems/bfs/btree/test.cpp
+++ b/src/tests/add-ons/kernel/file_systems/bfs/btree/test.cpp
@@ -7,6 +7,9 @@
//! BFS B+Tree torture test
+#include <set>
+#include <string>
+
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
@@ -179,12 +182,7 @@ dumpKeys()
void
generateName(int32 i, char* name, int32* _length)
{
- // We're using the index position as a hint for the length
- // of the string - this way, it's much less expansive to
- // test for string uniqueness.
- // We don't want to sort the strings to have more realistic
- // access patterns to the tree (only true for the strings test).
- int32 length = i % (MAX_STRING - MIN_STRING) + MIN_STRING;
+ int32 length = rand() % (MAX_STRING - MIN_STRING) + MIN_STRING;
for (int32 i = 0; i < length; i++) {
int32 c = int32(52.0 * rand() / RAND_MAX);
if (c >= 26)
@@ -244,18 +242,6 @@ fillBuffer(void* buffer, int32 start)
}
-bool
-findKey(void* key, int32 length, int32 maxIndex)
-{
- for (int32 i = length; i < maxIndex; i += MAX_STRING - MIN_STRING) {
- if (length == (int32)gKeys[i].length
- && !memcpy(key, gKeys[i].data, length))
- return true;
- }
- return false;
-}
-
-
status_t
createKeys()
{
@@ -264,18 +250,23 @@ createKeys()
return B_NO_MEMORY;
if (gType == S_STR_INDEX) {
+ std::set<std::string> set;
+
for (int32 i = 0; i < gNum; i++) {
char name[B_FILE_NAME_LENGTH];
int32 length;
int32 tries = 0;
- bool last;
+ std::set<std::string>::const_iterator found;
// create unique keys!
- do {
+ while (tries++ < 100) {
generateName(i, name, &length);
- } while ((last = findKey(name, length, i)) && tries++ <
100);
+ found = set.find(string(name));
+ if (found == set.end())
+ break;
+ }
- if (last) {
+ if (found != set.end()) {
printf("Couldn't create unique key list!\n");
dumpKeys();
bailOut();
@@ -287,6 +278,7 @@ createKeys()
gKeys[i].in = 0;
gKeys[i].count = 0;
gKeys[i].value = i;
+ set.insert(name);
}
} else {
int32 length;
@@ -437,8 +429,7 @@ addAllKeys(Transaction& transaction, BPlusTree* tree)
if (status != B_OK) {
printf("BPlusTree::Insert() returned: %s\n",
strerror(status));
printf("key: ");
- dumpKey(gKeys[i].data, gKeys[i].length);
- putchar('\n');
+ bailOutWithKey(gKeys[i].data, gKeys[i].length);
} else {
gKeys[i].in++;
gTreeCount++;
@@ -779,7 +770,8 @@ main(int argc, char** argv)
transaction.Done();
- // of course, we would have to free all our memory in a real
application here...
+ // Of course, we would have to free all our memory in a real application
+ // here...
// write the cache back to the tree
shutdown_cache(gVolume->Device(), gVolume->BlockSize());
Other related posts:
- » [haiku-commits] haiku: hrev48681 - in src: tests/add-ons/kernel/file_systems/bfs/btree apps/sudoku - axeld
