From 31de97a42b384ffd2ce7051248cefc075e935522 Mon Sep 17 00:00:00 2001 From: Warren Dukes Date: Sun, 6 Aug 2006 06:40:11 +0000 Subject: merge changes from mpd-tree: -use tree for tagTracker -eliminate the master process git-svn-id: https://svn.musicpd.org/mpd/trunk@4571 09075e82-0dd4-0310-85a5-a0d7c8717e4f --- src/Makefile.am | 2 + src/directory.c | 1 + src/main.c | 89 ++----- src/player.c | 89 ++++--- src/player.h | 2 - src/playerData.c | 19 +- src/playerData.h | 3 - src/sig_handlers.c | 91 +------ src/sig_handlers.h | 4 - src/tagTracker.c | 137 +++++------ src/tree.c | 712 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/tree.h | 62 +++++ 12 files changed, 916 insertions(+), 295 deletions(-) create mode 100644 src/tree.c create mode 100644 src/tree.h 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 #include #include +#include #include #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 #include -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 +#include -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 +#include +#include + +#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 -- cgit v1.2.3