From 3ef31f6e0c13aa7b2ebd1fcacd7e1aa3ac560ba5 Mon Sep 17 00:00:00 2001 From: Max Kellermann Date: Mon, 15 Sep 2008 13:27:33 +0200 Subject: [PATCH] manage tag string allocations in a pool There are many duplicated strings in the tag database, e.g. many songs having the same artist. Don't allocate such strings twice, manage all strings in a pool. --- src/Makefile.am | 4 +- src/libmpdclient.c | 87 +++++++++++++++---------------- src/str_pool.c | 125 +++++++++++++++++++++++++++++++++++++++++++++ src/str_pool.h | 28 ++++++++++ 4 files changed, 200 insertions(+), 44 deletions(-) create mode 100644 src/str_pool.c create mode 100644 src/str_pool.h diff --git a/src/Makefile.am b/src/Makefile.am index 176edf2..53342ff 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -30,6 +30,7 @@ ncmpc_headers = \ ncmpc.h\ screen_browse.h\ src_lyrics.h \ + str_pool.h \ gcc.h # $Id$ @@ -62,7 +63,8 @@ ncmpc_SOURCES = \ wreadln.c\ strfsong.c\ utils.c\ - src_lyrics.c + src_lyrics.c \ + str_pool.c if LEOSLYRICS_FIXED ncmpc_SOURCES+=lyrics_leoslyrics.c diff --git a/src/libmpdclient.c b/src/libmpdclient.c index 48d7d4f..b049844 100644 --- a/src/libmpdclient.c +++ b/src/libmpdclient.c @@ -31,6 +31,7 @@ */ #include "libmpdclient.h" +#include "str_pool.h" #include #include @@ -279,15 +280,15 @@ static mpd_ReturnElement * mpd_newReturnElement(const char * name, const char * { mpd_ReturnElement * ret = malloc(sizeof(mpd_ReturnElement)); - ret->name = strdup(name); - ret->value = strdup(value); + ret->name = str_pool_get(name); + ret->value = str_pool_get(value); return ret; } static void mpd_freeReturnElement(mpd_ReturnElement * re) { - free(re->name); - free(re->value); + str_pool_put(re->name); + str_pool_put(re->value); free(re); } @@ -930,17 +931,17 @@ static void mpd_initSong(mpd_Song * song) { } static void mpd_finishSong(mpd_Song * song) { - if(song->file) free(song->file); - if(song->artist) free(song->artist); - if(song->album) free(song->album); - if(song->title) free(song->title); - if(song->track) free(song->track); - if(song->name) free(song->name); - if(song->date) free(song->date); - if(song->genre) free(song->genre); - if(song->composer) free(song->composer); - if(song->disc) free(song->disc); - if(song->comment) free(song->comment); + if(song->file) str_pool_put(song->file); + if(song->artist) str_pool_put(song->artist); + if(song->album) str_pool_put(song->album); + if(song->title) str_pool_put(song->title); + if(song->track) str_pool_put(song->track); + if(song->name) str_pool_put(song->name); + if(song->date) str_pool_put(song->date); + if(song->genre) str_pool_put(song->genre); + if(song->composer) str_pool_put(song->composer); + if(song->disc) str_pool_put(song->disc); + if(song->comment) str_pool_put(song->comment); } mpd_Song * mpd_newSong(void) { @@ -959,17 +960,17 @@ void mpd_freeSong(mpd_Song * song) { mpd_Song * mpd_songDup(mpd_Song * song) { mpd_Song * ret = mpd_newSong(); - if(song->file) ret->file = strdup(song->file); - if(song->artist) ret->artist = strdup(song->artist); - if(song->album) ret->album = strdup(song->album); - if(song->title) ret->title = strdup(song->title); - if(song->track) ret->track = strdup(song->track); - if(song->name) ret->name = strdup(song->name); - if(song->date) ret->date = strdup(song->date); - if(song->genre) ret->genre= strdup(song->genre); - if(song->composer) ret->composer= strdup(song->composer); - if(song->disc) ret->disc = strdup(song->disc); - if(song->comment) ret->comment = strdup(song->comment); + if(song->file) ret->file = str_pool_dup(song->file); + if(song->artist) ret->artist = str_pool_dup(song->artist); + if(song->album) ret->album = str_pool_dup(song->album); + if(song->title) ret->title = str_pool_dup(song->title); + if(song->track) ret->track = str_pool_dup(song->track); + if(song->name) ret->name = str_pool_dup(song->name); + if(song->date) ret->date = str_pool_dup(song->date); + if(song->genre) ret->genre= str_pool_dup(song->genre); + if(song->composer) ret->composer= str_pool_dup(song->composer); + if(song->disc) ret->disc = str_pool_dup(song->disc); + if(song->comment) ret->comment = str_pool_dup(song->comment); ret->time = song->time; ret->pos = song->pos; ret->id = song->id; @@ -983,7 +984,7 @@ static void mpd_initDirectory(mpd_Directory * directory) { static void mpd_finishDirectory(mpd_Directory * directory) { if (directory->path) - free(directory->path); + str_pool_put(directory->path); } mpd_Directory * mpd_newDirectory(void) { @@ -1004,7 +1005,7 @@ mpd_Directory * mpd_directoryDup(mpd_Directory * directory) { mpd_Directory * ret = mpd_newDirectory(); if (directory->path) - ret->path = strdup(directory->path); + ret->path = str_pool_dup(directory->path); return ret; } @@ -1015,7 +1016,7 @@ static void mpd_initPlaylistFile(mpd_PlaylistFile * playlist) { static void mpd_finishPlaylistFile(mpd_PlaylistFile * playlist) { if (playlist->path) - free(playlist->path); + str_pool_put(playlist->path); } mpd_PlaylistFile * mpd_newPlaylistFile(void) { @@ -1035,7 +1036,7 @@ mpd_PlaylistFile * mpd_playlistFileDup(mpd_PlaylistFile * playlist) { mpd_PlaylistFile * ret = mpd_newPlaylistFile(); if (playlist->path) - ret->path = strdup(playlist->path); + ret->path = str_pool_dup(playlist->path); return ret; } @@ -1091,7 +1092,7 @@ mpd_InfoEntity * mpd_getNextInfoEntity(mpd_Connection * connection) { entity->type = MPD_INFO_ENTITY_TYPE_SONG; entity->info.song = mpd_newSong(); entity->info.song->file = - strdup(connection->returnElement->value); + str_pool_dup(connection->returnElement->value); } else if(strcmp(connection->returnElement->name, "directory")==0) { @@ -1099,14 +1100,14 @@ mpd_InfoEntity * mpd_getNextInfoEntity(mpd_Connection * connection) { entity->type = MPD_INFO_ENTITY_TYPE_DIRECTORY; entity->info.directory = mpd_newDirectory(); entity->info.directory->path = - strdup(connection->returnElement->value); + str_pool_dup(connection->returnElement->value); } else if(strcmp(connection->returnElement->name,"playlist")==0) { entity = mpd_newInfoEntity(); entity->type = MPD_INFO_ENTITY_TYPE_PLAYLISTFILE; entity->info.playlistFile = mpd_newPlaylistFile(); entity->info.playlistFile->path = - strdup(connection->returnElement->value); + str_pool_dup(connection->returnElement->value); } else if(strcmp(connection->returnElement->name, "cpos") == 0){ entity = mpd_newInfoEntity(); @@ -1135,23 +1136,23 @@ mpd_InfoEntity * mpd_getNextInfoEntity(mpd_Connection * connection) { strlen(re->value)) { if(!entity->info.song->artist && strcmp(re->name,"Artist")==0) { - entity->info.song->artist = strdup(re->value); + entity->info.song->artist = str_pool_dup(re->value); } else if(!entity->info.song->album && strcmp(re->name,"Album")==0) { - entity->info.song->album = strdup(re->value); + entity->info.song->album = str_pool_dup(re->value); } else if(!entity->info.song->title && strcmp(re->name,"Title")==0) { - entity->info.song->title = strdup(re->value); + entity->info.song->title = str_pool_dup(re->value); } else if(!entity->info.song->track && strcmp(re->name,"Track")==0) { - entity->info.song->track = strdup(re->value); + entity->info.song->track = str_pool_dup(re->value); } else if(!entity->info.song->name && strcmp(re->name,"Name")==0) { - entity->info.song->name = strdup(re->value); + entity->info.song->name = str_pool_dup(re->value); } else if(entity->info.song->time==MPD_SONG_NO_TIME && strcmp(re->name,"Time")==0) { @@ -1167,23 +1168,23 @@ mpd_InfoEntity * mpd_getNextInfoEntity(mpd_Connection * connection) { } else if(!entity->info.song->date && strcmp(re->name, "Date") == 0) { - entity->info.song->date = strdup(re->value); + entity->info.song->date = str_pool_dup(re->value); } else if(!entity->info.song->genre && strcmp(re->name, "Genre") == 0) { - entity->info.song->genre = strdup(re->value); + entity->info.song->genre = str_pool_dup(re->value); } else if(!entity->info.song->composer && strcmp(re->name, "Composer") == 0) { - entity->info.song->composer = strdup(re->value); + entity->info.song->composer = str_pool_dup(re->value); } else if(!entity->info.song->disc && strcmp(re->name, "Disc") == 0) { - entity->info.song->disc = strdup(re->value); + entity->info.song->disc = str_pool_dup(re->value); } else if(!entity->info.song->comment && strcmp(re->name, "Comment") == 0) { - entity->info.song->comment = strdup(re->value); + entity->info.song->comment = str_pool_dup(re->value); } } else if(entity->type == MPD_INFO_ENTITY_TYPE_DIRECTORY) { diff --git a/src/str_pool.c b/src/str_pool.c new file mode 100644 index 0000000..74839b5 --- /dev/null +++ b/src/str_pool.c @@ -0,0 +1,125 @@ +/* ncmpc + * Copyright (C) 2008 Max Kellermann + * 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 "str_pool.h" + +#include +#include +#include +#include + +#define NUM_SLOTS 4096 + +struct slot { + struct slot *next; + unsigned char ref; + char value[1]; +} __attribute__((packed)); + +struct slot *slots[NUM_SLOTS]; + +static inline unsigned +calc_hash(const char *p) +{ + unsigned hash = 5381; + + assert(p != NULL); + + while (*p != 0) + hash = (hash << 5) + hash + *p++; + + return hash; +} + +static inline struct slot * +value_to_slot(char *value) +{ + return (struct slot*)(value - offsetof(struct slot, value)); +} + +static struct slot *slot_alloc(struct slot *next, const char *value) +{ + size_t length = strlen(value); + struct slot *slot = malloc(sizeof(*slot) + length); + if (slot == NULL) + abort(); /* XXX */ + + slot->next = next; + slot->ref = 1; + memcpy(slot->value, value, length + 1); + return slot; +} + +char *str_pool_get(const char *value) +{ + struct slot **slot_p, *slot; + + slot_p = &slots[calc_hash(value) % NUM_SLOTS]; + for (slot = *slot_p; slot != NULL; slot = slot->next) { + if (strcmp(value, slot->value) == 0 && slot->ref < 0xff) { + assert(slot->ref > 0); + ++slot->ref; + return slot->value; + } + } + + slot = slot_alloc(*slot_p, value); + *slot_p = slot; + return slot->value; +} + +char *str_pool_dup(char *value) +{ + struct slot *slot = value_to_slot(value); + + assert(slot->ref > 0); + + if (slot->ref < 0xff) { + ++slot->ref; + return value; + } else { + /* the reference counter overflows above 0xff; + duplicate the value, and start with 1 */ + struct slot **slot_p = + &slots[calc_hash(slot->value) % NUM_SLOTS]; + slot = slot_alloc(*slot_p, slot->value); + *slot_p = slot; + return slot->value; + } +} + +void str_pool_put(char *value) +{ + struct slot **slot_p, *slot; + + slot = value_to_slot(value); + assert(slot->ref > 0); + --slot->ref; + + if (slot->ref > 0) + return; + + for (slot_p = &slots[calc_hash(value) % NUM_SLOTS]; + *slot_p != slot; + slot_p = &(*slot_p)->next) { + assert(*slot_p != NULL); + } + + *slot_p = slot->next; + free(slot); +} diff --git a/src/str_pool.h b/src/str_pool.h new file mode 100644 index 0000000..4a0ad12 --- /dev/null +++ b/src/str_pool.h @@ -0,0 +1,28 @@ +/* ncmpc + * Copyright (C) 2008 Max Kellermann + * 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 STR_POOL_H +#define STR_POOL_H + +char *str_pool_get(const char *value); + +char *str_pool_dup(char *value); + +void str_pool_put(char *value); + +#endif -- 2.30.2