diff options
28 files changed, 6214 insertions, 172 deletions
diff --git a/apps/commander/commander.c b/apps/commander/commander.c index 55d3b82e7..a642ac093 100644 --- a/apps/commander/commander.c +++ b/apps/commander/commander.c @@ -581,46 +581,6 @@ void handle_command(int status_pub, struct vehicle_status_s *current_vehicle_sta } break; - /* preflight parameter load / store */ - case MAV_CMD_PREFLIGHT_STORAGE: { - /* Read all parameters from EEPROM to RAM */ - - if (((int)cmd->param1) == 0) { - - if (OK == get_params_from_eeprom(global_data_parameter_storage)) { - //printf("[commander] Loaded EEPROM params in RAM\n"); - mavlink_log_info(mavlink_fd, "[commander] CMD Loaded EEPROM params in RAM"); - result = MAV_RESULT_ACCEPTED; - - } else { - //fprintf(stderr, "[commander] ERROR loading EEPROM params in RAM\n"); - mavlink_log_critical(mavlink_fd, "[commander] ERROR loading EEPROM params in RAM"); - result = MAV_RESULT_FAILED; - } - - /* Write all parameters from RAM to EEPROM */ - - } else if (((int)cmd->param1) == 1) { - - if (OK == store_params_in_eeprom(global_data_parameter_storage)) { - //printf("[commander] RAM params written to EEPROM\n"); - mavlink_log_info(mavlink_fd, "[commander] RAM params written to EEPROM"); - result = MAV_RESULT_ACCEPTED; - - } else { - //fprintf(stderr, "[commander] ERROR writing RAM params to EEPROM\n"); - mavlink_log_critical(mavlink_fd, "[commander] ERROR writing RAM params to EEPROM"); - result = MAV_RESULT_FAILED; - } - - } else { - //fprintf(stderr, "[commander] refusing unsupported storage request\n"); - mavlink_log_critical(mavlink_fd, "[commander] refusing unsupported storage request"); - result = MAV_RESULT_UNSUPPORTED; - } - } - break; - default: { mavlink_log_critical(mavlink_fd, "[commander] refusing unsupported command"); result = MAV_RESULT_UNSUPPORTED; diff --git a/apps/mavlink/mavlink.c b/apps/mavlink/mavlink.c index 97822510c..596953789 100644 --- a/apps/mavlink/mavlink.c +++ b/apps/mavlink/mavlink.c @@ -151,8 +151,8 @@ static enum { void mavlink_wpm_send_message(mavlink_message_t *msg); void mavlink_wpm_send_gcs_string(const char *string); uint64_t mavlink_wpm_get_system_timestamp(void); -void mavlink_missionlib_send_message(mavlink_message_t *msg); -void mavlink_missionlib_send_gcs_string(const char *string); +int mavlink_missionlib_send_message(mavlink_message_t *msg); +int mavlink_missionlib_send_gcs_string(const char *string); uint64_t mavlink_missionlib_get_system_timestamp(void); void handleMessage(mavlink_message_t *msg); @@ -183,13 +183,18 @@ static void usage(const char *reason); static uint8_t missionlib_msg_buf[MAVLINK_MAX_PACKET_LEN]; -void mavlink_missionlib_send_message(mavlink_message_t *msg) +int mavlink_missionlib_send_message(mavlink_message_t *msg) { uint16_t len = mavlink_msg_to_send_buffer(missionlib_msg_buf, msg); - write(uart, missionlib_msg_buf, len); + int writelen = write(uart, missionlib_msg_buf, len); + if (writelen != len) { + return 1; + } else { + return 0; + } } -void mavlink_missionlib_send_gcs_string(const char *string) +int mavlink_missionlib_send_gcs_string(const char *string) { const int len = MAVLINK_MSG_STATUSTEXT_FIELD_TEXT_LEN; mavlink_statustext_t statustext; @@ -210,7 +215,9 @@ void mavlink_missionlib_send_gcs_string(const char *string) mavlink_message_t msg; mavlink_msg_statustext_encode(mavlink_system.sysid, mavlink_system.compid, &msg, &statustext); - mavlink_missionlib_send_message(&msg); + return mavlink_missionlib_send_message(&msg); + } else { + return 1; } } diff --git a/apps/mavlink/mavlink_parameters.c b/apps/mavlink/mavlink_parameters.c index a064fc167..ab788c461 100644 --- a/apps/mavlink/mavlink_parameters.c +++ b/apps/mavlink/mavlink_parameters.c @@ -45,52 +45,153 @@ #include <fcntl.h> #include <stdbool.h> #include <string.h> +#include <systemlib/param/param.h> extern mavlink_system_t mavlink_system; -extern void mavlink_missionlib_send_message(mavlink_message_t *msg); -extern void mavlink_missionlib_send_gcs_string(const char *string); +extern int mavlink_missionlib_send_message(mavlink_message_t *msg); +extern int mavlink_missionlib_send_gcs_string(const char *string); -/* send one parameter, assume lock on global_data_parameter_storage */ -void mavlink_pm_send_one_parameter(uint16_t next_param) +/** + * If the queue index is not at 0, the queue sending + * logic will send parameters from the current index + * to len - 1, the end of the param list. + */ +static unsigned int mavlink_param_queue_index = 0; + +/** + * Callback for param interface. + */ +void mavlink_pm_callback(void *arg, param_t param); + +void mavlink_pm_callback(void *arg, param_t param) +{ + mavlink_pm_send_param(param); + usleep(*(unsigned int*)arg); +} + +void mavlink_pm_send_all_params(unsigned int delay) { - if (next_param < global_data_parameter_storage->pm.size) { - static char name_buf[MAVLINK_MSG_PARAM_VALUE_FIELD_PARAM_ID_LEN]; - mavlink_message_t tx_msg; - - strncpy((char *)name_buf, global_data_parameter_storage->pm.param_names[next_param], MAVLINK_MSG_PARAM_VALUE_FIELD_PARAM_ID_LEN); - - mavlink_msg_param_value_pack_chan(mavlink_system.sysid, - mavlink_system.compid, - MAVLINK_COMM_0, - &tx_msg, - name_buf, - global_data_parameter_storage->pm.param_values[next_param], - MAVLINK_TYPE_FLOAT, - global_data_parameter_storage->pm.size, - next_param); - mavlink_missionlib_send_message(&tx_msg); - - - // mavlink_msg_param_value_send(MAVLINK_COMM_0, - // name_buf, - // global_data_parameter_storage->pm.param_values[next_param], - // MAVLINK_TYPE_FLOAT, - // global_data_parameter_storage->pm.size, - // next_param); + unsigned int dbuf = delay; + param_foreach(&mavlink_pm_callback, &dbuf, false); +} + +int mavlink_pm_queued_send() +{ + if (mavlink_param_queue_index < param_count()) { + mavlink_pm_send_param(param_for_index(mavlink_param_queue_index)); + mavlink_param_queue_index++; + return 0; + } else { + return 1; + } +} + +void mavlink_pm_start_queued_send() +{ + mavlink_param_queue_index = 0; +} + +int mavlink_pm_send_param_for_index(uint16_t index) +{ + return mavlink_pm_send_param(param_for_index(index)); +} + +int mavlink_pm_send_param_for_name(const char* name) +{ + return mavlink_pm_send_param(param_find(name)); +} + +int mavlink_pm_send_param(param_t param) +{ + if (param == PARAM_INVALID) return 1; + + /* buffers for param transmission */ + static char name_buf[MAVLINK_MSG_PARAM_VALUE_FIELD_PARAM_ID_LEN]; + float val_buf; + static mavlink_message_t tx_msg; + + /* query parameter type */ + param_type_t type = param_type(param); + /* copy parameter name */ + strncpy((char *)name_buf, param_name(param), MAVLINK_MSG_PARAM_VALUE_FIELD_PARAM_ID_LEN); + + /* + * Map onboard parameter type to MAVLink type, + * endianess matches (both little endian) + */ + uint8_t mavlink_type; + if (type == PARAM_TYPE_INT32) { + mavlink_type = MAVLINK_TYPE_INT32_T; + } else if (type == PARAM_TYPE_FLOAT) { + mavlink_type = MAVLINK_TYPE_FLOAT; + } + + /* + * get param value, since MAVLink encodes float and int params in the same + * space during transmission, copy param onto float val_buf + */ + if (param_get(param, &val_buf) != OK) return; + + mavlink_msg_param_value_pack_chan(mavlink_system.sysid, + mavlink_system.compid, + MAVLINK_COMM_0, + &tx_msg, + name_buf, + val_buf, + mavlink_type, + param_count(), + param_get_index(param)); + return mavlink_missionlib_send_message(&tx_msg); +} + +static int +mavlink_pm_save_eeprom() +{ + const char* name = "/eeprom"; + int fd = open("/eeprom", O_WRONLY | O_CREAT | O_EXCL); + + if (fd < 0) + warn(1, "opening '%s' failed", name); + + int result = param_export(fd, false); + close(fd); + + if (result < 0) { + warn(1, "error exporting to '%s'", name); } + + return 0; +} + +static int +mavlink_pm_load_eeprom() +{ + const char* name = "/eeprom"; + int fd = open(name, O_RDONLY); + + if (fd < 0) + warn(1, "open '%s' failed", name); + + int result = param_import(fd); + close(fd); + + if (result < 0) + warn(1, "error importing from '%s'", name); + + return 0; } void mavlink_pm_message_handler(const mavlink_channel_t chan, const mavlink_message_t *msg) { switch (msg->msgid) { - case MAVLINK_MSG_ID_PARAM_REQUEST_LIST: { + case MAVLINK_MSG_ID_PARAM_REQUEST_LIST: { /* Start sending parameters */ - global_data_parameter_storage->pm.next_param = 0; - mavlink_missionlib_send_gcs_string("[pm] sending list"); + mavlink_pm_start_queued_send(); + mavlink_missionlib_send_gcs_string("[mavlink pm] sending list"); } break; - case MAVLINK_MSG_ID_PARAM_SET: { + case MAVLINK_MSG_ID_PARAM_SET: { /* Handle parameter setting */ @@ -99,91 +200,97 @@ void mavlink_pm_message_handler(const mavlink_channel_t chan, const mavlink_mess mavlink_msg_param_set_decode(msg, &mavlink_param_set); if (mavlink_param_set.target_system == mavlink_system.sysid && ((mavlink_param_set.target_component == mavlink_system.compid) || (mavlink_param_set.target_component == MAV_COMP_ID_ALL))) { + /* local name buffer to enforce null-terminated string */ + char name[MAVLINK_MSG_PARAM_VALUE_FIELD_PARAM_ID_LEN+1]; + strncpy(name, mavlink_param_set.param_id, MAVLINK_MSG_PARAM_VALUE_FIELD_PARAM_ID_LEN); + /* enforce null termination */ + name[MAVLINK_MSG_PARAM_VALUE_FIELD_PARAM_ID_LEN] = '\0'; + /* attempt to find parameter, set and send it */ + param_t param = param_find(name); - uint16_t i; //parameters - uint16_t j; //chars - bool match; - - for (i = 0; i < PARAM_MAX_COUNT; i++) { - match = true; - - for (j = 0; j < MAX_PARAM_NAME_LEN; j++) { - /* Compare char by char */ - if (global_data_parameter_storage->pm.param_names[i][j] != mavlink_param_set.param_id[j]) { - match = false; - } - - /* End matching if null termination is reached */ - if (global_data_parameter_storage->pm.param_names[i][j] == '\0') { - break; - } - } - - /* Check if matched */ - if (match) { - // XXX handle param type as well, assuming float here - global_data_parameter_storage->pm.param_values[i] = mavlink_param_set.param_value; - mavlink_pm_send_one_parameter(i); - } + if (param == PARAM_INVALID) { + char buf[MAVLINK_MSG_STATUSTEXT_FIELD_TEXT_LEN]; + sprintf(buf, "[mavlink pm] unknown: %s", name); + mavlink_missionlib_send_gcs_string(buf); + } else { + /* set and send parameter */ + param_set(param, &(mavlink_param_set.param_value)); + mavlink_pm_send_param(param); } } } } break; - case MAVLINK_MSG_ID_PARAM_REQUEST_READ: { + case MAVLINK_MSG_ID_PARAM_REQUEST_READ: { mavlink_param_request_read_t mavlink_param_request_read; mavlink_msg_param_request_read_decode(msg, &mavlink_param_request_read); - if (mavlink_param_request_read.target_system == mavlink_system.sysid && ((mavlink_param_request_read.target_component == mavlink_system.compid) || (mavlink_param_request_read.target_component == MAV_COMP_ID_ALL))) { - /* when no index is given, loop through string ids and compare them */ - if (mavlink_param_request_read.param_index == -1) { + if (mavlink_param_request_read.target_system == mavlink_system.sysid && ((mavlink_param_request_read.target_component == mavlink_system.compid) || (mavlink_param_request_read.target_component == MAV_COMP_ID_ALL))) { + /* when no index is given, loop through string ids and compare them */ + if (mavlink_param_request_read.param_index == -1) { + /* local name buffer to enforce null-terminated string */ + char name[MAVLINK_MSG_PARAM_VALUE_FIELD_PARAM_ID_LEN+1]; + strncpy(name, mavlink_param_request_read.param_id, MAVLINK_MSG_PARAM_VALUE_FIELD_PARAM_ID_LEN); + /* enforce null termination */ + name[MAVLINK_MSG_PARAM_VALUE_FIELD_PARAM_ID_LEN] = '\0'; + /* attempt to find parameter and send it */ + mavlink_pm_send_param_for_name(name); + } else { + /* when index is >= 0, send this parameter again */ + mavlink_pm_send_param_for_index(mavlink_param_request_read.param_index); + } + } - uint16_t i; //parameters - uint16_t j; //chars - bool match; + } break; - for (i = 0; i < PARAM_MAX_COUNT; i++) { - match = true; + case MAVLINK_MSG_ID_COMMAND_LONG: { + mavlink_command_long_t cmd_mavlink; + mavlink_msg_command_long_decode(msg, &cmd_mavlink); - for (j = 0; j < MAX_PARAM_NAME_LEN; j++) { - /* Compare char by char */ - if (global_data_parameter_storage->pm.param_names[i][j] != mavlink_param_request_read.param_id[j]) { - match = false; - } + uint8_t result; - /* End matching if null termination is reached */ - if (global_data_parameter_storage->pm.param_names[i][j] == '\0') { - break; - } + if (cmd_mavlink.target_system == mavlink_system.sysid && + ((cmd_mavlink.target_component == mavlink_system.compid) ||(cmd_mavlink.target_component == MAV_COMP_ID_ALL))) { + + /* preflight parameter load / store */ + if (cmd_mavlink.command == MAV_CMD_PREFLIGHT_STORAGE) { + /* Read all parameters from EEPROM to RAM */ + + if (((int)(cmd_mavlink.param1)) == 0) { + + if (OK == mavlink_pm_load_eeprom()) { + //printf("[mavlink pm] Loaded EEPROM params in RAM\n"); + mavlink_missionlib_send_gcs_string("[mavlink pm] CMD Loaded EEPROM params in RAM"); + result = MAV_RESULT_ACCEPTED; + + } else { + //fprintf(stderr, "[mavlink pm] ERROR loading EEPROM params in RAM\n"); + mavlink_missionlib_send_gcs_string("[mavlink pm] ERROR loading EEPROM params in RAM"); + result = MAV_RESULT_FAILED; } - /* Check if matched */ - if (match) { - mavlink_pm_send_one_parameter(i); + /* Write all parameters from RAM to EEPROM */ + + } else if (((int)(cmd_mavlink.param1)) == 1) { + + if (OK == mavlink_pm_save_eeprom()) { + //printf("[mavlink pm] RAM params written to EEPROM\n"); + mavlink_missionlib_send_gcs_string("[mavlink pm] RAM params written to EEPROM"); + result = MAV_RESULT_ACCEPTED; + + } else { + //fprintf(stderr, "[mavlink pm] ERROR writing RAM params to EEPROM\n"); + mavlink_missionlib_send_gcs_string("[mavlink pm] ERROR writing RAM params to EEPROM"); + result = MAV_RESULT_FAILED; } - } - } else { - /* when index is >= 0, send this parameter again */ - mavlink_pm_send_one_parameter(mavlink_param_request_read.param_index); + } else { + //fprintf(stderr, "[mavlink pm] refusing unsupported storage request\n"); + mavlink_missionlib_send_gcs_string("[mavlink pm] refusing unsupported storage request"); + result = MAV_RESULT_UNSUPPORTED; + } } } - } break; } } - - -/** - * Send low-priority messages at a maximum rate of xx Hertz. - * - * This function sends messages at a lower rate to not exceed the wireless - * bandwidth. It sends one message each time it is called until the buffer is empty. - * Call this function with xx Hertz to increase/decrease the bandwidth. - */ -void mavlink_pm_queued_send(void) -{ - //send parameters one by one: - mavlink_pm_send_one_parameter(global_data_parameter_storage->pm.next_param); - global_data_parameter_storage->pm.next_param++; -} diff --git a/apps/mavlink/mavlink_parameters.h b/apps/mavlink/mavlink_parameters.h index e32732f58..950f82d2d 100644 --- a/apps/mavlink/mavlink_parameters.h +++ b/apps/mavlink/mavlink_parameters.h @@ -1,7 +1,7 @@ /**************************************************************************** * - * Copyright (C) 2008-2012 PX4 Development Team. All rights reserved. - * Author: Lorenz Meier <lm@inf.ethz.ch> + * Copyright (C) 2012 PX4 Development Team. All rights reserved. + * Author: @author Lorenz Meier <lm@inf.ethz.ch> * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -43,6 +43,60 @@ #include "v1.0/common/mavlink.h" #include <stdbool.h> +#include <systemlib/param/param.h> +/** + * Handle parameter related messages. + */ void mavlink_pm_message_handler(const mavlink_channel_t chan, const mavlink_message_t *msg); -void mavlink_pm_queued_send(void); + +/** + * Send all parameters at once. + * + * This function blocks until all parameters have been sent. + * it delays each parameter by the passed amount of microseconds. + * + * @param delay The delay in us between sending all parameters. + */ +void mavlink_pm_send_all_params(unsigned int delay); + +/** + * Send one parameter. + * + * @param param The parameter id to send. + * @return zero on success, nonzero on failure. + */ +int mavlink_pm_send_param(param_t param); + +/** + * Send one parameter identified by index. + * + * @param index The index of the parameter to send. + * @return zero on success, nonzero else. + */ +int mavlink_pm_send_param_for_index(uint16_t index); + +/** + * Send one parameter identified by name. + * + * @param name The index of the parameter to send. + * @return zero on success, nonzero else. + */ +int mavlink_pm_send_param_for_name(const char* name); + +/** + * Send a queue of parameters, one parameter per function call. + * + * @return zero on success, nonzero on failure + */ + int mavlink_pm_queued_send(void); + +/** + * Start sending the parameter queue. + * + * This function will not directly send parameters, but instead + * activate the sending of one parameter on each call of + * mavlink_pm_queued_send(). + * @see mavlink_pm_queued_send() + */ +void mavlink_pm_start_queued_send(void); diff --git a/apps/px4/tests/tests.h b/apps/px4/tests/tests.h index aa6dae1e0..f2e35972f 100644 --- a/apps/px4/tests/tests.h +++ b/apps/px4/tests/tests.h @@ -95,5 +95,6 @@ extern int test_sleep(int argc, char *argv[]); extern int test_time(int argc, char *argv[]); extern int test_uart_console(int argc, char *argv[]); extern int test_jig_voltages(int argc, char *argv[]); +extern int test_param(int argc, char *argv[]); #endif /* __APPS_PX4_TESTS_H */ diff --git a/apps/px4/tests/tests_main.c b/apps/px4/tests/tests_main.c index 268e7d5f9..a4613288f 100644 --- a/apps/px4/tests/tests_main.c +++ b/apps/px4/tests/tests_main.c @@ -108,6 +108,7 @@ struct { {"perf", test_perf, OPT_NOJIGTEST, 0}, {"all", test_all, OPT_NOALLTEST | OPT_NOJIGTEST, 0}, {"jig", test_jig, OPT_NOJIGTEST | OPT_NOALLTEST, 0}, + {"param", test_param, 0, 0}, {"help", test_help, OPT_NOALLTEST | OPT_NOHELP | OPT_NOJIGTEST, 0}, {NULL, NULL, 0, 0} }; diff --git a/apps/px4/tests/tests_param.c b/apps/px4/tests/tests_param.c new file mode 100644 index 000000000..5ac9f0343 --- /dev/null +++ b/apps/px4/tests/tests_param.c @@ -0,0 +1,81 @@ +/**************************************************************************** + * + * Copyright (C) 2012 PX4 Development Team. All rights reserved. + * Author: @author Lorenz Meier <lm@inf.ethz.ch> + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name PX4 nor the names of its contributors may be + * used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + ****************************************************************************/ + +/** + * @file tests_param.c + * + * Tests related to the parameter system. + */ + +#include <stdio.h> +#include "systemlib/err.h" + +#include "systemlib/param/param.h" +#include "tests.h" + +PARAM_DEFINE_INT32(test, 0x12345678); + +int +test_param(int argc, char *argv[]) +{ + param_t p; + + p = param_find("test"); + if (p == PARAM_INVALID) + errx(1, "test parameter not found"); + + param_type_t t = param_type(p); + if (t != PARAM_TYPE_INT32) + errx(1, "test parameter type mismatch (got %u)", (unsigned)t); + + int32_t val; + if (param_get(p, &val) != 0) + errx(1, "failed to read test parameter"); + if (val != 0x12345678) + errx(1, "parameter value mismatch"); + + val = 0xa5a5a5a5; + if (param_set(p, &val) != 0) + errx(1, "failed to write test parameter"); + if (param_get(p, &val) != 0) + errx(1, "failed to re-read test parameter"); + if ((uint32_t)val != 0xa5a5a5a5) + errx(1, "parameter value mismatch after write"); + + param_export(-1, false); + + warnx("parameter test PASS"); + + return 0; +} diff --git a/apps/systemcmds/eeprom/Makefile b/apps/systemcmds/eeprom/Makefile new file mode 100644 index 000000000..2f3db0fdc --- /dev/null +++ b/apps/systemcmds/eeprom/Makefile @@ -0,0 +1,42 @@ +############################################################################ +# +# Copyright (C) 2012 PX4 Development Team. All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# 1. Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# 2. Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in +# the documentation and/or other materials provided with the +# distribution. +# 3. Neither the name PX4 nor the names of its contributors may be +# used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS +# FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE +# COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, +# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, +# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS +# OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED +# AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN +# ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +# POSSIBILITY OF SUCH DAMAGE. +# +############################################################################ + +# +# Build the eeprom tool. +# + +APPNAME = eeprom +PRIORITY = SCHED_PRIORITY_DEFAULT +STACKSIZE = 4096 + +include $(APPDIR)/mk/app.mk diff --git a/apps/systemcmds/eeprom/eeprom.c b/apps/systemcmds/eeprom/eeprom.c new file mode 100644 index 000000000..90a8a5b9b --- /dev/null +++ b/apps/systemcmds/eeprom/eeprom.c @@ -0,0 +1,191 @@ +/**************************************************************************** + * + * Copyright (C) 2012 PX4 Development Team. All rights reserved. + * Author: Lorenz Meier <lm@inf.ethz.ch> + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name PX4 nor the names of its contributors may be + * used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + ****************************************************************************/ + +/** + * @file eeprom.c + * + * EEPROM service and utility app. + */ + +#include <nuttx/config.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <stdbool.h> +#include <unistd.h> +#include <fcntl.h> +#include <sys/mount.h> +#include <sys/ioctl.h> + +#include <nuttx/i2c.h> +#include <nuttx/mtd.h> +#include <nuttx/fs/nxffs.h> +#include <nuttx/fs/ioctl.h> + +#include <arch/board/board.h> + +#include "systemlib/systemlib.h" +#include "systemlib/param/param.h" +#include "systemlib/err.h" + +#ifndef PX4_I2C_BUS_ONBOARD +# error PX4_I2C_BUS_ONBOARD not defined, cannot locate onboard EEPROM +#endif +#if !defined(CONFIG_MTD_AT24XX) || !CONFIG_MTD_AT24XX +# error CONFIG_MTD_AT24XX not defined, no supported EEPROM available +#endif + +__EXPORT int eeprom_main(int argc, char *argv[]); + +static void eeprom_start(void); +static void eeprom_ioctl(unsigned operation); +static void eeprom_save(const char *name); +static void eeprom_load(const char *name); + +int eeprom_main(int argc, char *argv[]) +{ + if (argc >= 2) { + if (!strcmp(argv[1], "start")) + eeprom_start(); + + if (!strcmp(argv[1], "save_param")) + eeprom_save(argv[2]); + + if (!strcmp(argv[1], "load_param")) + eeprom_load(argv[2]); + + if (0) { /* these actually require a file on the filesystem... */ + + if (!strcmp(argv[1], "reformat")) + eeprom_ioctl(FIOC_REFORMAT); + + if (!strcmp(argv[1], "repack")) + eeprom_ioctl(FIOC_OPTIMIZE); + } + } + + errx(1, "expected a command, try 'start'"); +} + + +static void +eeprom_start(void) +{ + static bool started = false; + int ret; + + if (started) + errx(1, "EEPROM service already started"); + + /* find the right I2C */ + struct i2c_dev_s *i2c = up_i2cinitialize(PX4_I2C_BUS_ONBOARD); + /* this resets the I2C bus, set correct bus speed again */ + I2C_SETFREQUENCY(i2c, 400000); + + if (i2c == NULL) + errx(1, "failed to locate I2C bus"); + + /* start the MTD driver */ + struct mtd_dev_s *mtd = at24c_initialize(i2c); + + if (mtd == NULL) + errx(1, "failed to initialize EEPROM driver"); + + /* start NXFFS */ + ret = nxffs_initialize(mtd); + + if (ret < 0) + err(1, "failed to initialize NXFFS"); + + /* mount the EEPROM */ + ret = mount(NULL, "/eeprom", "nxffs", 0, NULL); + + if (ret < 0) + err(1, "failed to mount EEPROM"); + + errx(0, "mounted EEPROM at /eeprom"); +} + +static void +eeprom_ioctl(unsigned operation) +{ + int fd; + + fd = open("/eeprom/.", 0); + + if (fd < 0) + err(1, "open /eeprom"); + + if (ioctl(fd, operation, 0) < 0) + err(1, "ioctl"); + + exit(0); +} + +static void +eeprom_save(const char *name) +{ + int fd = open(name, O_WRONLY | O_CREAT | O_EXCL); + + if (fd < 0) + err(1, "opening '%s' failed", name); + + int result = param_export(fd, false); + close(fd); + + if (result < 0) { + unlink(name); + errx(1, "error exporting to '%s'", name); + } + + exit(0); +} + +static void +eeprom_load(const char *name) +{ + int fd = open(name, O_RDONLY); + + if (fd < 0) + err(1, "open '%s'", name); + + int result = param_import(fd); + close(fd); + + if (result < 0) + errx(1, "error importing from '%s'", name); + + exit(0); +} diff --git a/apps/systemlib/Makefile b/apps/systemlib/Makefile index e1a6db598..0b3cb3c7b 100644 --- a/apps/systemlib/Makefile +++ b/apps/systemlib/Makefile @@ -37,7 +37,9 @@ CSRCS = err.c \ hx_stream.c \ - perf_counter.c + perf_counter.c \ + param/param.c \ + bson/tinybson.c # # XXX this really should be a CONFIG_* test diff --git a/apps/systemlib/bson/tinybson.c b/apps/systemlib/bson/tinybson.c new file mode 100644 index 000000000..1e5274a12 --- /dev/null +++ b/apps/systemlib/bson/tinybson.c @@ -0,0 +1,312 @@ +/**************************************************************************** + * + * Copyright (C) 2012 PX4 Development Team. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name PX4 nor the names of its contributors may be + * used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + ****************************************************************************/ + +/** + * @file tinybson.c + * + * A simple subset SAX-style BSON parser and generator. + */ + +#include <unistd.h> +#include <string.h> +#include <err.h> + +#include "tinybson.h" + + +#if 1 +# define debug(fmt, args...) do { warnx("BSON:" fmt, ##args); } while(0) +#else +# define debug(fmt, args...) do { } while(0) +#endif + +#define CODER_CHECK(_c) do { if (_c->fd == -1) return -1; } while(0) +#define CODER_KILL(_c, _reason) do { debug("killed:%s", _reason); _c->fd = -1; return -1; } while(0) + +static int +read_int8(bson_decoder_t decoder, int8_t *b) +{ + return (read(decoder->fd, b, sizeof(*b)) == sizeof(*b)) ? 0 : -1; +} + +static int +read_int32(bson_decoder_t decoder, int32_t *i) +{ + return (read(decoder->fd, i, sizeof(*i)) == sizeof(*i)) ? 0 : -1; +} + +static int +read_double(bson_decoder_t decoder, double *d) +{ + return (read(decoder->fd, d, sizeof(*d)) == sizeof(*d)) ? 0 : -1; +} + +int +bson_decoder_init(bson_decoder_t decoder, int fd, bson_decoder_callback callback, void *private) +{ + int32_t junk; + + decoder->fd = fd; + decoder->callback = callback; + decoder->private = private; + decoder->nesting = 1; + decoder->pending = 0; + decoder->node.type = BSON_UNDEFINED; + + /* read and discard document size */ + if (read_int32(decoder, &junk)) + CODER_KILL(decoder, "failed reading length"); + + /* ready for decoding */ + return 0; +} + +int +bson_decoder_next(bson_decoder_t decoder) +{ + int8_t tbyte; + unsigned nlen; + + CODER_CHECK(decoder); + + /* if the previous node was EOO, pop a nesting level */ + if (decoder->node.type == BSON_EOO) { + if (decoder->nesting > 0) + decoder->nesting--; + + /* if the nesting level is now zero, the top-level document is done */ + if (decoder->nesting == 0) + CODER_KILL(decoder, "nesting is zero, document is done"); + } + + /* if there are unread bytes pending in the stream, discard them */ + while (decoder->pending > 0) { + if (read_int8(decoder, &tbyte)) + CODER_KILL(decoder, "read error discarding pending bytes"); + decoder->pending--; + } + + /* get the type byte */ + if (read_int8(decoder, &tbyte)) + CODER_KILL(decoder, "read error on type byte"); + decoder->node.type = tbyte; + decoder->pending = 0; + + debug("got type byte 0x%02x", decoder->node.type); + + /* EOO is special; it has no name/data following */ + if (decoder->node.type != BSON_EOO) { + + /* get the node name */ + nlen = 0; + for (;;) { + if (nlen >= BSON_MAXNAME) + CODER_KILL(decoder, "node name overflow"); + if (read_int8(decoder, (int8_t *)&decoder->node.name[nlen])) + CODER_KILL(decoder, "read error on node name"); + if (decoder->node.name[nlen] == '\0') + break; + nlen++; + } + + debug("got name '%s'", decoder->node.name); + + switch (decoder->node.type) { + case BSON_INT: + if (read_int32(decoder, &decoder->node.i)) + CODER_KILL(decoder, "read error on BSON_INT"); + break; + case BSON_DOUBLE: + if (read_double(decoder, &decoder->node.d)) + CODER_KILL(decoder, "read error on BSON_DOUBLE"); + break; + case BSON_STRING: + if (read_int32(decoder, &decoder->pending)) + CODER_KILL(decoder, "read error on BSON_STRING length"); + break; + case BSON_BINDATA: + if (read_int32(decoder, &decoder->pending)) + CODER_KILL(decoder, "read error on BSON_BINDATA size"); + if (read_int8(decoder, &tbyte)) + CODER_KILL(decoder, "read error on BSON_BINDATA subtype"); + decoder->node.subtype = tbyte; + break; + + /* XXX currently not supporting other types */ + default: + CODER_KILL(decoder, "unsupported node type"); + } + } + + /* call the callback and pass its results back */ + return decoder->callback(decoder, decoder->private, &decoder->node); +} + +int +bson_decoder_copy_data(bson_decoder_t decoder, void *buf) +{ + int result; + + CODER_CHECK(decoder); + + /* if data already copied, return zero bytes */ + if (decoder->pending == 0) + return 0; + + /* copy bytes per the node size */ + result = read(decoder->fd, buf, decoder->pending); + if (result != decoder->pending) + CODER_KILL(decoder, "read error on copy_data"); + + /* pending count is discharged */ + decoder->pending = 0; + return 0; +} + +size_t +bson_decoder_data_pending(bson_decoder_t decoder) +{ + return decoder->pending; +} + +static int +write_int8(bson_encoder_t encoder, int8_t b) +{ + debug("write_int8 %d", b); + return (write(encoder->fd, &b, sizeof(b)) == sizeof(b)) ? 0 : -1; +} + +static int +write_int32(bson_encoder_t encoder, int32_t i) +{ + debug("write_int32 %d", i); + return (write(encoder->fd, &i, sizeof(i)) == sizeof(i)) ? 0 : -1; +} + +static int +write_double(bson_encoder_t encoder, double d) +{ + debug("write_double"); + return (write(encoder->fd, &d, sizeof(d)) == sizeof(d)) ? 0 : -1; +} + +static int +write_name(bson_encoder_t encoder, const char *name) +{ + size_t len = strlen(name); + + if (len > BSON_MAXNAME) + return -1; + debug("write name '%s' len %d", name, len); + return (write(encoder->fd, name, len + 1) == (int)(len + 1)) ? 0 : -1; +} + +int +bson_encoder_init(bson_encoder_t encoder, int fd) +{ + encoder->fd = fd; + + if (write_int32(encoder, 0)) + CODER_KILL(encoder, "write error on document length"); + + return 0; +} + +int +bson_encoder_fini(bson_encoder_t encoder) +{ + CODER_CHECK(encoder); + + if (write_int8(encoder, 0)) + CODER_KILL(encoder, "write error on document terminator"); + + return 0; +} + +int +bson_encoder_append_int(bson_encoder_t encoder, const char *name, int32_t value) +{ + CODER_CHECK(encoder); + + if (write_int8(encoder, BSON_INT) || + write_name(encoder, name) || + write_int32(encoder, value)) + CODER_KILL(encoder, "write error on BSON_INT"); + + return 0; +} + +int +bson_encoder_append_double(bson_encoder_t encoder, const char *name, double value) +{ + CODER_CHECK(encoder); + + if (write_int8(encoder, BSON_DOUBLE) || + write_name(encoder, name) || + write_double(encoder, value)) + CODER_KILL(encoder, "write error on BSON_DOUBLE"); + + + return 0; +} + +int +bson_encoder_append_string(bson_encoder_t encoder, const char *name, const char *string) +{ + size_t len; + + CODER_CHECK(encoder); + + len = strlen(string); + + if (write_int8(encoder, BSON_DOUBLE) || + write_name(encoder, name) || + write_int32(encoder, len) || + write(encoder->fd, name, len + 1) != (int)(len + 1)) + CODER_KILL(encoder, "write error on BSON_STRING"); + return 0; +} + +int +bson_encoder_append_binary(bson_encoder_t encoder, const char *name, bson_binary_subtype_t subtype, size_t size, const void *data) +{ + CODER_CHECK(encoder); + + if (write_int8(encoder, BSON_BINDATA) || + write_name(encoder, name) || + write_int32(encoder, size) || + write_int8(encoder, subtype) || + write(encoder->fd, data, size) != (int)(size)) + CODER_KILL(encoder, "write error on BSON_BINDATA"); + return 0; +} diff --git a/apps/systemlib/bson/tinybson.h b/apps/systemlib/bson/tinybson.h new file mode 100644 index 000000000..05bae007b --- /dev/null +++ b/apps/systemlib/bson/tinybson.h @@ -0,0 +1,169 @@ +/**************************************************************************** + * + * Copyright (C) 2012 PX4 Development Team. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name PX4 nor the names of its contributors may be + * used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + ****************************************************************************/ + + /** + * @file tinybson.h + * + * A simple subset SAX-style BSON parser and generator. + * + * Some types and defines taken from the standalone BSON parser/generator + * in the Mongo C connector. + */ + +#ifndef _TINYBSON_H +#define _TINYBSON_H + +#include <sys/types.h> +#include <stdint.h> +#include <stdbool.h> + +/** subset of the BSON node types we might care about */ +typedef enum { + BSON_EOO = 0, + BSON_DOUBLE = 1, + BSON_STRING = 2, + BSON_OBJECT = 3, + BSON_ARRAY = 4, + BSON_BINDATA = 5, + BSON_UNDEFINED = 6, + BSON_BOOL = 8, + BSON_DATE = 9, + BSON_NULL = 10, + BSON_INT = 16, + BSON_TIMESTAMP = 17, + BSON_LONG = 18 +} bson_type_t; + +typedef enum bson_binary_subtype { + BSON_BIN_BINARY = 0, + BSON_BIN_USER = 128 +} bson_binary_subtype_t; + +/** + * Maximum node name length. + */ +#define BSON_MAXNAME 32 + +/** + * Node structure passed to the callback. + */ +typedef struct bson_node_s +{ + char name[BSON_MAXNAME]; + bson_type_t type; + bson_binary_subtype_t subtype; + union { + int32_t i; + double d; + bool b; + }; +} *bson_node_t; + +typedef struct bson_decoder_s *bson_decoder_t; + +/** + * Node callback. + */ +typedef int (* bson_decoder_callback)(bson_decoder_t decoder, void *private, bson_node_t node); + +struct bson_decoder_s +{ + int fd; + bson_decoder_callback callback; + void *private; + unsigned nesting; + struct bson_node_s node; + int32_t pending; +}; + +/** + * Initialise the decoder. + */ +__EXPORT int bson_decoder_init(bson_decoder_t decoder, int fd, bson_decoder_callback callback, void *private); + +/** + * Process the next node from the stream and invoke the callback. + */ +__EXPORT int bson_decoder_next(bson_decoder_t decoder); + +/** + * Copy node data. + */ +__EXPORT int bson_decoder_copy_data(bson_decoder_t decoder, void *buf); + +/** + * Report copyable data size. + */ +__EXPORT size_t bson_decoder_data_pending(bson_decoder_t decoder); + +/** + * Encoder state structure. + */ +typedef struct bson_encoder_s +{ + int fd; + +} *bson_encoder_t; + +/** + * Initialze the encoder. + */ +__EXPORT int bson_encoder_init(bson_encoder_t encoder, int fd); + +/** + * Finalise the encoded stream. + */ +__EXPORT int bson_encoder_fini(bson_encoder_t encoder); + +/** + * Append an integer to the encoded stream. + */ +__EXPORT int bson_encoder_append_int(bson_encoder_t encoder, const char *name, int32_t value); + +/** + * Append a double to the encoded stream + */ +__EXPORT int bson_encoder_append_double(bson_encoder_t encoder, const char *name, double value); + +/** + * Append a string to the encoded stream. + */ +__EXPORT int bson_encoder_append_string(bson_encoder_t encoder, const char *name, const char *string); + +/** + * Append a binary blob to the encoded stream. + */ +__EXPORT int bson_encoder_append_binary(bson_encoder_t encoder, const char *name, bson_binary_subtype_t subtype, size_t size, const void *data); + + +#endif diff --git a/apps/systemlib/param/param.c b/apps/systemlib/param/param.c new file mode 100644 index 000000000..692489cd4 --- /dev/null +++ b/apps/systemlib/param/param.c @@ -0,0 +1,585 @@ +/**************************************************************************** + * + * Copyright (C) 2012 PX4 Development Team. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name PX4 nor the names of its contributors may be + * used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + ****************************************************************************/ + +/** + * @file param.c + * + * Global parameter store. + */ + +#include <debug.h> +#include <string.h> +#include <stdbool.h> +#include <fcntl.h> +#include <unistd.h> +#include <err.h> + +#include <sys/stat.h> + +#include "systemlib/param/param.h" +#include "systemlib/uthash/utarray.h" +#include "systemlib/bson/tinybson.h" + +#if 1 +# define debug(fmt, args...) do { warnx(fmt, ##args); } while(0) +#else +# define debug(fmt, args...) do { } while(0) +#endif + +/** + * Array of static parameter info. + */ +extern char __param_start, __param_end; +static const struct param_info_s *param_info_base = (struct param_info_s *) &__param_start; +static const struct param_info_s *param_info_limit = (struct param_info_s *) &__param_end; +#define param_info_count ((unsigned)(param_info_limit - param_info_base)) + +/** + * Storage for modified parameters. + */ +struct param_wbuf_s { + param_t param; + union param_value_u val; + bool unsaved; +}; + +/** flexible array holding modified parameter values */ +UT_array *param_values; + +/** array info for the modified parameters array */ +UT_icd param_icd = {sizeof(struct param_wbuf_s), NULL, NULL, NULL}; + +/** lock the parameter store */ +static void +param_lock(void) +{ + /* XXX */ +} + +/** unlock the parameter store */ +static void +param_unlock(void) +{ + /* XXX */ +} + +/** assert that the parameter store is locked */ +static void +param_assert_locked(void) +{ + /* XXX */ +} + +/** + * Test whether a param_t is value. + * + * @param param The parameter handle to test. + * @return True if the handle is valid. + */ +static bool +handle_in_range(param_t param) +{ + return (param < param_info_count); +} + +/** + * Compare two modifid parameter structures to determine ordering. + * + * This function is suitable for passing to qsort or bsearch. + */ +static int +param_compare_values(const void *a, const void *b) +{ + struct param_wbuf_s *pa = (struct param_wbuf_s *)a; + struct param_wbuf_s *pb = (struct param_wbuf_s *)b; + + if (pa->param < pb->param) + return -1; + + if (pa->param > pb->param) + return 1; + + return 0; +} + +/** + * Locate the modified parameter structure for a parameter, if it exists. + * + * @param param The parameter being searched. + * @return The structure holding the modified value, or + * NULL if the parameter has not been modified. + */ +static struct param_wbuf_s * +param_find_changed(param_t param) { + struct param_wbuf_s *s = NULL; + + param_assert_locked(); + + if (param_values != NULL) { +#if 0 /* utarray_find requires bsearch, not available */ + struct param_wbuf_s key; + key.param = param; + s = utarray_find(param_values, &key, param_compare_values); +#else + + while ((s = (struct param_wbuf_s *)utarray_next(param_values, s)) != NULL) { + if (s->param == param) + break; + } + +#endif + } + + return s; +} + +param_t +param_find(const char *name) +{ + param_t param; + + /* perform a linear search of the known parameters */ + for (param = 0; handle_in_range(param); param++) { + if (!strcmp(param_info_base[param].name, name)) + return param; + } + + /* not found */ + return PARAM_INVALID; +} + +unsigned +param_count(void) +{ + return param_info_count; +} + +param_t +param_for_index(unsigned index) +{ + if (index < param_info_count) + return (param_t)index; + + return PARAM_INVALID; +} + +int +param_get_index(param_t param) +{ + if (handle_in_range(param)) + return (unsigned)param; + + return -1; +} + +const char * +param_name(param_t param) +{ + if (handle_in_range(param)) + return param_info_base[param].name; + + return NULL; +} + +enum param_type_e +param_type(param_t param) +{ + if (handle_in_range(param)) + return param_info_base[param].type; + + return PARAM_TYPE_UNKNOWN; +} + +size_t +param_size(param_t param) +{ + if (handle_in_range(param)) { + switch (param_type(param)) { + case PARAM_TYPE_INT32: + case PARAM_TYPE_FLOAT: + return 4; + + case PARAM_TYPE_STRUCT ... PARAM_TYPE_STRUCT_MAX: + /* decode structure size from type value */ + return param_type(param) - PARAM_TYPE_STRUCT; + + default: + return 0; + } + } + + return 0; +} + +/** + * Obtain a pointer to the storage allocated for a parameter. + * + * @param param The parameter whose storage is sought. + * @return A pointer to the parameter value, or NULL + * if the parameter does not exist. + */ +static const void * +param_get_value_ptr(param_t param) +{ + const void *result = NULL; + + param_assert_locked(); + + if (handle_in_range(param)) { + + const union param_value_u *v; + + /* work out whether we're fetching the default or a written value */ + struct param_wbuf_s *s = param_find_changed(param); + + if (s != NULL) { + v = &s->val; + + } else { + v = ¶m_info_base[param].val; + } + + if (param_type(param) == PARAM_TYPE_STRUCT) { + result = v->p; + + } else { + result = v; + } + } + + return result; +} + +int +param_get(param_t param, void *val) +{ + int result = -1; + + param_lock(); + + const void *v = param_get_value_ptr(param); + + if (val != NULL) { + memcpy(val, v, param_size(param)); + result = 0; + } + + param_unlock(); + + return result; +} + +int +param_set(param_t param, const void *val) +{ + int result = -1; + + param_lock(); + + if (param_values == NULL) + utarray_new(param_values, ¶m_icd); + + if (param_values == NULL) { + debug("failed to allocate modified values array"); + goto out; + } + + if (handle_in_range(param)) { + + struct param_wbuf_s *s = param_find_changed(param); + + if (s == NULL) { + + /* construct a new parameter */ + struct param_wbuf_s buf = { + .param = param, + .val.p = NULL, + .unsaved = false + }; + + /* add it to the array and sort */ + utarray_push_back(param_values, &buf); + utarray_sort(param_values, param_compare_values); + + /* find it after sorting */ + s = param_find_changed(param); + } + + /* update the changed value */ + switch (param_type(param)) { + case PARAM_TYPE_INT32: + s->val.i = *(int32_t *)val; + break; + + case PARAM_TYPE_FLOAT: + s->val.f = *(float *)val; + break; + + case PARAM_TYPE_STRUCT ... PARAM_TYPE_STRUCT_MAX: + if (s->val.p == NULL) { + s->val.p = malloc(param_size(param)); + + if (s->val.p == NULL) { + debug("failed to allocate parameter storage"); + goto out; + } + } + + memcpy(s->val.p, val, param_size(param)); + break; + + default: + goto out; + } + + s->unsaved = true; + + result = 0; + } + +out: + param_unlock(); + return result; +} + +int +param_export(int fd, bool only_unsaved) +{ + struct param_wbuf_s *s = NULL; + struct bson_encoder_s encoder; + int result = -1; + + param_lock(); + + bson_encoder_init(&encoder, fd); + + /* no modified parameters -> we are done */ + if (param_values == NULL) { + result = 0; + goto out; + } + + while ((s = (struct param_wbuf_s *)utarray_next(param_values, s)) != NULL) { + + int32_t i; + float f; + + /* + * If we are only saving values changed since last save, and this + * one hasn't, then skip it + */ + if (only_unsaved & !s->unsaved) + continue; + + s->unsaved = false; + + /* append the appripriate BSON type object */ + switch (param_type(s->param)) { + case PARAM_TYPE_INT32: + param_get(s->param, &i); + if (bson_encoder_append_int(&encoder, param_name(s->param), i)) { + debug("BSON append failed for '%s'", param_name(s->param)); + goto out; + } + + break; + + case PARAM_TYPE_FLOAT: + param_get(s->param, &f); + if (bson_encoder_append_double(&encoder, param_name(s->param), f)) { + debug("BSON append failed for '%s'", param_name(s->param)); + goto out; + } + + break; + + case PARAM_TYPE_STRUCT ... PARAM_TYPE_STRUCT_MAX: + if (bson_encoder_append_binary(&encoder, + param_name(s->param), + BSON_BIN_BINARY, + param_size(s->param), + param_get_value_ptr(s->param))) { + debug("BSON append failed for '%s'", param_name(s->param)); + goto out; + } + + break; + + default: + debug("unrecognised parameter type"); + goto out; + } + } + + if (bson_encoder_fini(&encoder)) + goto out; + + result = 0; + +out: + param_unlock(); + + return result; +} + +static int +param_import_callback(bson_decoder_t decoder, void *private, bson_node_t node) +{ + float f; + int32_t i; + void *v, *tmp = NULL; + int result = -1; + + /* + * EOO means the end of the parameter object. + */ + if (node->type == BSON_EOO) { + *(bool *)private = true; + debug("end of parameters"); + return 0; + } + + /* + * Find the parameter this node represents. If we don't know it, + * ignore the node. + */ + param_t param = param_find(node->name); + if (param == PARAM_INVALID) + return 0; + + /* + * Handle setting the parameter from the node + */ + + switch (node->type) { + case BSON_INT: + if (param_type(param) != PARAM_TYPE_INT32) { + debug("unexpected type for '%s", node->name); + goto out; + } + i = node->i; + v = &i; + break; + + case BSON_DOUBLE: + if (param_type(param) != PARAM_TYPE_FLOAT) { + debug("unexpected type for '%s", node->name); + goto out; + } + f = node->d; + v = &f; + break; + + case BSON_BINDATA: + if (node->subtype != BSON_BIN_BINARY) { + debug("unexpected subtype for '%s", node->name); + goto out; + } + if (bson_decoder_data_pending(decoder) != param_size(param)) { + debug("bad size for '%s'", node->name); + goto out; + } + /* XXX check actual file data size? */ + tmp = malloc(param_size(param)); + if (tmp == NULL) { + debug("failed allocating for '%s'", node->name); + goto out; + } + if (bson_decoder_copy_data(decoder, tmp)) { + debug("failed copying data for '%s'", node->name); + goto out; + } + v = tmp; + break; + default: + debug("unrecognised node type"); + goto out; + } + + if (param_set(param, v)) { + debug("error setting value for '%s'", node->name); + goto out; + } + if (tmp != NULL) { + free(tmp); + tmp = NULL; + } + + result = 0; + +out: + if (tmp != NULL) + free(tmp); + return result; +} + +int +param_import(int fd) +{ + bool done; + struct bson_decoder_s decoder; + int result = -1; + + if (bson_decoder_init(&decoder, fd, param_import_callback, &done)) { + debug("decoder init failed"); + goto out; + } + + done = false; + + while (!done) { + result = bson_decoder_next(&decoder); + if (result != 0) { + debug("error during BSON decode"); + break; + } + } + +out: + return result; +} + +void +param_foreach(void (*func)(void *arg, param_t param), void *arg, bool only_changed) +{ + param_t param; + + for (param = 0; handle_in_range(param); param++) { + + /* if requested, skip unchanged values */ + if (only_changed && (param_find_changed(param) == NULL)) + continue; + + func(arg, param); + } +}
\ No newline at end of file diff --git a/apps/systemlib/param/param.h b/apps/systemlib/param/param.h new file mode 100644 index 000000000..643d0ef7b --- /dev/null +++ b/apps/systemlib/param/param.h @@ -0,0 +1,248 @@ +/**************************************************************************** + * + * Copyright (C) 2012 PX4 Development Team. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name PX4 nor the names of its contributors may be + * used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + ****************************************************************************/ + +/** + * @file param.h + * + * Global parameter store. + * + * Note that a number of API members are marked const or pure; these + * assume that the set of parameters cannot change, or that a parameter + * cannot change type or size over its lifetime. If any of these assumptions + * are invalidated, the attributes should be re-evaluated. + */ + +#ifndef _SYSTEMLIB_PARAM_PARAM_H +#define _SYSTEMLIB_PARAM_PARAM_H + +#include <stdint.h> +#include <stdbool.h> + +/** Maximum size of the parameter backing file */ +#define PARAM_FILE_MAXSIZE 4096 + +/** + * Parameter types. + */ +typedef enum param_type_e { + /* globally-known parameter types */ + PARAM_TYPE_INT32 = 0, + PARAM_TYPE_FLOAT, + + /* structure parameters; size is encoded in the type value */ + PARAM_TYPE_STRUCT = 100, + PARAM_TYPE_STRUCT_MAX = 16384 + PARAM_TYPE_STRUCT, + + PARAM_TYPE_UNKNOWN = 0xffff +} param_type_t; + +/** + * Parameter handle. + * + * Parameters are represented by parameter handles, which can + * be obtained by looking up (or creating?) parameters. + */ +typedef uintptr_t param_t; + +/** + * Handle returned when a parameter cannot be found. + */ +#define PARAM_INVALID ((uintptr_t)0xffffffff) + +/** + * Look up a parameter by name. + * + * @param name The canonical name of the parameter being looked up. + * @return A handle to the parameter, or PARAM_INVALID if the parameter does not exist. + */ +__EXPORT param_t param_find(const char *name) __attribute__((const)); + +/** + * Return the total number of parameters. + * + * @return The number of parameters. + */ +__EXPORT unsigned param_count(void) __attribute__((const)); + +/** + * Look up a parameter by index. + * + * @param index An index from 0 to n, where n is param_count()-1. + * @return A handle to the parameter, or PARAM_INVALID if the index is out of range. + */ +__EXPORT param_t param_for_index(unsigned index) __attribute__((const)); + +/** + * Look up the index of a parameter. + * + * @param param The parameter to obtain the index for. + * @return The index, or -1 if the parameter does not exist. + */ +__EXPORT int param_get_index(param_t param) __attribute__((const)); + +/** + * Obtain the name of a parameter. + * + * @param param A handle returned by param_find or passed by param_foreach. + * @return The name assigned to the parameter, or NULL if the handle is invalid. + */ +__EXPORT const char *param_name(param_t param) __attribute__((const)); + +/** + * Obtain the type of a parameter. + * + * @param param A handle returned by param_find or passed by param_foreach. + * @return The type assigned to the parameter. + */ +__EXPORT param_type_t param_type(param_t param) __attribute__((const)); + +/** + * Determine the size of a parameter. + * + * @param param A handle returned by param_find or passed by param_foreach. + * @return The size of the parameter's value. + */ +__EXPORT size_t param_size(param_t param) __attribute__((const)); + +/** + * Copy the value of a parameter. + * + * @param param A handle returned by param_find or passed by param_foreach. + * @param val Where to return the value, assumed to point to suitable storage for the parameter type. + * For structures, a bitwise copy of the structure is performed to this address. + * @return Zero if the parameter's value could be returned, nonzero otherwise. + */ +__EXPORT int param_get(param_t param, void *val); + +/** + * Set the scalar value of a parameter. + * + * @param param A handle returned by param_find or passed by param_foreach. + * @param val The value to set; assumed to point to a variable of the parameter type. + * For structures, the pointer is assumed to point to a copy of the structure. + * @return Zero if the parameter's value could be set from a scalar, nonzero otherwise. + */ +__EXPORT int param_set(param_t param, const void *val); + +/** + * Export changed parameters to a file. + * + * @param fd File descriptor to export to. + * @param only_unsaved Only export changed parameters that have not yet been exported. + * @return Zero on success, nonzero on failure. + */ +__EXPORT int param_export(int fd, bool only_unsaved); + +/** + * Import parameters from a file, discarding any unrecognized parameters. + * + * @param fd File descriptor to import from. (Currently expected to be a file.) + * @return Zero on success, nonzero if an error occurred during import. + * Note that in the failure case, parameters may be inconsistent. + */ +__EXPORT int param_import(int fd); + +/** + * Apply a function to each parameter. + * + * Note that the parameter set is not locked during the traversal. It also does + * not hold an internal state, so the callback function can block or sleep between + * parameter callbacks. + * + * @param func The function to invoke for each parameter. + * @param arg Argument passed to the function. + * @param only_changed If true, the function is only called for parameters whose values have + * been changed from the default. + */ +__EXPORT void param_foreach(void (*func)(void *arg, param_t param), void *arg, bool only_changed); + +/* + * Macros creating static parameter definitions. + * + * Note that these structures are not known by name; they are + * collected into a section that is iterated by the parameter + * code. + */ + +/** define an int32 parameter */ +#define PARAM_DEFINE_INT32(_name, _default) \ + static const \ + __attribute__((used, section("__param"))) \ + struct param_info_s __param__##_name = { \ + .name = #_name, \ + .type = PARAM_TYPE_INT32, \ + .val.i = _default \ + } + +/** define a float parameter */ +#define PARAM_DEFINE_FLOAT(_name, _default) \ + static const \ + __attribute__((used, section("__param"))) \ + struct param_info_s __param__##_name = { \ + .name = #_name, \ + .type = PARAM_TYPE_FLOAT, \ + .val.f = _default \ + } + +/** define a parameter that points to a structure */ +#define PARAM_DEFINE_STRUCT(_name, _default) \ + static const \ + __attribute__((used, section("__param"))) \ + struct param_info_s __param__##_name = { \ + .name = #_name, \ + .type = PARAM_TYPE_STRUCT + sizeof(_default), \ + .val.p = &_default; \ + } + +/** + * Parameter value union. + */ +union param_value_u { + void *p; + int32_t i; + float f; +}; + +/** + * Static parameter definition structure. + * + * This is normally not used by user code; see the PARAM_DEFINE macros + * instead. + */ +struct param_info_s { + const char *name; + param_type_t type; + union param_value_u val; +}; + +#endif diff --git a/apps/systemlib/uthash/doc/userguide.txt b/apps/systemlib/uthash/doc/userguide.txt new file mode 100644 index 000000000..3e65a52fc --- /dev/null +++ b/apps/systemlib/uthash/doc/userguide.txt @@ -0,0 +1,1682 @@ +uthash User Guide +================= +Troy D. Hanson <thanson@users.sourceforge.net> +v1.9.6, April 2012 + +include::sflogo.txt[] +include::topnav.txt[] + +A hash in C +----------- +include::toc.txt[] + +This document is written for C programmers. Since you're reading this, chances +are that you know a hash is used for looking up items using a key. In scripting +languages like Perl, hashes are used all the time. In C, hashes don't exist in +the language itself. This software provides a hash table for C structures. + +What can it do? +~~~~~~~~~~~~~~~~~ +This software supports these operations on items in a hash table: + +1. add +2. find +3. delete +4. count +5. iterate +6. sort +7. select + +Is it fast? +~~~~~~~~~~~ +Add, find and delete are normally constant-time operations. This is influenced +by your key domain and the hash function. + +This hash aims to be minimalistic and efficient. It's around 900 lines of C. +It inlines automatically because it's implemented as macros. It's fast as long +as the hash function is suited to your keys. You can use the default hash +function, or easily compare performance and choose from among several other +<<hash_functions,built-in hash functions>>. + +Is it a library? +~~~~~~~~~~~~~~~~ +No, it's just a single header file: `uthash.h`. All you need to do is copy +the header file into your project, and: + + #include "uthash.h" + +Since uthash is a header file only, there is no library code to link against. + +C/C++ and platforms +~~~~~~~~~~~~~~~~~~~ +This software can be used in C and C++ programs. It has been tested on: + + * Linux + * Mac OS X + * Windows using Visual Studio 2008 and 2010 + * Solaris + * OpenBSD + * FreeBSD + +Test suite +^^^^^^^^^^ +To run the test suite, enter the `tests` directory. Then, + + * on Unix platforms, run `make` + * on Windows, run the "do_tests_win32.cmd" batch file. (You may edit the + batch file if your Visual Studio is installed in a non-standard location). + +BSD licensed +~~~~~~~~~~~~ +This software is made available under the +link:license.html[revised BSD license]. +It is free and open source. + +Obtaining uthash +~~~~~~~~~~~~~~~~ +Please follow the link to download on the +http://uthash.sourceforge.net[uthash website] at http://uthash.sourceforge.net. + +A number of platforms include uthash in their package repositories. For example, +Debian/Ubuntu users may simply `aptitude install uthash-dev`. + +Getting help +~~~~~~~~~~~~ +Feel free to mailto:tdh@tkhanson.net[email the author] at +tdh@tkhanson.net. + +Resources +~~~~~~~~~ +Users of uthash may wish to follow the news feed for information about new +releases. Also, there are some extra bonus headers included with uthash. + +News:: + The author has a news feed for http://troydhanson.wordpress.com/[software updates] image:img/rss.png[(RSS)]. +Extras included with uthash:: + uthash ships with these "extras"-- independent headers similar to uthash. + First link:utlist.html[utlist.h] provides linked list macros for C structures. + Second, link:utarray.html[utarray.h] implements dynamic arrays using macros. + Third, link:utstring.html[utstring.h] implements a basic dynamic string. +Other software:: + Other open-source software by the author is listed at http://tkhanson.net. + +Who's using it? +~~~~~~~~~~~~~~~ +Since releasing uthash in 2006, it has been downloaded thousands of times, +incorporated into commercial software, academic research, and into other +open-source software. + +Your structure +-------------- + +In uthash, a hash table is comprised of structures. Each structure represents a +key-value association. One or more of the structure fields constitute the key. +The structure pointer itself is the value. + +.Defining a structure that can be hashed +---------------------------------------------------------------------- +#include "uthash.h" + +struct my_struct { + int id; /* key */ + char name[10]; + UT_hash_handle hh; /* makes this structure hashable */ +}; +---------------------------------------------------------------------- + +Note that, in uthash, your structure will never be moved or copied into another +location when you add it into a hash table. This means that you can keep other +data structures that safely point to your structure-- regardless of whether you +add or delete it from a hash table during your program's lifetime. + +The key +~~~~~~~ +There are no restrictions on the data type or name of the key field. The key +can also comprise multiple contiguous fields, having any names and data types. + +.Any data type... really? +***************************************************************************** +Yes, your key and structure can have any data type. Unlike function calls with +fixed prototypes, uthash consists of macros-- whose arguments are untyped-- and +thus able to work with any type of structure or key. +***************************************************************************** + +Unique keys +^^^^^^^^^^^ +As with any hash, every item must have a unique key. Your application must +enforce key uniqueness. Before you add an item to the hash table, you must +first know (if in doubt, check!) that the key is not already in use. You +can check whether a key already exists in the hash table using `HASH_FIND`. + +The hash handle +~~~~~~~~~~~~~~~ +The `UT_hash_handle` field must be present in your structure. It is used for +the internal bookkeeping that makes the hash work. It does not require +initialization. It can be named anything, but you can simplify matters by +naming it `hh`. This allows you to use the easier "convenience" macros to add, +find and delete items. + +A word about memory +~~~~~~~~~~~~~~~~~~~ +Some have asked how uthash cleans up its internal memory. The answer is simple: +'when you delete the final item' from a hash table, uthash releases all the +internal memory associated with that hash table, and sets its pointer to NULL. + +Hash operations +--------------- + +This section introduces the uthash macros by example. For a more succinct +listing, see <<Macro_reference,Macro Reference>>. + +.Convenience vs. general macros: +***************************************************************************** +The uthash macros fall into two categories. The 'convenience' macros can be used +with integer, pointer or string keys (and require that you chose the conventional +name `hh` for the `UT_hash_handle` field). The convenience macros take fewer +arguments than the general macros, making their usage a bit simpler for these +common types of keys. + +The 'general' macros can be used for any types of keys, or for multi-field keys, +or when the `UT_hash_handle` has been named something other than `hh`. These +macros take more arguments and offer greater flexibility in return. But if the +convenience macros suit your needs, use them-- your code will be more readable. +***************************************************************************** + +Declare the hash +~~~~~~~~~~~~~~~~ +Your hash must be declared as a `NULL`-initialized pointer to your structure. + + struct my_struct *users = NULL; /* important! initialize to NULL */ + +Add item +~~~~~~~~ +Allocate and initialize your structure as you see fit. The only aspect +of this that matters to uthash is that your key must be initialized to +a unique value. Then call `HASH_ADD`. (Here we use the convenience macro +`HASH_ADD_INT`, which offers simplified usage for keys of type `int`). + +.Add an item to a hash +---------------------------------------------------------------------- +void add_user(int user_id, char *name) { + struct my_struct *s; + + s = malloc(sizeof(struct my_struct)); + s->id = user_id; + strcpy(s->name, name); + HASH_ADD_INT( users, id, s ); /* id: name of key field */ +} +---------------------------------------------------------------------- + +The first parameter to `HASH_ADD_INT` is the hash table, and the +second parameter is the 'name' of the key field. Here, this is `id`. The +last parameter is a pointer to the structure being added. + +[[validc]] +.Wait.. the field name is a parameter? +******************************************************************************* +If you find it strange that `id`, which is the 'name of a field' in the +structure, can be passed as a parameter, welcome to the world of macros. Don't +worry- the C preprocessor expands this to valid C code. +******************************************************************************* + +Key must not be modified while in-use +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Once a structure has been added to the hash, do not change the value of its key. +Instead, delete the item from the hash, change the key, and then re-add it. + +Passing the hash pointer into functions +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +In the example above `users` is a global variable, but what if the caller wanted +to pass the hash pointer 'into' the `add_user` function? At first glance it would +appear that you could simply pass `users` as an argument, but that won't work +right. + + /* bad */ + void add_user(struct my_struct *users, int user_id, char *name) { + ... + HASH_ADD_INT( users, id, s ); + } + +You really need to pass 'a pointer' to the hash pointer: + + /* good */ + void add_user(struct my_struct **users, int user_id, char *name) { ... + ... + HASH_ADD_INT( *users, id, s ); + } + +Note that we dereferenced the pointer in the `HASH_ADD` also. + +The reason it's necessary to deal with a pointer to the hash pointer is simple: +the hash macros modify it (in other words, they modify the 'pointer itself' not +just what it points to). + +Find item +~~~~~~~~~ +To look up a structure in a hash, you need its key. Then call `HASH_FIND`. +(Here we use the convenience macro `HASH_FIND_INT` for keys of type `int`). + +.Find a structure using its key +---------------------------------------------------------------------- +struct my_struct *find_user(int user_id) { + struct my_struct *s; + + HASH_FIND_INT( users, &user_id, s ); /* s: output pointer */ + return s; +} +---------------------------------------------------------------------- + +Here, the hash table is `users`, and `&user_id` points to the key (an integer +in this case). Last, `s` is the 'output' variable of `HASH_FIND_INT`. The +final result is that `s` points to the structure with the given key, or +is `NULL` if the key wasn't found in the hash. + +[NOTE] +The middle argument is a 'pointer' to the key. You can't pass a literal key +value to `HASH_FIND`. Instead assign the literal value to a variable, and pass +a pointer to the variable. + + +Delete item +~~~~~~~~~~~ +To delete a structure from a hash, you must have a pointer to it. (If you only +have the key, first do a `HASH_FIND` to get the structure pointer). + +.Delete an item from a hash +---------------------------------------------------------------------- +void delete_user(struct my_struct *user) { + HASH_DEL( users, user); /* user: pointer to deletee */ + free(user); /* optional; it's up to you! */ +} +---------------------------------------------------------------------- + +Here again, `users` is the hash table, and `user` is a pointer to the +structure we want to remove from the hash. + +uthash never frees your structure +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +Deleting a structure just removes it from the hash table-- it doesn't `free` +it. The choice of when to free your structure is entirely up to you; uthash +will never free your structure. + +Delete can change the pointer +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +The hash table pointer (which initially points to the first item added to the +hash) can change in response to `HASH_DEL` (i.e. if you delete the first item +in the hash table). + +Iterative deletion +^^^^^^^^^^^^^^^^^^ +The `HASH_ITER` macro is a deletion-safe iteration construct which expands +to a simple 'for' loop. + +.Delete all items from a hash +---------------------------------------------------------------------- +void delete_all() { + struct my_struct *current_user, *tmp; + + HASH_ITER(hh, users, current_user, tmp) { + HASH_DEL(users,current_user); /* delete; users advances to next */ + free(current_user); /* optional- if you want to free */ + } +} +---------------------------------------------------------------------- + +All-at-once deletion +^^^^^^^^^^^^^^^^^^^^ +If you only want to delete all the items, but not free them or do any +per-element clean up, you can do this more efficiently in a single operation: + + HASH_CLEAR(hh,users); + +Afterward, the list head (here, `users`) will be set to `NULL`. + +Count items +~~~~~~~~~~~ + +The number of items in the hash table can be obtained using `HASH_COUNT`: + +.Count of items in the hash table +---------------------------------------------------------------------- +unsigned int num_users; +num_users = HASH_COUNT(users); +printf("there are %u users\n", num_users); +---------------------------------------------------------------------- + +Incidentally, this works even the list (`users`, here) is `NULL`, in +which case the count is 0. + +Iterating and sorting +~~~~~~~~~~~~~~~~~~~~~ + +You can loop over the items in the hash by starting from the beginning and +following the `hh.next` pointer. + +.Iterating over all the items in a hash +---------------------------------------------------------------------- +void print_users() { + struct my_struct *s; + + for(s=users; s != NULL; s=s->hh.next) { + printf("user id %d: name %s\n", s->id, s->name); + } +} +---------------------------------------------------------------------- + +There is also an `hh.prev` pointer you could use to iterate backwards through +the hash, starting from any known item. + +[[deletesafe]] +Deletion-safe iteration +^^^^^^^^^^^^^^^^^^^^^^^ +In the example above, it would not be safe to delete and free `s` in the body +of the 'for' loop, (because `s` is derefenced each time the loop iterates). +This is easy to rewrite correctly (by copying the `s->hh.next` pointer to a +temporary variable 'before' freeing `s`), but it comes up often enough that a +deletion-safe iteration macro, `HASH_ITER`, is included. It expands to a +`for`-loop header. Here is how it could be used to rewrite the last example: + + struct my_struct *s, *tmp; + + HASH_ITER(hh, users, s, tmp) { + printf("user id %d: name %s\n", s->id, s->name); + /* ... it is safe to delete and free s here */ + } + +.A hash is also a doubly-linked list. +******************************************************************************* +Iterating backward and forward through the items in the hash is possible +because of the `hh.prev` and `hh.next` fields. All the items in the hash can +be reached by repeatedly following these pointers, thus the hash is also a +doubly-linked list. +******************************************************************************* + +If you're using uthash in a C++ program, you need an extra cast on the `for` +iterator, e.g., `s=(struct my_struct*)s->hh.next`. + +Sorted iteration +^^^^^^^^^^^^^^^^ +The items in the hash are, by default, traversed in the order they were added +("insertion order") when you follow the `hh.next` pointer. But you can sort +the items into a new order using `HASH_SORT`. E.g., + + HASH_SORT( users, name_sort ); + +The second argument is a pointer to a comparison function. It must accept two +arguments which are pointers to two items to compare. Its return value should +be less than zero, zero, or greater than zero, if the first item sorts before, +equal to, or after the second item, respectively. (Just like `strcmp`). + +.Sorting the items in the hash +---------------------------------------------------------------------- +int name_sort(struct my_struct *a, struct my_struct *b) { + return strcmp(a->name,b->name); +} + +int id_sort(struct my_struct *a, struct my_struct *b) { + return (a->id - b->id); +} + +void sort_by_name() { + HASH_SORT(users, name_sort); +} + +void sort_by_id() { + HASH_SORT(users, id_sort); +} +---------------------------------------------------------------------- + +When the items in the hash are sorted, the first item may change position. In +the example above, `users` may point to a different structure after calling +`HASH_SORT`. + +A complete example +~~~~~~~~~~~~~~~~~~ + +We'll repeat all the code and embellish it with a `main()` function to form a +working example. + +If this code was placed in a file called `example.c` in the same directory as +`uthash.h`, it could be compiled and run like this: + + cc -o example example.c + ./example + +Follow the prompts to try the program. + +.A complete program +---------------------------------------------------------------------- +#include <stdio.h> /* gets */ +#include <stdlib.h> /* atoi, malloc */ +#include <string.h> /* strcpy */ +#include "uthash.h" + +struct my_struct { + int id; /* key */ + char name[10]; + UT_hash_handle hh; /* makes this structure hashable */ +}; + +struct my_struct *users = NULL; + +void add_user(int user_id, char *name) { + struct my_struct *s; + + s = (struct my_struct*)malloc(sizeof(struct my_struct)); + s->id = user_id; + strcpy(s->name, name); + HASH_ADD_INT( users, id, s ); /* id: name of key field */ +} + +struct my_struct *find_user(int user_id) { + struct my_struct *s; + + HASH_FIND_INT( users, &user_id, s ); /* s: output pointer */ + return s; +} + +void delete_user(struct my_struct *user) { + HASH_DEL( users, user); /* user: pointer to deletee */ + free(user); +} + +void delete_all() { + struct my_struct *current_user, *tmp; + + HASH_ITER(hh, users, current_user, tmp) { + HASH_DEL(users,current_user); /* delete it (users advances to next) */ + free(current_user); /* free it */ + } +} + +void print_users() { + struct my_struct *s; + + for(s=users; s != NULL; s=(struct my_struct*)(s->hh.next)) { + printf("user id %d: name %s\n", s->id, s->name); + } +} + +int name_sort(struct my_struct *a, struct my_struct *b) { + return strcmp(a->name,b->name); +} + +int id_sort(struct my_struct *a, struct my_struct *b) { + return (a->id - b->id); +} + +void sort_by_name() { + HASH_SORT(users, name_sort); +} + +void sort_by_id() { + HASH_SORT(users, id_sort); +} + +int main(int argc, char *argv[]) { + char in[10]; + int id=1, running=1; + struct my_struct *s; + unsigned num_users; + + while (running) { + printf("1. add user\n"); + printf("2. find user\n"); + printf("3. delete user\n"); + printf("4. delete all users\n"); + printf("5. sort items by name\n"); + printf("6. sort items by id\n"); + printf("7. print users\n"); + printf("8. count users\n"); + printf("9. quit\n"); + gets(in); + switch(atoi(in)) { + case 1: + printf("name?\n"); + add_user(id++, gets(in)); + break; + case 2: + printf("id?\n"); + s = find_user(atoi(gets(in))); + printf("user: %s\n", s ? s->name : "unknown"); + break; + case 3: + printf("id?\n"); + s = find_user(atoi(gets(in))); + if (s) delete_user(s); + else printf("id unknown\n"); + break; + case 4: + delete_all(); + break; + case 5: + sort_by_name(); + break; + case 6: + sort_by_id(); + break; + case 7: + print_users(); + break; + case 8: + num_users=HASH_COUNT(users); + printf("there are %u users\n", num_users); + break; + case 9: + running=0; + break; + } + } + + delete_all(); /* free any structures */ + return 0; +} +---------------------------------------------------------------------- + +This program is included in the distribution in `tests/example.c`. You can run +`make example` in that directory to compile it easily. + +Standard key types +------------------ +This section goes into specifics of how to work with different kinds of keys. +You can use nearly any type of key-- integers, strings, pointers, structures, etc. + +[NOTE] +.A note about float +================================================================================ +You can use floating point keys. This comes with the same caveats as with any +program that tests floating point equality. In other words, even the tiniest +difference in two floating point numbers makes them distinct keys. +================================================================================ + +Integer keys +~~~~~~~~~~~~ +The preceding examples demonstrated use of integer keys. To recap, use the +convenience macros `HASH_ADD_INT` and `HASH_FIND_INT` for structures with +integer keys. (The other operations such as `HASH_DELETE` and `HASH_SORT` are +the same for all types of keys). + +String keys +~~~~~~~~~~~ +If your structure has a string key, the operations to use depend on whether your +structure 'points to' the key (`char *`) or the string resides `within` the +structure (`char a[10]`). *This distinction is important*. As we'll see below, +you need to use `HASH_ADD_KEYPTR` when your structure 'points' to a key (that is, +the key itself is 'outside' of the structure); in contrast, use `HASH_ADD_STR` +for a string key that is contained *within* your structure. + +[NOTE] +.char[ ] vs. char* +================================================================================ +The string is 'within' the structure in the first example below-- `name` is a +`char[10]` field. In the second example, the key is 'outside' of the +structure-- `name` is a `char *`. So the first example uses `HASH_ADD_STR` but +the second example uses `HASH_ADD_KEYPTR`. For information on this macro, see +the <<Macro_reference,Macro reference>>. +================================================================================ + +String 'within' structure +^^^^^^^^^^^^^^^^^^^^^^^^^ + +.A string-keyed hash (string within structure) +---------------------------------------------------------------------- +#include <string.h> /* strcpy */ +#include <stdlib.h> /* malloc */ +#include <stdio.h> /* printf */ +#include "uthash.h" + +struct my_struct { + char name[10]; /* key (string is WITHIN the structure) */ + int id; + UT_hash_handle hh; /* makes this structure hashable */ +}; + + +int main(int argc, char *argv[]) { + const char **n, *names[] = { "joe", "bob", "betty", NULL }; + struct my_struct *s, *tmp, *users = NULL; + int i=0; + + for (n = names; *n != NULL; n++) { + s = (struct my_struct*)malloc(sizeof(struct my_struct)); + strncpy(s->name, *n,10); + s->id = i++; + HASH_ADD_STR( users, name, s ); + } + + HASH_FIND_STR( users, "betty", s); + if (s) printf("betty's id is %d\n", s->id); + + /* free the hash table contents */ + HASH_ITER(hh, users, s, tmp) { + HASH_DEL(users, s); + free(s); + } + return 0; +} +---------------------------------------------------------------------- + +This example is included in the distribution in `tests/test15.c`. It prints: + + betty's id is 2 + +String 'pointer' in structure +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +Now, here is the same example but using a `char *` key instead of `char [ ]`: + +.A string-keyed hash (structure points to string) +---------------------------------------------------------------------- +#include <string.h> /* strcpy */ +#include <stdlib.h> /* malloc */ +#include <stdio.h> /* printf */ +#include "uthash.h" + +struct my_struct { + const char *name; /* key */ + int id; + UT_hash_handle hh; /* makes this structure hashable */ +}; + + +int main(int argc, char *argv[]) { + const char **n, *names[] = { "joe", "bob", "betty", NULL }; + struct my_struct *s, *tmp, *users = NULL; + int i=0; + + for (n = names; *n != NULL; n++) { + s = (struct my_struct*)malloc(sizeof(struct my_struct)); + s->name = *n; + s->id = i++; + HASH_ADD_KEYPTR( hh, users, s->name, strlen(s->name), s ); + } + + HASH_FIND_STR( users, "betty", s); + if (s) printf("betty's id is %d\n", s->id); + + /* free the hash table contents */ + HASH_ITER(hh, users, s, tmp) { + HASH_DEL(users, s); + free(s); + } + return 0; +} +---------------------------------------------------------------------- + +This example is included in `tests/test40.c`. + +Pointer keys +~~~~~~~~~~~~ +Your key can be a pointer. To be very clear, this means the 'pointer itself' +can be the key (in contrast, if the thing 'pointed to' is the key, this is a +different use case handled by `HASH_ADD_KEYPTR`). + +Here is a simple example where a structure has a pointer member, called `key`. + +.A pointer key +---------------------------------------------------------------------- +#include <stdio.h> +#include <stdlib.h> +#include "uthash.h" + +typedef struct { + void *key; + int i; + UT_hash_handle hh; +} el_t; + +el_t *hash = NULL; +char *someaddr = NULL; + +int main() { + el_t *d; + el_t *e = (el_t*)malloc(sizeof(el_t)); + if (!e) return -1; + e->key = (void*)someaddr; + e->i = 1; + HASH_ADD_PTR(hash,key,e); + HASH_FIND_PTR(hash, &someaddr, d); + if (d) printf("found\n"); + + /* release memory */ + HASH_DEL(hash,e); + free(e); + return 0; +} +---------------------------------------------------------------------- + +This example is included in `tests/test57.c`. Note that the end of the program +deletes the element out of the hash, (and since no more elements remain in the +hash), uthash releases its internal memory. + +Structure keys +~~~~~~~~~~~~~~ +Your key field can have any data type. To uthash, it is just a sequence of +bytes. Therefore, even a nested structure can be used as a key. We'll use the +general macros `HASH_ADD` and `HASH_FIND` to demonstrate. + +NOTE: Structures contain padding (wasted internal space used to fulfill +alignment requirements for the members of the structure). These padding bytes +'must be zeroed' before adding an item to the hash or looking up an item. +Therefore always zero the whole structure before setting the members of +interest. The example below does this-- see the two calls to `memset`. + +.A key which is a structure +---------------------------------------------------------------------- +#include <stdlib.h> +#include <stdio.h> +#include "uthash.h" + +typedef struct { + char a; + int b; +} record_key_t; + +typedef struct { + record_key_t key; + /* ... other data ... */ + UT_hash_handle hh; +} record_t; + +int main(int argc, char *argv[]) { + record_t l, *p, *r, *tmp, *records = NULL; + + r = (record_t*)malloc( sizeof(record_t) ); + memset(r, 0, sizeof(record_t)); + r->key.a = 'a'; + r->key.b = 1; + HASH_ADD(hh, records, key, sizeof(record_key_t), r); + + memset(&l, 0, sizeof(record_t)); + l.key.a = 'a'; + l.key.b = 1; + HASH_FIND(hh, records, &l.key, sizeof(record_key_t), p); + + if (p) printf("found %c %d\n", p->key.a, p->key.b); + + HASH_ITER(hh, records, p, tmp) { + HASH_DEL(records, p); + free(p); + } + return 0; +} + +---------------------------------------------------------------------- + +This usage is nearly the same as use of a compound key explained below. + +Note that the general macros require the name of the `UT_hash_handle` to be +passed as the first argument (here, this is `hh`). The general macros are +documented in <<Macro_reference,Macro Reference>>. + +Advanced Topics +--------------- + +Compound keys +~~~~~~~~~~~~~ +Your key can even comprise multiple contiguous fields. + +.A multi-field key +---------------------------------------------------------------------- +#include <stdlib.h> /* malloc */ +#include <stddef.h> /* offsetof */ +#include <stdio.h> /* printf */ +#include <string.h> /* memset */ +#include "uthash.h" + +#define UTF32 1 + +typedef struct { + UT_hash_handle hh; + int len; + char encoding; /* these two fields */ + int text[]; /* comprise the key */ +} msg_t; + +typedef struct { + char encoding; + int text[]; +} lookup_key_t; + +int main(int argc, char *argv[]) { + unsigned keylen; + msg_t *msg, *tmp, *msgs = NULL; + lookup_key_t *lookup_key; + + int beijing[] = {0x5317, 0x4eac}; /* UTF-32LE for 北京 */ + + /* allocate and initialize our structure */ + msg = (msg_t*)malloc( sizeof(msg_t) + sizeof(beijing) ); + memset(msg, 0, sizeof(msg_t)+sizeof(beijing)); /* zero fill */ + msg->len = sizeof(beijing); + msg->encoding = UTF32; + memcpy(msg->text, beijing, sizeof(beijing)); + + /* calculate the key length including padding, using formula */ + keylen = offsetof(msg_t, text) /* offset of last key field */ + + sizeof(beijing) /* size of last key field */ + - offsetof(msg_t, encoding); /* offset of first key field */ + + /* add our structure to the hash table */ + HASH_ADD( hh, msgs, encoding, keylen, msg); + + /* look it up to prove that it worked :-) */ + msg=NULL; + + lookup_key = (lookup_key_t*)malloc(sizeof(*lookup_key) + sizeof(beijing)); + memset(lookup_key, 0, sizeof(*lookup_key) + sizeof(beijing)); + lookup_key->encoding = UTF32; + memcpy(lookup_key->text, beijing, sizeof(beijing)); + HASH_FIND( hh, msgs, &lookup_key->encoding, keylen, msg ); + if (msg) printf("found \n"); + free(lookup_key); + + HASH_ITER(hh, msgs, msg, tmp) { + HASH_DEL(msgs, msg); + free(msg); + } + return 0; +} +---------------------------------------------------------------------- + +This example is included in the distribution in `tests/test22.c`. + +If you use multi-field keys, recognize that the compiler pads adjacent fields +(by inserting unused space between them) in order to fulfill the alignment +requirement of each field. For example a structure containing a `char` followed +by an `int` will normally have 3 "wasted" bytes of padding after the char, in +order to make the `int` field start on a multiple-of-4 address (4 is the length +of the int). + +.Calculating the length of a multi-field key: +******************************************************************************* +To determine the key length when using a multi-field key, you must include any +intervening structure padding the compiler adds for alignment purposes. + +An easy way to calculate the key length is to use the `offsetof` macro from +`<stddef.h>`. The formula is: + + key length = offsetof(last_key_field) + + sizeof(last_key_field) + - offsetof(first_key_field) + +In the example above, the `keylen` variable is set using this formula. +******************************************************************************* + +When dealing with a multi-field key, you must zero-fill your structure before +`HASH_ADD`'ing it to a hash table, or using its fields in a `HASH_FIND` key. + +In the previous example, `memset` is used to initialize the structure by +zero-filling it. This zeroes out any padding between the key fields. If we +didn't zero-fill the structure, this padding would contain random values. The +random values would lead to `HASH_FIND` failures; as two "identical" keys will +appear to mismatch if there are any differences within their padding. + +[[multilevel]] +Multi-level hash tables +~~~~~~~~~~~~~~~~~~~~~~~ +A multi-level hash table arises when each element of a hash table contains its +own secondary hash table. There can be any number of levels. In a scripting +language you might see: + + $items{bob}{age}=37 + +The C program below builds this example in uthash: the hash table is called +`items`. It contains one element (`bob`) whose own hash table contains one +element (`age`) with value 37. No special functions are necessary to build +a multi-level hash table. + +While this example represents both levels (`bob` and `age`) using the same +structure, it would also be fine to use two different structure definitions. +It would also be fine if there were three or more levels instead of two. + +.Multi-level hash table +---------------------------------------------------------------------- +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include "uthash.h" + +/* hash of hashes */ +typedef struct item { + char name[10]; + struct item *sub; + int val; + UT_hash_handle hh; +} item_t; + +item_t *items=NULL; + +int main(int argc, char *argvp[]) { + item_t *item1, *item2, *tmp1, *tmp2; + + /* make initial element */ + item_t *i = malloc(sizeof(*i)); + strcpy(i->name, "bob"); + i->sub = NULL; + i->val = 0; + HASH_ADD_STR(items, name, i); + + /* add a sub hash table off this element */ + item_t *s = malloc(sizeof(*s)); + strcpy(s->name, "age"); + s->sub = NULL; + s->val = 37; + HASH_ADD_STR(i->sub, name, s); + + /* iterate over hash elements */ + HASH_ITER(hh, items, item1, tmp1) { + HASH_ITER(hh, item1->sub, item2, tmp2) { + printf("$items{%s}{%s} = %d\n", item1->name, item2->name, item2->val); + } + } + + /* clean up both hash tables */ + HASH_ITER(hh, items, item1, tmp1) { + HASH_ITER(hh, item1->sub, item2, tmp2) { + HASH_DEL(item1->sub, item2); + free(item2); + } + HASH_DEL(items, item1); + free(item1); + } + + return 0; +} +---------------------------------------------------------------------- +The example above is included in `tests/test59.c`. + +[[multihash]] +Items in several hash tables +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +A structure can be added to more than one hash table. A few reasons you might do +this include: + +- each hash table may use an alternative key; +- each hash table may have its own sort order; +- or you might simply use multiple hash tables for grouping purposes. E.g., + you could have users in an `admin_users` and a `users` hash table. + +Your structure needs to have a `UT_hash_handle` field for each hash table to +which it might be added. You can name them anything. E.g., + + UT_hash_handle hh1, hh2; + +Items with alternative keys +~~~~~~~~~~~~~~~~~~~~~~~~~~~ +You might create a hash table keyed on an ID field, and another hash table keyed +on username (if usernames are unique). You can add the same user structure to +both hash tables (without duplication of the structure), allowing lookup of a +user structure by their name or ID. The way to achieve this is to have a +separate `UT_hash_handle` for each hash to which the structure may be added. + +.A structure with two alternative keys +---------------------------------------------------------------------- +struct my_struct { + int id; /* usual key */ + char username[10]; /* alternative key */ + UT_hash_handle hh1; /* handle for first hash table */ + UT_hash_handle hh2; /* handle for second hash table */ +}; +---------------------------------------------------------------------- + +In the example above, the structure can now be added to two separate hash +tables. In one hash, `id` is its key, while in the other hash, `username` is +its key. (There is no requirement that the two hashes have different key +fields. They could both use the same key, such as `id`). + +Notice the structure has two hash handles (`hh1` and `hh2`). In the code +below, notice that each hash handle is used exclusively with a particular hash +table. (`hh1` is always used with the `users_by_id` hash, while `hh2` is +always used with the `users_by_name` hash table). + +.Two keys on a structure +---------------------------------------------------------------------- + struct my_struct *users_by_id = NULL, *users_by_name = NULL, *s; + int i; + char *name; + + s = malloc(sizeof(struct my_struct)); + s->id = 1; + strcpy(s->username, "thanson"); + + /* add the structure to both hash tables */ + HASH_ADD(hh1, users_by_id, id, sizeof(int), s); + HASH_ADD(hh2, users_by_name, username, strlen(s->username), s); + + /* lookup user by ID in the "users_by_id" hash table */ + i=1; + HASH_FIND(hh1, users_by_id, &i, sizeof(int), s); + if (s) printf("found id %d: %s\n", i, s->username); + + /* lookup user by username in the "users_by_name" hash table */ + name = "thanson"; + HASH_FIND(hh2, users_by_name, name, strlen(name), s); + if (s) printf("found user %s: %d\n", name, s->id); +---------------------------------------------------------------------- + + +Several sort orders +~~~~~~~~~~~~~~~~~~~ +It comes as no suprise that two hash tables can have different sort orders, but +this fact can also be used advantageously to sort the 'same items' in several +ways. This is based on the ability to store a structure in several hash tables. + +Extending the previous example, suppose we have many users. We have added each +user structure to the `users_by_id` hash table and the `users_by_name` hash table. +(To reiterate, this is done without the need to have two copies of each structure). +Now we can define two sort functions, then use `HASH_SRT`. + + int sort_by_id(struct my_struct *a, struct my_struct *b) { + if (a->id == b->id) return 0; + return (a->id < b->id) ? -1 : 1; + } + + int sort_by_name(struct my_struct *a, struct my_struct *b) { + return strcmp(a->username,b->username); + } + + HASH_SRT(hh1, users_by_id, sort_by_id); + HASH_SRT(hh2, users_by_name, sort_by_name); + +Now iterating over the items in `users_by_id` will traverse them in id-order +while, naturally, iterating over `users_by_name` will traverse them in +name-order. The items are fully forward-and-backward linked in each order. +So even for one set of users, we might store them in two hash tables to provide +easy iteration in two different sort orders. + +Bloom filter (faster misses) +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Programs that generate a fair miss rate (`HASH_FIND` that result in `NULL`) may +benefit from the built-in Bloom filter support. This is disabled by default, +because programs that generate only hits would incur a slight penalty from it. +Also, programs that do deletes should not use the Bloom filter. While the +program would operate correctly, deletes diminish the benefit of the filter. +To enable the Bloom filter, simply compile with `-DHASH_BLOOM=n` like: + + -DHASH_BLOOM=27 + +where the number can be any value up to 32 which determines the amount of memory +used by the filter, as shown below. Using more memory makes the filter more +accurate and has the potential to speed up your program by making misses bail +out faster. + +.Bloom filter sizes for selected values of n +[width="50%",cols="10m,30",grid="none",options="header"] +|===================================================================== +| n | Bloom filter size (per hash table) +| 16 | 8 kilobytes +| 20 | 128 kilobytes +| 24 | 2 megabytes +| 28 | 32 megabytes +| 32 | 512 megabytes +|===================================================================== + +Bloom filters are only a performance feature; they do not change the results of +hash operations in any way. The only way to gauge whether or not a Bloom filter +is right for your program is to test it. Reasonable values for the size of the +Bloom filter are 16-32 bits. + +Select +~~~~~~ +An experimental 'select' operation is provided that inserts those items from a +source hash that satisfy a given condition into a destination hash. This +insertion is done with somewhat more efficiency than if this were using +`HASH_ADD`, namely because the hash function is not recalculated for keys of the +selected items. This operation does not remove any items from the source hash. +Rather the selected items obtain dual presence in both hashes. The destination +hash may already have items in it; the selected items are added to it. In order +for a structure to be usable with `HASH_SELECT`, it must have two or more hash +handles. (As described <<multihash,here>>, a structure can exist in many +hash tables at the same time; it must have a separate hash handle for each one). + + user_t *users=NULL, *admins=NULL; /* two hash tables */ + + typedef struct { + int id; + UT_hash_handle hh; /* handle for users hash */ + UT_hash_handle ah; /* handle for admins hash */ + } user_t; + +Now suppose we have added some users, and want to select just the administrator +users who have id's less than 1024. + + #define is_admin(x) (((user_t*)x)->id < 1024) + HASH_SELECT(ah,admins,hh,users,is_admin); + +The first two parameters are the 'destination' hash handle and hash table, the +second two parameters are the 'source' hash handle and hash table, and the last +parameter is the 'select condition'. Here we used a macro `is_admin()` but we +could just as well have used a function. + + int is_admin(void *userv) { + user_t *user = (user_t*)userv; + return (user->id < 1024) ? 1 : 0; + } + +If the select condition always evaluates to true, this operation is +essentially a 'merge' of the source hash into the destination hash. Of course, +the source hash remains unchanged under any use of `HASH_SELECT`. It only adds +items to the destination hash selectively. + +The two hash handles must differ. An example of using `HASH_SELECT` is included +in `tests/test36.c`. + + +[[hash_functions]] +Built-in hash functions +~~~~~~~~~~~~~~~~~~~~~~~ +Internally, a hash function transforms a key into a bucket number. You don't +have to take any action to use the default hash function, currently Jenkin's. + +Some programs may benefit from using another of the built-in hash functions. +There is a simple analysis utility included with uthash to help you determine +if another hash function will give you better performance. + +You can use a different hash function by compiling your program with +`-DHASH_FUNCTION=HASH_xyz` where `xyz` is one of the symbolic names listed +below. E.g., + + cc -DHASH_FUNCTION=HASH_BER -o program program.c + +.Built-in hash functions +[width="50%",cols="^5m,20",grid="none",options="header"] +|=============================================================================== +|Symbol | Name +|JEN | Jenkins (default) +|BER | Bernstein +|SAX | Shift-Add-Xor +|OAT | One-at-a-time +|FNV | Fowler/Noll/Vo +|SFH | Paul Hsieh +|MUR | MurmurHash v3 (see note) +|=============================================================================== + +[NOTE] +.MurmurHash +================================================================================ +A special symbol must be defined if you intend to use MurmurHash. To use it, add +`-DHASH_USING_NO_STRICT_ALIASING` to your `CFLAGS`. And, if you are using +the gcc compiler with optimization, add `-fno-strict-aliasing` to your `CFLAGS`. +================================================================================ + +Which hash function is best? +^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +You can easily determine the best hash function for your key domain. To do so, +you'll need to run your program once in a data-collection pass, and then run +the collected data through an included analysis utility. + +First you must build the analysis utility. From the top-level directory, + + cd tests/ + make + +We'll use `test14.c` to demonstrate the data-collection and analysis steps +(here using `sh` syntax to redirect file descriptor 3 to a file): + +.Using keystats +-------------------------------------------------------------------------------- +% cc -DHASH_EMIT_KEYS=3 -I../src -o test14 test14.c +% ./test14 3>test14.keys +% ./keystats test14.keys +fcn ideal% #items #buckets dup% fl add_usec find_usec del-all usec +--- ------ ---------- ---------- ----- -- ---------- ---------- ------------ +SFH 91.6% 1219 256 0% ok 92 131 25 +FNV 90.3% 1219 512 0% ok 107 97 31 +SAX 88.7% 1219 512 0% ok 111 109 32 +OAT 87.2% 1219 256 0% ok 99 138 26 +JEN 86.7% 1219 256 0% ok 87 130 27 +BER 86.2% 1219 256 0% ok 121 129 27 +-------------------------------------------------------------------------------- + +[NOTE] +The number 3 in `-DHASH_EMIT_KEYS=3` is a file descriptor. Any file descriptor +that your program doesn't use for its own purposes can be used instead of 3. +The data-collection mode enabled by `-DHASH_EMIT_KEYS=x` should not be used in +production code. + +Usually, you should just pick the first hash function that is listed. Here, this +is `SFH`. This is the function that provides the most even distribution for +your keys. If several have the same `ideal%`, then choose the fastest one +according to the `find_usec` column. + +keystats column reference +^^^^^^^^^^^^^^^^^^^^^^^^^ +fcn:: + symbolic name of hash function +ideal%:: + The percentage of items in the hash table which can be looked up within an + ideal number of steps. (Further explained below). +#items:: + the number of keys that were read in from the emitted key file +#buckets:: + the number of buckets in the hash after all the keys were added +dup%:: + the percent of duplicate keys encountered in the emitted key file. + Duplicates keys are filtered out to maintain key uniqueness. (Duplicates + are normal. For example, if the application adds an item to a hash, + deletes it, then re-adds it, the key is written twice to the emitted file.) +flags:: + this is either `ok`, or `nx` (noexpand) if the expansion inhibited flag is + set, described in <<expansion,Expansion internals>>. It is not recommended + to use a hash function that has the `noexpand` flag set. +add_usec:: + the clock time in microseconds required to add all the keys to a hash +find_usec:: + the clock time in microseconds required to look up every key in the hash +del-all usec:: + the clock time in microseconds required to delete every item in the hash + +[[ideal]] +ideal% +^^^^^^ + +.What is ideal%? +***************************************************************************** +The 'n' items in a hash are distributed into 'k' buckets. Ideally each bucket +would contain an equal share '(n/k)' of the items. In other words, the maximum +linear position of any item in a bucket chain would be 'n/k' if every bucket is +equally used. If some buckets are overused and others are underused, the +overused buckets will contain items whose linear position surpasses 'n/k'. +Such items are considered non-ideal. + +As you might guess, `ideal%` is the percentage of ideal items in the hash. These +items have favorable linear positions in their bucket chains. As `ideal%` +approaches 100%, the hash table approaches constant-time lookup performance. +***************************************************************************** + +[[hashscan]] +hashscan +~~~~~~~~ +NOTE: This utility is only available on Linux, and on FreeBSD (8.1 and up). + +A utility called `hashscan` is included in the `tests/` directory. It +is built automatically when you run `make` in that directory. This tool +examines a running process and reports on the uthash tables that it finds in +that program's memory. It can also save the keys from each table in a format +that can be fed into `keystats`. + +Here is an example of using `hashscan`. First ensure that it is built: + + cd tests/ + make + +Since `hashscan` needs a running program to inspect, we'll start up a simple +program that makes a hash table and then sleeps as our test subject: + + ./test_sleep & + pid: 9711 + +Now that we have a test program, let's run `hashscan` on it: + + ./hashscan 9711 + Address ideal items buckets mc fl bloom/sat fcn keys saved to + ------------------ ----- -------- -------- -- -- --------- --- ------------- + 0x862e038 81% 10000 4096 11 ok 16 14% JEN + +If we wanted to copy out all its keys for external analysis using `keystats`, +add the `-k` flag: + + ./hashscan -k 9711 + Address ideal items buckets mc fl bloom/sat fcn keys saved to + ------------------ ----- -------- -------- -- -- --------- --- ------------- + 0x862e038 81% 10000 4096 11 ok 16 14% JEN /tmp/9711-0.key + +Now we could run `./keystats /tmp/9711-0.key` to analyze which hash function +has the best characteristics on this set of keys. + +hashscan column reference +^^^^^^^^^^^^^^^^^^^^^^^^^ +Address:: + virtual address of the hash table +ideal:: + The percentage of items in the table which can be looked up within an ideal + number of steps. See <<ideal>> in the `keystats` section. +items:: + number of items in the hash table +buckets:: + number of buckets in the hash table +mc:: + the maximum chain length found in the hash table (uthash usually tries to + keep fewer than 10 items in each bucket, or in some cases a multiple of 10) +fl:: + flags (either `ok`, or `NX` if the expansion-inhibited flag is set) +bloom/sat:: + if the hash table uses a Bloom filter, this is the size (as a power of two) + of the filter (e.g. 16 means the filter is 2^16 bits in size). The second + number is the "saturation" of the bits expressed as a percentage. The lower + the percentage, the more potential benefit to identify cache misses quickly. +fcn:: + symbolic name of hash function +keys saved to:: + file to which keys were saved, if any + +.How hashscan works +***************************************************************************** +When hashscan runs, it attaches itself to the target process, which suspends +the target process momentarily. During this brief suspension, it scans the +target's virtual memory for the signature of a uthash hash table. It then +checks if a valid hash table structure accompanies the signature and reports +what it finds. When it detaches, the target process resumes running normally. +The hashscan is performed "read-only"-- the target process is not modified. +Since hashscan is analyzing a momentary snapshot of a running process, it may +return different results from one run to another. +***************************************************************************** + +[[expansion]] +Expansion internals +~~~~~~~~~~~~~~~~~~~ +Internally this hash manages the number of buckets, with the goal of having +enough buckets so that each one contains only a small number of items. + +.Why does the number of buckets matter? +******************************************************************************** +When looking up an item by its key, this hash scans linearly through the items +in the appropriate bucket. In order for the linear scan to run in constant +time, the number of items in each bucket must be bounded. This is accomplished +by increasing the number of buckets as needed. +******************************************************************************** + +Normal expansion +^^^^^^^^^^^^^^^^ +This hash attempts to keep fewer than 10 items in each bucket. When an item is +added that would cause a bucket to exceed this number, the number of buckets in +the hash is doubled and the items are redistributed into the new buckets. In an +ideal world, each bucket will then contain half as many items as it did before. + +Bucket expansion occurs automatically and invisibly as needed. There is +no need for the application to know when it occurs. + +Per-bucket expansion threshold +++++++++++++++++++++++++++++++ +Normally all buckets share the same threshold (10 items) at which point bucket +expansion is triggered. During the process of bucket expansion, uthash can +adjust this expansion-trigger threshold on a per-bucket basis if it sees that +certain buckets are over-utilized. + +When this threshold is adjusted, it goes from 10 to a multiple of 10 (for that +particular bucket). The multiple is based on how many times greater the actual +chain length is than the ideal length. It is a practical measure to reduce +excess bucket expansion in the case where a hash function over-utilizes a few +buckets but has good overall distribution. However, if the overall distribution +gets too bad, uthash changes tactics. + +Inhibited expansion +^^^^^^^^^^^^^^^^^^^ +You usually don't need to know or worry about this, particularly if you used +the `keystats` utility during development to select a good hash for your keys. + +A hash function may yield an uneven distribution of items across the buckets. +In moderation this is not a problem. Normal bucket expansion takes place as +the chain lengths grow. But when significant imbalance occurs (because the hash +function is not well suited to the key domain), bucket expansion may be +ineffective at reducing the chain lengths. + +Imagine a very bad hash function which always puts every item in bucket 0. No +matter how many times the number of buckets is doubled, the chain length of +bucket 0 stays the same. In a situation like this, the best behavior is to +stop expanding, and accept O(n) lookup performance. This is what uthash +does. It degrades gracefully if the hash function is ill-suited to the keys. + +If two consecutive bucket expansions yield `ideal%` values below 50%, uthash +inhibits expansion for that hash table. Once set, the 'bucket expansion +inhibited' flag remains in effect as long as the hash has items in it. +Inhibited expansion may cause `HASH_FIND` to exhibit worse than constant-time +performance. + +Hooks +~~~~~ +You don't need to use these hooks- they are only here if you want to modify +the behavior of uthash. Hooks can be used to change how uthash allocates +memory, and to run code in response to certain internal events. + +malloc/free +^^^^^^^^^^^ +By default this hash implementation uses `malloc` and `free` to manage memory. +If your application uses its own custom allocator, this hash can use them too. + +.Specifying alternate memory management functions +---------------------------------------------------------------------------- +#include "uthash.h" + +/* undefine the defaults */ +#undef uthash_malloc +#undef uthash_free + +/* re-define, specifying alternate functions */ +#define uthash_malloc(sz) my_malloc(sz) +#define uthash_free(ptr,sz) my_free(ptr) + +... +---------------------------------------------------------------------------- + +Notice that `uthash_free` receives two parameters. The `sz` parameter is for +convenience on embedded platforms that manage their own memory. + +Out of memory +^^^^^^^^^^^^^ +If memory allocation fails (i.e., the malloc function returned `NULL`), the +default behavior is to terminate the process by calling `exit(-1)`. This can +be modified by re-defining the `uthash_fatal` macro. + + #undef uthash_fatal + #define uthash_fatal(msg) my_fatal_function(msg); + +The fatal function should terminate the process or `longjmp` back to a safe +place. Uthash does not support "returning a failure" if memory cannot be +allocated. + +Internal events +^^^^^^^^^^^^^^^ +There is no need for the application to set these hooks or take action in +response to these events. They are mainly for diagnostic purposes. + +These two hooks are "notification" hooks which get executed if uthash is +expanding buckets, or setting the 'bucket expansion inhibited' flag. Normally +both of these hooks are undefined and thus compile away to nothing. + +Expansion ++++++++++ +There is a hook for the bucket expansion event. + +.Bucket expansion hook +---------------------------------------------------------------------------- +#include "uthash.h" + +#undef uthash_expand_fyi +#define uthash_expand_fyi(tbl) printf("expanded to %d buckets\n", tbl->num_buckets) + +... +---------------------------------------------------------------------------- + +Expansion-inhibition +++++++++++++++++++++ +This hook can be defined to code to execute in the event that uthash decides to +set the 'bucket expansion inhibited' flag. + +.Bucket expansion inhibited hook +---------------------------------------------------------------------------- +#include "uthash.h" + +#undef uthash_noexpand_fyi +#define uthash_noexpand_fyi printf("warning: bucket expansion inhibited\n"); + +... +---------------------------------------------------------------------------- + + +Debug mode +~~~~~~~~~~ +If a program that uses this hash is compiled with `-DHASH_DEBUG=1`, a special +internal consistency-checking mode is activated. In this mode, the integrity +of the whole hash is checked following every add or delete operation. This is +for debugging the uthash software only, not for use in production code. + +In the `tests/` directory, running `make debug` will run all the tests in +this mode. + +In this mode, any internal errors in the hash data structure will cause a +message to be printed to `stderr` and the program to exit. + +The `UT_hash_handle` data structure includes `next`, `prev`, `hh_next` and +`hh_prev` fields. The former two fields determine the "application" ordering +(that is, insertion order-- the order the items were added). The latter two +fields determine the "bucket chain" order. These link the `UT_hash_handles` +together in a doubly-linked list that is a bucket chain. + +Checks performed in `-DHASH_DEBUG=1` mode: + +- the hash is walked in its entirety twice: once in 'bucket' order and a + second time in 'application' order +- the total number of items encountered in both walks is checked against the + stored number +- during the walk in 'bucket' order, each item's `hh_prev` pointer is compared + for equality with the last visited item +- during the walk in 'application' order, each item's `prev` pointer is compared + for equality with the last visited item + +.Macro debugging: +******************************************************************************** +Sometimes it's difficult to interpret a compiler warning on a line which +contains a macro call. In the case of uthash, one macro can expand to dozens of +lines. In this case, it is helpful to expand the macros and then recompile. +By doing so, the warning message will refer to the exact line within the macro. + +Here is an example of how to expand the macros and then recompile. This uses the +`test1.c` program in the `tests/` subdirectory. + + gcc -E -I../src test1.c > /tmp/a.c + egrep -v '^#' /tmp/a.c > /tmp/b.c + indent /tmp/b.c + gcc -o /tmp/b /tmp/b.c + +The last line compiles the original program (test1.c) with all macros expanded. +If there was a warning, the referenced line number can be checked in `/tmp/b.c`. +******************************************************************************** + +Thread safety +~~~~~~~~~~~~~ +You can use uthash in a threaded program. But you must do the locking. Use a +read-write lock to protect against concurrent writes. It is ok to have +concurrent readers (since uthash 1.5). + +For example using pthreads you can create an rwlock like this: + + pthread_rwlock_t lock; + if (pthread_rwlock_init(&lock,NULL) != 0) fatal("can't create rwlock"); + +Then, readers must acquire the read lock before doing any `HASH_FIND` calls or +before iterating over the hash elements: + + if (pthread_rwlock_rdlock(&lock) != 0) fatal("can't get rdlock"); + HASH_FIND_INT(elts, &i, e); + pthread_rwlock_unlock(&lock); + +Writers must acquire the exclusive write lock before doing any update. Add, +delete, and sort are all updates that must be locked. + + if (pthread_rwlock_wrlock(&lock) != 0) fatal("can't get wrlock"); + HASH_DEL(elts, e); + pthread_rwlock_unlock(&lock); + +If you prefer, you can use a mutex instead of a read-write lock, but this will +reduce reader concurrency to a single thread at a time. + +An example program using uthash with a read-write lock is included in +`tests/threads/test1.c`. + +[[Macro_reference]] +Macro reference +--------------- + +Convenience macros +~~~~~~~~~~~~~~~~~~ +The convenience macros do the same thing as the generalized macros, but +require fewer arguments. + +In order to use the convenience macros, + +1. the structure's `UT_hash_handle` field must be named `hh`, and +2. for add or find, the key field must be of type `int` or `char[]` or pointer + +.Convenience macros +[width="90%",cols="10m,30m",grid="none",options="header"] +|=============================================================================== +|macro | arguments +|HASH_ADD_INT | (head, keyfield_name, item_ptr) +|HASH_FIND_INT | (head, key_ptr, item_ptr) +|HASH_ADD_STR | (head, keyfield_name, item_ptr) +|HASH_FIND_STR | (head, key_ptr, item_ptr) +|HASH_ADD_PTR | (head, keyfield_name, item_ptr) +|HASH_FIND_PTR | (head, key_ptr, item_ptr) +|HASH_DEL | (head, item_ptr) +|HASH_SORT | (head, cmp) +|HASH_COUNT | (head) +|=============================================================================== + +General macros +~~~~~~~~~~~~~~ + +These macros add, find, delete and sort the items in a hash. You need to +use the general macros if your `UT_hash_handle` is named something other +than `hh`, or if your key's data type isn't `int` or `char[]`. + +.General macros +[width="90%",cols="10m,30m",grid="none",options="header"] +|=============================================================================== +|macro | arguments +|HASH_ADD | (hh_name, head, keyfield_name, key_len, item_ptr) +|HASH_ADD_KEYPTR| (hh_name, head, key_ptr, key_len, item_ptr) +|HASH_FIND | (hh_name, head, key_ptr, key_len, item_ptr) +|HASH_DELETE | (hh_name, head, item_ptr) +|HASH_SRT | (hh_name, head, cmp) +|HASH_CNT | (hh_name, head) +|HASH_CLEAR | (hh_name, head) +|HASH_SELECT | (dst_hh_name, dst_head, src_hh_name, src_head, condition) +|HASH_ITER | (hh_name, head, item_ptr, tmp_item_ptr) +|=============================================================================== + +[NOTE] +`HASH_ADD_KEYPTR` is used when the structure contains a pointer to the +key, rather than the key itself. + + +Argument descriptions +^^^^^^^^^^^^^^^^^^^^^ +hh_name:: + name of the `UT_hash_handle` field in the structure. Conventionally called + `hh`. +head:: + the structure pointer variable which acts as the "head" of the hash. So + named because it initially points to the first item that is added to the hash. +keyfield_name:: + the name of the key field in the structure. (In the case of a multi-field + key, this is the first field of the key). If you're new to macros, it + might seem strange to pass the name of a field as a parameter. See + <<validc,note>>. +key_len:: + the length of the key field in bytes. E.g. for an integer key, this is + `sizeof(int)`, while for a string key it's `strlen(key)`. (For a + multi-field key, see the notes in this guide on calculating key length). +key_ptr:: + for `HASH_FIND`, this is a pointer to the key to look up in the hash + (since it's a pointer, you can't directly pass a literal value here). For + `HASH_ADD_KEYPTR`, this is the address of the key of the item being added. +item_ptr:: + pointer to the structure being added, deleted, or looked up, or the current + pointer during iteration. This is an input parameter for `HASH_ADD` and + `HASH_DELETE` macros, and an output parameter for `HASH_FIND` and + `HASH_ITER`. (When using `HASH_ITER` to iterate, `tmp_item_ptr` + is another variable of the same type as `item_ptr`, used internally). +cmp:: + pointer to comparison function which accepts two arguments (pointers to + items to compare) and returns an int specifying whether the first item + should sort before, equal to, or after the second item (like `strcmp`). +condition:: + a function or macro which accepts a single argument-- a void pointer to a + structure, which needs to be cast to the appropriate structure type. The + function or macro should return (or evaluate to) a non-zero value if the + structure should be "selected" for addition to the destination hash. + +// vim: set tw=80 wm=2 syntax=asciidoc: + diff --git a/apps/systemlib/uthash/doc/utarray.txt b/apps/systemlib/uthash/doc/utarray.txt new file mode 100644 index 000000000..37830f124 --- /dev/null +++ b/apps/systemlib/uthash/doc/utarray.txt @@ -0,0 +1,376 @@ +utarray: dynamic array macros for C +=================================== +Troy D. Hanson <thanson@users.sourceforge.net> +v1.9.5, November 2011 + +include::sflogo.txt[] +include::topnav_utarray.txt[] + +Introduction +------------ +include::toc.txt[] + +A set of general-purpose dynamic array macros for C structures are included with +uthash in `utarray.h`. To use these macros in your own C program, just +copy `utarray.h` into your source directory and use it in your programs. + + #include "utarray.h" + +The dynamic array supports basic operations such as push, pop, and erase on the +array elements. These array elements can be any simple datatype or structure. +The array <<operations,operations>> are based loosely on the C++ STL vector methods. + +Internally the dynamic array contains a contiguous memory region into which +the elements are copied. This buffer is grown as needed using `realloc` to +accomodate all the data that is pushed into it. + +Download +~~~~~~~~ +To download the `utarray.h` header file, follow the link on the +http://uthash.sourceforge.net[uthash home page]. + +BSD licensed +~~~~~~~~~~~~ +This software is made available under the +link:license.html[revised BSD license]. +It is free and open source. + +Platforms +~~~~~~~~~ +The 'utarray' macros have been tested on: + + * Linux, + * Mac OS X, + * Windows, using Visual Studio 2008 and Visual Studio 2010 + +Usage +----- + +Declaration +~~~~~~~~~~~ + +The array itself has the data type `UT_array`, regardless of the type of +elements to be stored in it. It is declared like, + + UT_array *nums; + +New and free +~~~~~~~~~~~~ +The next step is to create the array using `utarray_new`. Later when you're +done with the array, `utarray_free` will free it and all its elements. + +Push, pop, etc +~~~~~~~~~~~~~~ +The central features of the utarray involve putting elements into it, taking +them out, and iterating over them. There are several <<operations,operations>> +to pick from that deal with either single elements or ranges of elements at a +time. In the examples below we will use only the push operation to insert +elements. + +Elements +-------- + +Support for dynamic arrays of integers or strings is especially easy. These are +best shown by example: + +Integers +~~~~~~~~ +This example makes a utarray of integers, pushes 0-9 into it, then prints it. +Lastly it frees it. + +.Integer elements +------------------------------------------------------------------------------- +#include <stdio.h> +#include "utarray.h" + +int main() { + UT_array *nums; + int i, *p; + + utarray_new(nums,&ut_int_icd); + for(i=0; i < 10; i++) utarray_push_back(nums,&i); + + for(p=(int*)utarray_front(nums); + p!=NULL; + p=(int*)utarray_next(nums,p)) { + printf("%d\n",*p); + } + + utarray_free(nums); + + return 0; +} +------------------------------------------------------------------------------- + +The second argument to `utarray_push_back` is always a 'pointer' to the type +(so a literal cannot be used). So for integers, it is an `int*`. + +Strings +~~~~~~~ +In this example we make a utarray of strings, push two strings into it, print +it and free it. + +.String elements +------------------------------------------------------------------------------- +#include <stdio.h> +#include "utarray.h" + +int main() { + UT_array *strs; + char *s, **p; + + utarray_new(strs,&ut_str_icd); + + s = "hello"; utarray_push_back(strs, &s); + s = "world"; utarray_push_back(strs, &s); + p = NULL; + while ( (p=(char**)utarray_next(strs,p))) { + printf("%s\n",*p); + } + + utarray_free(strs); + + return 0; +} +------------------------------------------------------------------------------- + +In this example, since the element is a `char*`, we pass a pointer to it +(`char**`) as the second argument to `utarray_push_back`. Note that "push" makes +a copy of the source string and pushes that copy into the array. + +About UT_icd +~~~~~~~~~~~~ + +Arrays be made of any type of element, not just integers and strings. The +elements can be basic types or structures. Unless you're dealing with integers +and strings (which use pre-defined `ut_int_icd` and `ut_str_icd`), you'll need +to define a `UT_icd` helper structure. This structure contains everything that +utarray needs to initialize, copy or destruct elements. + + typedef struct { + size_t sz; + init_f *init; + ctor_f *copy; + dtor_f *dtor; + } UT_icd; + +The three function pointers `init`, `copy`, and `dtor` have these prototypes: + + typedef void (ctor_f)(void *dst, const void *src); + typedef void (dtor_f)(void *elt); + typedef void (init_f)(void *elt); + +The `sz` is just the size of the element being stored in the array. + +The `init` function will be invoked whenever utarray needs to initialize an +empty element. This only happens as a byproduct of `utarray_resize` or +`utarray_extend_back`. If `init` is `NULL`, it defaults to zero filling the +new element using memset. + +The `copy` function is used whenever an element is copied into the array. +It is invoked during `utarray_push_back`, `utarray_insert`, `utarray_inserta`, +or `utarray_concat`. If `copy` is `NULL`, it defaults to a bitwise copy using +memcpy. + +The `dtor` function is used to clean up an element that is being removed from +the array. It may be invoked due to `utarray_resize`, `utarray_pop_back`, +`utarray_erase`, `utarray_clear`, `utarray_done` or `utarray_free`. If the +elements need no cleanup upon destruction, `dtor` may be `NULL`. + +Scalar types +~~~~~~~~~~~~ + +The next example uses `UT_icd` with all its defaults to make a utarray of +`long` elements. This example pushes two longs, prints them, and frees the +array. + +.long elements +------------------------------------------------------------------------------- +#include <stdio.h> +#include "utarray.h" + +UT_icd long_icd = {sizeof(long), NULL, NULL, NULL }; + +int main() { + UT_array *nums; + long l, *p; + utarray_new(nums, &long_icd); + + l=1; utarray_push_back(nums, &l); + l=2; utarray_push_back(nums, &l); + + p=NULL; + while( (p=(long*)utarray_next(nums,p))) printf("%ld\n", *p); + + utarray_free(nums); + return 0; +} +------------------------------------------------------------------------------- + +Structures +~~~~~~~~~~ + +Structures can be used as utarray elements. If the structure requires no +special effort to initialize, copy or destruct, we can use `UT_icd` with all +its defaults. This example shows a structure that consists of two integers. Here +we push two values, print them and free the array. + +.Structure (simple) +------------------------------------------------------------------------------- +#include <stdio.h> +#include "utarray.h" + +typedef struct { + int a; + int b; +} intpair_t; + +UT_icd intpair_icd = {sizeof(intpair_t), NULL, NULL, NULL}; + +int main() { + + UT_array *pairs; + intpair_t ip, *p; + utarray_new(pairs,&intpair_icd); + + ip.a=1; ip.b=2; utarray_push_back(pairs, &ip); + ip.a=10; ip.b=20; utarray_push_back(pairs, &ip); + + for(p=(intpair_t*)utarray_front(pairs); + p!=NULL; + p=(intpair_t*)utarray_next(pairs,p)) { + printf("%d %d\n", p->a, p->b); + } + + utarray_free(pairs); + return 0; +} +------------------------------------------------------------------------------- + +The real utility of `UT_icd` is apparent when the elements of the utarray are +structures that require special work to initialize, copy or destruct. + +For example, when a structure contains pointers to related memory areas that +need to be copied when the structure is copied (and freed when the structure is +freed), we can use custom `init`, `copy`, and `dtor` members in the `UT_icd`. + +Here we take an example of a structure that contains an integer and a string. +When this element is copied (such as when an element is pushed into the array), +we want to "deep copy" the `s` pointer (so the original element and the new +element point to their own copies of `s`). When an element is destructed, we +want to "deep free" its copy of `s`. Lastly, this example is written to work +even if `s` has the value `NULL`. + +.Structure (complex) +------------------------------------------------------------------------------- +#include <stdio.h> +#include <stdlib.h> +#include "utarray.h" + +typedef struct { + int a; + char *s; +} intchar_t; + +void intchar_copy(void *_dst, const void *_src) { + intchar_t *dst = (intchar_t*)_dst, *src = (intchar_t*)_src; + dst->a = src->a; + dst->s = src->s ? strdup(src->s) : NULL; +} + +void intchar_dtor(void *_elt) { + intchar_t *elt = (intchar_t*)_elt; + if (elt->s) free(elt->s); +} + +UT_icd intchar_icd = {sizeof(intchar_t), NULL, intchar_copy, intchar_dtor}; + +int main() { + UT_array *intchars; + intchar_t ic, *p; + utarray_new(intchars, &intchar_icd); + + ic.a=1; ic.s="hello"; utarray_push_back(intchars, &ic); + ic.a=2; ic.s="world"; utarray_push_back(intchars, &ic); + + p=NULL; + while( (p=(intchar_t*)utarray_next(intchars,p))) { + printf("%d %s\n", p->a, (p->s ? p->s : "null")); + } + + utarray_free(intchars); + return 0; +} + +------------------------------------------------------------------------------- + +[[operations]] +Reference +--------- +This table lists all the utarray operations. These are loosely based on the C++ +vector class. + +Operations +~~~~~~~~~~ + +[width="100%",cols="50<m,40<",grid="none",options="none"] +|=============================================================================== +| utarray_new(UT_array *a, UT_icd *icd)| allocate a new array +| utarray_free(UT_array *a) | free an allocated array +| utarray_init(UT_array *a,UT_icd *icd)| init an array (non-alloc) +| utarray_done(UT_array *a) | dispose of an array (non-allocd) +| utarray_reserve(UT_array *a,int n) | ensure space available for 'n' more elements +| utarray_push_back(UT_array *a,void *p) | push element p onto a +| utarray_pop_back(UT_array *a) | pop last element from a +| utarray_extend_back(UT_array *a) | push empty element onto a +| utarray_len(UT_array *a) | get length of a +| utarray_eltptr(UT_array *a,int j) | get pointer of element from index +| utarray_eltidx(UT_array *a,void *e) | get index of element from pointer +| utarray_insert(UT_array *a,void *p, int j) | insert element p to index j +| utarray_inserta(UT_array *a,UT_array *w, int j) | insert array w into array a at index j +| utarray_resize(UT_array *dst,int num) | extend or shrink array to num elements +| utarray_concat(UT_array *dst,UT_array *src) | copy src to end of dst array +| utarray_erase(UT_array *a,int pos,int len) | remove len elements from a[pos]..a[pos+len-1] +| utarray_clear(UT_array *a) | clear all elements from a, setting its length to zero +| utarray_sort(UT_array *a,cmpfcn *cmp) | sort elements of a using comparison function +| utarray_find(UT_array *a,void *v, cmpfcn *cmp) | find element v in utarray (must be sorted) +| utarray_front(UT_array *a) | get first element of a +| utarray_next(UT_array *a,void *e) | get element of a following e (front if e is NULL) +| utarray_prev(UT_array *a,void *e) | get element of a before e (back if e is NULL) +| utarray_back(UT_array *a) | get last element of a +|=============================================================================== + +Notes +~~~~~ + +1. `utarray_new` and `utarray_free` are used to allocate a new array and free it, + while `utarray_init` and `utarray_done` can be used if the UT_array is already + allocated and just needs to be initialized or have its internal resources + freed. +2. `utarray_reserve` takes the "delta" of elements to reserve (not the total + desired capacity of the array-- this differs from the C++ STL "reserve" notion) +3. `utarray_sort` expects a comparison function having the usual `strcmp` -like + convention where it accepts two elements (a and b) and returns a negative + value if a precedes b, 0 if a and b sort equally, and positive if b precedes a. + This is an example of a comparison function: + + int intsort(const void *a,const void*b) { + int _a = *(int*)a; + int _b = *(int*)b; + return _a - _b; + } + +4. `utarray_find` uses a binary search to locate an element having a certain value + according to the given comparison function. The utarray must be first sorted + using the same comparison function. An example of using `utarray_find` with + a utarray of strings is included in `tests/test61.c`. + +5. A 'pointer' to a particular element (obtained using `utarray_eltptr` or + `utarray_front`, `utarray_next`, `utarray_prev`, `utarray_back`) becomes invalid whenever + another element is inserted into the utarray. This is because the internal + memory management may need to `realloc` the element storage to a new address. + For this reason, it's usually better to refer to an element by its integer + 'index' in code whose duration may include element insertion. + +// vim: set nowrap syntax=asciidoc: + diff --git a/apps/systemlib/uthash/doc/utlist.txt b/apps/systemlib/uthash/doc/utlist.txt new file mode 100644 index 000000000..fbf961c27 --- /dev/null +++ b/apps/systemlib/uthash/doc/utlist.txt @@ -0,0 +1,219 @@ +utlist: linked list macros for C structures +=========================================== +Troy D. Hanson <thanson@users.sourceforge.net> +v1.9.5, November 2011 + +include::sflogo.txt[] +include::topnav_utlist.txt[] + +Introduction +------------ +include::toc.txt[] + +A set of general-purpose 'linked list' macros for C structures are included with +uthash in `utlist.h`. To use these macros in your own C program, just +copy `utlist.h` into your source directory and use it in your programs. + + #include "utlist.h" + +These macros support the basic linked list operations: adding and deleting +elements, sorting them and iterating over them. + +Download +~~~~~~~~ +To download the `utlist.h` header file, follow the link on the +http://uthash.sourceforge.net[uthash home page]. + +BSD licensed +~~~~~~~~~~~~ +This software is made available under the +link:license.html[revised BSD license]. +It is free and open source. + +Platforms +~~~~~~~~~ +The 'utlist' macros have been tested on: + + * Linux, + * Mac OS X, and + * Windows, using Visual Studio 2008, Visual Studio 2010, or Cygwin/MinGW. + +Using utlist +------------ + +Types of lists +~~~~~~~~~~~~~~ +Three types of linked lists are supported: + +- *singly-linked* lists, +- *doubly-linked* lists, and +- *circular, doubly-linked* lists + +Efficiency +^^^^^^^^^^ +For all types of lists, prepending elements and deleting elements are +constant-time operations. Appending to a singly-linked list is an 'O(n)' +operation but appending to a doubly-linked list is constant time using these +macros. (This is because, in the utlist implementation of the doubly-linked +list, the head element's `prev` member points back to the list tail, even when +the list is non-circular). Sorting is an 'O(n log(n))' operation. Iteration +and searching are `O(n)` for all list types. + +List elements +~~~~~~~~~~~~~ +You can use any structure with these macros, as long as the structure +contains a `next` pointer. If you want to make a doubly-linked list, +the element also needs to have a `prev` pointer. + + typedef struct element { + char *name; + struct element *prev; /* needed for a doubly-linked list only */ + struct element *next; /* needed for singly- or doubly-linked lists */ + } element; + +You can name your structure anything. In the example above it is called `element`. +Within a particular list, all elements must be of the same type. + +List head +~~~~~~~~~ +The list head is simply a pointer to your element structure. You can name it +anything. *It must be initialized to `NULL`*. + + element *head = NULL; + +List operations +~~~~~~~~~~~~~~~ +The lists support inserting or deleting elements, sorting the elements and +iterating over them. + +[width="100%",cols="10<m,10<m,10<m",grid="cols",options="header"] +|=============================================================================== +|Singly-linked | Doubly-linked | Circular, doubly-linked +|LL_PREPEND(head,add); | DL_PREPEND(head,add); | CDL_PREPEND(head,add; +|LL_APPEND(head,add); | DL_APPEND(head,add); | +|LL_CONCAT(head1,head2); | DL_CONCAT(head1,head2); | +|LL_DELETE(head,del); | DL_DELETE(head,del); | CDL_DELETE(head,del); +|LL_SORT(head,cmp); | DL_SORT(head,cmp); | CDL_SORT(head,cmp); +|LL_FOREACH(head,elt) {...}| DL_FOREACH(head,elt) {...} | CDL_FOREACH(head,elt) {...} +|LL_FOREACH_SAFE(head,elt,tmp) {...}| DL_FOREACH_SAFE(head,elt,tmp) {...} | CDL_FOREACH_SAFE(head,elt,tmp1,tmp2) {...} +|LL_SEARCH_SCALAR(head,elt,mbr,val);| DL_SEARCH_SCALAR(head,elt,mbr,val); | CDL_SEARCH_SCALAR(head,elt,mbr,val); +|LL_SEARCH(head,elt,like,cmp);| DL_SEARCH(head,elt,like,cmp); | CDL_SEARCH(head,elt,like,cmp); +|=============================================================================== + +'Prepend' means to insert an element in front of the existing list head (if any), +changing the list head to the new element. 'Append' means to add an element at the +end of the list, so it becomes the new tail element. 'Concatenate' takes two +properly constructed lists and appends the second list to the first. (Visual +Studio 2008 does not support `LL_CONCAT` and `DL_CONCAT`, but VS2010 is ok.) + +The 'sort' operation never moves the elements in memory; rather it only adjusts +the list order by altering the `prev` and `next` pointers in each element. Also +the sort operation can change the list head to point to a new element. + +The 'foreach' operation is for easy iteration over the list from the head to the +tail. A usage example is shown below. You can of course just use the `prev` and +`next` pointers directly instead of using the 'foreach' macros. +The 'foreach_safe' operation should be used if you plan to delete any of the list +elements while iterating. + +The 'search' operation is a shortcut for iteration in search of a particular +element. It is not any faster than manually iterating and testing each element. +There are two forms: the "scalar" version searches for an element using a +simple equality test on a given structure member, while the general version takes an +element to which all others in the list will be compared using a `cmp` function. + + +The parameters shown in the table above are explained here: + +head:: + The list head (a pointer to your list element structure). +add:: + A pointer to the list element structure you are adding to the list. +del:: + A pointer to the list element structure you are deleting from the list. +elt:: + A pointer that will be assigned to each list element in succession (see + example) in the case of iteration macros; also, the output pointer from + the search macros. +like:: + An element pointer, having the same type as `elt`, for which the search macro + seeks a match (if found, the match is stored in `elt`). A match is determined + by the given `cmp` function. +cmp:: + pointer to comparison function which accepts two arguments-- these are + pointers to two element structures to be compared. The comparison function + must return an `int` that is negative, zero, or positive, which specifies + whether the first item should sort before, equal to, or after the second item, + respectively. (In other words, the same convention that is used by `strcmp`). + Note that under Visual Studio 2008 you may need to declare the two arguments + as `void *` and then cast them back to their actual types. +tmp:: + A pointer of the same type as `elt`. Used internally. Need not be initialized. +mbr:: + In the scalar search macro, the name of a member within the `elt` structure which + will be tested (using `==`) for equality with the value `val`. +val:: + In the scalar search macro, specifies the value of (of structure member + `field`) of the element being sought. + +Example +~~~~~~~ +This example program reads names from a text file (one name per line), and +appends each name to a doubly-linked list. Then it sorts and prints them. + +.A doubly-linked list +-------------------------------------------------------------------------------- +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include "utlist.h" + +#define BUFLEN 20 + +typedef struct el { + char bname[BUFLEN]; + struct el *next, *prev; +} el; + +int namecmp(el *a, el *b) { + return strcmp(a->bname,b->bname); +} + +el *head = NULL; /* important- initialize to NULL! */ + +int main(int argc, char *argv[]) { + el *name, *elt, *tmp, etmp; + + char linebuf[BUFLEN]; + FILE *file; + + if ( (file = fopen( "test11.dat", "r" )) == NULL ) { + perror("can't open: "); + exit(-1); + } + + while (fgets(linebuf,BUFLEN,file) != NULL) { + if ( (name = (el*)malloc(sizeof(el))) == NULL) exit(-1); + strncpy(name->bname,linebuf,BUFLEN); + DL_APPEND(head, name); + } + DL_SORT(head, namecmp); + DL_FOREACH(head,elt) printf("%s", elt->bname); + + memcpy(&etmp.bname, "WES\n", 5); + DL_SEARCH(head,elt,&etmp,namecmp); + if (elt) printf("found %s\n", elt->bname); + + /* now delete each element, use the safe iterator */ + DL_FOREACH_SAFE(head,elt,tmp) { + DL_DELETE(head,elt); + } + + fclose(file); + + return 0; +} +-------------------------------------------------------------------------------- + +// vim: set nowrap syntax=asciidoc: + diff --git a/apps/systemlib/uthash/doc/utstring.txt b/apps/systemlib/uthash/doc/utstring.txt new file mode 100644 index 000000000..abfdcd107 --- /dev/null +++ b/apps/systemlib/uthash/doc/utstring.txt @@ -0,0 +1,178 @@ +utstring: dynamic string macros for C +===================================== +Troy D. Hanson <thanson@users.sourceforge.net> +v1.9.5, November 2011 + +include::sflogo.txt[] +include::topnav_utstring.txt[] + +Introduction +------------ +include::toc.txt[] + +A set of very basic dynamic string macros for C programs are included with +uthash in `utstring.h`. To use these macros in your own C program, just +copy `utstring.h` into your source directory and use it in your programs. + + #include "utstring.h" + +The dynamic string supports basic operations such as inserting data (including +binary data-- despite its name, utstring is not limited to string content), +concatenation, getting the length and content, and clearing it. The string +<<operations,operations>> are listed below. + +Download +~~~~~~~~ +To download the `utstring.h` header file, follow the link on the +http://uthash.sourceforge.net[uthash home page]. + +BSD licensed +~~~~~~~~~~~~ +This software is made available under the +link:license.html[revised BSD license]. +It is free and open source. + +Platforms +~~~~~~~~~ +The 'utstring' macros have been tested on: + + * Linux, + * Windows, using Visual Studio 2008 and Visual Studio 2010 + +Usage +----- + +Declaration +~~~~~~~~~~~ + +The dynamic string itself has the data type `UT_string`. It is declared like, + + UT_string *str; + +New and free +~~~~~~~~~~~~ +The next step is to create the string using `utstring_new`. Later when you're +done with it, `utstring_free` will free it and all its content. + +Manipulation +~~~~~~~~~~~~ +The `utstring_printf` or `utstring_bincpy` operations insert (copy) data into +the string. To concatenate one utstring to another, use `utstring_concat`. To +clear the content of the string, use `utstring_clear`. The length of the string +is available from `utstring_len`, and its content from `utstring_body`. This +evaluates to a `char*`. The buffer it points to is always null-terminated. +So, it can be used directly with external functions that expect a string. +This automatic null terminator is not counted in the length of the string. + +Samples +~~~~~~~ + +These examples show how to use utstring. + +.Sample 1 +------------------------------------------------------------------------------- +#include <stdio.h> +#include "utstring.h" + +int main() { + UT_string *s; + + utstring_new(s); + utstring_printf(s, "hello world!" ); + printf("%s\n", utstring_body(s)); + + utstring_free(s); + return 0; +} +------------------------------------------------------------------------------- + +The next example is meant to demonstrate that printf 'appends' to the string. +It also shows concatenation. + +.Sample 2 +------------------------------------------------------------------------------- +#include <stdio.h> +#include "utstring.h" + +int main() { + UT_string *s, *t; + + utstring_new(s); + utstring_new(t); + + utstring_printf(s, "hello " ); + utstring_printf(s, "world " ); + + utstring_printf(t, "hi " ); + utstring_printf(t, "there " ); + + utstring_concat(s, t); + printf("length: %u\n", utstring_len(s)); + printf("%s\n", utstring_body(s)); + + utstring_free(s); + utstring_free(t); + return 0; +} +------------------------------------------------------------------------------- + +The last example shows how binary data can be inserted into the string. It also +clears the string and prints new data into it. + +.Sample 3 +------------------------------------------------------------------------------- +#include <stdio.h> +#include "utstring.h" + +int main() { + UT_string *s; + char binary[] = "\xff\xff"; + + utstring_new(s); + utstring_bincpy(s, binary, sizeof(binary)); + printf("length is %u\n", utstring_len(s)); + + utstring_clear(s); + utstring_printf(s,"number %d", 10); + printf("%s\n", utstring_body(s)); + + utstring_free(s); + return 0; +} +------------------------------------------------------------------------------- + +[[operations]] +Reference +--------- +These are the utstring operations. + +Operations +~~~~~~~~~~ + +[width="100%",cols="50<m,40<",grid="none",options="none"] +|=============================================================================== +| utstring_new(s) | allocate a new utstring +| utstring_renew(s) | allocate a new utstring (if s is `NULL`) otherwise clears it +| utstring_free(s) | free an allocated utstring +| utstring_init(s) | init a utstring (non-alloc) +| utstring_done(s) | dispose of a utstring (non-allocd) +| utstring_printf(s,fmt,...) | printf into a utstring (appends) +| utstring_bincpy(s,bin,len) | insert binary data of length len (appends) +| utstring_concat(dst,src) | concatenate src utstring to end of dst utstring +| utstring_clear(s) | clear the content of s (setting its length to 0) +| utstring_len(s) | obtain the length of s as an unsigned integer +| utstring_body(s) | get `char*` to body of s (buffer is always null-terminated) +|=============================================================================== + +Notes +~~~~~ + +1. `utstring_new` and `utstring_free` are used to allocate a new string and free it, + while `utstring_init` and `utstring_done` can be used if the UT_string is already + allocated and just needs to be initialized or have its internal resources + freed. +2. `utstring_printf` is actually a function defined statically in `utstring.h` + rather than a macro. + +// vim: set nowrap syntax=asciidoc: + diff --git a/apps/systemlib/uthash/utarray.h b/apps/systemlib/uthash/utarray.h new file mode 100644 index 000000000..4ffb630bf --- /dev/null +++ b/apps/systemlib/uthash/utarray.h @@ -0,0 +1,233 @@ +/* +Copyright (c) 2008-2012, Troy D. Hanson http://uthash.sourceforge.net +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +/* a dynamic array implementation using macros + * see http://uthash.sourceforge.net/utarray + */ +#ifndef UTARRAY_H +#define UTARRAY_H + +#define UTARRAY_VERSION 1.9.6 + +#ifdef __GNUC__ +#define _UNUSED_ __attribute__ ((__unused__)) +#else +#define _UNUSED_ +#endif + +#include <stddef.h> /* size_t */ +#include <string.h> /* memset, etc */ +#include <stdlib.h> /* exit */ + +#define oom() exit(-1) + +typedef void (ctor_f)(void *dst, const void *src); +typedef void (dtor_f)(void *elt); +typedef void (init_f)(void *elt); +typedef struct { + size_t sz; + init_f *init; + ctor_f *copy; + dtor_f *dtor; +} UT_icd; + +typedef struct { + unsigned i,n;/* i: index of next available slot, n: num slots */ + UT_icd icd; /* initializer, copy and destructor functions */ + char *d; /* n slots of size icd->sz*/ +} UT_array; + +#define utarray_init(a,_icd) do { \ + memset(a,0,sizeof(UT_array)); \ + (a)->icd=*_icd; \ +} while(0) + +#define utarray_done(a) do { \ + if ((a)->n) { \ + if ((a)->icd.dtor) { \ + size_t _ut_i; \ + for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ + (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \ + } \ + } \ + free((a)->d); \ + } \ + (a)->n=0; \ +} while(0) + +#define utarray_new(a,_icd) do { \ + a=(UT_array*)malloc(sizeof(UT_array)); \ + utarray_init(a,_icd); \ +} while(0) + +#define utarray_free(a) do { \ + utarray_done(a); \ + free(a); \ +} while(0) + +#define utarray_reserve(a,by) do { \ + if (((a)->i+by) > ((a)->n)) { \ + while(((a)->i+by) > ((a)->n)) { (a)->n = ((a)->n ? (2*(a)->n) : 8); } \ + if ( ((a)->d=(char*)realloc((a)->d, (a)->n*(a)->icd.sz)) == NULL) oom(); \ + } \ +} while(0) + +#define utarray_push_back(a,p) do { \ + utarray_reserve(a,1); \ + if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,(a)->i++), p); } \ + else { memcpy(_utarray_eltptr(a,(a)->i++), p, (a)->icd.sz); }; \ +} while(0) + +#define utarray_pop_back(a) do { \ + if ((a)->icd.dtor) { (a)->icd.dtor( _utarray_eltptr(a,--((a)->i))); } \ + else { (a)->i--; } \ +} while(0) + +#define utarray_extend_back(a) do { \ + utarray_reserve(a,1); \ + if ((a)->icd.init) { (a)->icd.init(_utarray_eltptr(a,(a)->i)); } \ + else { memset(_utarray_eltptr(a,(a)->i),0,(a)->icd.sz); } \ + (a)->i++; \ +} while(0) + +#define utarray_len(a) ((a)->i) + +#define utarray_eltptr(a,j) (((j) < (a)->i) ? _utarray_eltptr(a,j) : NULL) +#define _utarray_eltptr(a,j) ((char*)((a)->d + ((a)->icd.sz*(j) ))) + +#define utarray_insert(a,p,j) do { \ + utarray_reserve(a,1); \ + if (j > (a)->i) break; \ + if ((j) < (a)->i) { \ + memmove( _utarray_eltptr(a,(j)+1), _utarray_eltptr(a,j), \ + ((a)->i - (j))*((a)->icd.sz)); \ + } \ + if ((a)->icd.copy) { (a)->icd.copy( _utarray_eltptr(a,j), p); } \ + else { memcpy(_utarray_eltptr(a,j), p, (a)->icd.sz); }; \ + (a)->i++; \ +} while(0) + +#define utarray_inserta(a,w,j) do { \ + if (utarray_len(w) == 0) break; \ + if (j > (a)->i) break; \ + utarray_reserve(a,utarray_len(w)); \ + if ((j) < (a)->i) { \ + memmove(_utarray_eltptr(a,(j)+utarray_len(w)), \ + _utarray_eltptr(a,j), \ + ((a)->i - (j))*((a)->icd.sz)); \ + } \ + if ((a)->icd.copy) { \ + size_t _ut_i; \ + for(_ut_i=0;_ut_i<(w)->i;_ut_i++) { \ + (a)->icd.copy(_utarray_eltptr(a,j+_ut_i), _utarray_eltptr(w,_ut_i)); \ + } \ + } else { \ + memcpy(_utarray_eltptr(a,j), _utarray_eltptr(w,0), \ + utarray_len(w)*((a)->icd.sz)); \ + } \ + (a)->i += utarray_len(w); \ +} while(0) + +#define utarray_resize(dst,num) do { \ + size_t _ut_i; \ + if (dst->i > (size_t)(num)) { \ + if ((dst)->icd.dtor) { \ + for(_ut_i=num; _ut_i < dst->i; _ut_i++) { \ + (dst)->icd.dtor(utarray_eltptr(dst,_ut_i)); \ + } \ + } \ + } else if (dst->i < (size_t)(num)) { \ + utarray_reserve(dst,num-dst->i); \ + if ((dst)->icd.init) { \ + for(_ut_i=dst->i; _ut_i < num; _ut_i++) { \ + (dst)->icd.init(utarray_eltptr(dst,_ut_i)); \ + } \ + } else { \ + memset(_utarray_eltptr(dst,dst->i),0,(dst)->icd.sz*(num-dst->i)); \ + } \ + } \ + dst->i = num; \ +} while(0) + +#define utarray_concat(dst,src) do { \ + utarray_inserta((dst),(src),utarray_len(dst)); \ +} while(0) + +#define utarray_erase(a,pos,len) do { \ + if ((a)->icd.dtor) { \ + size_t _ut_i; \ + for(_ut_i=0; _ut_i < len; _ut_i++) { \ + (a)->icd.dtor(utarray_eltptr((a),pos+_ut_i)); \ + } \ + } \ + if ((a)->i > (pos+len)) { \ + memmove( _utarray_eltptr((a),pos), _utarray_eltptr((a),pos+len), \ + (((a)->i)-(pos+len))*((a)->icd.sz)); \ + } \ + (a)->i -= (len); \ +} while(0) + +#define utarray_renew(a,u) do { \ + if (a) utarray_clear(a); \ + else utarray_new((a),(u)); \ +} while(0) + +#define utarray_clear(a) do { \ + if ((a)->i > 0) { \ + if ((a)->icd.dtor) { \ + size_t _ut_i; \ + for(_ut_i=0; _ut_i < (a)->i; _ut_i++) { \ + (a)->icd.dtor(utarray_eltptr(a,_ut_i)); \ + } \ + } \ + (a)->i = 0; \ + } \ +} while(0) + +#define utarray_sort(a,cmp) do { \ + qsort((a)->d, (a)->i, (a)->icd.sz, cmp); \ +} while(0) + +#define utarray_find(a,v,cmp) bsearch((v),(a)->d,(a)->i,(a)->icd.sz,cmp) + +#define utarray_front(a) (((a)->i) ? (_utarray_eltptr(a,0)) : NULL) +#define utarray_next(a,e) (((e)==NULL) ? utarray_front(a) : ((((a)->i) > (utarray_eltidx(a,e)+1)) ? _utarray_eltptr(a,utarray_eltidx(a,e)+1) : NULL)) +#define utarray_prev(a,e) (((e)==NULL) ? utarray_back(a) : ((utarray_eltidx(a,e) > 0) ? _utarray_eltptr(a,utarray_eltidx(a,e)-1) : NULL)) +#define utarray_back(a) (((a)->i) ? (_utarray_eltptr(a,(a)->i-1)) : NULL) +#define utarray_eltidx(a,e) (((char*)(e) >= (char*)((a)->d)) ? (((char*)(e) - (char*)((a)->d))/(a)->icd.sz) : -1) + +/* last we pre-define a few icd for common utarrays of ints and strings */ +static void utarray_str_cpy(void *dst, const void *src) { + char **_src = (char**)src, **_dst = (char**)dst; + *_dst = (*_src == NULL) ? NULL : strdup(*_src); +} +static void utarray_str_dtor(void *elt) { + char **eltc = (char**)elt; + if (*eltc) free(*eltc); +} +static const UT_icd ut_str_icd _UNUSED_ = {sizeof(char*),NULL,utarray_str_cpy,utarray_str_dtor}; +static const UT_icd ut_int_icd _UNUSED_ = {sizeof(int),NULL,NULL,NULL}; +static const UT_icd ut_ptr_icd _UNUSED_ = {sizeof(void*),NULL,NULL,NULL}; + + +#endif /* UTARRAY_H */ diff --git a/apps/systemlib/uthash/uthash.h b/apps/systemlib/uthash/uthash.h new file mode 100644 index 000000000..9f83fc34f --- /dev/null +++ b/apps/systemlib/uthash/uthash.h @@ -0,0 +1,915 @@ +/* +Copyright (c) 2003-2012, Troy D. Hanson http://uthash.sourceforge.net +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef UTHASH_H +#define UTHASH_H + +#include <string.h> /* memcmp,strlen */ +#include <stddef.h> /* ptrdiff_t */ +#include <stdlib.h> /* exit() */ + +/* These macros use decltype or the earlier __typeof GNU extension. + As decltype is only available in newer compilers (VS2010 or gcc 4.3+ + when compiling c++ source) this code uses whatever method is needed + or, for VS2008 where neither is available, uses casting workarounds. */ +#ifdef _MSC_VER /* MS compiler */ +#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ +#define DECLTYPE(x) (decltype(x)) +#else /* VS2008 or older (or VS2010 in C mode) */ +#define NO_DECLTYPE +#define DECLTYPE(x) +#endif +#else /* GNU, Sun and other compilers */ +#define DECLTYPE(x) (__typeof(x)) +#endif + +#ifdef NO_DECLTYPE +#define DECLTYPE_ASSIGN(dst,src) \ +do { \ + char **_da_dst = (char**)(&(dst)); \ + *_da_dst = (char*)(src); \ +} while(0) +#else +#define DECLTYPE_ASSIGN(dst,src) \ +do { \ + (dst) = DECLTYPE(dst)(src); \ +} while(0) +#endif + +/* a number of the hash function use uint32_t which isn't defined on win32 */ +#ifdef _MSC_VER +typedef unsigned int uint32_t; +typedef unsigned char uint8_t; +#else +#include <inttypes.h> /* uint32_t */ +#endif + +#define UTHASH_VERSION 1.9.6 + +#ifndef uthash_fatal +#define uthash_fatal(msg) exit(-1) /* fatal error (out of memory,etc) */ +#endif +#ifndef uthash_malloc +#define uthash_malloc(sz) malloc(sz) /* malloc fcn */ +#endif +#ifndef uthash_free +#define uthash_free(ptr,sz) free(ptr) /* free fcn */ +#endif + +#ifndef uthash_noexpand_fyi +#define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */ +#endif +#ifndef uthash_expand_fyi +#define uthash_expand_fyi(tbl) /* can be defined to log expands */ +#endif + +/* initial number of buckets */ +#define HASH_INITIAL_NUM_BUCKETS 32 /* initial number of buckets */ +#define HASH_INITIAL_NUM_BUCKETS_LOG2 5 /* lg2 of initial number of buckets */ +#define HASH_BKT_CAPACITY_THRESH 10 /* expand when bucket count reaches */ + +/* calculate the element whose hash handle address is hhe */ +#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho))) + +#define HASH_FIND(hh,head,keyptr,keylen,out) \ +do { \ + unsigned _hf_bkt,_hf_hashv; \ + out=NULL; \ + if (head) { \ + HASH_FCN(keyptr,keylen, (head)->hh.tbl->num_buckets, _hf_hashv, _hf_bkt); \ + if (HASH_BLOOM_TEST((head)->hh.tbl, _hf_hashv)) { \ + HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], \ + keyptr,keylen,out); \ + } \ + } \ +} while (0) + +#ifdef HASH_BLOOM +#define HASH_BLOOM_BITLEN (1ULL << HASH_BLOOM) +#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8) + ((HASH_BLOOM_BITLEN%8) ? 1:0) +#define HASH_BLOOM_MAKE(tbl) \ +do { \ + (tbl)->bloom_nbits = HASH_BLOOM; \ + (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \ + if (!((tbl)->bloom_bv)) { uthash_fatal( "out of memory"); } \ + memset((tbl)->bloom_bv, 0, HASH_BLOOM_BYTELEN); \ + (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \ +} while (0) + +#define HASH_BLOOM_FREE(tbl) \ +do { \ + uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ +} while (0) + +#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8] |= (1U << ((idx)%8))) +#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8] & (1U << ((idx)%8))) + +#define HASH_BLOOM_ADD(tbl,hashv) \ + HASH_BLOOM_BITSET((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) + +#define HASH_BLOOM_TEST(tbl,hashv) \ + HASH_BLOOM_BITTEST((tbl)->bloom_bv, (hashv & (uint32_t)((1ULL << (tbl)->bloom_nbits) - 1))) + +#else +#define HASH_BLOOM_MAKE(tbl) +#define HASH_BLOOM_FREE(tbl) +#define HASH_BLOOM_ADD(tbl,hashv) +#define HASH_BLOOM_TEST(tbl,hashv) (1) +#endif + +#define HASH_MAKE_TABLE(hh,head) \ +do { \ + (head)->hh.tbl = (UT_hash_table*)uthash_malloc( \ + sizeof(UT_hash_table)); \ + if (!((head)->hh.tbl)) { uthash_fatal( "out of memory"); } \ + memset((head)->hh.tbl, 0, sizeof(UT_hash_table)); \ + (head)->hh.tbl->tail = &((head)->hh); \ + (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \ + (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \ + (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \ + (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \ + HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ + if (! (head)->hh.tbl->buckets) { uthash_fatal( "out of memory"); } \ + memset((head)->hh.tbl->buckets, 0, \ + HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ + HASH_BLOOM_MAKE((head)->hh.tbl); \ + (head)->hh.tbl->signature = HASH_SIGNATURE; \ +} while(0) + +#define HASH_ADD(hh,head,fieldname,keylen_in,add) \ + HASH_ADD_KEYPTR(hh,head,&((add)->fieldname),keylen_in,add) + +#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ +do { \ + unsigned _ha_bkt; \ + (add)->hh.next = NULL; \ + (add)->hh.key = (char*)keyptr; \ + (add)->hh.keylen = (unsigned)keylen_in; \ + if (!(head)) { \ + head = (add); \ + (head)->hh.prev = NULL; \ + HASH_MAKE_TABLE(hh,head); \ + } else { \ + (head)->hh.tbl->tail->next = (add); \ + (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ + (head)->hh.tbl->tail = &((add)->hh); \ + } \ + (head)->hh.tbl->num_items++; \ + (add)->hh.tbl = (head)->hh.tbl; \ + HASH_FCN(keyptr,keylen_in, (head)->hh.tbl->num_buckets, \ + (add)->hh.hashv, _ha_bkt); \ + HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt],&(add)->hh); \ + HASH_BLOOM_ADD((head)->hh.tbl,(add)->hh.hashv); \ + HASH_EMIT_KEY(hh,head,keyptr,keylen_in); \ + HASH_FSCK(hh,head); \ +} while(0) + +#define HASH_TO_BKT( hashv, num_bkts, bkt ) \ +do { \ + bkt = ((hashv) & ((num_bkts) - 1)); \ +} while(0) + +/* delete "delptr" from the hash table. + * "the usual" patch-up process for the app-order doubly-linked-list. + * The use of _hd_hh_del below deserves special explanation. + * These used to be expressed using (delptr) but that led to a bug + * if someone used the same symbol for the head and deletee, like + * HASH_DELETE(hh,users,users); + * We want that to work, but by changing the head (users) below + * we were forfeiting our ability to further refer to the deletee (users) + * in the patch-up process. Solution: use scratch space to + * copy the deletee pointer, then the latter references are via that + * scratch pointer rather than through the repointed (users) symbol. + */ +#define HASH_DELETE(hh,head,delptr) \ +do { \ + unsigned _hd_bkt; \ + struct UT_hash_handle *_hd_hh_del; \ + if ( ((delptr)->hh.prev == NULL) && ((delptr)->hh.next == NULL) ) { \ + uthash_free((head)->hh.tbl->buckets, \ + (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ + HASH_BLOOM_FREE((head)->hh.tbl); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + head = NULL; \ + } else { \ + _hd_hh_del = &((delptr)->hh); \ + if ((delptr) == ELMT_FROM_HH((head)->hh.tbl,(head)->hh.tbl->tail)) { \ + (head)->hh.tbl->tail = \ + (UT_hash_handle*)((char*)((delptr)->hh.prev) + \ + (head)->hh.tbl->hho); \ + } \ + if ((delptr)->hh.prev) { \ + ((UT_hash_handle*)((char*)((delptr)->hh.prev) + \ + (head)->hh.tbl->hho))->next = (delptr)->hh.next; \ + } else { \ + DECLTYPE_ASSIGN(head,(delptr)->hh.next); \ + } \ + if (_hd_hh_del->next) { \ + ((UT_hash_handle*)((char*)_hd_hh_del->next + \ + (head)->hh.tbl->hho))->prev = \ + _hd_hh_del->prev; \ + } \ + HASH_TO_BKT( _hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ + HASH_DEL_IN_BKT(hh,(head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \ + (head)->hh.tbl->num_items--; \ + } \ + HASH_FSCK(hh,head); \ +} while (0) + + +/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ +#define HASH_FIND_STR(head,findstr,out) \ + HASH_FIND(hh,head,findstr,strlen(findstr),out) +#define HASH_ADD_STR(head,strfield,add) \ + HASH_ADD(hh,head,strfield,strlen(add->strfield),add) +#define HASH_FIND_INT(head,findint,out) \ + HASH_FIND(hh,head,findint,sizeof(int),out) +#define HASH_ADD_INT(head,intfield,add) \ + HASH_ADD(hh,head,intfield,sizeof(int),add) +#define HASH_FIND_PTR(head,findptr,out) \ + HASH_FIND(hh,head,findptr,sizeof(void *),out) +#define HASH_ADD_PTR(head,ptrfield,add) \ + HASH_ADD(hh,head,ptrfield,sizeof(void *),add) +#define HASH_DEL(head,delptr) \ + HASH_DELETE(hh,head,delptr) + +/* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined. + * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined. + */ +#ifdef HASH_DEBUG +#define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0) +#define HASH_FSCK(hh,head) \ +do { \ + unsigned _bkt_i; \ + unsigned _count, _bkt_count; \ + char *_prev; \ + struct UT_hash_handle *_thh; \ + if (head) { \ + _count = 0; \ + for( _bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; _bkt_i++) { \ + _bkt_count = 0; \ + _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \ + _prev = NULL; \ + while (_thh) { \ + if (_prev != (char*)(_thh->hh_prev)) { \ + HASH_OOPS("invalid hh_prev %p, actual %p\n", \ + _thh->hh_prev, _prev ); \ + } \ + _bkt_count++; \ + _prev = (char*)(_thh); \ + _thh = _thh->hh_next; \ + } \ + _count += _bkt_count; \ + if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \ + HASH_OOPS("invalid bucket count %d, actual %d\n", \ + (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \ + } \ + } \ + if (_count != (head)->hh.tbl->num_items) { \ + HASH_OOPS("invalid hh item count %d, actual %d\n", \ + (head)->hh.tbl->num_items, _count ); \ + } \ + /* traverse hh in app order; check next/prev integrity, count */ \ + _count = 0; \ + _prev = NULL; \ + _thh = &(head)->hh; \ + while (_thh) { \ + _count++; \ + if (_prev !=(char*)(_thh->prev)) { \ + HASH_OOPS("invalid prev %p, actual %p\n", \ + _thh->prev, _prev ); \ + } \ + _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \ + _thh = ( _thh->next ? (UT_hash_handle*)((char*)(_thh->next) + \ + (head)->hh.tbl->hho) : NULL ); \ + } \ + if (_count != (head)->hh.tbl->num_items) { \ + HASH_OOPS("invalid app item count %d, actual %d\n", \ + (head)->hh.tbl->num_items, _count ); \ + } \ + } \ +} while (0) +#else +#define HASH_FSCK(hh,head) +#endif + +/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to + * the descriptor to which this macro is defined for tuning the hash function. + * The app can #include <unistd.h> to get the prototype for write(2). */ +#ifdef HASH_EMIT_KEYS +#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \ +do { \ + unsigned _klen = fieldlen; \ + write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \ + write(HASH_EMIT_KEYS, keyptr, fieldlen); \ +} while (0) +#else +#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) +#endif + +/* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */ +#ifdef HASH_FUNCTION +#define HASH_FCN HASH_FUNCTION +#else +#define HASH_FCN HASH_JEN +#endif + +/* The Bernstein hash function, used in Perl prior to v5.6 */ +#define HASH_BER(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _hb_keylen=keylen; \ + char *_hb_key=(char*)(key); \ + (hashv) = 0; \ + while (_hb_keylen--) { (hashv) = ((hashv) * 33) + *_hb_key++; } \ + bkt = (hashv) & (num_bkts-1); \ +} while (0) + + +/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at + * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */ +#define HASH_SAX(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _sx_i; \ + char *_hs_key=(char*)(key); \ + hashv = 0; \ + for(_sx_i=0; _sx_i < keylen; _sx_i++) \ + hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \ + bkt = hashv & (num_bkts-1); \ +} while (0) + +#define HASH_FNV(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _fn_i; \ + char *_hf_key=(char*)(key); \ + hashv = 2166136261UL; \ + for(_fn_i=0; _fn_i < keylen; _fn_i++) \ + hashv = (hashv * 16777619) ^ _hf_key[_fn_i]; \ + bkt = hashv & (num_bkts-1); \ +} while(0) + +#define HASH_OAT(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _ho_i; \ + char *_ho_key=(char*)(key); \ + hashv = 0; \ + for(_ho_i=0; _ho_i < keylen; _ho_i++) { \ + hashv += _ho_key[_ho_i]; \ + hashv += (hashv << 10); \ + hashv ^= (hashv >> 6); \ + } \ + hashv += (hashv << 3); \ + hashv ^= (hashv >> 11); \ + hashv += (hashv << 15); \ + bkt = hashv & (num_bkts-1); \ +} while(0) + +#define HASH_JEN_MIX(a,b,c) \ +do { \ + a -= b; a -= c; a ^= ( c >> 13 ); \ + b -= c; b -= a; b ^= ( a << 8 ); \ + c -= a; c -= b; c ^= ( b >> 13 ); \ + a -= b; a -= c; a ^= ( c >> 12 ); \ + b -= c; b -= a; b ^= ( a << 16 ); \ + c -= a; c -= b; c ^= ( b >> 5 ); \ + a -= b; a -= c; a ^= ( c >> 3 ); \ + b -= c; b -= a; b ^= ( a << 10 ); \ + c -= a; c -= b; c ^= ( b >> 15 ); \ +} while (0) + +#define HASH_JEN(key,keylen,num_bkts,hashv,bkt) \ +do { \ + unsigned _hj_i,_hj_j,_hj_k; \ + char *_hj_key=(char*)(key); \ + hashv = 0xfeedbeef; \ + _hj_i = _hj_j = 0x9e3779b9; \ + _hj_k = (unsigned)keylen; \ + while (_hj_k >= 12) { \ + _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ + + ( (unsigned)_hj_key[2] << 16 ) \ + + ( (unsigned)_hj_key[3] << 24 ) ); \ + _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \ + + ( (unsigned)_hj_key[6] << 16 ) \ + + ( (unsigned)_hj_key[7] << 24 ) ); \ + hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \ + + ( (unsigned)_hj_key[10] << 16 ) \ + + ( (unsigned)_hj_key[11] << 24 ) ); \ + \ + HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ + \ + _hj_key += 12; \ + _hj_k -= 12; \ + } \ + hashv += keylen; \ + switch ( _hj_k ) { \ + case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); \ + case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); \ + case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); \ + case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); \ + case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); \ + case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); \ + case 5: _hj_j += _hj_key[4]; \ + case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); \ + case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); \ + case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); \ + case 1: _hj_i += _hj_key[0]; \ + } \ + HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ + bkt = hashv & (num_bkts-1); \ +} while(0) + +/* The Paul Hsieh hash function */ +#undef get16bits +#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ + || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) +#define get16bits(d) (*((const uint16_t *) (d))) +#endif + +#if !defined (get16bits) +#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ + +(uint32_t)(((const uint8_t *)(d))[0]) ) +#endif +#define HASH_SFH(key,keylen,num_bkts,hashv,bkt) \ +do { \ + char *_sfh_key=(char*)(key); \ + uint32_t _sfh_tmp, _sfh_len = keylen; \ + \ + int _sfh_rem = _sfh_len & 3; \ + _sfh_len >>= 2; \ + hashv = 0xcafebabe; \ + \ + /* Main loop */ \ + for (;_sfh_len > 0; _sfh_len--) { \ + hashv += get16bits (_sfh_key); \ + _sfh_tmp = (get16bits (_sfh_key+2) << 11) ^ hashv; \ + hashv = (hashv << 16) ^ _sfh_tmp; \ + _sfh_key += 2*sizeof (uint16_t); \ + hashv += hashv >> 11; \ + } \ + \ + /* Handle end cases */ \ + switch (_sfh_rem) { \ + case 3: hashv += get16bits (_sfh_key); \ + hashv ^= hashv << 16; \ + hashv ^= _sfh_key[sizeof (uint16_t)] << 18; \ + hashv += hashv >> 11; \ + break; \ + case 2: hashv += get16bits (_sfh_key); \ + hashv ^= hashv << 11; \ + hashv += hashv >> 17; \ + break; \ + case 1: hashv += *_sfh_key; \ + hashv ^= hashv << 10; \ + hashv += hashv >> 1; \ + } \ + \ + /* Force "avalanching" of final 127 bits */ \ + hashv ^= hashv << 3; \ + hashv += hashv >> 5; \ + hashv ^= hashv << 4; \ + hashv += hashv >> 17; \ + hashv ^= hashv << 25; \ + hashv += hashv >> 6; \ + bkt = hashv & (num_bkts-1); \ +} while(0) + +#ifdef HASH_USING_NO_STRICT_ALIASING +/* The MurmurHash exploits some CPU's (x86,x86_64) tolerance for unaligned reads. + * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error. + * MurmurHash uses the faster approach only on CPU's where we know it's safe. + * + * Note the preprocessor built-in defines can be emitted using: + * + * gcc -m64 -dM -E - < /dev/null (on gcc) + * cc -## a.c (where a.c is a simple test file) (Sun Studio) + */ +#if (defined(__i386__) || defined(__x86_64__)) +#define MUR_GETBLOCK(p,i) p[i] +#else /* non intel */ +#define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 0x3) == 0) +#define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 0x3) == 1) +#define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 0x3) == 2) +#define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 0x3) == 3) +#define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL)) +#if (defined(__BIG_ENDIAN__) || defined(SPARC) || defined(__ppc__) || defined(__ppc64__)) +#define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24)) +#define MUR_TWO_TWO(p) ((((*WP(p))&0x0000ffff) <<16) | (((*(WP(p)+1))&0xffff0000) >> 16)) +#define MUR_ONE_THREE(p) ((((*WP(p))&0x000000ff) <<24) | (((*(WP(p)+1))&0xffffff00) >> 8)) +#else /* assume little endian non-intel */ +#define MUR_THREE_ONE(p) ((((*WP(p))&0xffffff00) >> 8) | (((*(WP(p)+1))&0x000000ff) << 24)) +#define MUR_TWO_TWO(p) ((((*WP(p))&0xffff0000) >>16) | (((*(WP(p)+1))&0x0000ffff) << 16)) +#define MUR_ONE_THREE(p) ((((*WP(p))&0xff000000) >>24) | (((*(WP(p)+1))&0x00ffffff) << 8)) +#endif +#define MUR_GETBLOCK(p,i) (MUR_PLUS0_ALIGNED(p) ? ((p)[i]) : \ + (MUR_PLUS1_ALIGNED(p) ? MUR_THREE_ONE(p) : \ + (MUR_PLUS2_ALIGNED(p) ? MUR_TWO_TWO(p) : \ + MUR_ONE_THREE(p)))) +#endif +#define MUR_ROTL32(x,r) (((x) << (r)) | ((x) >> (32 - (r)))) +#define MUR_FMIX(_h) \ +do { \ + _h ^= _h >> 16; \ + _h *= 0x85ebca6b; \ + _h ^= _h >> 13; \ + _h *= 0xc2b2ae35l; \ + _h ^= _h >> 16; \ +} while(0) + +#define HASH_MUR(key,keylen,num_bkts,hashv,bkt) \ +do { \ + const uint8_t *_mur_data = (const uint8_t*)(key); \ + const int _mur_nblocks = (keylen) / 4; \ + uint32_t _mur_h1 = 0xf88D5353; \ + uint32_t _mur_c1 = 0xcc9e2d51; \ + uint32_t _mur_c2 = 0x1b873593; \ + const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+_mur_nblocks*4); \ + int _mur_i; \ + for(_mur_i = -_mur_nblocks; _mur_i; _mur_i++) { \ + uint32_t _mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i); \ + _mur_k1 *= _mur_c1; \ + _mur_k1 = MUR_ROTL32(_mur_k1,15); \ + _mur_k1 *= _mur_c2; \ + \ + _mur_h1 ^= _mur_k1; \ + _mur_h1 = MUR_ROTL32(_mur_h1,13); \ + _mur_h1 = _mur_h1*5+0xe6546b64; \ + } \ + const uint8_t *_mur_tail = (const uint8_t*)(_mur_data + _mur_nblocks*4); \ + uint32_t _mur_k1=0; \ + switch((keylen) & 3) { \ + case 3: _mur_k1 ^= _mur_tail[2] << 16; \ + case 2: _mur_k1 ^= _mur_tail[1] << 8; \ + case 1: _mur_k1 ^= _mur_tail[0]; \ + _mur_k1 *= _mur_c1; \ + _mur_k1 = MUR_ROTL32(_mur_k1,15); \ + _mur_k1 *= _mur_c2; \ + _mur_h1 ^= _mur_k1; \ + } \ + _mur_h1 ^= (keylen); \ + MUR_FMIX(_mur_h1); \ + hashv = _mur_h1; \ + bkt = hashv & (num_bkts-1); \ +} while(0) +#endif /* HASH_USING_NO_STRICT_ALIASING */ + +/* key comparison function; return 0 if keys equal */ +#define HASH_KEYCMP(a,b,len) memcmp(a,b,len) + +/* iterate over items in a known bucket to find desired item */ +#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out) \ +do { \ + if (head.hh_head) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,head.hh_head)); \ + else out=NULL; \ + while (out) { \ + if ((out)->hh.keylen == keylen_in) { \ + if ((HASH_KEYCMP((out)->hh.key,keyptr,keylen_in)) == 0) break; \ + } \ + if ((out)->hh.hh_next) DECLTYPE_ASSIGN(out,ELMT_FROM_HH(tbl,(out)->hh.hh_next)); \ + else out = NULL; \ + } \ +} while(0) + +/* add an item to a bucket */ +#define HASH_ADD_TO_BKT(head,addhh) \ +do { \ + head.count++; \ + (addhh)->hh_next = head.hh_head; \ + (addhh)->hh_prev = NULL; \ + if (head.hh_head) { (head).hh_head->hh_prev = (addhh); } \ + (head).hh_head=addhh; \ + if (head.count >= ((head.expand_mult+1) * HASH_BKT_CAPACITY_THRESH) \ + && (addhh)->tbl->noexpand != 1) { \ + HASH_EXPAND_BUCKETS((addhh)->tbl); \ + } \ +} while(0) + +/* remove an item from a given bucket */ +#define HASH_DEL_IN_BKT(hh,head,hh_del) \ + (head).count--; \ + if ((head).hh_head == hh_del) { \ + (head).hh_head = hh_del->hh_next; \ + } \ + if (hh_del->hh_prev) { \ + hh_del->hh_prev->hh_next = hh_del->hh_next; \ + } \ + if (hh_del->hh_next) { \ + hh_del->hh_next->hh_prev = hh_del->hh_prev; \ + } + +/* Bucket expansion has the effect of doubling the number of buckets + * and redistributing the items into the new buckets. Ideally the + * items will distribute more or less evenly into the new buckets + * (the extent to which this is true is a measure of the quality of + * the hash function as it applies to the key domain). + * + * With the items distributed into more buckets, the chain length + * (item count) in each bucket is reduced. Thus by expanding buckets + * the hash keeps a bound on the chain length. This bounded chain + * length is the essence of how a hash provides constant time lookup. + * + * The calculation of tbl->ideal_chain_maxlen below deserves some + * explanation. First, keep in mind that we're calculating the ideal + * maximum chain length based on the *new* (doubled) bucket count. + * In fractions this is just n/b (n=number of items,b=new num buckets). + * Since the ideal chain length is an integer, we want to calculate + * ceil(n/b). We don't depend on floating point arithmetic in this + * hash, so to calculate ceil(n/b) with integers we could write + * + * ceil(n/b) = (n/b) + ((n%b)?1:0) + * + * and in fact a previous version of this hash did just that. + * But now we have improved things a bit by recognizing that b is + * always a power of two. We keep its base 2 log handy (call it lb), + * so now we can write this with a bit shift and logical AND: + * + * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) + * + */ +#define HASH_EXPAND_BUCKETS(tbl) \ +do { \ + unsigned _he_bkt; \ + unsigned _he_bkt_i; \ + struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ + UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ + _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ + 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ + if (!_he_new_buckets) { uthash_fatal( "out of memory"); } \ + memset(_he_new_buckets, 0, \ + 2 * tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ + tbl->ideal_chain_maxlen = \ + (tbl->num_items >> (tbl->log2_num_buckets+1)) + \ + ((tbl->num_items & ((tbl->num_buckets*2)-1)) ? 1 : 0); \ + tbl->nonideal_items = 0; \ + for(_he_bkt_i = 0; _he_bkt_i < tbl->num_buckets; _he_bkt_i++) \ + { \ + _he_thh = tbl->buckets[ _he_bkt_i ].hh_head; \ + while (_he_thh) { \ + _he_hh_nxt = _he_thh->hh_next; \ + HASH_TO_BKT( _he_thh->hashv, tbl->num_buckets*2, _he_bkt); \ + _he_newbkt = &(_he_new_buckets[ _he_bkt ]); \ + if (++(_he_newbkt->count) > tbl->ideal_chain_maxlen) { \ + tbl->nonideal_items++; \ + _he_newbkt->expand_mult = _he_newbkt->count / \ + tbl->ideal_chain_maxlen; \ + } \ + _he_thh->hh_prev = NULL; \ + _he_thh->hh_next = _he_newbkt->hh_head; \ + if (_he_newbkt->hh_head) _he_newbkt->hh_head->hh_prev = \ + _he_thh; \ + _he_newbkt->hh_head = _he_thh; \ + _he_thh = _he_hh_nxt; \ + } \ + } \ + uthash_free( tbl->buckets, tbl->num_buckets*sizeof(struct UT_hash_bucket) ); \ + tbl->num_buckets *= 2; \ + tbl->log2_num_buckets++; \ + tbl->buckets = _he_new_buckets; \ + tbl->ineff_expands = (tbl->nonideal_items > (tbl->num_items >> 1)) ? \ + (tbl->ineff_expands+1) : 0; \ + if (tbl->ineff_expands > 1) { \ + tbl->noexpand=1; \ + uthash_noexpand_fyi(tbl); \ + } \ + uthash_expand_fyi(tbl); \ +} while(0) + + +/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ +/* Note that HASH_SORT assumes the hash handle name to be hh. + * HASH_SRT was added to allow the hash handle name to be passed in. */ +#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn) +#define HASH_SRT(hh,head,cmpfcn) \ +do { \ + unsigned _hs_i; \ + unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ + struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ + if (head) { \ + _hs_insize = 1; \ + _hs_looping = 1; \ + _hs_list = &((head)->hh); \ + while (_hs_looping) { \ + _hs_p = _hs_list; \ + _hs_list = NULL; \ + _hs_tail = NULL; \ + _hs_nmerges = 0; \ + while (_hs_p) { \ + _hs_nmerges++; \ + _hs_q = _hs_p; \ + _hs_psize = 0; \ + for ( _hs_i = 0; _hs_i < _hs_insize; _hs_i++ ) { \ + _hs_psize++; \ + _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ + ((void*)((char*)(_hs_q->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + if (! (_hs_q) ) break; \ + } \ + _hs_qsize = _hs_insize; \ + while ((_hs_psize > 0) || ((_hs_qsize > 0) && _hs_q )) { \ + if (_hs_psize == 0) { \ + _hs_e = _hs_q; \ + _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ + ((void*)((char*)(_hs_q->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_qsize--; \ + } else if ( (_hs_qsize == 0) || !(_hs_q) ) { \ + _hs_e = _hs_p; \ + _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ + ((void*)((char*)(_hs_p->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_psize--; \ + } else if (( \ + cmpfcn(DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_p)), \ + DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl,_hs_q))) \ + ) <= 0) { \ + _hs_e = _hs_p; \ + _hs_p = (UT_hash_handle*)((_hs_p->next) ? \ + ((void*)((char*)(_hs_p->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_psize--; \ + } else { \ + _hs_e = _hs_q; \ + _hs_q = (UT_hash_handle*)((_hs_q->next) ? \ + ((void*)((char*)(_hs_q->next) + \ + (head)->hh.tbl->hho)) : NULL); \ + _hs_qsize--; \ + } \ + if ( _hs_tail ) { \ + _hs_tail->next = ((_hs_e) ? \ + ELMT_FROM_HH((head)->hh.tbl,_hs_e) : NULL); \ + } else { \ + _hs_list = _hs_e; \ + } \ + _hs_e->prev = ((_hs_tail) ? \ + ELMT_FROM_HH((head)->hh.tbl,_hs_tail) : NULL); \ + _hs_tail = _hs_e; \ + } \ + _hs_p = _hs_q; \ + } \ + _hs_tail->next = NULL; \ + if ( _hs_nmerges <= 1 ) { \ + _hs_looping=0; \ + (head)->hh.tbl->tail = _hs_tail; \ + DECLTYPE_ASSIGN(head,ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ + } \ + _hs_insize *= 2; \ + } \ + HASH_FSCK(hh,head); \ + } \ +} while (0) + +/* This function selects items from one hash into another hash. + * The end result is that the selected items have dual presence + * in both hashes. There is no copy of the items made; rather + * they are added into the new hash through a secondary hash + * hash handle that must be present in the structure. */ +#define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \ +do { \ + unsigned _src_bkt, _dst_bkt; \ + void *_last_elt=NULL, *_elt; \ + UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ + ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ + if (src) { \ + for(_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ + for(_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ + _src_hh; \ + _src_hh = _src_hh->hh_next) { \ + _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ + if (cond(_elt)) { \ + _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \ + _dst_hh->key = _src_hh->key; \ + _dst_hh->keylen = _src_hh->keylen; \ + _dst_hh->hashv = _src_hh->hashv; \ + _dst_hh->prev = _last_elt; \ + _dst_hh->next = NULL; \ + if (_last_elt_hh) { _last_elt_hh->next = _elt; } \ + if (!dst) { \ + DECLTYPE_ASSIGN(dst,_elt); \ + HASH_MAKE_TABLE(hh_dst,dst); \ + } else { \ + _dst_hh->tbl = (dst)->hh_dst.tbl; \ + } \ + HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \ + HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt],_dst_hh); \ + (dst)->hh_dst.tbl->num_items++; \ + _last_elt = _elt; \ + _last_elt_hh = _dst_hh; \ + } \ + } \ + } \ + } \ + HASH_FSCK(hh_dst,dst); \ +} while (0) + +#define HASH_CLEAR(hh,head) \ +do { \ + if (head) { \ + uthash_free((head)->hh.tbl->buckets, \ + (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ + HASH_BLOOM_FREE((head)->hh.tbl); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + (head)=NULL; \ + } \ +} while(0) + +#ifdef NO_DECLTYPE +#define HASH_ITER(hh,head,el,tmp) \ +for((el)=(head), (*(char**)(&(tmp)))=(char*)((head)?(head)->hh.next:NULL); \ + el; (el)=(tmp),(*(char**)(&(tmp)))=(char*)((tmp)?(tmp)->hh.next:NULL)) +#else +#define HASH_ITER(hh,head,el,tmp) \ +for((el)=(head),(tmp)=DECLTYPE(el)((head)?(head)->hh.next:NULL); \ + el; (el)=(tmp),(tmp)=DECLTYPE(el)((tmp)?(tmp)->hh.next:NULL)) +#endif + +/* obtain a count of items in the hash */ +#define HASH_COUNT(head) HASH_CNT(hh,head) +#define HASH_CNT(hh,head) ((head)?((head)->hh.tbl->num_items):0) + +typedef struct UT_hash_bucket { + struct UT_hash_handle *hh_head; + unsigned count; + + /* expand_mult is normally set to 0. In this situation, the max chain length + * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If + * the bucket's chain exceeds this length, bucket expansion is triggered). + * However, setting expand_mult to a non-zero value delays bucket expansion + * (that would be triggered by additions to this particular bucket) + * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH. + * (The multiplier is simply expand_mult+1). The whole idea of this + * multiplier is to reduce bucket expansions, since they are expensive, in + * situations where we know that a particular bucket tends to be overused. + * It is better to let its chain length grow to a longer yet-still-bounded + * value, than to do an O(n) bucket expansion too often. + */ + unsigned expand_mult; + +} UT_hash_bucket; + +/* random signature used only to find hash tables in external analysis */ +#define HASH_SIGNATURE 0xa0111fe1 +#define HASH_BLOOM_SIGNATURE 0xb12220f2 + +typedef struct UT_hash_table { + UT_hash_bucket *buckets; + unsigned num_buckets, log2_num_buckets; + unsigned num_items; + struct UT_hash_handle *tail; /* tail hh in app order, for fast append */ + ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */ + + /* in an ideal situation (all buckets used equally), no bucket would have + * more than ceil(#items/#buckets) items. that's the ideal chain length. */ + unsigned ideal_chain_maxlen; + + /* nonideal_items is the number of items in the hash whose chain position + * exceeds the ideal chain maxlen. these items pay the penalty for an uneven + * hash distribution; reaching them in a chain traversal takes >ideal steps */ + unsigned nonideal_items; + + /* ineffective expands occur when a bucket doubling was performed, but + * afterward, more than half the items in the hash had nonideal chain + * positions. If this happens on two consecutive expansions we inhibit any + * further expansion, as it's not helping; this happens when the hash + * function isn't a good fit for the key domain. When expansion is inhibited + * the hash will still work, albeit no longer in constant time. */ + unsigned ineff_expands, noexpand; + + uint32_t signature; /* used only to find hash tables in external analysis */ +#ifdef HASH_BLOOM + uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ + uint8_t *bloom_bv; + char bloom_nbits; +#endif + +} UT_hash_table; + +typedef struct UT_hash_handle { + struct UT_hash_table *tbl; + void *prev; /* prev element in app order */ + void *next; /* next element in app order */ + struct UT_hash_handle *hh_prev; /* previous hh in bucket order */ + struct UT_hash_handle *hh_next; /* next hh in bucket order */ + void *key; /* ptr to enclosing struct's key */ + unsigned keylen; /* enclosing struct's key len */ + unsigned hashv; /* result of hash-fcn(key) */ +} UT_hash_handle; + +#endif /* UTHASH_H */ diff --git a/apps/systemlib/uthash/utlist.h b/apps/systemlib/uthash/utlist.h new file mode 100644 index 000000000..1578acad2 --- /dev/null +++ b/apps/systemlib/uthash/utlist.h @@ -0,0 +1,522 @@ +/* +Copyright (c) 2007-2012, Troy D. Hanson http://uthash.sourceforge.net +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef UTLIST_H +#define UTLIST_H + +#define UTLIST_VERSION 1.9.6 + +#include <assert.h> + +/* + * This file contains macros to manipulate singly and doubly-linked lists. + * + * 1. LL_ macros: singly-linked lists. + * 2. DL_ macros: doubly-linked lists. + * 3. CDL_ macros: circular doubly-linked lists. + * + * To use singly-linked lists, your structure must have a "next" pointer. + * To use doubly-linked lists, your structure must "prev" and "next" pointers. + * Either way, the pointer to the head of the list must be initialized to NULL. + * + * ----------------.EXAMPLE ------------------------- + * struct item { + * int id; + * struct item *prev, *next; + * } + * + * struct item *list = NULL: + * + * int main() { + * struct item *item; + * ... allocate and populate item ... + * DL_APPEND(list, item); + * } + * -------------------------------------------------- + * + * For doubly-linked lists, the append and delete macros are O(1) + * For singly-linked lists, append and delete are O(n) but prepend is O(1) + * The sort macro is O(n log(n)) for all types of single/double/circular lists. + */ + +/* These macros use decltype or the earlier __typeof GNU extension. + As decltype is only available in newer compilers (VS2010 or gcc 4.3+ + when compiling c++ code), this code uses whatever method is needed + or, for VS2008 where neither is available, uses casting workarounds. */ +#ifdef _MSC_VER /* MS compiler */ +#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ +#define LDECLTYPE(x) decltype(x) +#else /* VS2008 or older (or VS2010 in C mode) */ +#define NO_DECLTYPE +#define LDECLTYPE(x) char* +#endif +#else /* GNU, Sun and other compilers */ +#define LDECLTYPE(x) __typeof(x) +#endif + +/* for VS2008 we use some workarounds to get around the lack of decltype, + * namely, we always reassign our tmp variable to the list head if we need + * to dereference its prev/next pointers, and save/restore the real head.*/ +#ifdef NO_DECLTYPE +#define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } +#define _NEXT(elt,list) ((char*)((list)->next)) +#define _NEXTASGN(elt,list,to) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } +#define _PREV(elt,list) ((char*)((list)->prev)) +#define _PREVASGN(elt,list,to) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); } +#define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } +#define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } +#else +#define _SV(elt,list) +#define _NEXT(elt,list) ((elt)->next) +#define _NEXTASGN(elt,list,to) ((elt)->next)=(to) +#define _PREV(elt,list) ((elt)->prev) +#define _PREVASGN(elt,list,to) ((elt)->prev)=(to) +#define _RS(list) +#define _CASTASGN(a,b) (a)=(b) +#endif + +/****************************************************************************** + * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort * + * Unwieldy variable names used here to avoid shadowing passed-in variables. * + *****************************************************************************/ +#define LL_SORT(list, cmp) \ +do { \ + LDECLTYPE(list) _ls_p; \ + LDECLTYPE(list) _ls_q; \ + LDECLTYPE(list) _ls_e; \ + LDECLTYPE(list) _ls_tail; \ + LDECLTYPE(list) _ls_oldhead; \ + LDECLTYPE(list) _tmp; \ + int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ + if (list) { \ + _ls_insize = 1; \ + _ls_looping = 1; \ + while (_ls_looping) { \ + _CASTASGN(_ls_p,list); \ + _CASTASGN(_ls_oldhead,list); \ + list = NULL; \ + _ls_tail = NULL; \ + _ls_nmerges = 0; \ + while (_ls_p) { \ + _ls_nmerges++; \ + _ls_q = _ls_p; \ + _ls_psize = 0; \ + for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ + _ls_psize++; \ + _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \ + if (!_ls_q) break; \ + } \ + _ls_qsize = _ls_insize; \ + while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ + if (_ls_psize == 0) { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ + } else if (_ls_qsize == 0 || !_ls_q) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ + } else if (cmp(_ls_p,_ls_q) <= 0) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ + } else { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ + } \ + if (_ls_tail) { \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ + } else { \ + _CASTASGN(list,_ls_e); \ + } \ + _ls_tail = _ls_e; \ + } \ + _ls_p = _ls_q; \ + } \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \ + if (_ls_nmerges <= 1) { \ + _ls_looping=0; \ + } \ + _ls_insize *= 2; \ + } \ + } else _tmp=NULL; /* quiet gcc unused variable warning */ \ +} while (0) + +#define DL_SORT(list, cmp) \ +do { \ + LDECLTYPE(list) _ls_p; \ + LDECLTYPE(list) _ls_q; \ + LDECLTYPE(list) _ls_e; \ + LDECLTYPE(list) _ls_tail; \ + LDECLTYPE(list) _ls_oldhead; \ + LDECLTYPE(list) _tmp; \ + int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ + if (list) { \ + _ls_insize = 1; \ + _ls_looping = 1; \ + while (_ls_looping) { \ + _CASTASGN(_ls_p,list); \ + _CASTASGN(_ls_oldhead,list); \ + list = NULL; \ + _ls_tail = NULL; \ + _ls_nmerges = 0; \ + while (_ls_p) { \ + _ls_nmerges++; \ + _ls_q = _ls_p; \ + _ls_psize = 0; \ + for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ + _ls_psize++; \ + _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \ + if (!_ls_q) break; \ + } \ + _ls_qsize = _ls_insize; \ + while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ + if (_ls_psize == 0) { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ + } else if (_ls_qsize == 0 || !_ls_q) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ + } else if (cmp(_ls_p,_ls_q) <= 0) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ + } else { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ + } \ + if (_ls_tail) { \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ + } else { \ + _CASTASGN(list,_ls_e); \ + } \ + _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \ + _ls_tail = _ls_e; \ + } \ + _ls_p = _ls_q; \ + } \ + _CASTASGN(list->prev, _ls_tail); \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \ + if (_ls_nmerges <= 1) { \ + _ls_looping=0; \ + } \ + _ls_insize *= 2; \ + } \ + } else _tmp=NULL; /* quiet gcc unused variable warning */ \ +} while (0) + +#define CDL_SORT(list, cmp) \ +do { \ + LDECLTYPE(list) _ls_p; \ + LDECLTYPE(list) _ls_q; \ + LDECLTYPE(list) _ls_e; \ + LDECLTYPE(list) _ls_tail; \ + LDECLTYPE(list) _ls_oldhead; \ + LDECLTYPE(list) _tmp; \ + LDECLTYPE(list) _tmp2; \ + int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ + if (list) { \ + _ls_insize = 1; \ + _ls_looping = 1; \ + while (_ls_looping) { \ + _CASTASGN(_ls_p,list); \ + _CASTASGN(_ls_oldhead,list); \ + list = NULL; \ + _ls_tail = NULL; \ + _ls_nmerges = 0; \ + while (_ls_p) { \ + _ls_nmerges++; \ + _ls_q = _ls_p; \ + _ls_psize = 0; \ + for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ + _ls_psize++; \ + _SV(_ls_q,list); \ + if (_NEXT(_ls_q,list) == _ls_oldhead) { \ + _ls_q = NULL; \ + } else { \ + _ls_q = _NEXT(_ls_q,list); \ + } \ + _RS(list); \ + if (!_ls_q) break; \ + } \ + _ls_qsize = _ls_insize; \ + while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ + if (_ls_psize == 0) { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ + if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ + } else if (_ls_qsize == 0 || !_ls_q) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ + if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ + } else if (cmp(_ls_p,_ls_q) <= 0) { \ + _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ + if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ + } else { \ + _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ + if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ + } \ + if (_ls_tail) { \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ + } else { \ + _CASTASGN(list,_ls_e); \ + } \ + _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \ + _ls_tail = _ls_e; \ + } \ + _ls_p = _ls_q; \ + } \ + _CASTASGN(list->prev,_ls_tail); \ + _CASTASGN(_tmp2,list); \ + _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp2); _RS(list); \ + if (_ls_nmerges <= 1) { \ + _ls_looping=0; \ + } \ + _ls_insize *= 2; \ + } \ + } else _tmp=NULL; /* quiet gcc unused variable warning */ \ +} while (0) + +/****************************************************************************** + * singly linked list macros (non-circular) * + *****************************************************************************/ +#define LL_PREPEND(head,add) \ +do { \ + (add)->next = head; \ + head = add; \ +} while (0) + +#define LL_CONCAT(head1,head2) \ +do { \ + LDECLTYPE(head1) _tmp; \ + if (head1) { \ + _tmp = head1; \ + while (_tmp->next) { _tmp = _tmp->next; } \ + _tmp->next=(head2); \ + } else { \ + (head1)=(head2); \ + } \ +} while (0) + +#define LL_APPEND(head,add) \ +do { \ + LDECLTYPE(head) _tmp; \ + (add)->next=NULL; \ + if (head) { \ + _tmp = head; \ + while (_tmp->next) { _tmp = _tmp->next; } \ + _tmp->next=(add); \ + } else { \ + (head)=(add); \ + } \ +} while (0) + +#define LL_DELETE(head,del) \ +do { \ + LDECLTYPE(head) _tmp; \ + if ((head) == (del)) { \ + (head)=(head)->next; \ + } else { \ + _tmp = head; \ + while (_tmp->next && (_tmp->next != (del))) { \ + _tmp = _tmp->next; \ + } \ + if (_tmp->next) { \ + _tmp->next = ((del)->next); \ + } \ + } \ +} while (0) + +/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */ +#define LL_APPEND_VS2008(head,add) \ +do { \ + if (head) { \ + (add)->next = head; /* use add->next as a temp variable */ \ + while ((add)->next->next) { (add)->next = (add)->next->next; } \ + (add)->next->next=(add); \ + } else { \ + (head)=(add); \ + } \ + (add)->next=NULL; \ +} while (0) + +#define LL_DELETE_VS2008(head,del) \ +do { \ + if ((head) == (del)) { \ + (head)=(head)->next; \ + } else { \ + char *_tmp = (char*)(head); \ + while ((head)->next && ((head)->next != (del))) { \ + head = (head)->next; \ + } \ + if ((head)->next) { \ + (head)->next = ((del)->next); \ + } \ + { \ + char **_head_alias = (char**)&(head); \ + *_head_alias = _tmp; \ + } \ + } \ +} while (0) +#ifdef NO_DECLTYPE +#undef LL_APPEND +#define LL_APPEND LL_APPEND_VS2008 +#undef LL_DELETE +#define LL_DELETE LL_DELETE_VS2008 +#undef LL_CONCAT /* no LL_CONCAT_VS2008 */ +#undef DL_CONCAT /* no DL_CONCAT_VS2008 */ +#endif +/* end VS2008 replacements */ + +#define LL_FOREACH(head,el) \ + for(el=head;el;el=(el)->next) + +#define LL_FOREACH_SAFE(head,el,tmp) \ + for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) + +#define LL_SEARCH_SCALAR(head,out,field,val) \ +do { \ + LL_FOREACH(head,out) { \ + if ((out)->field == (val)) break; \ + } \ +} while(0) + +#define LL_SEARCH(head,out,elt,cmp) \ +do { \ + LL_FOREACH(head,out) { \ + if ((cmp(out,elt))==0) break; \ + } \ +} while(0) + +/****************************************************************************** + * doubly linked list macros (non-circular) * + *****************************************************************************/ +#define DL_PREPEND(head,add) \ +do { \ + (add)->next = head; \ + if (head) { \ + (add)->prev = (head)->prev; \ + (head)->prev = (add); \ + } else { \ + (add)->prev = (add); \ + } \ + (head) = (add); \ +} while (0) + +#define DL_APPEND(head,add) \ +do { \ + if (head) { \ + (add)->prev = (head)->prev; \ + (head)->prev->next = (add); \ + (head)->prev = (add); \ + (add)->next = NULL; \ + } else { \ + (head)=(add); \ + (head)->prev = (head); \ + (head)->next = NULL; \ + } \ +} while (0) + +#define DL_CONCAT(head1,head2) \ +do { \ + LDECLTYPE(head1) _tmp; \ + if (head2) { \ + if (head1) { \ + _tmp = (head2)->prev; \ + (head2)->prev = (head1)->prev; \ + (head1)->prev->next = (head2); \ + (head1)->prev = _tmp; \ + } else { \ + (head1)=(head2); \ + } \ + } \ +} while (0) + +#define DL_DELETE(head,del) \ +do { \ + assert((del)->prev != NULL); \ + if ((del)->prev == (del)) { \ + (head)=NULL; \ + } else if ((del)==(head)) { \ + (del)->next->prev = (del)->prev; \ + (head) = (del)->next; \ + } else { \ + (del)->prev->next = (del)->next; \ + if ((del)->next) { \ + (del)->next->prev = (del)->prev; \ + } else { \ + (head)->prev = (del)->prev; \ + } \ + } \ +} while (0) + + +#define DL_FOREACH(head,el) \ + for(el=head;el;el=(el)->next) + +/* this version is safe for deleting the elements during iteration */ +#define DL_FOREACH_SAFE(head,el,tmp) \ + for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) + +/* these are identical to their singly-linked list counterparts */ +#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR +#define DL_SEARCH LL_SEARCH + +/****************************************************************************** + * circular doubly linked list macros * + *****************************************************************************/ +#define CDL_PREPEND(head,add) \ +do { \ + if (head) { \ + (add)->prev = (head)->prev; \ + (add)->next = (head); \ + (head)->prev = (add); \ + (add)->prev->next = (add); \ + } else { \ + (add)->prev = (add); \ + (add)->next = (add); \ + } \ +(head)=(add); \ +} while (0) + +#define CDL_DELETE(head,del) \ +do { \ + if ( ((head)==(del)) && ((head)->next == (head))) { \ + (head) = 0L; \ + } else { \ + (del)->next->prev = (del)->prev; \ + (del)->prev->next = (del)->next; \ + if ((del) == (head)) (head)=(del)->next; \ + } \ +} while (0) + +#define CDL_FOREACH(head,el) \ + for(el=head;el;el=((el)->next==head ? 0L : (el)->next)) + +#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ + for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \ + (el) && ((tmp2)=(el)->next, 1); \ + ((el) = (((el)==(tmp1)) ? 0L : (tmp2)))) + +#define CDL_SEARCH_SCALAR(head,out,field,val) \ +do { \ + CDL_FOREACH(head,out) { \ + if ((out)->field == (val)) break; \ + } \ +} while(0) + +#define CDL_SEARCH(head,out,elt,cmp) \ +do { \ + CDL_FOREACH(head,out) { \ + if ((cmp(out,elt))==0) break; \ + } \ +} while(0) + +#endif /* UTLIST_H */ + diff --git a/apps/systemlib/uthash/utstring.h b/apps/systemlib/uthash/utstring.h new file mode 100644 index 000000000..a181ad778 --- /dev/null +++ b/apps/systemlib/uthash/utstring.h @@ -0,0 +1,148 @@ +/* +Copyright (c) 2008-2012, Troy D. Hanson http://uthash.sourceforge.net +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +/* a dynamic string implementation using macros + * see http://uthash.sourceforge.net/utstring + */ +#ifndef UTSTRING_H +#define UTSTRING_H + +#define UTSTRING_VERSION 1.9.6 + +#ifdef __GNUC__ +#define _UNUSED_ __attribute__ ((__unused__)) +#else +#define _UNUSED_ +#endif + +#include <stdlib.h> +#include <string.h> +#include <stdarg.h> +#define oom() exit(-1) + +typedef struct { + char *d; + size_t n; /* allocd size */ + size_t i; /* index of first unused byte */ +} UT_string; + +#define utstring_reserve(s,amt) \ +do { \ + if (((s)->n - (s)->i) < (size_t)(amt)) { \ + (s)->d = (char*)realloc((s)->d, (s)->n + amt); \ + if ((s)->d == NULL) oom(); \ + (s)->n += amt; \ + } \ +} while(0) + +#define utstring_init(s) \ +do { \ + (s)->n = 0; (s)->i = 0; (s)->d = NULL; \ + utstring_reserve(s,100); \ + (s)->d[0] = '\0'; \ +} while(0) + +#define utstring_done(s) \ +do { \ + if ((s)->d != NULL) free((s)->d); \ + (s)->n = 0; \ +} while(0) + +#define utstring_free(s) \ +do { \ + utstring_done(s); \ + free(s); \ +} while(0) + +#define utstring_new(s) \ +do { \ + s = (UT_string*)calloc(sizeof(UT_string),1); \ + if (!s) oom(); \ + utstring_init(s); \ +} while(0) + +#define utstring_renew(s) \ +do { \ + if (s) { \ + utstring_clear(s); \ + } else { \ + utstring_new(s); \ + } \ +} while(0) + +#define utstring_clear(s) \ +do { \ + (s)->i = 0; \ + (s)->d[0] = '\0'; \ +} while(0) + +#define utstring_bincpy(s,b,l) \ +do { \ + utstring_reserve((s),(l)+1); \ + if (l) memcpy(&(s)->d[(s)->i], b, l); \ + (s)->i += l; \ + (s)->d[(s)->i]='\0'; \ +} while(0) + +#define utstring_concat(dst,src) \ +do { \ + utstring_reserve((dst),((src)->i)+1); \ + if ((src)->i) memcpy(&(dst)->d[(dst)->i], (src)->d, (src)->i); \ + (dst)->i += (src)->i; \ + (dst)->d[(dst)->i]='\0'; \ +} while(0) + +#define utstring_len(s) ((unsigned)((s)->i)) + +#define utstring_body(s) ((s)->d) + +_UNUSED_ static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) { + int n; + va_list cp; + while (1) { +#ifdef _WIN32 + cp = ap; +#else + va_copy(cp, ap); +#endif + n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp); + va_end(cp); + + if ((n > -1) && (n < (int)(s->n-s->i))) { + s->i += n; + return; + } + + /* Else try again with more space. */ + if (n > -1) utstring_reserve(s,n+1); /* exact */ + else utstring_reserve(s,(s->n)*2); /* 2x */ + } +} +_UNUSED_ static void utstring_printf(UT_string *s, const char *fmt, ...) { + va_list ap; + va_start(ap,fmt); + utstring_printf_va(s,fmt,ap); + va_end(ap); +} + +#endif /* UTSTRING_H */ diff --git a/nuttx/configs/px4fmu/common/ld.script b/nuttx/configs/px4fmu/common/ld.script index e3ca771b1..b1852b0bd 100644 --- a/nuttx/configs/px4fmu/common/ld.script +++ b/nuttx/configs/px4fmu/common/ld.script @@ -75,8 +75,6 @@ SECTIONS *(.gnu.warning) *(.rodata .rodata.*) *(.gnu.linkonce.t.*) - *(.glue_7) - *(.glue_7t) *(.got) *(.gcc_except_table) *(.gnu.linkonce.r.*) @@ -89,6 +87,15 @@ SECTIONS __errno = get_errno_ptr; } > flash + /* + * Construction data for parameters. + */ + __param ALIGN(4): { + __param_start = ABSOLUTE(.); + KEEP(*(__param*)) + __param_end = ABSOLUTE(.); + } > flash + .ARM.extab : { *(.ARM.extab*) } > flash diff --git a/nuttx/configs/px4fmu/include/board.h b/nuttx/configs/px4fmu/include/board.h index 0db8580ba..29ad52c61 100755 --- a/nuttx/configs/px4fmu/include/board.h +++ b/nuttx/configs/px4fmu/include/board.h @@ -289,7 +289,7 @@ */ #define PX4_I2C_OBDEV_HMC5883 0x1e #define PX4_I2C_OBDEV_MS5611 NOTDEFINED -#define PX4_I2C_OBDEV_EEPROM 0x50 +#define PX4_I2C_OBDEV_EEPROM NOTDEFINED #define PX4_I2C_OBDEV_PX4IO_BL 0x18 #define PX4_I2C_OBDEV_PX4IO 0x19 diff --git a/nuttx/configs/px4fmu/include/drv_eeprom.h b/nuttx/configs/px4fmu/include/drv_eeprom.h index e6801f6c4..57589ed84 100644 --- a/nuttx/configs/px4fmu/include/drv_eeprom.h +++ b/nuttx/configs/px4fmu/include/drv_eeprom.h @@ -31,34 +31,21 @@ * ****************************************************************************/ -/* - * Driver for the ST MS5611 gyroscope - */ - -/* IMPORTANT NOTES: - * - * SPI max. clock frequency: 10 Mhz - * CS has to be high before transfer, - * go low right before transfer and - * go high again right after transfer +/** + * @file drv_eeprom.h * + * Config for the non-MTD EEPROM driver. */ /* IMPORTANT: Adjust this number! */ -#define MAX_EEPROMS 2 +#define MAX_EEPROMS 2 /* FMU onboard */ -#define FMU_ONBOARD_EEPROM_ADDRESS 0x50 -#define FMU_ONBOARD_EEPROM_TOTAL_SIZE_BYTES 16000 -#define FMU_ONBOARD_EEPROM_PAGE_SIZE_BYTES 64 -#define FMU_ONBOARD_EEPROM_PAGE_WRITE_TIME_US 5500 -#define FMU_ONBOARD_EEPROM_BUS_CLOCK 1000000 ///< 1 Mhz max. clock - -#define FMU_BASEBOARD_EEPROM_ADDRESS 0x57 +#define FMU_BASEBOARD_EEPROM_ADDRESS 0x57 #define FMU_BASEBOARD_EEPROM_TOTAL_SIZE_BYTES 128 #define FMU_BASEBOARD_EEPROM_PAGE_SIZE_BYTES 8 #define FMU_BASEBOARD_EEPROM_PAGE_WRITE_TIME_US 3300 -#define FMU_BASEBOARD_EEPROM_BUS_CLOCK 400000 ///< 400 KHz max. clock +#define FMU_BASEBOARD_EEPROM_BUS_CLOCK 400000 ///< 400 KHz max. clock /** * @brief i2c I2C bus struct diff --git a/nuttx/configs/px4fmu/nsh/appconfig b/nuttx/configs/px4fmu/nsh/appconfig index 3323d1998..a99b5f6ad 100644 --- a/nuttx/configs/px4fmu/nsh/appconfig +++ b/nuttx/configs/px4fmu/nsh/appconfig @@ -50,6 +50,7 @@ CONFIGURED_APPS += systemcmds/perf CONFIGURED_APPS += systemcmds/top CONFIGURED_APPS += systemcmds/boardinfo CONFIGURED_APPS += systemcmds/mixer +CONFIGURED_APPS += systemcmds/eeprom #CONFIGURED_APPS += systemcmds/calibration # Tutorial code from diff --git a/nuttx/configs/px4fmu/nsh/defconfig b/nuttx/configs/px4fmu/nsh/defconfig index a87ce7ffa..283edf7dd 100755 --- a/nuttx/configs/px4fmu/nsh/defconfig +++ b/nuttx/configs/px4fmu/nsh/defconfig @@ -247,6 +247,14 @@ CONFIG_STM32_I2CTIMEOUS_START_STOP=700 CONFIG_DEBUG_I2C=n # +# Enable the MTD driver for the onboard I2C EEPROM +# +CONFIG_MTD_AT24XX=y +CONFIG_AT24XX_ADDR=0x50 +CONFIG_AT24XX_SIZE=128 +CONFIG_AT24XX_MTD_BLOCKSIZE=256 + +# # STM32F40xxx specific serial device driver settings # # CONFIG_SERIAL_TERMIOS - Serial driver supports termios.h interfaces (tcsetattr, @@ -699,7 +707,10 @@ CONFIG_FS_FAT=y CONFIG_FAT_LCNAMES=y CONFIG_FAT_LFN=y CONFIG_FAT_MAXFNAME=32 -CONFIG_FS_NXFFS=n +CONFIG_FS_NXFFS=y +CONFIG_NXFFS_MAXNAMLEN=32 +CONFIG_NXFFS_TAILTHRESHOLD=2048 +CONFIG_NXFFS_PREALLOCATED=y CONFIG_FS_ROMFS=y # diff --git a/nuttx/configs/px4fmu/src/up_nsh.c b/nuttx/configs/px4fmu/src/up_nsh.c index d089f2df3..d185bf7f1 100644 --- a/nuttx/configs/px4fmu/src/up_nsh.c +++ b/nuttx/configs/px4fmu/src/up_nsh.c @@ -290,6 +290,7 @@ int nsh_archinitialize(void) FMU_BASEBOARD_EEPROM_PAGE_SIZE_BYTES, FMU_BASEBOARD_EEPROM_PAGE_WRITE_TIME_US, "/dev/baseboard_eeprom", 1); +#if 0 int eeprom_attempts = 0; int eeprom_fail; while (eeprom_attempts < 5) @@ -306,8 +307,10 @@ int nsh_archinitialize(void) if (eeprom_fail) message("[boot] FAILED to attach FMU EEPROM\r\n"); +#endif + /* Report back sensor status */ - if (gyro_fail || mag_fail || baro_fail || eeprom_fail) + if (gyro_fail || mag_fail || baro_fail/* || eeprom_fail*/) { up_ledon(LED_AMBER); } |