条件跳转或移动取决于未初始化的值 ADT 设置

Question

我一直在尝试使用哈希表的开放寻址和延迟删除来实现 Set ADT，但是，我在调整 Set 大小时遇到了问题。 我可以插入最多占 Set 总容量 75% 的元素，但是当我调整它的大小并尝试再次访问所有元素（所有插入的元素都是唯一的）时，我收到此错误：

==294546== Conditional jump or move depends on uninitialised value(s)
==294546==    at 0x48D6AD6: __vfprintf_internal (vfprintf-internal.c:1516)
==294546==    by 0x48C079E: printf (printf.c:33)
==294546==    by 0x10FD3D: showDisciplineStatistics (simple.c:149)
==294546==    by 0x109454: main (main.c:37)
==294546==  Uninitialised value was created by a stack allocation
==294546==    at 0x10FC00: showDisciplineStatistics (simple.c:127)

我知道这与调整大小后如何将元素添加回集合有关，但我不知道如何正确执行此操作。在每次迭代中，我都会在索引 128 及之后的所有位置精确得到错误。这是我插入元素的方式，v[] 是一个用于检查所有元素是否存在的标志：

#include <stdlib.h>
#include <stdio.h>

#include "set.h"

int main() {
  PtSet set = setCreate();

  int v[200];
  for(int i = 0; i < 200; i++) {
    setAdd(set, i);
  }

  int elementsSize;
  setSize(set, &elementsSize);
  SetElem *elements = setValues(set);

  for(int i = 0; i < elementsSize; i++) {
    v[elements[i]] = 1;
  }

  for(int i = 0; i < 200; i++) {
    printf("%d - %d\n", i, v[i]);
  }

  return EXIT_SUCCESS;
}

set.c，SetElem 输入为整数：

#define LOAD_FACTOR_THRESHOLD 0.75

typedef struct setNode {
  SetElem element; // Element present at this node.
  int occupied; // Whether this node is occupied or not.
  int deleted; // Whether this node has been deleted or not.
} SetNode;

typedef struct setImpl {
  SetNode* nodes; // Nodes of the set.
  int size; // Size of the set.
  int deletedCount; // Number of nodes that have been deleted.
  int index; // Determines the capacity (getPrime(index)) and multiplier (getPrime(index - 1)). 
} SetImpl;

static int hashFunction(SetElem elem, int multiplier, int tableSize);

static bool ensureCapacity(PtSet set);

static int findPosition();

static int getPrime(int index);

PtSet setCreate() {
  PtSet set = (PtSet) malloc(sizeof(SetImpl));
  if(set == NULL) return NULL;
  
  SetNode* newNodes = (SetNode*) calloc(getPrime(1), sizeof(SetNode));
  if(newNodes == NULL) return NULL;

  set->nodes = newNodes;
  set->size = 0;
  set->deletedCount = 0;
  set->index = 1;

  return set;
}

int setAdd(PtSet set, SetElem elem) {
  if(set == NULL) return SET_NULL;

  if(!ensureCapacity(set)) return SET_NO_MEMORY;

  int position = findPosition(set, elem);
  if(position == -1) return SET_ERROR;

  int capacity = getPrime(set->index);
  int firstDeletedIndex = -1;
  bool added = false;
  for(int i = 0; i < capacity; i++) {
    if(set->nodes[position].occupied == 0 && set->nodes[position].deleted == 0) {
      if(firstDeletedIndex != -1) {
        position = firstDeletedIndex;
        set->deletedCount--;
      }
      set->nodes[position].element = elem;
      set->nodes[position].occupied = 1;
      set->nodes[position].deleted = 0;
      set->size++;
      added = true;
      break;
    }
    if(set->nodes[position].occupied == 1) {
      if(setElemCompare(set->nodes[position].element, elem) == 0) {
        return SET_DUPLICATE;
      }
    }
    if(set->nodes[position].deleted == 1 && firstDeletedIndex == -1) {
      firstDeletedIndex = position;
    }
    position = (position + 1) % capacity;
  }

  if(added == false) return SET_FULL;
  else return SET_OK;
}

int setSize(PtSet set, int *ptSize) {
  if(set == NULL) return SET_NULL;

  *ptSize = set->size;

  return SET_OK;
}

SetElem* setValues(PtSet set) {
  if(set == NULL) return NULL;
  
  SetElem *newValues = (SetElem*) calloc(set->size, sizeof(SetElem));

  int j = 0;
  for(int i = 0; i < getPrime(set->index); i++) {
    if(set->nodes[i].occupied == 1) {
      newValues[j++] = set->nodes[i].element;
    }
  }

  return newValues;
}

static int hashFunction(SetElem elem, int multiplier, int tableSize) {
  int len_bytes = sizeof(elem);
  char *byte = (char*)&elem;
  int c, hash = 5381;

  for(int i=0; i < len_bytes; i++) {
    c = *byte++;
    hash = ((hash << 5) + hash) + c;
  }

  return abs((hash * multiplier) % tableSize);
}

static bool ensureCapacity(PtSet set) {
  if(set == NULL) return false;
  
  if((double) (set->size + set->deletedCount) / getPrime(set->index) >= LOAD_FACTOR_THRESHOLD) {
    SetNode *newNodes = (SetNode*) calloc(getPrime(set->index + 1), sizeof(SetNode));
    if(newNodes == NULL) return false;

    int oldElementsSize;
    setSize(set, &oldElementsSize);
    SetElem *oldElements = setValues(set);

    free(set->nodes);
    set->nodes = newNodes;
    set->size = 0;
    set->deletedCount = 0;
    set->index++;

    for(int i = 0; i < oldElementsSize; i++) {
      setAdd(set, oldElements[i]);
    }
    free(oldElements);

    return true;
  }

  return true;
}

static int findPosition(PtSet set, SetElem elem) {
  if(set == NULL) return -1;

  int position = hashFunction(elem, getPrime(set->index - 1), getPrime(set->index));

  return position;
}

static int getPrime(int index) {
  // Useful prime numbers for setting table size.
  int primeTable[] = {
    53, 107, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
    49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917,
    25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741
  };
  int primeSize = sizeof(primeTable) / sizeof(int);

  if(index >= primeSize) return -1;
  else return primeTable[index];
}

设置.h：

#define SET_OK 0
#define SET_NULL 1 
#define SET_NO_MEMORY   2
#define SET_EMPTY 3
#define SET_FULL 4
#define SET_ERROR 5
#define SET_DUPLICATE 6

#include "setElem.h"
#include <stdbool.h>

/** Forward declaration of the data structure. */
struct setImpl;

/** Definition of pointer to the  data stucture. */
typedef struct setImpl *PtSet;

/**
 * @brief Creates a new empty set.
 * 
 * @return PtSet pointer to allocated data structure, or
 * @return NULL if unsufficient memory for allocation.
 */
PtSet setCreate();

/**
 * @brief Add an element to the set. If it already exists, then silently replace it.
 * 
 * @param set [in] pointer to the set.
 * @param elem [in] element to add.
 * 
 * @return SET_OK if successful, or
 * @return SET_FULL if no capacity available, or
 * @return SET_NO_MEMORY if unsufficient memory for allocation, or
 * @return SET_NULL if 'set' is NULL.
 */
int setAdd(PtSet set, SetElem elem);

/**
 * @brief Gets the size of the set.
 * 
 * @param set [in] pointer to the set.
 * @param ptSize [out] size of the set.
 * 
 * @return SET_OK if successful, or
 * @return SET_FULL if no capacity available, or
 * @return SET_NO_MEMORY if unsufficient memory for allocation, or
 * @return SET_NULL if 'set' is NULL.
 */
int setSize(PtSet set, int *ptSize);

/**
 * @brief Gets the values from a given set. 
 *
 * The size of the dynamic array will be the size of the set.
 * 
 * @param set [in] pointer to the set.
 * 
 * @return array containing the values of the set, or
 * @return NULL if the 'set' is empty or NULL
 */
SetElem* setValues(PtSet set);

setElemCompare() 和 setElemPrint():

void setElemPrint(SetElem elem) {
  printf("%d\n", elem);
}

int setElemCompare(SetElem elem1, SetElem elem2) {
  if(elem1 == elem2) return true;
  else return false;
}

Valgrind 设置：

valgrind --leak-check=full --show-reachable=yes --track-origins=yes ./prog

我真的不知道发生了什么，我从事这件事的时间比我愿意承认的要长，而且似乎无法正确调整哈希表的大小。

Answer 1

我已经修复了，我不知道我出了什么问题，在setAdd函数中：

    if(set->nodes[position].occupied == 1) {
      if(setElemCompare(set->nodes[position].element, elem) == 0) {
        return SET_DUPLICATE;
      }
    }

应该是：

    if(set->nodes[position].occupied == 1) {
      if(setElemCompare(set->nodes[position].element, elem) == true) {
        return SET_DUPLICATE;
      }
    }

setElemCompare 应该返回一个布尔值。 抱歉给您带来了麻烦，该套件现在按预期工作。