C and Splint checking
Posted: 2004-05-31 09:17pm
My hashtable throws craploads errors when checked with Splint, but seems to run cleanly when run with valgrind. Can anyone familiar with splint point out annotations to use and or explain each example thrown up, and check the code for other errors?
Yes, I know about the // comments in C. It's allowed in most compilers, and C99.
Yes, I know about the // comments in C. It's allowed in most compilers, and C99.
Code: Select all
config.h
#define HASHTABLETEST 1
#define HASHTABLEDEBUG 0
Code: Select all
// err.h
#ifndef _ERR_H_
#define _ERR_H_
typedef enum err{SUCCESS = 0,FAILURE = -1, MEMALLOCFAILURE = -3} err;
#endif
Code: Select all
// hashtable.h
#ifndef _HASHTABLE_H_
#define _HASHTABLE_H_
#include <stdbool.h>
#include "err.h"
typedef struct ht_cell_{
char *key;
void *data;
struct ht_cell_ *next;
} ht_cell_;
typedef struct hashTable{
/*@null@*/ht_cell_ **table;
unsigned long range;
} hashTable;
/**
* @brief Sets pointer given as a parameter to a
* new tree structure, and initializes function
* pointers
* @param tr NULL pointer to tree object.
* @return Returns 0 on success, -1 on failure,
* usually caused by out of memory
*/
err newHashTable(hashTable **ht);
err hashTableAdd(hashTable *ht, const char *key, const void *data);
err hashTableRemove(hashTable *ht, const char *key, const bool freeData);
err hashTableGet(const hashTable *ht, const char *key, void **data);
err destroyHashTable(hashTable **ht, const bool freeData);
err hash(const char *key, const unsigned long range, /*@out@*/unsigned long *hashvalue);
#endif
Code: Select all
// hashtable.c
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "config.h"
#include "err.h"
#include "hashtable.h"
#include "input.h"
#ifndef DEBUG
#define INITIALRANGE 10000
#else
#define INITIALRANGE 2
//Maximize hash collisions to test chaining
#endif
err newHashTable(hashTable **ht){
*ht = (hashTable*)calloc(1, sizeof(hashTable));
if((*ht) == NULL){
return MEMALLOCFAILURE;
}
(*ht)->range = INITIALRANGE;
/*
* Not memory leak since freshly calloced, despite what splint likes to
* complain about
*/
(*ht)->table = (ht_cell_**)calloc((size_t)(*ht)->range, sizeof(ht_cell_*));
if((*ht)->table == NULL){
return MEMALLOCFAILURE;
}
return SUCCESS;
}
err destroyHashTable(hashTable **ht, const bool freeData){
unsigned long i;
for(i = 0; i < (*ht)->range; i++){
if((*ht)->table != NULL){
if((*ht)->table[i] != NULL){
ht_cell_ *cl, *next;
cl = (*ht)->table[i];
while(cl != NULL){
next = cl->next;
if(freeData){
free(cl->data);
cl->data = NULL;
}
free(cl);
cl = next;
}
}
}
}
free((*ht)->table);
free(*ht);
*ht = NULL;
return SUCCESS;
}
err hashTableAdd(hashTable *ht, const char *key, const void *data){
unsigned long hashvalue;
if(hash(key, ht->range, &hashvalue) == MEMALLOCFAILURE){
// should never fail
return MEMALLOCFAILURE;
}
if(hashvalue > ht->range){
// out of bounds, should never happen
return FAILURE;
}
// Hash collision
if(ht->table[hashvalue] != NULL){
ht_cell_ *cl;
cl = ht->table[hashvalue];
if(strcmp(cl->key, key) == 0){
return FAILURE;
}
while(cl->next != NULL){
if(strcmp(cl->key, key) == 0){
return FAILURE;
}
cl = cl->next;
}
cl->next = (ht_cell_*)calloc(1,sizeof(ht_cell_));
if(cl->next == NULL){
return MEMALLOCFAILURE;
}else{
// Splint is stupid, not memory leak since
// pointers to NULL
free(cl->next->key);
cl->next->key = (char*)key;
cl->next->data = (void*)data;
cl->next->next = NULL;
return SUCCESS;
// Splint has problems with branching code
}
}else{ // Not hash collision
ht->table[hashvalue] = (ht_cell_*)calloc(1,sizeof(ht_cell_));
if(ht->table[hashvalue] == NULL){
return MEMALLOCFAILURE;
}else{
// Splint is stupid, not memory leak since
// pointers to NULL
ht->table[hashvalue]->key = (char*)key;
ht->table[hashvalue]->data = (void*)data;
ht->table[hashvalue]->next = NULL;
return SUCCESS;
}
}
}
err hashTableRemove(hashTable *ht, const char *key, const bool freeData){
unsigned long hashvalue;
if(hash(key, ht->range, &hashvalue) == MEMALLOCFAILURE){
// should never fail
return MEMALLOCFAILURE;
}
if(hashvalue > ht->range){ // out of bounds, also should never happen
return FAILURE;
}
// Something exists at hash index
if(ht->table[hashvalue] != NULL){
ht_cell_ **cl, *next;
cl = &ht->table[hashvalue];
while(*cl != NULL){
next = (*cl)->next;
if(strcmp((*cl)->key, key) == 0){
if(freeData){
free((*cl)->data);
(*cl)->data = NULL;
}
free(*cl);
*cl = next;
return SUCCESS;
}
cl = &next;
}
return FAILURE;
}
return FAILURE;
}
err hashTableGet(const hashTable *ht, const char *key, void **data){
unsigned long hashvalue;
(void)hash(key, ht->range, &hashvalue);
if(hashvalue > ht->range){ // out of bounds, also should never happen
return FAILURE;
}
if(ht->table[hashvalue] != NULL){
ht_cell_ *cl;
cl = ht->table[hashvalue];
if(strcmp(cl->key, key) != 0) {
while(strcmp(cl->next->key, key) != 0){
if(cl->next == NULL){
*data = NULL;
return FAILURE;
}
cl = cl->next;
}
}
*data = cl->data;
return SUCCESS;
}else{
*data = NULL;
return FAILURE;
}
}
err hash(const char *key, const unsigned long range, unsigned long *hashvalue){
unsigned long hvalue = 0;
unsigned long count = 0;
while((*key) != '\0'){
count += range / 256;
hvalue += (unsigned long)*(key++)*count; // multiply by count
// which is incremented to prevent cases such
// as the hashvalue for dd == ce
if(count >= range){
count = 0;
}
}
hvalue %= range;
*hashvalue = hvalue;
return SUCCESS; // Should never fail, return type err for
// consistency
}
#ifdef HASHTABLETEST
/*@ignore@*/
int main(void){
hashTable *ht;
void *string = NULL;
// Ignore most failures, since unlikely to
// run out of RAM
newHashTable(&ht);
(void)hashTableAdd(ht,"key1", "data1");
(void)hashTableAdd(ht,"key2", "data2");
(void)hashTableAdd(ht,"key3", "data3");
(void)hashTableAdd(ht,"key4", "data4");
(void)hashTableAdd(ht,"key5", "data5");
(void)hashTableAdd(ht,"key6", "data6");
(void)hashTableAdd(ht,"key7", "data7");
(void)hashTableAdd(ht,"key8", "data8");
(void)hashTableAdd(ht,"key9", "data9");
(void)hashTableAdd(ht,"key10", "data10");
(void)hashTableAdd(ht,"key11", "data11");
(void)hashTableAdd(ht,"key12", "data12");
(void)hashTableGet(ht,"key1", &string);
puts((char*)string);
(void)hashTableGet(ht,"key2", &string);
puts((char*)string);
(void)hashTableGet(ht,"key3", &string);
puts((char*)string);
(void)hashTableGet(ht,"key4", &string);
puts((char*)string);
(void)hashTableGet(ht,"key5", &string);
puts((char*)string);
(void)hashTableGet(ht,"key6", &string);
puts((char*)string);
(void)hashTableGet(ht,"key7", &string);
puts((char*)string);
(void)hashTableGet(ht,"key8", &string);
puts((char*)string);
(void)hashTableGet(ht,"key9", &string);
puts((char*)string);
(void)hashTableGet(ht,"key10", &string);
puts((char*)string);
(void)hashTableGet(ht,"key11", &string);
puts((char*)string);
(void)hashTableGet(ht,"key12", &string);
puts((char*)string);
(void)hashTableRemove(ht, "key12", false);
if(hashTableGet(ht,"key12", &string) == SUCCESS){
puts((char*)string);
}
destroyHashTable(&ht, false);
return 0;
}
/*@end@*/
#endif
Code: Select all
#splint.log
hashtable.c: (in function newHashTable)
hashtable.c:22:26: Function returns with possibly null storage derivable from
parameter *ht
A possibly null pointer is reachable from a parameter or global variable that
is not declared using a /*@null@*/ annotation. (Use -nullstate to inhibit
warning)
hashtable.c:20:8: Storage *ht may become null
hashtable.c:30:2: Implicitly only storage *ht->table (type ht_cell_ **) not
released before assignment: (*ht)->table = (ht_cell_ **)calloc((size_t)(*ht)
->range, sizeof(ht_cell_ *))
A memory leak has been detected. Only-qualified storage is not released
before the last reference to it is lost. (Use -mustfreeonly to inhibit
warning)
hashtable.c: (in function destroyHashTable)
hashtable.c:50:11: Only storage cl->key (type char *) derived from released
storage is not released (memory leak): cl
A storage leak due to incomplete deallocation of a structure or deep pointer
is suspected. Unshared storage that is reachable from a reference that is
being deallocated has not yet been deallocated. Splint assumes when an object
is passed as an out only void pointer that the outer object will be
deallocated, but the inner objects will not. (Use -compdestroy to inhibit
warning)
hashtable.c:50:11: Only storage cl->data (type void *) derived from released
storage is not released (memory leak): cl
hashtable.c:57:7: Unqualified storage *ht passed as only param: free (*ht)
Unqualified storage is transferred in an inconsistent way. (Use
-unqualifiedtrans to inhibit warning)
hashtable.c:59:17: Function returns with null storage derivable from parameter
*ht
hashtable.c:58:8: Storage *ht becomes null
hashtable.c: (in function hashTableAdd)
hashtable.c:74:5: Index of possibly null pointer ht->table: ht->table
A possibly null pointer is dereferenced. Value is either the result of a
function which may return null (in which case, code should check it is not
null), or a global, parameter or structure field declared with the null
qualifier. (Use -nullderef to inhibit warning)
hashtable.c:93:4: Implicitly temp storage key assigned to implicitly only:
cl->next->key = (char *)key
Temp storage (associated with a formal parameter) is transferred to a
non-temporary reference. The storage may be released or new aliases created.
(Use -temptrans to inhibit warning)
hashtable.c:94:4: Implicitly only storage cl->next->data (type void *) not
released before assignment: cl->next->data = (void *)data
hashtable.c:94:4: Implicitly temp storage data assigned to implicitly only:
cl->next->data = (void *)data
hashtable.c:95:4: Implicitly only storage cl->next->next (type struct ht_cell_
*) not released before assignment: cl->next->next = NULL
hashtable.c:96:19: Function returns with null storage derivable from parameter
ht->table[]->next->next
hashtable.c:95:21: Storage ht->table[]->next->next becomes null
hashtable.c:102:27: Function returns with possibly null storage derivable from
parameter ht->table[]
hashtable.c:100:26: Storage ht->table[] may become null
hashtable.c:106:4: Implicitly only storage ht->table[]->key (type char *) not
released before assignment: ht->table[hashvalue]->key = (char *)key
hashtable.c:106:4: Implicitly temp storage key assigned to implicitly only:
ht->table[hashvalue]->key = (char *)key
hashtable.c:107:4: Implicitly only storage ht->table[]->data (type void *) not
released before assignment: ht->table[hashvalue]->data = (void *)data
hashtable.c:107:4: Implicitly temp storage data assigned to implicitly only:
ht->table[hashvalue]->data = (void *)data
hashtable.c:108:4: Implicitly only storage ht->table[]->next (type struct
ht_cell_ *) not released before assignment:
ht->table[hashvalue]->next = NULL
hashtable.c:109:19: Function returns with null storage derivable from parameter
ht->table[]->next
hashtable.c:108:33: Storage ht->table[]->next becomes null
hashtable.c: (in function hashTableRemove)
hashtable.c:125:5: Index of possibly null pointer ht->table: ht->table
hashtable.c:135:10: Only storage *cl->key (type char *) derived from released
storage is not released (memory leak): *cl
hashtable.c:135:10: Only storage *cl->data (type void *) derived from released
storage is not released (memory leak): *cl
hashtable.c:137:20: Only storage next not released before return
hashtable.c:135:10: Storage next becomes only
hashtable.c:141:18: Only storage next not released before return
hashtable.c:135:10: Storage next becomes only
hashtable.c: (in function hashTableGet)
hashtable.c:154:5: Index of possibly null pointer ht->table: ht->table
hashtable.c:161:21: Function returns with null storage derivable from parameter
*data
hashtable.c:160:14: Storage *data becomes null
hashtable.c:166:3: Only storage cl->data assigned to unqualified:
*data = cl->data
The only reference to this storage is transferred to another reference (e.g.,
by returning it) that does not have the only annotation. This may lead to a
memory leak, since the new reference is not necessarily released. (Use
-onlytrans to inhibit warning)
hashtable.c:170:18: Function returns with null storage derivable from parameter
*data
hashtable.c:169:11: Storage *data becomes null
hashtable.h:28:5: Function exported but not used outside hashtable:
newHashTable
A declaration is exported, but not used outside this module. Declaration can
use static qualifier. (Use -exportlocal to inhibit warning)
hashtable.c:36:1: Definition of newHashTable
hashtable.h:29:5: Function exported but not used outside hashtable:
hashTableAdd
hashtable.c:112:1: Definition of hashTableAdd
hashtable.h:30:5: Function exported but not used outside hashtable:
hashTableRemove
hashtable.c:144:1: Definition of hashTableRemove
hashtable.h:31:5: Function exported but not used outside hashtable:
hashTableGet
hashtable.c:172:1: Definition of hashTableGet
hashtable.h:32:5: Function exported but not used outside hashtable:
destroyHashTable
hashtable.c:60:1: Definition of destroyHashTable
hashtable.h:34:5: Function exported but not used outside hashtable: hash
hashtable.c:191:1: Definition of hash