summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/Makefile.am2
-rw-r--r--src/directory.c1
-rw-r--r--src/main.c89
-rw-r--r--src/player.c89
-rw-r--r--src/player.h2
-rw-r--r--src/playerData.c19
-rw-r--r--src/playerData.h3
-rw-r--r--src/sig_handlers.c91
-rw-r--r--src/sig_handlers.h4
-rw-r--r--src/tagTracker.c137
-rw-r--r--src/tree.c712
-rw-r--r--src/tree.h62
12 files changed, 916 insertions, 295 deletions
diff --git a/src/Makefile.am b/src/Makefile.am
index 1dfcd476e..e7f301703 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -68,6 +68,7 @@ mpd_headers = \
stats.h \
tag.h \
tagTracker.h \
+ tree.h \
utf8.h \
utils.h \
volume.h
@@ -116,6 +117,7 @@ mpd_SOURCES = \
stats.c \
tag.c \
tagTracker.c \
+ tree.c \
utils.c \
volume.c \
utf8.c
diff --git a/src/directory.c b/src/directory.c
index da4b0a4eb..9b90418f2 100644
--- a/src/directory.c
+++ b/src/directory.c
@@ -173,6 +173,7 @@ int updateInit(int fd, List * pathList)
if (directory_updatePid == 0) {
/* child */
int dbUpdated = 0;
+ clearPlayerPid();
unblockSignals();
diff --git a/src/main.c b/src/main.c
index d06202857..30324cea2 100644
--- a/src/main.c
+++ b/src/main.c
@@ -54,14 +54,12 @@
#include <fcntl.h>
#include <pwd.h>
#include <grp.h>
+#include <time.h>
#include <unistd.h>
#define SYSTEM_CONFIG_FILE_LOCATION "/etc/mpd.conf"
#define USER_CONFIG_FILE_LOCATION "/.mpdconf"
-volatile int masterPid = 0;
-volatile int mainPid = 0;
-
typedef struct _Options {
int kill;
int daemon;
@@ -311,47 +309,6 @@ static void openDB(Options * options, char *argv0)
}
}
-static void startMainProcess(void)
-{
- int pid;
- fflush(0);
- pid = fork();
- if (pid > 0) {
- initInputStream();
- initReplayGainState();
-
- /* free stuff we don't need */
- freeAllListenSockets();
-
- mainPid = pid;
- masterInitSigHandlers();
- kill(mainPid, SIGUSR1);
- while (masterHandlePendingSignals() != COMMAND_RETURN_KILL)
- waitOnSignals();
- /* we're killed */
- playerKill();
-
- finishPlaylist();
-
- finishAudioConfig();
- finishAudioDriver();
-
- finishPaths();
-
- kill(mainPid, SIGTERM);
- waitpid(mainPid, NULL, 0);
- finishConf();
- close_log_files();
- exit(EXIT_SUCCESS);
-
- } else if (pid < 0) {
- ERROR("problems fork'ing main process!\n");
- exit(EXIT_FAILURE);
- }
-
- DEBUG("main process started!\n");
-}
-
static void daemonize(Options * options)
{
FILE *fp = NULL;
@@ -409,7 +366,6 @@ static void daemonize(Options * options)
DEBUG("writing pid file\n");
fprintf(fp, "%lu\n", (unsigned long)getpid());
fclose(fp);
- masterPid = getpid();
}
}
@@ -480,38 +436,30 @@ int main(int argc, char *argv[])
open_log_files(options.stdOutput);
- initPlayerData();
-
- initInputPlugins();
initPaths();
+ initPermissions();
+ initPlaylist();
+ initInputPlugins();
+
+ openDB(&options, argv[0]);
+
+ initCommands();
+ initPlayerData();
initAudioConfig();
initAudioDriver();
+ initVolume();
+ initInterfaces();
+ initReplayGainState();
initNormalization();
- initPlaylist();
- openDB(&options, argv[0]);
+ initInputStream();
daemonize(&options);
- initSigHandlers();
setup_log_output(options.stdOutput);
- startMainProcess();
- /* This is the main process which has
- * been forked from the master process.
- */
-
- initPermissions();
- initCommands();
- initVolume();
- initInterfaces();
- printMemorySavedByTagTracker();
- printSavedMemoryFromFilenames();
- /* wait for the master process to get ready so we can start
- * playing if readPlaylistState thinks we should*/
- while (COMMAND_MASTER_READY != handlePendingSignals())
- my_usleep(1);
+ initSigHandlers();
openVolumeDevice();
read_state_file();
@@ -525,13 +473,14 @@ int main(int argc, char *argv[])
}
write_state_file();
-
+ playerKill();
freeAllInterfaces();
closeAllListenSockets();
- /* This slows shutdown immensely, and doesn't really accomplish
- * anything. Uncomment when we rewrite tagTracker to use a tree. */
- /*closeMp3Directory(); */
+ clock_t start = clock();
+ closeMp3Directory();
+ DEBUG("closeMp3Directory took %f seconds\n",
+ ((float)(clock()-start))/CLOCKS_PER_SEC);
finishPlaylist();
freePlayerData();
diff --git a/src/player.c b/src/player.c
index 7353debcf..17ec780ed 100644
--- a/src/player.c
+++ b/src/player.c
@@ -44,7 +44,12 @@
#include <errno.h>
#include <fcntl.h>
-extern int masterPid;
+volatile int player_pid = 0;
+
+void clearPlayerPid()
+{
+ player_pid = 0;
+}
static void resetPlayerMetadata()
{
@@ -59,7 +64,7 @@ void resetPlayer()
{
int pid;
- setPlayerPid(0);
+ clearPlayerPid();
getPlayerData()->playerControl.stop = 0;
getPlayerData()->playerControl.play = 0;
getPlayerData()->playerControl.pause = 0;
@@ -78,17 +83,23 @@ void resetPlayer()
void player_sigChldHandler(int pid, int status)
{
- if (getPlayerPid() == pid) {
+ if (player_pid == pid)
+ {
DEBUG("SIGCHLD caused by player process\n");
- if (WIFSIGNALED(status) && WTERMSIG(status) != SIGTERM &&
- WTERMSIG(status) != SIGINT) {
+ if (WIFSIGNALED(status) &&
+ WTERMSIG(status) != SIGTERM &&
+ WTERMSIG(status) != SIGINT)
+ {
ERROR("player process died from signal: %i\n",
WTERMSIG(status));
}
resetPlayer();
- } else if (pid == getPlayerData()->playerControl.decode_pid
- && getPlayerPid() <= 0) {
- if (WIFSIGNALED(status) && WTERMSIG(status) != SIGTERM) {
+ }
+ else if (pid == getPlayerData()->playerControl.decode_pid &&
+ player_pid <= 0)
+ {
+ if (WIFSIGNALED(status) && WTERMSIG(status) != SIGTERM)
+ {
ERROR("(caught by master parent) "
"decode process died from a "
"non-TERM signal: %i\n", WTERMSIG(status));
@@ -99,25 +110,29 @@ void player_sigChldHandler(int pid, int status)
int playerInit()
{
- kill(masterPid, SIGUSR2);
- /* we need to wait for the signal to take effect: */
- while (getPlayerPid() == 0)
- my_usleep(10000);
- return 0;
-}
-
-int playerInitReal()
-{
- int player_pid;
blockSignals();
player_pid = fork();
- if (player_pid == 0) {
+ if (player_pid==0)
+ {
+ clock_t start = clock();
+
PlayerControl *pc = &(getPlayerData()->playerControl);
unblockSignals();
setSigHandlersForDecoder();
+ closeAllListenSockets();
+ freeAllInterfaces();
+ closeMp3Directory();
+ finishPlaylist();
+ finishPermissions();
+ finishCommands();
+ finishVolume();
+
+ DEBUG("took %f to init player\n",
+ (float)(clock()-start)/CLOCKS_PER_SEC);
+
while (1) {
if (pc->play)
decode();
@@ -143,14 +158,14 @@ int playerInitReal()
}
exit(EXIT_SUCCESS);
- } else if (player_pid < 0) {
+ }
+ else if (player_pid < 0)
+ {
unblockSignals();
ERROR("player Problems fork()'ing\n");
- setPlayerPid(0);
player_pid = 0;
return -1;
- } else
- setPlayerPid(player_pid);
+ }
unblockSignals();
@@ -174,13 +189,13 @@ int playerPlay(int fd, Song * song)
pathcpy_trunc(pc->utf8url, getSongUrl(song));
pc->play = 1;
- if (getPlayerPid() == 0 && playerInit() < 0) {
+ if (player_pid == 0 && playerInit() < 0) {
pc->play = 0;
return -1;
}
resetPlayerMetadata();
- while (getPlayerPid() > 0 && pc->play)
+ while (player_pid > 0 && pc->play)
my_usleep(1000);
return 0;
@@ -190,9 +205,9 @@ int playerStop(int fd)
{
PlayerControl *pc = &(getPlayerData()->playerControl);
- if (getPlayerPid() > 0 && pc->state != PLAYER_STATE_STOP) {
+ if (player_pid > 0 && pc->state != PLAYER_STATE_STOP) {
pc->stop = 1;
- while (getPlayerPid() > 0 && pc->stop)
+ while (player_pid > 0 && pc->stop)
my_usleep(1000);
}
@@ -211,7 +226,7 @@ void playerKill()
playerCloseAudio(stderr);
if(player_pid>0 && pc->closeAudio) sleep(1); */
- pid = getPlayerPid();
+ pid = player_pid;
if (pid > 0)
kill(pid, SIGTERM);
}
@@ -220,9 +235,9 @@ int playerPause(int fd)
{
PlayerControl *pc = &(getPlayerData()->playerControl);
- if (getPlayerPid() > 0 && pc->state != PLAYER_STATE_STOP) {
+ if (player_pid > 0 && pc->state != PLAYER_STATE_STOP) {
pc->pause = 1;
- while (getPlayerPid() > 0 && pc->pause)
+ while (player_pid > 0 && pc->pause)
my_usleep(1000);
}
@@ -233,7 +248,7 @@ int playerSetPause(int fd, int pause)
{
PlayerControl *pc = &(getPlayerData()->playerControl);
- if (getPlayerPid() <= 0)
+ if (player_pid <= 0)
return 0;
switch (pc->state) {
@@ -325,7 +340,7 @@ void playerCloseAudio()
{
PlayerControl *pc = &(getPlayerData()->playerControl);
- if (getPlayerPid() > 0) {
+ if (player_pid > 0) {
if (playerStop(STDERR_FILENO) < 0)
return;
pc->closeAudio = 1;
@@ -371,9 +386,9 @@ void playerQueueLock()
{
PlayerControl *pc = &(getPlayerData()->playerControl);
- if (getPlayerPid() > 0 && pc->queueLockState == PLAYER_QUEUE_UNLOCKED) {
+ if (player_pid > 0 && pc->queueLockState == PLAYER_QUEUE_UNLOCKED) {
pc->lockQueue = 1;
- while (getPlayerPid() > 0 && pc->lockQueue)
+ while (player_pid > 0 && pc->lockQueue)
my_usleep(1000);
}
}
@@ -382,9 +397,9 @@ void playerQueueUnlock()
{
PlayerControl *pc = &(getPlayerData()->playerControl);
- if (getPlayerPid() > 0 && pc->queueLockState == PLAYER_QUEUE_LOCKED) {
+ if (player_pid > 0 && pc->queueLockState == PLAYER_QUEUE_LOCKED) {
pc->unlockQueue = 1;
- while (getPlayerPid() > 0 && pc->unlockQueue)
+ while (player_pid > 0 && pc->unlockQueue)
my_usleep(1000);
}
}
@@ -414,7 +429,7 @@ int playerSeek(int fd, Song * song, float time)
resetPlayerMetadata();
pc->seekWhere = time;
pc->seek = 1;
- while (getPlayerPid() > 0 && pc->seek)
+ while (player_pid > 0 && pc->seek)
my_usleep(1000);
}
diff --git a/src/player.h b/src/player.h
index 77d16174b..ac83c9ea5 100644
--- a/src/player.h
+++ b/src/player.h
@@ -89,8 +89,6 @@ typedef struct _PlayerControl {
MetadataChunk fileMetadataChunk;
} PlayerControl;
-int playerInitReal();
-
void player_sigChldHandler(int pid, int status);
int playerPlay(int fd, Song * song);
diff --git a/src/playerData.c b/src/playerData.c
index 79663f00f..df928acc4 100644
--- a/src/playerData.c
+++ b/src/playerData.c
@@ -95,15 +95,18 @@ void initPlayerData(void)
/* for audioDeviceStates[] */
allocationSize += device_array_size;
- if ((shmid = shmget(IPC_PRIVATE, allocationSize, IPC_CREAT | 0600)) < 0) {
+ if ((shmid = shmget(IPC_PRIVATE, allocationSize, IPC_CREAT | 0600)) < 0)
+ {
ERROR("problems shmget'ing\n");
exit(EXIT_FAILURE);
}
- if (!(playerData_pd = shmat(shmid, NULL, 0))) {
+ if (!(playerData_pd = shmat(shmid, NULL, 0)))
+ {
ERROR("problems shmat'ing\n");
exit(EXIT_FAILURE);
}
- if (shmctl(shmid, IPC_RMID, NULL) < 0) {
+ if (shmctl(shmid, IPC_RMID, NULL) < 0)
+ {
ERROR("problems shmctl'ing\n");
exit(EXIT_FAILURE);
}
@@ -159,16 +162,6 @@ PlayerData *getPlayerData(void)
return playerData_pd;
}
-int getPlayerPid(void)
-{
- return playerData_pd->pid;
-}
-
-void setPlayerPid(int pid)
-{
- playerData_pd->pid = pid;
-}
-
void freePlayerData(void)
{
shmdt(playerData_pd);
diff --git a/src/playerData.h b/src/playerData.h
index 777232bfa..00ba66d02 100644
--- a/src/playerData.h
+++ b/src/playerData.h
@@ -38,14 +38,11 @@ typedef struct _PlayerData {
PlayerControl playerControl;
DecoderControl decoderControl;
mpd_uint8 *audioDeviceStates;
- int pid;
} PlayerData;
void initPlayerData();
PlayerData *getPlayerData();
-int getPlayerPid();
-void setPlayerPid(int pid);
void freePlayerData();
diff --git a/src/sig_handlers.c b/src/sig_handlers.c
index e5d300778..2c6a07a00 100644
--- a/src/sig_handlers.c
+++ b/src/sig_handlers.c
@@ -39,34 +39,8 @@
extern volatile int masterPid;
extern volatile int mainPid;
-int masterHandlePendingSignals()
-{
- if (signal_is_pending(SIGINT) || signal_is_pending(SIGTERM)) {
- DEBUG("master process got SIGINT or SIGTERM, exiting\n");
- return COMMAND_RETURN_KILL;
- }
-
- if (signal_is_pending(SIGHUP)) {
- signal_clear(SIGHUP);
- /* Forward it to the main process, which will update the DB */
- kill(mainPid, SIGHUP);
- }
-
- return 0;
-}
-
int handlePendingSignals()
{
- /* this SIGUSR1 signal comes before the KILL signals, because there if the process is
- * looping, waiting for this signal, it will not respond to the KILL signal. This might be
- * better implemented by using bit-wise defines and or'ing of the COMMAND_FOO as return.
- */
- if (signal_is_pending(SIGUSR1)) {
- signal_clear(SIGUSR1);
- DEBUG("The master process is ready to receive signals\n");
- return COMMAND_MASTER_READY;
- }
-
if (signal_is_pending(SIGINT) || signal_is_pending(SIGTERM)) {
DEBUG("main process got SIGINT or SIGTERM, exiting\n");
return COMMAND_RETURN_KILL;
@@ -99,56 +73,11 @@ void chldSigHandler(int signal)
else
break;
}
- directory_sigChldHandler(pid, status);
- }
-}
-
-void masterChldSigHandler(int signal)
-{
- int status;
- int pid;
- DEBUG("master process got SIGCHLD\n");
- while (0 != (pid = wait3(&status, WNOHANG, NULL))) {
- if (pid < 0) {
- if (errno == EINTR)
- continue;
- else
- break;
- }
- DEBUG("PID: %d\n", pid);
- if (pid == mainPid)
- kill(getpid(), SIGTERM);
player_sigChldHandler(pid, status);
+ directory_sigChldHandler(pid, status);
}
}
-int playerInitReal();
-
-void masterSigUsr2Handler(int signal)
-{
- DEBUG("Master process got SIGUSR2 starting a new player process\n");
- if (getPlayerPid() <= 0)
- playerInitReal();
-}
-
-void masterInitSigHandlers()
-{
- struct sigaction sa;
-
- sa.sa_flags = 0;
- sigemptyset(&sa.sa_mask);
- sa.sa_handler = SIG_IGN;
- while (sigaction(SIGPIPE, &sa, NULL) < 0 && errno == EINTR) ;
- sa.sa_handler = masterChldSigHandler;
- while (sigaction(SIGCHLD, &sa, NULL) < 0 && errno == EINTR) ;
- sa.sa_handler = masterSigUsr2Handler;
- while (sigaction(SIGUSR2, &sa, NULL) < 0 && errno == EINTR) ;
- signal_handle(SIGUSR1);
- signal_handle(SIGINT);
- signal_handle(SIGTERM);
- signal_handle(SIGHUP);
-}
-
void initSigHandlers()
{
struct sigaction sa;
@@ -159,7 +88,6 @@ void initSigHandlers()
while (sigaction(SIGPIPE, &sa, NULL) < 0 && errno == EINTR) ;
sa.sa_handler = chldSigHandler;
while (sigaction(SIGCHLD, &sa, NULL) < 0 && errno == EINTR) ;
- signal_handle(SIGUSR2);
signal_handle(SIGUSR1);
signal_handle(SIGINT);
signal_handle(SIGTERM);
@@ -202,26 +130,11 @@ void ignoreSignals()
while (sigaction(SIGPIPE, &sa, NULL) < 0 && errno == EINTR) ;
while (sigaction(SIGCHLD, &sa, NULL) < 0 && errno == EINTR) ;
while (sigaction(SIGUSR1, &sa, NULL) < 0 && errno == EINTR) ;
- while (sigaction(SIGUSR2, &sa, NULL) < 0 && errno == EINTR) ;
while (sigaction(SIGINT, &sa, NULL) < 0 && errno == EINTR) ;
while (sigaction(SIGTERM, &sa, NULL) < 0 && errno == EINTR) ;
while (sigaction(SIGHUP, &sa, NULL) < 0 && errno == EINTR) ;
}
-void waitOnSignals()
-{
- sigset_t sset;
-
- sigfillset(&sset);
- sigdelset(&sset, SIGCHLD);
- sigdelset(&sset, SIGUSR1);
- sigdelset(&sset, SIGUSR2);
- sigdelset(&sset, SIGHUP);
- sigdelset(&sset, SIGINT);
- sigdelset(&sset, SIGTERM);
- sigsuspend(&sset);
-}
-
void blockSignals()
{
sigset_t sset;
@@ -229,7 +142,6 @@ void blockSignals()
sigemptyset(&sset);
sigaddset(&sset, SIGCHLD);
sigaddset(&sset, SIGUSR1);
- sigaddset(&sset, SIGUSR2);
sigaddset(&sset, SIGHUP);
sigaddset(&sset, SIGINT);
sigaddset(&sset, SIGTERM);
@@ -243,7 +155,6 @@ void unblockSignals()
sigemptyset(&sset);
sigaddset(&sset, SIGCHLD);
sigaddset(&sset, SIGUSR1);
- sigaddset(&sset, SIGUSR2);
sigaddset(&sset, SIGHUP);
sigaddset(&sset, SIGINT);
sigaddset(&sset, SIGTERM);
diff --git a/src/sig_handlers.h b/src/sig_handlers.h
index 186ebb85f..c58696d0d 100644
--- a/src/sig_handlers.h
+++ b/src/sig_handlers.h
@@ -22,10 +22,8 @@
#include "../config.h"
int handlePendingSignals();
-int masterHandlePendingSignals();
void initSigHandlers();
-void masterInitSigHandlers();
void finishSigHandlers();
@@ -33,8 +31,6 @@ void setSigHandlersForDecoder();
void ignoreSignals();
-void waitOnSignals();
-
void blockSignals();
void unblockSignals();
diff --git a/src/tagTracker.c b/src/tagTracker.c
index b4de6129d..a0ab57d6f 100644
--- a/src/tagTracker.c
+++ b/src/tagTracker.c
@@ -18,12 +18,13 @@
#include "tagTracker.h"
-#include "list.h"
+#include "tree.h"
#include "log.h"
#include <assert.h>
+#include <stdlib.h>
-static List *tagLists[TAG_NUM_OF_ITEM_TYPES] = {
+static Tree *tagTrees[TAG_NUM_OF_ITEM_TYPES] = {
NULL,
NULL,
NULL,
@@ -40,129 +41,113 @@ typedef struct tagTrackerItem {
char *getTagItemString(int type, char *string)
{
- ListNode *node;
- int pos;
-
- if (tagLists[type] == NULL) {
- tagLists[type] = makeList(free, 1);
- sortList(tagLists[type]);
+ TreeIterator iter;
+
+ if (tagTrees[type] == NULL)
+ {
+ tagTrees[type] = MakeTree((TreeCompareKeyFunction)strcmp,
+ (TreeFreeFunction)free,
+ (TreeFreeFunction)free);
}
- if (findNodeInList(tagLists[type], string, &node, &pos)) {
- ((TagTrackerItem *) node->data)->count++;
- } else {
+ if (FindInTree(tagTrees[type], string, &iter))
+ {
+ ((TagTrackerItem *)GetTreeKeyData(&iter).data)->count++;
+ return (char *)GetTreeKeyData(&iter).key;
+ }
+ else
+ {
TagTrackerItem *item = malloc(sizeof(TagTrackerItem));
item->count = 1;
item->visited = 0;
- node = insertInListBeforeNode(tagLists[type], node, pos,
- string, item);
+ char * key= strdup(string);
+ InsertInTree(tagTrees[type], key, item);
+ return key;
}
-
- return node->key;
}
void removeTagItemString(int type, char *string)
{
- ListNode *node;
- int pos;
-
+ TreeIterator iter;
+
assert(string);
- assert(tagLists[type]);
- if (tagLists[type] == NULL)
+ assert(tagTrees[type]);
+ if (tagTrees[type] == NULL)
return;
- if (findNodeInList(tagLists[type], string, &node, &pos)) {
- TagTrackerItem *item = node->data;
+ if (FindInTree(tagTrees[type], string, &iter))
+ {
+ TagTrackerItem * item =
+ (TagTrackerItem *)GetTreeKeyData(&iter).data;
item->count--;
if (item->count <= 0)
- deleteNodeFromList(tagLists[type], node);
+ RemoveFromTreeByIterator(tagTrees[type], &iter);
}
- if (tagLists[type]->numberOfNodes == 0) {
- freeList(tagLists[type]);
- tagLists[type] = NULL;
+ if (GetTreeSize(tagTrees[type]) == 0)
+ {
+ FreeTree(tagTrees[type]);
+ tagTrees[type] = NULL;
}
}
int getNumberOfTagItems(int type)
{
- if (tagLists[type] == NULL)
+ if (tagTrees[type] == NULL)
return 0;
- return tagLists[type]->numberOfNodes;
-}
-
-void printMemorySavedByTagTracker(void)
-{
- int i;
- ListNode *node;
- size_t sum = 0;
-
- for (i = 0; i < TAG_NUM_OF_ITEM_TYPES; i++) {
- if (!tagLists[i])
- continue;
-
- sum -= sizeof(List);
-
- node = tagLists[i]->firstNode;
-
- while (node != NULL) {
- sum -= sizeof(ListNode);
- sum -= sizeof(TagTrackerItem);
- sum -= sizeof(node->key);
- sum += (strlen(node->key) + 1) * (*((int *)node->data));
- node = node->nextNode;
- }
- }
-
- DEBUG("saved memory from tags: %li\n", (long)sum);
+ return GetTreeSize(tagTrees[type]);
}
void resetVisitedFlagsInTagTracker(int type)
{
- ListNode *node;
+ TreeIterator iter;
- if (!tagLists[type])
+ if (!tagTrees[type])
return;
- node = tagLists[type]->firstNode;
-
- while (node) {
- ((TagTrackerItem *) node->data)->visited = 0;
- node = node->nextNode;
+ for (SetTreeIteratorToBegin(tagTrees[type], &iter);
+ !IsTreeIteratorAtEnd(&iter);
+ IncrementTreeIterator(&iter))
+ {
+ ((TagTrackerItem *)GetTreeKeyData(&iter).data)->visited = 0;
}
}
void visitInTagTracker(int type, char *str)
{
- void *item;
+ TreeIterator iter;
- if (!tagLists[type])
+ if (!tagTrees[type])
return;
- if (!findInList(tagLists[type], str, &item))
+ if (!FindInTree(tagTrees[type], str, &iter))
return;
- ((TagTrackerItem *) item)->visited = 1;
+ ((TagTrackerItem *)GetTreeKeyData(&iter).data)->visited = 1;
}
void printVisitedInTagTracker(int fd, int type)
{
- ListNode *node;
- TagTrackerItem *item;
+ TreeIterator iter;
+ TagTrackerItem * item;
- if (!tagLists[type])
+ if (!tagTrees[type])
return;
- node = tagLists[type]->firstNode;
-
- while (node) {
- item = node->data;
- if (item->visited) {
- fdprintf(fd, "%s: %s\n", mpdTagItemKeys[type],
- node->key);
+ for (SetTreeIteratorToBegin(tagTrees[type], &iter);
+ !IsTreeIteratorAtEnd(&iter);
+ IncrementTreeIterator(&iter))
+ {
+ item = ((TagTrackerItem *)GetTreeKeyData(&iter).data);
+
+ if (item->visited)
+ {
+ fdprintf(fd,
+ "%s: %s\n",
+ mpdTagItemKeys[type],
+ (char *)GetTreeKeyData(&iter).key);
}
- node = node->nextNode;
}
}
diff --git a/src/tree.c b/src/tree.c
new file mode 100644
index 000000000..9462d2a2c
--- /dev/null
+++ b/src/tree.c
@@ -0,0 +1,712 @@
+/* the Music Player Daemon (MPD)
+ * (c)2006 by Warren Dukes (warren.dukes@gmail.com)
+ * This project's homepage is: http://www.musicpd.org
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include "tree.h"
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+#ifndef CHILDREN_PER_NODE
+#define CHILDREN_PER_NODE 25
+#endif
+
+#define DATA_PER_NODE (CHILDREN_PER_NODE-1)
+
+#if CHILDREN_PER_NODE > 7
+#define USE_BINARY_SEARCH 1
+#endif
+
+
+/************************* DATA STRUCTURES **********************************/
+
+struct _TreeNode
+{
+ TreeKeyData keyData[DATA_PER_NODE];
+ struct _TreeNode * parent;
+ short parentPos;
+ struct _TreeNode * children[CHILDREN_PER_NODE];
+ short count;
+};
+
+struct _Tree
+{
+ TreeCompareKeyFunction compareKey;
+ TreeFreeFunction freeKey;
+ TreeFreeFunction freeData;
+ TreeNode * rootNode;
+ int size;
+};
+
+/************************* STATIC METHODS ***********************************/
+
+static
+TreeNode *
+_MakeNode()
+{
+ TreeNode * ret = malloc(sizeof(TreeNode));
+ memset(ret, 0, sizeof(TreeNode));
+ return ret;
+}
+
+static
+void
+_ClearKeyData(TreeKeyData * keyData)
+{
+ memset(keyData, 0, sizeof(TreeKeyData));
+}
+
+static
+int
+_FindPosition(Tree * tree, TreeNode * node, void * key, int * pos)
+{
+#ifdef USE_BINARY_SEARCH
+ int low = 0;
+ int high = node->count;
+ int cmp = -1;
+
+ while (high > low)
+ {
+ int cur = (high + low) >> 1;
+ cmp = tree->compareKey(key, node->keyData[cur].key);
+ if (cmp > 0)
+ {
+ low = cur+1;
+ }
+ else if (cmp < 0)
+ {
+ high = cur;
+ }
+ else
+ {
+ low = cur;
+ break;
+ }
+ }
+
+ *pos = low;
+ return (cmp == 0);
+#else
+ int i = 0;
+ int cmp = -1;
+ for (;
+ i < node->count &&
+ (cmp = tree->compareKey(key, node->keyData[i].key)) > 0;
+ i++);
+ *pos = i;
+ return (cmp == 0);
+#endif
+}
+
+static
+int
+_Find(TreeIterator * iter, void * key)
+{
+ while (1)
+ {
+ if (_FindPosition(iter->tree, iter->node, key, &iter->which))
+ {
+ iter->which++;
+ return 1;
+ }
+
+ if (iter->node->children[iter->which])
+ {
+ iter->node = iter->node->children[iter->which];
+ }
+ else
+ {
+ return 0;
+ }
+ }
+}
+
+static void _SetIteratorToRoot(Tree * tree, TreeIterator * iter)
+{
+ iter->tree = tree;
+ iter->node = tree->rootNode;
+ iter->which = 0;
+}
+
+static
+TreeNode *
+_SplitNode(TreeNode * node)
+{
+ assert(node->count == DATA_PER_NODE);
+
+ TreeNode * newNode = _MakeNode();
+
+ int i = DATA_PER_NODE/2;
+ int j = 0;
+ for (; i < DATA_PER_NODE; i++, j++)
+ {
+ newNode->keyData[j] = node->keyData[i];
+ newNode->children[j+1] = node->children[i+1];
+ if (newNode->children[j+1])
+ {
+ newNode->children[j+1]->parent = newNode;
+ newNode->children[j+1]->parentPos = j+1;
+ }
+ _ClearKeyData(&(node->keyData[i]));
+ node->children[i+1] = NULL;
+ }
+ newNode->count = (DATA_PER_NODE-DATA_PER_NODE/2);
+ node->count -= (DATA_PER_NODE-DATA_PER_NODE/2);
+
+ return newNode;
+}
+
+static
+void
+_InsertNodeAndData(Tree * tree,
+ TreeNode * node,
+ int pos,
+ TreeNode * newNode,
+ TreeKeyData keyData)
+{
+ assert(node->count < DATA_PER_NODE);
+
+ int j = node->count;
+ for (; j > pos; j--)
+ {
+ node->keyData[j] = node->keyData[j-1];
+ node->children[j+1] = node->children[j];
+ if (node->children[j+1])
+ {
+ node->children[j+1]->parentPos = j+1;
+ }
+ }
+
+ node->keyData[pos] = keyData;
+ node->count++;
+
+ node->children[pos+1] = newNode;
+ if (newNode)
+ {
+ newNode->parent = node;
+ newNode->parentPos = pos+1;
+ }
+}
+
+static
+TreeKeyData
+_AddDataToSplitNodes(Tree * tree,
+ TreeNode * lessNode,
+ TreeNode * moreNode,
+ int pos,
+ TreeNode * newNode,
+ TreeKeyData keyData)
+{
+ assert(moreNode->children[0] == NULL);
+
+ TreeKeyData retKeyData;
+
+ if (pos <= lessNode->count)
+ {
+ _InsertNodeAndData(tree, lessNode, pos, newNode, keyData);
+ lessNode->count--;
+ retKeyData = lessNode->keyData[lessNode->count];
+ _ClearKeyData(&(lessNode->keyData[lessNode->count]));
+ moreNode->children[0] =
+ lessNode->children[lessNode->count+1];
+ if (moreNode->children[0])
+ {
+ moreNode->children[0]->parent = moreNode;
+ moreNode->children[0]->parentPos = 0;
+ }
+ lessNode->children[lessNode->count+1] = NULL;
+ }
+ else
+ {
+ pos -= lessNode->count;
+ retKeyData = moreNode->keyData[0];
+ assert(!moreNode->children[0]);
+
+ int j = 0;
+ for (; j < pos; j++)
+ {
+ moreNode->keyData[j] = moreNode->keyData[j+1];
+ moreNode->children[j] = moreNode->children[j+1];
+ if (moreNode->children[j])
+ {
+ moreNode->children[j]->parentPos = j;
+ }
+ }
+
+ moreNode->keyData[pos-1] = keyData;
+ moreNode->children[pos] = newNode;
+ if (newNode)
+ {
+ newNode->parent = moreNode;
+ newNode->parentPos = pos;
+ }
+ }
+
+ return retKeyData;
+}
+
+static
+void
+_InsertAt(TreeIterator * iter, TreeKeyData keyData)
+{
+ TreeNode * node = iter->node;
+ TreeNode * insertNode = NULL;
+ int pos = iter->which;
+
+ while (node != NULL)
+ {
+ // see if there's any NULL data in the current node
+ if (node->count == DATA_PER_NODE)
+ {
+ // no open data slots, split this node!
+ TreeNode * newNode = _SplitNode(node);
+
+ // insert data in split nodes
+ keyData = _AddDataToSplitNodes(iter->tree,
+ node,
+ newNode,
+ pos,
+ insertNode,
+ keyData);
+
+ if (node->parent == NULL)
+ {
+ assert(node == iter->tree->rootNode);
+ iter->tree->rootNode = _MakeNode();
+ iter->tree->rootNode->children[0] = node;
+ node->parent = iter->tree->rootNode;
+ node->parentPos = 0;
+ iter->tree->rootNode->children[1] = newNode;
+ newNode->parent = iter->tree->rootNode;
+ newNode->parentPos = 1;
+ iter->tree->rootNode->keyData[0] = keyData;
+ iter->tree->rootNode->count = 1;
+ return;
+ }
+
+ pos = node->parentPos;
+ node = node->parent;
+ insertNode = newNode;
+ }
+ else
+ {
+ // insert the data and newNode
+ _InsertNodeAndData(iter->tree,
+ node,
+ pos,
+ insertNode,
+ keyData);
+ return;
+ }
+ }
+}
+
+static
+void
+_MergeNodes(TreeNode * lessNode, TreeNode * moreNode)
+{
+ int i = 0;
+ int j = lessNode->count;
+
+ assert((lessNode->count + moreNode->count) <= DATA_PER_NODE);
+ assert(lessNode->children[j] == NULL);
+
+ for(; i < moreNode->count; i++,j++)
+ {
+ assert(!lessNode->children[j]);
+ lessNode->keyData[j] = moreNode->keyData[i];
+ lessNode->children[j] = moreNode->children[i];
+ if (lessNode->children[j])
+ {
+ lessNode->children[j]->parent = lessNode;
+ lessNode->children[j]->parentPos = j;
+ }
+ }
+ lessNode->children[j] = moreNode->children[i];
+ if (lessNode->children[j])
+ {
+ lessNode->children[j]->parent = lessNode;
+ lessNode->children[j]->parentPos = j;
+ }
+ lessNode->count += i;
+
+ free(moreNode);
+}
+
+void
+_DeleteAt(TreeIterator * iter)
+{
+ TreeNode * node = iter->node;
+ int pos = iter->which - 1;
+ TreeKeyData * keyData = &(node->keyData[pos]);
+ TreeKeyData keyDataToFree = *keyData;
+
+ {
+ // find the least greater than data to fill the whole!
+ if (node->children[pos+1])
+ {
+ TreeNode * child = node->children[++pos];
+ while (child->children[0])
+ {
+ pos = 0;
+ child = child->children[0];
+ }
+
+ *keyData = child->keyData[0];
+ keyData = &(child->keyData[0]);
+ node = child;
+ }
+ // or the greatest lesser than data to fill the whole!
+ else if (node->children[pos])
+ {
+ TreeNode * child = node->children[pos];
+ while (child->children[child->count])
+ {
+ pos = child->count;
+ child = child->children[child->count];
+ }
+
+ *keyData = child->keyData[child->count-1];
+ keyData = &(child->keyData[child->count-1]);
+ node = child;
+ }
+ else
+ {
+ pos = node->parentPos;
+ }
+ }
+
+ // move data nodes over, we're at a leaf node, so we can ignore
+ // children
+ int i = keyData - node->keyData;;
+ for (; i < node->count-1; i++)
+ {
+ node->keyData[i] = node->keyData[i+1];
+ }
+ _ClearKeyData(&(node->keyData[--node->count]));
+
+ // merge the nodes from the bottom up which have too few data
+ while (node->count < (DATA_PER_NODE/2))
+ {
+ // if we're not the root
+ if (node->parent)
+ {
+ TreeNode ** child = &(node->parent->children[pos]);
+ assert(node->parent->children[pos] == node);
+
+ // check siblings for extra data
+ if (pos < node->parent->count &&
+ (*(child+1))->count > (DATA_PER_NODE/2))
+ {
+ child++;
+ node->keyData[node->count++] =
+ node->parent->keyData[pos];
+ node->children[node->count] =
+ (*child)->children[0];
+ if (node->children[node->count])
+ {
+ node->children[node->count]->
+ parent = node;
+ node->children[node->count]->
+ parentPos = node->count;
+ }
+ node->parent->keyData[pos] =
+ (*child)->keyData[0];
+ int i = 0;
+ for(; i < (*child)->count-1; i++)
+ {
+ (*child)->keyData[i] =
+ (*child)->keyData[i+1];
+ (*child)->children[i] =
+ (*child)->children[i+1];
+ if ((*child)->children[i])
+ {
+ (*child)->children[i]->
+ parentPos = i;
+ }
+ }
+ (*child)->children[i] = (*child)->children[i+1];
+ if ((*child)->children[i])
+ {
+ (*child)->children[i]->parentPos = i;
+ }
+ (*child)->children[i+1] =NULL;
+ _ClearKeyData(&((*child)->keyData[i]));
+ (*child)->count--;
+ }
+ else if (pos > 0 &&
+ (*(child-1))->count>(DATA_PER_NODE/2))
+ {
+ child--;
+ int i = node->count++;
+ for(; i > 0; i--)
+ {
+ node->keyData[i] = node->keyData[i-1];
+ node->children[i+1] = node->children[i];
+ if (node->children[i+1])
+ {
+ node->children[i+1]->parentPos =
+ i+1;
+ }
+ }
+ node->children[1] = node->children[0];
+ if (node->children[1])
+ {
+ node->children[1]->parentPos = 1;
+ }
+ node->keyData[0] = node->parent->keyData[pos-1];
+ node->children[0] =
+ (*child)->children[(*child)->count];
+ if (node->children[0])
+ {
+ node->children[0]->parent = node;
+ node->children[0]->parentPos = 0;
+ }
+ node->parent->keyData[pos-1] =
+ (*child)->keyData[(*child)->count-1];
+ (*child)->children[(*child)->count--] =
+ NULL;
+ _ClearKeyData(
+ &((*child)->keyData[(*child)->count]));
+ }
+ // merge with one of our siblings
+ else
+ {
+ if (pos < node->parent->count)
+ {
+ child++;
+ assert(*child);
+
+ node->keyData[node->count++] =
+ node->parent->keyData[pos];
+
+ _MergeNodes(node, *child);
+ }
+ else
+ {
+ assert(pos > 0);
+ child--;
+ assert(*child);
+ pos--;
+
+ (*child)->keyData[(*child)->count++] =
+ node->parent->keyData[pos];
+
+ _MergeNodes(*child, node);
+ node = *child;
+ }
+
+ int i = pos;
+ for(; i < node->parent->count-1; i++)
+ {
+ node->parent->keyData[i] =
+ node->parent->keyData[i+1];
+ node->parent->children[i+1] =
+ node->parent->children[i+2];
+ if (node->parent->children[i+1])
+ {
+ node->parent->children[i+1]->
+ parentPos = i+1;
+ }
+ }
+ _ClearKeyData(&(node->parent->keyData[i]));
+ node->parent->children[i+1] = NULL;
+ node->parent->count--;
+
+ node = node->parent;
+ pos = node->parentPos;
+ }
+ }
+ // this is a root node
+ else
+ {
+ if (node->count == 0)
+ {
+ if (node->children[0])
+ {
+ node->children[0]->parent = NULL;
+ node->children[0]->parentPos = 0;
+ }
+
+ iter->tree->rootNode = node->children[0];
+
+ free(node);
+ }
+
+ break;
+ }
+ }
+
+ if (iter->tree->freeKey)
+ {
+ iter->tree->freeData(keyDataToFree.key);
+ }
+ if (iter->tree->freeData)
+ {
+ iter->tree->freeData(keyDataToFree.data);
+ }
+}
+
+/************************* PUBLIC METHODS ***********************************/
+
+Tree *
+MakeTree(TreeCompareKeyFunction compareKey,
+ TreeFreeFunction freeKey,
+ TreeFreeFunction freeData)
+{
+ Tree * ret = malloc(sizeof(Tree));
+ ret->compareKey = compareKey;
+ ret->freeKey = freeKey;
+ ret->freeData = freeData;
+ ret->rootNode = _MakeNode();
+ ret->size = 0;
+ return ret;
+}
+
+void
+FreeTree(Tree * tree)
+{
+ assert(tree->rootNode == NULL);
+ free(tree);
+}
+
+int
+GetTreeSize(Tree * tree)
+{
+ return tree->size;
+}
+
+void SetTreeIteratorToBegin(Tree * tree, TreeIterator * iter)
+{
+ _SetIteratorToRoot(tree, iter);
+ IncrementTreeIterator(iter);
+}
+
+int IsTreeIteratorAtEnd(const TreeIterator * iter)
+{
+ return (iter->node == NULL);
+}
+
+void IncrementTreeIterator(TreeIterator * iter)
+{
+ while(iter->node)
+ {
+ if (iter->node->children[iter->which])
+ {
+ iter->node = iter->node->children[iter->which];
+ iter->which = 0;
+ }
+ else
+ {
+ iter->which++;
+ }
+
+ while (iter->node && iter->which > iter->node->count)
+ {
+ TreeNode * childNode = iter->node;
+ iter->node = childNode->parent;
+ if (iter->node)
+ {
+ for (iter->which = 0;
+ childNode !=
+ iter->node->children[iter->which];
+ iter->which++)
+ {
+ assert(iter->which <=
+ iter->node->count);
+ }
+ iter->which++;
+ }
+ }
+
+ if (iter->node &&
+ iter->which > 0 && iter->which <= iter->node->count)
+ {
+ return;
+ }
+ }
+}
+
+TreeKeyData
+GetTreeKeyData(TreeIterator * iter)
+{
+ assert(iter->node &&
+ iter->which > 0 &&
+ iter->which <= iter->node->count);
+ return iter->node->keyData[iter->which-1];
+}
+
+int
+InsertInTree(Tree * tree, void * key, void * data)
+{
+ TreeKeyData keyData = {key, data};
+ TreeIterator iter;
+ _SetIteratorToRoot(tree, &iter);
+
+ if (_Find(&iter, key))
+ {
+ return 0;
+ }
+
+ _InsertAt(&iter, keyData);
+ tree->size++;
+
+ return 1;
+}
+
+int
+RemoveFromTreeByKey(Tree * tree, void * key)
+{
+ TreeIterator iter;
+ _SetIteratorToRoot(tree, &iter);
+
+ if (_Find(&iter, key))
+ {
+ _DeleteAt(&iter);
+ tree->size--;
+ return 1;
+ }
+
+ return 0;
+}
+
+void
+RemoveFromTreeByIterator(Tree * tree, TreeIterator * iter)
+{
+ _DeleteAt(iter);
+ tree->size--;
+}
+
+int
+FindInTree(Tree * tree, void * key, TreeIterator * iter)
+{
+ TreeIterator i;
+
+ if (iter == NULL)
+ {
+ iter = &i;
+ }
+
+ _SetIteratorToRoot(tree, iter);
+ if (_Find(iter, key))
+ {
+ return 1;
+ }
+
+ return 0;
+}
diff --git a/src/tree.h b/src/tree.h
new file mode 100644
index 000000000..54416a065
--- /dev/null
+++ b/src/tree.h
@@ -0,0 +1,62 @@
+/* the Music Player Daemon (MPD)
+ * (c)2006 by Warren Dukes (warren.dukes@gmail.com)
+ * This project's homepage is: http://www.musicpd.org
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#ifndef TREE_H
+#define TREE_H
+
+typedef struct _Tree Tree;
+typedef struct _TreeNode TreeNode;
+typedef struct _TreeIterator TreeIterator;
+typedef struct _TreeKeyData TreeKeyData;
+
+struct _TreeIterator
+{
+ Tree * tree;
+ TreeNode * node;
+ int which;
+};
+
+struct _TreeKeyData
+{
+ void * key;
+ void * data;
+};
+
+typedef int (*TreeCompareKeyFunction)(const void * key1, const void * key2);
+typedef void (*TreeFreeFunction)(void * data);
+
+Tree * MakeTree(TreeCompareKeyFunction compareFunc,
+ TreeFreeFunction freeKey,
+ TreeFreeFunction freeData);
+void FreeTree(Tree * tree);
+
+int GetTreeSize(Tree * tree);
+
+void SetTreeIteratorToBegin(Tree * tree, TreeIterator * iter);
+int IsTreeIteratorAtEnd(const TreeIterator * iter);
+void IncrementTreeIterator(TreeIterator * iter);
+
+TreeKeyData GetTreeKeyData(TreeIterator * iter);
+
+int InsertInTree(Tree * tree, void * key, void * data);
+int RemoveFromTreeByKey(Tree * tree, void * key);
+void RemoveFromTreeByIterator(Tree * tree, TreeIterator * iter);
+
+int FindInTree(Tree * tree, void * key, TreeIterator * iter /* can be NULL */);
+
+#endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-15 06:53:12 +0000